Last active
November 14, 2017 05:10
-
-
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| 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