Computing sums of weird pattern in 2D array as efficiently as possible

Question

This is a problem from Hackerrank (https://www.hackerrank.com/challenges/2d-array/problem). We're given a 6x6 (always) 2D array and asked to compute the sums of all the hourglass patterns in the array. An hourglass pattern is of the shape

1 1 1 
  1   
1 1 1

where the 1's form the hourglass. In this case the sum is 7, but it could be any integer from -63 to 63, the constraints being: -9 <= arr[i][j] <= 9. There are 16 hourglasses in each 6x6 2D array, and we're asked to return the greatest hourglass value.

As an example, the following 2D array has a maximum hourglass value of 28:

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

My code:

def hourglassSum(arr):
    max_hourglass = -63
    for column in range(len(arr)-2):
        for row in range(len(arr)-2):
            max_hourglass = max(arr[row][column] + arr[row][column+1] + arr[row][column+2] \
            + arr[row+1][column+1] + arr[row+2][column] + arr[row+2][column+1] \
                                + arr[row+2][column+2], max_hourglass)
    return max_hourglass

Is there any way to make this faster / more efficient? I'm reusing a lot of the same numbers in my calculations, which seems wasteful; is there a dynamic programming solution I'm not seeing, anything else? I appreciate any comments or optimization opportunities on my code, thank you.

Answer 1

Drat. My super pretty NumPy solution which is probably efficient doesn't get accepted because HackerRank apparently doesn't support NumPy here. Oh well, here it is anyway, maybe interesting/amusing for someone.

import sys
import numpy as np

a = np.loadtxt(sys.stdin, dtype=np.int8)

h = a[0:4, 0:4] + a[0:4, 1:5] + a[0:4, 2:6]     + \
                  a[1:5, 1:5]                   + \
    a[2:6, 0:4] + a[2:6, 1:5] + a[2:6, 2:6]

print(h.max())

Or with less code repetition:

import sys
import numpy as np

a = np.loadtxt(sys.stdin, dtype=np.int8)

i, j, k = (slice(i, i+4) for i in range(3))

h = a[i,i] + a[i,j] + a[i,k]     + \
             a[j,j]              + \
    a[k,i] + a[k,j] + a[k,k]

print(h.max())

The 4x4 submatrix a[0:4, 0:4] contains the top-left value for each of the 16 hourglasses, a[0:4, 1:5] contains the top-middle value for each of the 16 hourglasses, etc. So adding them computes a 4x4 matrix containing the 16 hourglass sums.