Problem 011 : Largest Product in a Grid

Largest product in a grid

Problem 11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

                                                                                                       (https://projecteuler.net/problem=11)

Problem 11 can be done manually without complicated algorithms.

There will be four components in our calculation: horizontal —, vertical |, descending diagonal \ and ascending diagonal /.

First step is to store the numbers into 20 x 20 2-D arrays.

This can be done manually, or using file reader.

public static int[][] read()
{
 int[][] text = new int[20][20];
 File file = new File(text011);
 try (BufferedReader br = new BufferedReader(new FileReader(file)))
 {
  String line;
  for (int i=0; (line = br.readLine()) != null; i++)
  {
   String[] temp = line.split(" ");
   for (int j=0; j < 20; j++)
    text[i][j] = Integer.parseInt(temp[j]);
  }
 }
 catch (IOException e)
 {
  System.err.println(e);
 }
 return text;
}

After this, we will set the limit to 20 - 3, or 17.

The reason is that once we get to the column (or row) 17, we reached the maximum starting point since 17, 18, 19, 20 will form the last four-adjacent groups.

The remaining steps are to calculate the greatest sum using nested for-loops.

Horizontal will be increasing column by 0, 1, 2, 3:

h = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3];

Vertical will be increasing row by 0, 1, 2, 3:

v = grid[j][i] * grid[j+1][i] * grid[j+2][i] * grid[j+3][i];

Descending Diagonal will be increasing both row and column by 0, 1, 2, 3:

d1 = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3];

Ascending Diagonal will be decreasing column and increasing row at the same time by 1:

d2 = grid[i][j+3] * grid[i+1][j+2] * grid[i+2][j+1] * grid[i+3][j];

thus maintaining the sum of row and column as i + j + 3.

It was relatively easy problem, and there isn't any faster or fancier algorithm to solve it.


Answer is 70600674
Execution time is 3.771644 ms, or 0.003 seconds
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem011.java