Hacker rank 30 days of code Maximum Sum of Hourglass

Question

I came up with this code as a solution to a contest question. The original question can be viewed here for attribution sake: Hackerrank 2d array problem

Sample input is like this:

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 is like this:

19

My actual code input from the submission website is as follows:

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())))



total = 0
max_total = -1073741824


for i in range(len(arr)):
    for j in range(len(arr[i])):
        if (j+2 < 6) and (i+2 < 6):
            total = 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]
            if max_total < total:

                max_total = total
print(max_total)

There were several code listings on a different StackOverflow posting C++/Ruby solutions to 2d array problem. Being an absolute beginner in Python, I am still coming up to speed with advanced concepts in Python so my solution presented here is "un-Pythonic" and am sure not at all times optimized. How can I rewrite this code to be more "Pythonic"? I understand list comprehensions, but how can they be applied to multi-dimensional arrays like this case? Also, would rewriting the code to be Pythonic actually optimize the solution?

Answer 1

Your main algorithm is fine, and the logic cannot be further optimized. You can eliminate an unnecessary condition by reducing the ranges:

for i in range(len(arr) - 2):
    for j in range(len(arr[i]) - 2):
        total = 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]
        max_total = max(max_total, total)

I also use max(...) to eliminate another condition for more compact writing style.

The readability could be slightly improved if you extract the long sum to compute the total into a helper function, so that you rewrite the long line as:

total = hourglass(arr, i, j)

At this point, we're getting close to a form where the implementation can be rewritten as a generator comprehension. But I don't think it would be worth it. It would not improve the performance, and it would hardly improve readability. Just because Python has comprehension, doesn't mean you should always use them no matter what.

---

The if __name__ == "__main__": is ineffective, because some code still remains in global space. Worse, if somebody tries to import this script, it will raise an error, because the arr is only initialized in the if __name__ == "__main__": guard, and code outside of it tries to use it.

Solution: move the implementation into a function, and avoid code execution in global space.

---

The initialization total = 0 is unnecessary. The value is always recomputed and overwritten inside the nested loop.

---

You should remove unused imports.

Answer 2

Reading the input data in a loop

arr = []
for _ in range(6):
    arr.append(list(map(int, input().rstrip().split())))

can be done with list comprehension, also rstrip() is not needed here because split() without arguments ignores trailing whitespace:

arr = [ list(map(int, input().split())) for _ in range(6)]

---

In

for i in range(len(arr)):
  for j in range(len(arr[i])):

I would assign the dimensions to separate variables, making the code self-documenting:

num_rows = len(arr)
num_cols = len(arr[0])
for i in range(num_rows - 2):
    for j in range(num_cols - 2):

---

The initial value

max_total = -1073741824

looks arbitrary without an explaining comment. What about

max_total = -7 * 9 - 1  # An hourglass sum is at least 7 * (-9)

instead? And (even though @janos advised against it :) you can get rid of both the total and the max_total variable if you use the built-in max() function on a generator of hourglass sums:

def hourglass_sums(arr):
    """Generate all sums of hourglasses in the array."""
    num_rows = len(arr)
    num_cols = len(arr[0])
    for i in range(num_rows - 2):
        for j in range(num_cols - 2):
            yield (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])


def max_hourglass_sum(arr):
    """Maximal hour glass sum in the array."""
    return max(hourglass_sums(arr))

Answer 3

A different approach would be to use the fact that the operation you have to implement is a 2-D convolution. That is, you take the mask given by the hourglas,

mask = [[1, 1, 1], [0, 1, 0], [1, 1, 1]]

you place it over the top-left part of the array, multiply element-wise between the elements of the mask and the array below, and sum everything. Then you move the mask one to the right and repeat. Once you reach the right border, you move one row down and repeat.

As you can see, this is exactly the described operation. The SciPy library has a built-in function for this: scipy.signal.convolve2d:

result = convolve2d(arr, mask, 'valid')

The result will be an array containing the "hourglas sum" for each position where you can place the mask, i.e. for each hourglas:

[[ 7  4  2  0]
 [ 4  8 10  8]
 [ 3  6  7  6]
 [ 3  9 19 14]]

Then all you need to do is to get the maximum of that output array. As the result will be a NumPy array, you can call the max() method:

result.max()

As there are already multiple good answers going over the coding style and other suggestions for more pythonic code, I won't go over that here.

Answer 4

import math
import os
import random
import re
import sys

First, don't import stuff you don't use. As far as I can tell you don't actually use any of those modules.

if __name__ == "__main__":

