2
\$\begingroup\$

This is a java solution to a Hackerrank problem.

I know it's not optimized, can anyone help me to refactor and optimize?

Task:

Calculate the hourglass sum for every hourglass in the 6×6 array, then print the maximum hourglass sum.

An "hourglass sum" is defined as the sum of any 7 entries of the array that are selected by this pattern mask:

✓ ✓ ✓
  ✓
✓ ✓ ✓

Input Format:

There are 6 lines of input, where each line contains 6 space-separated integers describing 2D Array; every entry is in the inclusive range -9 to 9.

Output Format

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

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

Solution:

public class TestHourGlass {


        public static void main(String[] args) {
                Scanner in = new Scanner(System.in);
                int arr[][] = new int[6][6]; 
                int hourGlassSum[] = new int[16];
                int pos = 0;

                //Reads data from user input and store in 6*6 Array
                for (int arr_i = 0; arr_i < 6; arr_i++) {
                    for (int arr_j = 0; arr_j < 6; arr_j++) {
                        arr[arr_i][arr_j] = in.nextInt();
                    }
                }
                //Find each possible hourGlass and calculate sum of each hourGlass
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        hourGlassSum[pos] = calculateHourGlassSum(arr, i, i + 2, j, j + 2);
                        pos++;
                    }
                }
                System.out.println(findmax(hourGlassSum));

            }
            /**
             * @param arr 
             * @param pos1 - Row startPoint
             * @param pos2 - Row endPoint
             * @param pos3 - column startPoint
             * @param pos4 - column endPoint
             * @return
             */
            public static int calculateHourGlassSum(int arr[][], int pos1, int pos2, int pos3, int pos4) {

                int sum = 0;
                int exclRowNum = pos1 + 1;
                int exclColNum1 = pos3;
                int exclColNum2 = pos4;
                for (int arr_i = pos1; arr_i <= pos2; arr_i++) {
                    for (int arr_j = pos3; arr_j <= pos4; arr_j++) {
                        sum = sum + arr[arr_i][arr_j];
                    }
                }
                sum = sum - (arr[exclRowNum][exclColNum1] + arr[exclRowNum][exclColNum2]);
                return sum;
            }

            /**
             * @param arr
             * @return max elem of Array
             */
            public static int findmax(int arr[]) {
                int max = arr[0];
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] >= max)
                        max = arr[i];
                }
                return max;
            }
}
\$\endgroup\$
5
\$\begingroup\$

Avoid magic number

6 and 16 should be replace with properly named constants... 16 is also dependant of the first number ; if I'm not mistaken the number of possible hourglasses is (6 - 2)²

public static final int GRID_SIZE = 6;
public static final int NUMBER_OF_POSSIBLE_HOURGLASSES = Math.pow(GRID_SIZE - 2, 2);

Better naming

Most of your variable have good name, however it's not useful to name indices arr_i and arr_j, name them simply i and j.

The class name is not that good IMO, HourGlassSolver or HourGlassFinder would be better.

findmax should be cased like this findMax

Parameters for calculateHourGlassSum have unclear name (pos2 ??)

Simplify your function

Your function do their jobs well but can be made shorter thanks to the new Java 8 Stream API.

For example, your findmax :

public static int findMax(final int arr[]) {
    return Arrays.stream(arr).max().get();
}

Extract part of your code into a function

for (int i = 0; i < 4; i++) {
   for (int j = 0; j < 4; j++) {
       hourGlassSum[pos] = calculateHourGlassSum(arr, i, i + 2, j, j + 2);
       pos++;
   }
}

This should probably be made into a distinct function that returns an int array or a List<Integer>.

\$\endgroup\$
2
\$\begingroup\$

for a grid that's 6X6. Like @Ronan mentioned, there are (6-2)^2 number of hourglass because if you look at the center of the hour glass, at position d. It's only valid from position at (1,1) to (4,4).

So in the main function, you can first scanner the digits and store in an int arr[][].

Then from (1,1) to (4,4), I call the below function:

public static int hourGlassSum (int[][] arr, int row, int col){
    int sum = arr[row][col]+ arr[row-1][col-1]+ arr[row-1][col]+ arr[row-1][col+1]
        + arr[row+1][col-1]+arr[row+1][col]+ arr[row+1][col+1];
    return sum;
}

Notice how int row and int col from the above function is the position of the center of the hourglass, position d in the graph. in my personal opinion, this is easier to understand than your calculateHourGlassSum()

\$\endgroup\$
2
\$\begingroup\$

Do you really need an array to store all the sums? You could just keep track of the maximum sum since that is what you're going to return in the end.

int max = 0;
for(int row = 0; row < GRID_SIZE-2; row++){
    for(int col = 0; col < GRID_SIZE-2; col++){
        int temp = hourGlassSum(arr, row, col);
        max = Math.max(temp, max);
    }
}
System.out.println(max);

I also agree with Angela but I would reason about the top left corner instead from the middle:

public static int hourGlassSum (int[][] arr, int row, int col){
    return    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];
}

which my editor sadly auto indents back to

public static int hourGlassSum(int[][] arr, int row, int col) {
    return 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];
}
\$\endgroup\$
  • \$\begingroup\$ Thanks @Imus..No need of an array here..your logic works... \$\endgroup\$ – Rishikesh Tripathy Jun 8 '17 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.