This challenge explores 2D arrays. Given a 6x6 2D array, there are 16 hourglass shapes within the array, as seen below. For example, in the following 6x6 array:
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
We have the following 16 hourglass shapes
1 1 1 1 1 0 1 0 0 0 0 0
1 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0
0 0 2 0 2 4 2 4 4 4 4 0
1 1 1 1 1 0 1 0 0 0 0 0
0 2 4 4
0 0 0 0 0 2 0 2 0 2 0 0
0 0 2 0 2 4 2 4 4 4 4 0
0 0 2 0
0 0 1 0 1 2 1 2 4 2 4 0
If we sum up the numbers in each of these, the greatest sum would be 19.
2 4 4
2
1 2 4
Sample Input:
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
Sample Output:
19
To create a regular 1D array or list, you can create it directly or read in user inputs.
my_arr = [1, 2, 3, 4, 5] #create the array yourself
print(my_arr)
user_1d_arr = list(map(int, input().strip().split())) #allow the user to input numbers all at once e.g. 3 2 4 1 2
print(user_1d_arr)
user_2d_arr = [] #append each row to the end of the list
for _ in range(6):
user_2d_arr.append(list(map(int, input().strip().split())))
print(user_2d_arr)
[1, 2, 3, 4, 5]
[3, 2, 4, 1, 2]
[[3, 4, 5, 6, 7, 7], [1, 2, 3, 4, 5, 6], [2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6, 9], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]
Before looping through the 2D array to find the maximum sum, we can create a max_sum variable. As it loops through the array, it will check each hourglass sum against this number. If the hourglass sum greater, the max_sum will be set to equal to this sum. At first, I used a default of 0. In the examples shown so far, 0 would work. However, the numbers within the hourglass can also be negative which is noted in the “Constraints” section of the problem. Instead, I set the max_sum variable equal to the sum of the first hourglass, however you could also set it equal to something like -100, which is outside the range.
arr = []
for _ in range(6):
arr.append(list(map(int, input().rstrip().split())))
max_sum = arr[0][0] + arr[0][1] + arr[0][2] + arr[1][1] + arr[2][0] + arr[2][1] + arr[2][2] #the first hourglass
To loop through a 2D array, we need to keep track of both the rows and the columns. This can be done using a double loop (a for loop within another for loop). The following loop starts on row 0 (i=0) and then loops through columns 0-3. It ends on row 3 (i=3) and then loops through columns 0-3. Each element is accessed using array[row][column].
#If the array 'arr' is as follows:
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
for i in range(4): #i is the row
for j in range(4): #j is the column
print(arr[i][j]) #array[row][column] returns the element on this row/column
1
1
1
0
0
1
0
0
1
1
1
0
0
0
2
4
You might notice that this didn’t loop through every element of the 6x6 array. Instead, it’s looping through the top, left-most elements of each of the 16 hourglasses. The rest can be summed up using indeces.
for i in range(4):
for j in range(4):
sum_curr = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2] #top row, middle row, end row with arr[i][j] being the top, left-most part of the hourglass
print(sum_curr)
#the sums of each of 16 hourglasses
7
4
2
0
4
8
10
8
3
6
7
6
3
9
19
14
A shorter way to make this sum:
sum(arr[i][j:j+3]) + arr[i+1][j+1] + sum(arr[i+2][j:j+3])
Now all that is needed is a check to update the max_sum. In the 2D array we have been using, the max_sum would be set to 7 (the first hourglass sum), and then updated in the loop to 8, then 10, and then finally 19.
for i in range(4):
for j in range(4):
sum_curr = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2] #top row, middle row, end row with arr[i][j] being the top, left-most part of the hourglass
if sum_curr > max_sum: #if the current sum is greater than the max_sum (originally set to the first hourglass sum)
max_sum = sum_curr
Sample Solution 1:
#!/bin/python3
import math
import os
import random
import re
import sys
if __name__ == '__main__':
arr = []
for _ in range(6):
arr.append(list(map(int, input().rstrip().split())))
max_sum = arr[0][0] + arr[0][1] + arr[0][2] + arr[1][1] + arr[2][0] + arr[2][1] + arr[2][2] #top row, middle, end row #max sum should NOT be set to 0 since hourglass could be negative, set equal to the first hourglass
for i in range(4):
for j in range(4):
sum_curr = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2] #top row, middle, end row
if sum_curr > max_sum:
max_sum = sum_curr
print(max_sum)
Sample Solution 2:
#!/bin/python3
import math
import os
import random
import re
import sys
if __name__ == '__main__':
arr = []
for _ in range(6):
arr.append(list(map(int, input().rstrip().split())))
max_sum = -100
for i in range(4):
for j in range(4):
sum_curr = sum(arr[i][j:j+3]) + arr[i+1][j+1] + sum(arr[i+2][j:j+3])
if sum_curr > max_sum:
max_sum = sum_curr
print(max_sum)