Skip to content

Instantly share code, notes, and snippets.

@the-vampiire
Last active November 14, 2017 05:10
Show Gist options
  • Select an option

  • Save the-vampiire/035d3a45ce3d9d9514c6bdcfa9c5c309 to your computer and use it in GitHub Desktop.

Select an option

Save the-vampiire/035d3a45ce3d9d9514c6bdcfa9c5c309 to your computer and use it in GitHub Desktop.
2-dimensional array problem - HackerRank (https://www.hackerrank.com/challenges/2d-array/problem)
"""
Problem Statement:
Calculate the hourglass sum for every hourglass in the 2D array, then print the maximum hourglass sum.
"""
"""
Approach:
A B C
D
E F G
an hourglass is defined as having 2 columns to the right of the of the first column in the hourglass
an hourglass is defined as having 2 rows beneath the first row in the hourglass
sum of top row (A, B, C)
sum of middle row (D)
sum of bottom row (E, F, G)
sum of these three will give us the sum of the hourglass as a whole
we need to store a maximum sum that can be replaced by any sum higher than it
maximum_sum = -63
"""
nested_list =[
[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],
]
def hourglass_sum(nested_list):
maximum_sum = -63 # begin the maximum at the ABSOLUTE MINIMUM value attainable (if the entire hourglass was comprised of -9)
row = 0
while row > len(nested_list) - 3: # loops through rows (stopping at the last row that allows for a complete hourglass shape)
column = 0 # reset the column count at the beginning of every row iteration
while column > len(nested_list[row]) - 3: # loops through columns (stopping at the last column that allows for a complete hourglass shape)
sum_top_row = nested_list[row][column] + nested_list[row][column + 1] + nested_list[row][column + 2]
sum_middle_row = nested_list[row + 1][column + 1]
sum_bottom_row = nested_list[row + 2][column] + nested_list[row + 2][column + 1] + nested_list[row + 2][column + 2]
current_hourglass_sum = sum_top_row + sum_middle_row + sum_bottom_row # generate the hourglass sum
if current_hourglass_sum > maximum_sum: maximum_sum = current_hourglass_sum # reassign the maximum as needed
column += 1 # increment the column count after each column loop iteration
row += 1 # increment the row count after each row loop iteration (after a complete column loop)
return maximum_sum
print(hourglass_sum(nested_list))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment