Hướng dẫn hackerrank hourglass solution python

Published Jun 17, 2021Last updated Mar 07, 2022

When I saw this question on Hackerrank, I wondered why it was under the easy difficulty level.

Given a 6x6 2D Array, A:
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
We define an hourglass in A to be a subset of values with indices falling in this pattern in A's graphical representation: a bcdefg\begin{matrix}a & b & c\\ & d & \\e & f & g\end{matrix}
There are 16 hourglasses in A, and an hourglass sum is the sum of an hourglass' values.
Task: Calculate the hourglass sum for every hourglass in A, then print the maximum hourglass sum.
Input Format: There are 6 lines of input, where each line contains 6 space-separated integers that describe the 2D Array A.
Constraints:

• −9≤A[ i][j]≤9-9 \le A[i][j] \le 9
• 0≤i,j≤50 \le i,j \le 5
  Output Format: Print the maximum hourglass sum in A.

Well, upon research, I agree with the difficulty level.
This question asks for the sum of the values in each houglass in matrix A and return the highest.
Hourglass is a subset of the matrix A. It is a 3x3 matrix with only one element on the second row, and this element is located on the second column: ab cdefg\begin{matrix}a & b & c\\ & d & \\e & f & g\end{matrix}

Constraints Explained

−9≤A[i][j]≤9-9 \le A[i][j] \le 9 Implies that each element is a single digit as it ranges between -9 and 9 inclusive
0≤i,j≤50 \le i,j \le 5 Implies that i and j range from 0 to 5 inclusive indicating that the number of rows and the number of columns are not more than 6 [since arrays are zero-indexed and a matrix is a type of array]

Labelled Array

Let's number the cells of our array A as follows:
1 234567891011121314 151617181920212223242 52627282930313233343536 \begin{matrix}1&2&3&4&5&6\\ 7&8&9&10&11&12\\ 13&14&15&16&17&18\\ 19&20&21&22&23&24\\ 25&26&27&28&29&30\\ 31&32&33&34&35&36\end{matrix}
The above 6x6 matrix has 36 elements numbered 1-36
At row[0], column[0], A[0][0], we have 1
At row[0], column[1], A[0][1], we have 2
At row[0], column[2], A[0][2], we have 3
...
At row[1], column[0], A[1][0], we have 7
At row[1], column[1], A[1][1], we have 8
...
At row[2], column[0], A[2][0], we have 13
...
At row[2], column[5], A[2][5], we have 18
...
At row[5], column[0], A[5][0], we have 31
...
At row[5], column[5], A[5][5], we have 36

The Hourglasses

The first hourglass from our numbered array A will be:
row[0]column[0]row[0]colu mn[1]row[0]column[2]row[1]column[0]row[1]c olumn[1]row[1]column[2]row[2]column[0]row[ 2]column[1]row[2]column[2]\begin{matrix}row[0]column[0] & row[0]column[1] & row[0]column[2]\\ row[1]column[0] & row[1]column[1] & row[1]column[2]\\ row[2]column[0] & row[2]column[1] & row[2]column[2]\end{matrix} thats is [12381314 15]\begin{bmatrix}1&2&3\\ &8& \\13&14&15\end{bmatrix}
Then...
[234 9141516]\begin{bmatrix}2&3&4\\ &9& \\14&15&16\end{bmatrix}, [3 4510151617]\begin{bmatrix}3&4&5\\ &10& \\15&16&17\end{bmatrix} , [45611161718] \begin{bmatrix}4&5&6\\ &11& \\16&17&18\end{bmatrix}

[789141 92021]\begin{bmatrix}7&8&9\\ &14& \\19&20&21\end{bmatrix}, [8910 15202122]\begin{bmatrix}8&9&10\\ &15& \\20&21&22\end{bmatrix}, [9101116212223]\begin{bmatrix}9&10&11\\ &16& \\21&22&23\end{bmatrix}, [101112172 22324]\begin{bmatrix}10&11&12\\ &17& \\22&23&24\end{bmatrix},
...and so on

• We are to programmically get all the hourglasses
• Sum up the elements of each hourglass
• Return the highest sum

Solution

import math

def get_max_hour_glass_sum[arr]:
  result = -math.inf
  for row in range[4]:
        for col in range[4]:
            hour_glass_sum = \
            arr[row][col] + arr[row][col+1] + arr[row][col+2] + \
            arr[row+1][col+1] + \
            arr[row+2][col] + arr[row+2][col+1] + arr[row+2][col+2]
            result = max[[result, hour_glass_sum]]
    print[result]

In the above code, we import the math module so we can use it in our function.

• We define our function get_max_hour_glass_sum which takes arr as parameter.
• We assign negative infinity [-math.inf] to the result variable. Since the question asks for maximum sum, we start with negative infinity and change the value of result to the hourglass sum higher than the current result value. Every time we generate the sum of an hourglass, we check it against the value of result; if result is higher, it remains unchanged, else, the value of result changes to the value of the hourglass sum.
• We run a nested for-loop that starts at the first row till the fourth row then the first column till the fourth column. If we went beyond the fourth row or column, we wont be able to acheive an hourglass. For instance, using our numbered matrix above, going to the fifth column gives us: [56121718]\begin{bmatrix}5&6&\\ &12& \\17&18&\end{bmatrix}
• We sum the current elements and its neighbours that make up an hourglass and assign the sum to hour_glass_sum
• We check for the highest between hour_glass_sum and result and assign it to result
• Finally, we print out result.

Please, let me know if there is a more efficient way to achieve the result; I'ld love to learn.
Enjoy!

Thanks to Knowledge Center
Photo by Nathan Dumlao on Unsplash

Enjoy this post? Give Olaide Alaka a like if it's helpful.

Share

Python/Django full-stack developer

I am a full-stack developer versed in Python/Django with JavaScript, HTML, CSS, jQuery/Ajax. I have developed several web and desktop applications, including school management, quiz, school learning, eCommerce, and inventory appl...

Discover and read more posts from Olaide Alaka

Enjoy this post?

Leave a like and comment for Olaide