Project Euler: 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?

Solution

Not really much interesting you can do with this one really. Going through the whole grid while checking every single possibility is really the only way you can do it. We have take every number in the grid and multiply it with the three numbers to the left of it, below it, diagonally up to the right, and so on, like shown below.

EulerProblem11-Example-1

However, this way we would actually be checking all the possibilities twice because a product doesn’t care in what order its factors are. This means we can for example just check the ones to the right and not the ones to the left. We then end up with only four of the original eight “arms” of factors to multiply.

EulerProblem11-Example-2

I put the grid in a two dimensional array and then just looped through all of them looking for the highest product. It is very simple to make. Only thing that can be a bit tricky is to make sure you do try out all the possibilities without going out the side the array bounds. Anyways, you can see my result below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
var grid = new[,]
    {
        {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},
    };

var rows = grid.GetLength(0);
var columns = grid.GetLength(1);

var greatest = 0;

for (var r = 0; r < rows; r++)
    for (var c = 0; c < columns; c++)
    {
        if (c < columns - 3)
        {
            // Right and "Left"
            greatest = Math.Max(greatest, Grid[r, c] * Grid[r, c + 1] * Grid[r, c + 2] * Grid[r, c + 3]);
        }

        if (r < rows - 3)
        {
            // Down and "Up"
            greatest = Math.Max(greatest, Grid[r, c] * Grid[r + 1, c] * Grid[r + 2, c] * Grid[r + 3, c]);

            // Diagonally, down to the right
            if (c < columns - 3)
                greatest = Math.Max(greatest, Grid[r, c] * Grid[r + 1, c + 1] * Grid[r + 2, c + 2] * Grid[r + 3, c + 3]);

            // Diagonally, down to the left
            if (c > 3)
                greatest = Math.Max(greatest, Grid[r, c] * Grid[r + 1, c - 1] * Grid[r + 2, c - 2] * Grid[r + 3, c - 3]);
        }
    }

var answer = greatest;

And that’s pretty much it! Takes around 150 ticks, and is not really interesting to be honest :P Next Euler problem however is a bit more tricky… will write about that one next, so stay tuned :)

  • Pingback: Solution to Project Euler problem 11 in C# | Mathblog

  • Paramo23

    You can combine some of those if statements and use the Max method; (greatest = Max(greatest, [expression]), instead of entering it twice

    • mastermind

      yep…

    • http://www.geekality.net/ Torleif Berger

      Didn’t really get what you meant when I first read your comment, but read it again now when @mastermind added his. Get it now! Smart. Will test it out and update the post shortly.

    • http://www.geekality.net/ Torleif Berger

      Fixed! Worked great. Thanks for the tip :)

  • Karthik

    Hi, Could you help me with my code. I am getting a wrong answer. The code is kinda pretty much messed up.

    Code : https://drive.google.com/file/d/0B6rjVqmsp5tBbmx5a3p5RUU5OEk/edit?usp=sharing

    • http://www.geekality.net/ Torleif Berger

      Not able to see your code. And either way I suggest you ask for help through StackOverflow instead. Much bigger community and better help.