hour-glass-2D-array.py

# -*- coding: utf-8 -*-
"""
Created on Fri Dec 27 22:09:02 2019

@author: USER
"""
# SOLVED!

"""
Problem Description:
    Given a 6 X 6 2D Array, arr:
    
        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 arr's graphical representation:

        a b c
          d
        e f g
    
    There are 16 hourglasses in A, and an hourglass sum is the sum of an
    hourglass' values. Calculate the hourglass sum for every hourglass in arr,
    then print the maximum hourglass sum.
    
    For example, given the 2D array:
    
        -9 -9 -9  1 1 1 
         0 -9  0  4 3 2
        -9 -9 -9  1 2 3
         0  0  8  6 6 0
         0  0  0 -2 0 0
         0  0  1  2 4 0
     
    We calculate the following 16 hourglass values:
    
        -63, -34, -9, 12, 
        -10, 0, 28, 23, 
        -27, -11, -2, 10, 
        9, 17, 25, 18
    
    Our highest hourglass value is 28 from the hourglass:
    
        0 4 3
          1
        8 6 6
    
    Note: If you have already solved the Java domain's Java 2D Array challenge,
    you may wish to skip this challenge.
    
    Function Description:
        Complete the function hourglassSum in the editor below. 
        It should return an integer, the maximum hourglass sum in the array.
        
        hourglassSum has the following parameter(s):
        
        arr: an array of integers
    
    
    Sample Input:
        
        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:
        19
    
    Explanation:
     arr contains the following hourglasses:
    
    1 1 1   1 1 0   ....  0 0 0
      1       0     ....    0 
    1 1 1   1 1 0   ....  0 0 0
    
    .
    .
    .
    
    
    
    The hourglass with the maximum sum (19) is:
    
        2 4 4
          2
        1 2 4

"""

import sys


def hourglassSum(arr):
    max_sum = -sys.maxsize - 1
    for i in range(len(arr)-2):
        rui = i # index for upper row
        rmi = i + 1 # index for middle row
        rli = i + 2 # index for lower row
        for j in range(len(arr[0])-2):
            cui = j # index for upper column
            cmi = j + 1 # index for middle column
            cli = j + 2 # index for lower column
            total_for_upper = arr[rui][cui] + arr[rui][cmi] + arr[rui][cli]
            total_for_mid = arr[rmi][cmi]
            total_for_lower = arr[rli][cui] + arr[rli][cmi] + arr[rli][cli]
            total = total_for_upper + total_for_mid + total_for_lower
            max_sum = max(max_sum, total)
    return max_sum