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 😛 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…

    • 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.

    • 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

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

    • Shengfa Lin

      Your consideration for the reverse diagnal is wrong. One of the i, j direction should be increasing and the other decreasing if you think about it. Your current reverse would have the same effect as the original diagnal.

  • nate

    Should line line 49 be c > 2 assuming zero-based indexing?

  • Vishesh Mangla

    hi i tried to solve this problem with a different approach.My answer didn’t match but I trust my approach.If i can know how my approach is wrong or else why my program’s not giving me correct answer i would be obliged.

    My logic

    consider a 4X4 matrix with top point as (i,j) instead of default (0,0)

    for i in range(0,17,1):
    for j in range(0,17,1):

    l=[vert1,vert2,hor1,hor2,ld,rd]
    t.append(max(l))
    vert1=1
    vert2=1

    hor1=1
    hor2=1

    ld=1
    rd=1
    for x in range(i,i+4,1):
    for y in range(j,j+4,1):
    if y==j:
    vert1*=int(a[x][y])
    if y==j+3:
    vert2*=int(a[x][y])

    if x==i:
    hor1*=int(a[x][y])

    if x==i+3:
    hor2*=int(a[x][y])

    if x==y:
    ld*=int(a[x][y])
    if x==3-y:
    rd*=int(a[x][y])

    print(max(t))

    • “My answer didn’t match but I trust my approach.” Um… you should have a second look at that trust in yourself. If you get the wrong answer, you’ve done something wrong. Maybe it’s the approach, maybe it’s a bug. Either way, I don’t have time to find it for you (and also no idea what language you’re writing in…), sorry.

      I recommend asking for help at either https://stackoverflow.com or https://codereview.stackexchange.com.

      • Vishesh Mangla

        thanks for the advice