# Project Euler: Problem 11 – 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 x 63 x 78 x 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

#### Idea:

At first, the problem seemed daunting for all the directions they wanted to find the maximum product. However, finding the product upwards is the same as downwards, as is left and right; diagonally requires two directions even though only one is listed.

Finding the maximum product of any 4 adjacent numbers horizontally or vertically is relatively trivial as only one index is being modified. Finding the diagonals is only slightly more complicated in that both indices are being modified, but the modification is the same for both. The hardest part is making sure you stay within the appropriate array boundaries.

```long answer = -1;
int[] numbers = new int[4];

int ROWS = 20;
int COLS = 20;

int[][] grid = problem11grid();  //recreates the grid above

//vertical
for(int i = 0; i < ROWS-4; i++) {
for(int j = 0; j < COLS; j++) {
long tmp = grid[i][j]* grid[i+1][j]* grid[i+2][j]* grid [i+3][j];
if(tmp > answer) {
answer = tmp;
numbers[0] = grid[i][j];
numbers[1] = grid[i+1][j];
numbers[2] = grid[i+2][j];
numbers[3] = grid[i+3][j];
}
}
}

//horizontal
for(int i = 0; i < ROWS; i++) {
for(int j = 0; j < COLS-4; j++) {
long tmp = grid[i][j]* grid[i][j+1]* grid[i][j+2]* grid [i][j+3];
if(tmp > answer) {
answer = tmp;
numbers[0] = grid[i][j];
numbers[1] = grid[i][j+1];
numbers[2] = grid[i][j+2];
numbers[3] = grid[i][j+3];
}
}
}

//diagonal right
for(int i = 0; i < ROWS-4; i++) {
for(int j = 0; j < COLS-4; j++) {
long tmp = grid[i][j]* grid[i+1][j+1]* grid[i+2][j+2]* grid [i+3][j+3];
if(tmp > answer) {
answer = tmp;
numbers[0] = grid[i][j];
numbers[1] = grid[i+1][j+1];
numbers[2] = grid[i+2][j+2];
numbers[3] = grid[i+3][j+3];
}
}
}

//diagonal left
for(int i = 3; i < ROWS; i++) {
for(int j = 0; j < COLS-4; j++) {
long tmp = grid[i][j]* grid[i-1][j+1]* grid[i-2][j+2]* grid [i-3][j+3];
if(tmp > answer) {
answer = tmp;
numbers[0] = grid[i][j];
numbers[1] = grid[i-1][j+1];
numbers[2] = grid[i-2][j+2];
numbers[3] = grid[i-3][j+3];
}
}
}

System.out.println("Answer: "+answer);
for(int i = 0; i < numbers.length; System.out.print(numbers[i]+" "),i++);```
Bookmark the permalink.