1
\$\begingroup\$

About this 2D Arrays HackerRank problem.

The task is to find the maximum sum of a region in a 2D array. Specifically, it is to find the maximum sum of an "hourglass" region, defined as a 3x3 square without the middle entries on the left and right sides, as shown by this mask.

1 1 1
0 1 0
1 1 1

Here's my solution.

I'd appreciate some review about code quality.

# Begin of HackerRank code: data entries for testing the user code
# ----------------------------------------------------------------
arr = []

for _ in range(6):
    arr.append(list(map(int, input().rstrip().split())))
# ----------------------------------------------------------------
# End of HackerRank code


my_hourglasses = list()

for i in range(0,4):
    for j in range(0,4):
        hourglass = list()
        hourglass += arr[i][j:j+3]
        hourglass.append(arr[i+1][j+1])
        hourglass += arr[i+2][j:j+3]
        my_hourglasses.append(hourglass)

hourglasses_sums = [sum(item) for item in my_hourglasses]

print(max(hourglasses_sums))
\$\endgroup\$
5
\$\begingroup\$

One thing I like about this code is the clear division of role.

You have a section for identifying and extracting the hourglasses. Then you sum the individual hourglasses. Then you find the maximum.

There's a quote by Computer Scientist Tony Hoare that "There are two ways to write code: write code so simple there are obviously no bugs in it, or write code so complex that there are no obvious bugs in it." The clear structure helps make this into the first category. This is the sort of code that I'd like to see, for example, in a reference implementation or test case.

On the other hand, that simplicity comes at a cost. Your implementation requires allocating a bunch of extra memory to hold all the temporary hourglasses, and a bit more still to hold all the sums.

In principle, you could add them up as soon as you identify the elements in an hourglass, and then only store hourglasses_sums instead of my_hourglasses. Furthermore, instead of storing a list of all the sums you have seen, you could just keep track of the highest score you have seen thus far. You'd then have something like this:

max_hourglass_score = -63  # Minimum possible score = -9 * 7
for i in range(0,4):
    for j in range(0,4):
        hourglass = list()
        hourglass += arr[i][j:j+3]
        hourglass.append(arr[i+1][j+1])
        hourglass += arr[i+2][j:j+3]
        hourglass_sum = sum(hourglass)
        max_hourglass_score = max(max_hourglass_score, hourglass_sum)

print(max_hourglass_score)

Of course, the same pattern could be applied to do the sum as you go rather than picking it into an intermediate hourglass list.

max_hourglass_score = -63  # Minimum possible score
for i in range(0,4):
    for j in range(0,4):
        hourglass_sum = 0
        hourglass_sum += sum(arr[i][j:j+3])
        hourglass_sum += arr[i+1][j+1]
        hourglass_sum += sum(arr[i+2][j:j+3])
        max_hourglass_score = max(max_hourglass_score, hourglass_sum)

print(max_hourglass_score)

This only allocates a few primitive variables rather than all the extra arrays you had before.

There are in fact still cleverer algorithms which require fewer arithmetic operations. The key idea is easier to explain with squares rather than hourglasses. If you look at the square in the top left corner and compare it with the square one place across, many of the entries are the same. Specifically, of the nine entries in a square, six are overlapped. The potential for speeding up the program come from not looking that the overlap squares any more, but starting from the last sum, taking away the values that are no longer in it, and adding the values that are new to it.

That algorithm, however clever, is complicated. It's hard to get right, and even hard to see whether it is right. It's therefore a judgement call how much you value making your code run as fast as possible, and how much you prefer writing it in a way that is easy to understand. There isn't a best answer. It depends on what you want to use it for. If this were running in real time on video frames and were (somewhat appropriately) the biggest bottleneck in your program, then you'd probably prefer faster. If it's trundling along on a small grid, you would want clear code.


A couple of other general comments:

  • Variable naming is important. Although "hourglass" would usually seem like a fairly specific and helpful word to identify what's going on, when three of your main variables are built around the same word one should wonder whether it actually gets confusing. (Also, "my_" is usually unnecessary.)
  • I appreciate the use of Python comprehensions. If you only want to use it once, a generator comprehension is often better. In terms of how it's written, just swap the square brackets around sum(item) for item in my_hourglasses for parentheses. In terms of what it does, it avoids actually doing the calculation until you need it, giving space and sometimes time savings.
  • Beware of magic numbers. I realise that 4 is the width of the big grid, minus 2, which you need because the width of the hourglass is 3 and the overlap is 1. But that's not immediately obvious, so it's worth spelling out what 4 means.
\$\endgroup\$
  • \$\begingroup\$ Thanks! But I got lost max_hourglass_score = -63 # Minimum possible score = -9 * 7. Where this calculation came from? \$\endgroup\$ – Bruno Lemos Jul 22 at 19:34
  • \$\begingroup\$ I enjoyed a lot the max_hourglass_score = max(max_hourglass_score, hourglass_sum). Sounded very clever to me. It´s a great way to avoid using "if" for cheking the highest value, isn´t it? \$\endgroup\$ – Bruno Lemos Jul 22 at 19:36
  • 2
    \$\begingroup\$ The problem description says that each cell is between plus and minus 9, and an hourglass has 7 cells. Therefore the minimum possible total is 7*-9 \$\endgroup\$ – Josiah Jul 22 at 20:05
  • 1
    \$\begingroup\$ And yes, max(old_max, new_possible) hides the if. It doesn't behave any differently, but most people would find it easier to read. \$\endgroup\$ – Josiah Jul 22 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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