7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Please add a link to the original Hackerrank problem. \$\endgroup\$
    – G. Sliepen
    Oct 16, 2020 at 18:33

1 Answer 1

6
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ @Emma LeetCode does, and HackerRank does have a NumPy section \$\endgroup\$ Oct 16, 2020 at 19:15
  • 1
    \$\begingroup\$ Could you explain what it's doing? Does numpy loop automatically over the entire matrix? \$\endgroup\$ Oct 16, 2020 at 20:27
  • 1
    \$\begingroup\$ @jeremyradcliff Kinda, yes. I mean, a[0:4, 0:4] for example is the top-left 4x4 submatrix. That holds the top-left value for each of the 16 hourglasses. And a[0:4, 1:5] holds the top-middle value for each of the 16 hourglasses. And so on. What I do is I get those seven 4x4 submatrices and have NumPy add them for me (NumPy does the looping required for that). So I'm building all 16 hourglass sums at the same time, at NumPy speed. \$\endgroup\$ Oct 17, 2020 at 1:25
  • \$\begingroup\$ That's incredible. Thanks for explaining, I'm going to play with it today and try to integrate it \$\endgroup\$ Oct 17, 2020 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.