Second, you haven't written a module useful to import, so don't do if __name__ == "main":. Also, the rest of your code would throw an exception at line 21 where you do len(arr) with arr undefined. It's fine to not use such a check if it's understood that you don't intend people to import your module.

I would prefer sys.stdin to input, this is only due to python2/3 changing of what input() does. Going forward in purely python3 it'll probably be fine. I would also just use a list comprehension instead of bothering with map in that case.

arr = [[int(_) for _ in sys.stdin.readline().strip().split()] 
       for i in range(6)]

As far as what is and isn't pythonic, I would argue that a big part of pythonic is readability/maintainability over things like speed (at least assuming we're not changing the big-O order). To that end, I'd suggest defining the hourglass shape as a list and then using that instead of built in indexing.

hourglass = [[1, 1, 1],
             [0, 1, 0],
             [1, 1, 1]]

Finally, you can use itertools.product to do a lot of the gruntwork in terms of generating nested for loops and then use max on a map of the result:

print(max(map(hourglass.count, itertools.product(i_range, j_range, [arr]))))

All put together:

import sys
import itertools

arr = [[int(_) for _ in sys.stdin.readline().strip().split()] 
       for i in range(6)]

class Hourglass(object):
    hourglass = [[1, 1, 1],
                 [0, 1, 0],
                 [1, 1, 1]]

    def __init__(self, hourglass_shape=None):
        if hourglass_shape is not None:
            self.hourglass = hourglass_shape

    def count(self, info):
        i, j, array_ = info
        return sum([sum([a*b for a,b in zip(array_line[j:], hourglass_line)])
                    for array_line, hourglass_line in zip(array_[i:], 
                                                          self.hourglass)])

hourglass = Hourglass()

i_range = range(len(arr) - len(hourglass.hourglass) + 1)
# Assuming rectangular
j_range = range(len(arr[0]) - len(hourglass.hourglass[0]) + 1)

print(max(map(hourglass.count, itertools.product(i_range, j_range, [arr]))))

Most importantly, "pythonic" tends to mean easily readable and understandable by those who understand python well. So:

• Don't import things you don't plan to use. This will make it take a little longer for others to digest your code as their first assumption will be that you're using something from each of those modules.
• Don't do if __name__ == "main": unless you plan to write a module for import.
• Don't hard code stuff in (your array indexing).
• Use list comprehension where it makes sense.
• Use builtins like max and sum wherever it makes sense.

Other stuff like how I use itertools.product and map'd the result are less "pythonic" vs "non-pythonic" and just how I'd do them to reduce lines of code.

Finally, the question of how "pythonic" your code is really only matters if you plan on sharing it. Python is great for whipping up quick results to (real world versions of) questions like these. If all you're looking for is a quick answer, do whatever works quickest for you. Often the time it would take you to worry about how you're writing code for a problem like this can take longer than it could ever save.

Answer 5

From looking at your code, the main things I notice are:

1. The unused imports at the top
2. The __name__ == "__main__" that isn't implemented correctly
3. The overly complicated and long lines that are hard to read

If I were to solve this question in a pythonic way, I'd go with numpy. It provides both clarity and efficiency. The following solution works for any size of the input array, and is a lot more efficient for larger arrays.

import numpy as np    

input_array = np.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]])

# Since the I-shape has size 3x3, we want an array with two rows and 
# two columns fewer
shape = tuple(i-2 for i in input_array.shape)

# This denotes the shape of the I, with [0,0] being the upper left corner
offsets = [[0,0], [0,1], [0,2], [1,1], [2,0], [2,1], [2,2]]

result_array = np.zeros(shape, dtype=np.int64)

# Add all offsets to each value in result_array
for x,y in offsets:
    result_array += input_array[x:x+shape[0], y:y+shape[1]]

# The result_array will contain the sum of every I-shape for the input_array
print(result_array.max())

Answer 6

You shouldn't assume initial values for max_total or total because may be your assumption becomes the maximum value.

Also starting the loop without max_total defined will be a syntax error when you try to access that variable outside the loop.

That's why I set the max_total = True to be my initial value and at the start of the loop I will override this value with the first total value.

I already tested that with hackerrank and all test cases including arrays of negative integers passed.

max_total = True
for i in range(len(arr) - 2):
    for j in range(len(arr[i]) - 2):
        total = 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]
        if max_total == True:
            max_total = total
        max_total = max(max_total, total)
print(max_total)

Answer 7

In addition to the other excellent answers, the loops could be replaced by the standard built-ins to make the code more expressive:

def hourglass(arr, i, j):
    return 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]

mat_height = len(arr)
mat_width = len(arr[0])
maximum_hourglass = max(hourglass(arr, x, y) for x in range(mat_width - 2) for y in range(mat_height - 2))