Greatest product in 20×20 grid – Problem 11

Written by on 26 November 2010

Topics: Project Euler

We are more or less revisiting a well known problem. I here I am thinking of Problem 8. Only in Problem 11 of Project Euler. The problem has become two dimensional.

The problem reads

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 any direction (up, down, left, right, or diagonally) in the 20*20 grid?

That seems like a fairly simple task to solve, and it is.

As shown on the figure, when ever we are looking at one number, we would need to check eight directions to find the maximum product of that particular number. However, since we will visit all numbers, we will only need to check four different coloured directions for each number, since the rest of the directions are already being checked when we vist(ed) another number.

Grid Directions

Example of that, when I stand on the marked number 03, I don’t need to check the up directions to find out that the product is 03*35*78*94ย  = 769860. I already knew that since I checked the down direction as I visited number four lines above.

Input Reader

I have made a small input reader function, so I can read the input from a file, and make it into an 2D array. You could have chosen to type in the array directly as he did at Geekality, but I am far to lazy to do that. The function looks like

private int[,] readInput(string filename) {
    int lines = 0;
    string line;
    string[] linePieces;

    StreamReader r = new StreamReader(filename);
    while(r.ReadLine() != null){
        lines++;
    }

    int[,] inputSquare = new int[lines, lines];
    r.BaseStream.Seek(0, SeekOrigin.Begin);

    int j =0;
    while ((line = r.ReadLine()) != null) {
        linePieces = line.Split(' ');
        for (int i = 0; i < linePieces.Length; i++) {
            inputSquare[j, i] = int.Parse(linePieces[i]);
        }
        j++;
    }

    r.Close();

    return inputSquare;
}

The input reader expects a file with numbers separated by a white space, and lines separated by a new line. So basically you can copy the text from the web page.

Finding the solution

The code for finding the solutions looks like

public void Solve() {
    string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\input.txt";
    const int numbersInProduct = 4;

    decimal product = 0;

    int[,] inputSquare = readInput(filename);
    for (int col = 0; col < inputSquare.GetLength(0); col++) {
        for (int row = 0; row < inputSquare.GetLength(1); row++) {
            decimal tempProd;

            // Check Vertically
            if (row < inputSquare.GetLength(0) - numbersInProduct) {
                tempProd = inputSquare[col, row];
                for (int i = 1; i < numbersInProduct; i++) {
                    tempProd *= inputSquare[col, row + i];
                }
                product = Math.Max(product, tempProd);
            }

            // Check Horisontally
            if (col < inputSquare.GetLength(1) - numbersInProduct) {
                tempProd = inputSquare[col, row];
                for (int i = 1; i < numbersInProduct; i++) {
                    tempProd *= inputSquare[col + i, row];
                }
                product = Math.Max(product, tempProd);
            }

            // Check diagonally upwards / forwards
            if ((col < inputSquare.GetLength(0) - numbersInProduct) && (row >= numbersInProduct)) {
                tempProd = inputSquare[col, row];
                for (int i = 1; i < numbersInProduct; i++) {
                    tempProd *= inputSquare[col + i, row - i];
                }
                product = Math.Max(product, tempProd);
            }

            // Check diagonally Downwards / forwards
            if ((row < inputSquare.GetLength(0) - numbersInProduct) && (col < inputSquare.GetLength(1) - numbersInProduct)) {
                tempProd = inputSquare[col, row];
                for (int i = 1; i < numbersInProduct; i++) {
                    tempProd *= inputSquare[col + i, row + i];
                }
                product = Math.Max(product, tempProd);
            }
        }
    }
 }

Not really any mysterious about it, nor anything particularly interesting. But it runs, and it runs fast enough to generate a solution within the time limit.

The greatest product of 4 entries, is 70600674
Solution took 0 ms

Closing remarks

I haven’t spent that much time on this problem, as I don’t find it particularly challenging. If you find some optimized way of doing this, please let me know, I would be interested.

The source code is available as always for you to download.

