In this blog post we will be looking at problem 11 of Project Euler and we will program a solution in Java.

The problem of Project Euler found here, below is the problem for quick lookup.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

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

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

-Project Euler problem 11

What we need is a way to get the input numbers into the program where we can differnatiate them. I decided to use an array. Once you have these numbers formatted and in your program the solution is quite simple.

I decided to just use four two dimensional for loops to check all for required directions. We only need four directions instead of six since the horizontal(left/right) results would be the same regardless of the direction you would multiply them. This is the same for the vertical multiplication.

The horizontal for loop:

for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 17; j++) {
        productHorizon = Grid[i][j] * Grid[i][j + 1] * Grid[i][j + 2] * Grid[i][j + 3];
        if (largest < productHorizon){
            largest = productHorizon;
        }
    }
}

The second for loop loops till 16(smaller than 17) because the array is from 0 to 19, And since you get the value of variable i plus 1/2/3 looping till 20/19/18 would cause an ArrayIndexOutOfBoundsException, this is true for the other loops too but with different conditions.

The vertical for loop:

for (int i = 0; i < 17; i++) {
    for (int j = 0; j < 20; j++) {
        productVertical     = Grid[i][j] * Grid[i + 1][j] * Grid[i + 2][j] * Grid[i + 3][j];
        if (largest < productVertical){
            largest = productVertical;
        }
    }
}

The diagonal right for loop:

for (int i = 0; i < 17; i++) {
    for (int j = 0; j < 17; j++) {
        productDiagRight    = Grid[i][j] * Grid[i + 1][j + 1] * Grid[i + 2][j + 2] * Grid[i + 3][j + 3];
        if (largest < productDiagRight){
            largest = productDiagRight;
        }
    }
}

The diagonal left for loop:

for (int i = 0; i <17; i++) {
    for (int j = 3; j < 20; j++) {
        productDiagLeft     = Grid[i][j] * Grid[i + 1][j - 1] * Grid[i + 2][j - 2] * Grid[i + 3][j - 3];
        if (largest < productDiagLeft){
            largest = productDiagLeft;
        }
    }
}

After these four for loops the variale named ‘largest’ contains the largest product. Check out the github for the full code.

Check out the ‘Project Euler in Java’ page for more solutions!

Link to github.

That was Project Euler problem 11 in Java!