Solution of “Extended” Hourglass Sum problem of Hackerrank in C#

Problem source: Compute Hourglass Sum of a 2D array.

Note: Original problem is having 6 rows and 6 columns. But in this solution I’ve extended it little bit so that it can be used for n x n (n>= 3).

Given a 6×6 2D Array, :

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 b c
  d
e f g

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 2 or more lines of input, where each line contains 3 or more space-separated integers describing 2D Array A; every value in A will be in the inclusive range of -9 to 9.

Constraints

-9 <= A[i][j]<=9

0 <= i,j<= 5

Output Format

Print the largest (maximum) hourglass sum found in A.

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

A contains the following hourglasses:

1 1 1   1 1 0   1 0 0   0 0 0
  1       0       0       0
1 1 1   1 1 0   1 0 0   0 0 0

0 1 0   1 0 0   0 0 0   0 0 0
  1       1       0       0
0 0 2   0 2 4   2 4 4   4 4 0

1 1 1   1 1 0   1 0 0   0 0 0
  0       2       4       4
0 0 0   0 0 2   0 2 0   2 0 0

0 0 2   0 2 4   2 4 4   4 4 0
  0       0       2       0
0 0 1   0 1 2   1 2 4   2 4 0

The hourglass with the maximum sum (19) is:

2 4 4
  2
1 2 4

Code in C#

class HourglassSum
    {
        static void Main(string[] args)
        {
            int[][] arr = new int[6][];
            for (int arr_i = 0; arr_i < 6; arr_i++)
            {
                string[] arr_temp = Console.ReadLine().Split(' ');
                arr[arr_i] = Array.ConvertAll(arr_temp, Int32.Parse);
            }

            Console.WriteLine(CalculateHourGlassSum(arr));
            Console.ReadKey();
        }

        private static int CalculateHourGlassSum(int[][] arr)
        {
            /* Whatever the count of the rows of the array, 
             our loop should run till n -2. For example 
             row count is 3, in this case loop should run only once 
             123
             546
             156

            Because this is a perfect hourglass, so sum of this is
            our answer. So our loop should run just 1 time.
            45689
            41256
            02530
            00000
            in this case total rows are 4, and there can be at max 
            3 hourglass, so 5 - 2 = 3, so we need to run the loop 
            only 3 times.
             */
            int rowCount = arr.Length - 2;
            int maxSum = int.MinValue;
            for (int i = 0; i < rowCount; i++)
            {
                /// Same logic that we are using for rows will be 
                /// applicable for columns too.
                int columnCount = arr[i].Length - 2;
                for (int j = 0; j < columnCount; j++)
                {
                    /*
                     for example our array is as below:
                     Rows: i = 0, Columns: j = 0
                     45612
                     07000
                     45872
                     33333
                     66666

                     to compute sum of hourglass we have below formula:
                     Sum = arr[i][j]        = 4
                     + arr[i][j + 1]        = 5
                     + arr[i][j + 2]        = 6
                     + arr[i + 1][j + 1]    = 7
                     + arr[i + 2][j]        = 4
                     + arr[i + 2][j + 1]    = 5
                     + arr[i + 2][j + 2]    = 8   
                     */
                    int sum = arr[i][j] + arr[i][j + 1] + arr[i][j + 2]
                                            + arr[i + 1][j + 1]
                            + arr[i + 2][j] + arr[i + 2][j + 1] + arr[i + 2][j + 2];
                    if (maxSum < sum)
                    {
                        maxSum = sum;
                    }
                }
            }
            return maxSum;
        }
    }
Advertisements

2 thoughts on “Solution of “Extended” Hourglass Sum problem of Hackerrank in C#

  1. using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace HackerRankPractice
    {
    class Class1
    {
    static int[][] CreateHourGlassForIndexAndSumIt(int p, int q, int[][] arr)
    {
    int[][] hourGlass = new int[3][];

    int x = 0, y = 0;
    for (int i = p; i <= p + 2; i++)
    {
    hourGlass[x] = new int[3];
    int[] temp = new int[3];
    int k = 0;
    for (int j = q; j <= q + 2; j++)
    {
    temp[k] = arr[i][j];
    k++;
    }
    hourGlass[x] = temp;
    x++;
    }

    return hourGlass;
    }

    static int findSumOfEachHourGlass(int[][] arr)
    {
    int sum = 0;
    for (int i = 0; i < arr.Length; i++)
    {
    for (int j = 0; j < arr.Length; j++)
    {
    if (!((i == 1 && j == 0) || (i == 1 && j == 2)))
    sum += arr[i][j];
    }

    }

    return sum;
    }

    static void Main(string[] args)
    {
    int[][] arr = new int[6][];
    for (int arr_i = 0; arr_i < 6; arr_i++)
    {
    string[] arr_temp = Console.ReadLine().Split(' ');
    arr[arr_i] = Array.ConvertAll(arr_temp, Int32.Parse);
    }

    int[] sum = new int[16];
    int k = 0;
    for (int i = 0; i < 4; i++)
    {
    for (int j = 0; j < 4; j++)
    {
    int[][] hourGlass = CreateHourGlassForIndexAndSumIt(i, j, arr);
    sum[k] = findSumOfEachHourGlass(hourGlass);
    k++;
    }
    }

    Console.WriteLine(sum.Max());

    }
    }
    }

  2. class Class1
    {
    static int[][] CreateHourGlassForIndexAndSumIt(int p, int q, int[][] arr)
    {
    int[][] hourGlass = new int[3][];

    int x = 0, y = 0;
    for (int i = p; i <= p + 2; i++)
    {
    hourGlass[x] = new int[3];
    int[] temp = new int[3];
    int k = 0;
    for (int j = q; j <= q + 2; j++)
    {
    temp[k] = arr[i][j];
    k++;
    }
    hourGlass[x] = temp;
    x++;
    }

    return hourGlass;
    }

    static int findSumOfEachHourGlass(int[][] arr)
    {
    int sum = 0;
    for (int i = 0; i < arr.Length; i++)
    {
    for (int j = 0; j < arr.Length; j++)
    {
    if (!((i == 1 && j == 0) || (i == 1 && j == 2)))
    sum += arr[i][j];
    }

    }

    return sum;
    }

    static void Main(string[] args)
    {
    int[][] arr = new int[6][];
    for (int arr_i = 0; arr_i < 6; arr_i++)
    {
    string[] arr_temp = Console.ReadLine().Split(' ');
    arr[arr_i] = Array.ConvertAll(arr_temp, Int32.Parse);
    }

    int[] sum = new int[16];
    int k = 0;
    for (int i = 0; i < 4; i++)
    {
    for (int j = 0; j < 4; j++)
    {
    int[][] hourGlass = CreateHourGlassForIndexAndSumIt(i, j, arr);
    sum[k] = findSumOfEachHourGlass(hourGlass);
    k++;
    }
    }
    //max in sum array
    Console.WriteLine(sum.Max());

    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s