15 Comments For This Post I'd Love to Hear Yours!

  1. Svish says:

    Bet I spent less energy and time on making those numbers into an array, than you spent writing that input reader :p

    (Why do you have two identical blogs with the same name anyways?)

  2. Kristian says:

    You caught me in the middle of a move between two different blogs. I have moved it from a sub domain to a real domain.

    And yes, I do believe it was faster than using an input reader. But now I have the class available for similar problems ๐Ÿ™‚

  3. Zac says:

    Can you give me this source code in c++? I tried running it with c++ and it did not work.

  4. Kristian says:

    The source code is in c#, and I don’t have it in c++. However, it should not be difficult to translate it.

  5. Ardianto says:

    I copied those numbers into word processor, then colored the number >=85 red.

    http://prntscr.com/p8lcm

    Then I saw a diagonal up red line numbers, so I just do:
    89x94x97x87 = 706000674

    ๐Ÿ˜€

  6. Kristian says:

    Yes you could definitely solve it that way, and it works. But personally I don’t get much satisfaction from that solution. I guess each to his own, and it is indeed a working solution.

  7. Harshad says:

    Hi,

    Thank you for providing a solution to this problem from project euler. I was bit confused about how to find answer to this questions. From your post it looked very simple.

    I am trying to run your code and getting error “Input string was not in correct format” on line 18 of the function readInput.

    I am not able to understand why that error is throwing up. Can you please help?

  8. Kristian says:

    It seems that your input file was corrupted for some reason. I haven’t written, the input reader to be robust in any way.

  9. Derokorian says:

    Why do you have 4 inner loops, instead of using one? That seems more expensive than 4 product variables with one loop. Below was my approach
    and it runs in 1.5ms.

    $grid = file('prodGrid.txt');
    $grid = array_map(function ($e) { return explode(' ', trim($e)); }, $grid);
    
    $x = count($grid[0]);
    $y = count($grid);
    $largest = -1;
    
    for( $row = 0; $row < $y; $row++ )
    {
        for( $col = 0; $col < $x; $col++ )
        {
            $pA = 1;
            $pV = 1;
            $pDD = 1;
            $pDU = 1;
            for( $i = 0; $i < 4; $i++ )
            {
                if( isset($grid[$row+$i][$col]) )
                    $pV *= $grid[$row+$i][$col];
                if( isset($grid[$row][$col+$i]) )
                    $pA *= $grid[$row][$col+$i];
                if( isset($grid[$row+$i][$col+$i]) )
                    $pDD *= $grid[$row+$i][$col+$i];
                if( isset($grid[$row-$i][$col+$i]) )
                    $pDU *= $grid[$row-$i][$col+$i];
            }
            if( $pV > $largest )
                $largest = $pV;
            if( $pA > $largest )
                $largest = $pA;
            if( $pDD > $largest )
                $largest = $pDD;
            if( $pDU > $largest )
                $largest = $pDU;
        }
    }
  10. Derokorian says:

    Erm.. I wasn’t trying to be rude, your blog has helped me understand the problems before, and I’m just confused why you took your approach. Is there a difference in the optimal approach in C#? I’ve noticed generally speaking optimum approaches in PHP and C# are very similar.

  11. Kristian says:

    I can see where you are going with that, and it could be a better solution. However, I am not sure it makes any difference at all. My guess is that the compiler optimizes most of it away anyway.

    Of course it would be fun to compare it (task for you ๐Ÿ™‚ ), but this implementation detail is not what will make or break the solution.

  12. Kristian says:

    Sorry for appearing to ignore you. Due to the amount of spam, I have opted for approving all posters, therefore it is always a little time under way. I am past 200k spam messages on the blog, and I don’t want them to drown comments like yours.

    Please keep up posting. I love input like that.

  13. Jean-Marie Hachey says:

    Table 1 gives the greatest product obtained with a number of factors between 2 and 10.
    As given in the article, if the number of factors in the product is 4, then the greatest product is 70600674.

    Table 1
    Greatest product obtained by varying the number of factors (2 – 10).
    http://img4.hostingpics.net/pics/621178pe11gptable1.jpg

    ___

    Sources:
    1) Project Euler 11
    Kristianโ€™s algorithm.
    http://www.mathblog.dk/files/euler/Problem11.cs
    2) Microsoft Visual C# 2010 Express
    3) Prime Factorization Calculator
    http://www.mathblog.dk/tools/prime-factorization/
    4) Javascripter.net
    http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
    5) Microsoft Office Excel (2007)

  14. Jean-Marie Hachey says:

    Fig. 1 gives the greatest product obtained with a number of factors between 2 and 10.
    (Accompanying the previous comment)

    http://img4.hostingpics.net/pics/662089pe11gpfig1.jpg

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.