# Greatest product in 20×20 grid – Problem 11

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.

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. 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 033578*94  = 769860. I already knew that since I checked the down direction as I visited number four lines above.

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;

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;

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. ### Posted by Kristian Svish

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?) Kristian

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 🙂 Zac

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

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

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

😀 Kristian

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

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

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);
\$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;
}
}``` Derokorian

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

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

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. Jean-Marie Hachey

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) Jean-Marie Hachey

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 Nghia Luong

here is my solution in objective C
http://nghialuong.github.io/code/Project-Euler-Problem-11-using-Objective-C/

Happy coding. Colin

Anyone have the code in c++? Beowolf

Hello guys!
I found this answer: 918897*14 = 75347272
Why no one found him? Mahesh

//Here is C++ code you can refer @Colin

#include <bits/stdc++.h>
using namespace std;

int arr;int p=0,q=0;
// function to find max product
int FindMaxProduct()
{
int n =20;
int max = 0, result;

```// iterate the rows. for (int i = 0; i < n; i++) { ```

``` // iterate the columns. for (int j = 0; j < n; j++) { // check the maximum product // in horizontal row. if ((j - 3) >= 0) { result = arr[i][j] * arr[i][j - 1] * arr[i][j - 2] * arr[i][j - 3]; if (max < result) {max = result;p=i;q=j;} // max = result; } // check the maximum product // in vertical row. if ((i - 3) >= 0) { result = arr[i][j] * arr[i - 1][j] * arr[i - 2][j] * arr[i - 3][j]; if (max < result) {max = result;p=i;q=j;} // max = result; } // check the maximum product in // diagonal and anti - diagonal if ((i - 3) >= 0 && (j - 3) >= 0) { result = arr[i][j] * arr[i - 1][j - 1] * arr[i - 2][j - 2] * arr[i - 3][j - 3]; if (max < result) {max = result;p=i;q=j;} } if ((i - 3) >= 0 && (j + 3) <= 19) { result = arr[i][j] * arr[i - 1][j + 1] * arr[i - 2][j + 2] * arr[i - 3][j +3]; if (max < result) {max = result;p=i;q=j;} } } } ```

```cout<<p<<" "<<q<<endl; return max; ```

}

string s = R”(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)”;

// std::vector<vector>v ;

int c=0;
string s1 = “”;
void get_vector(){
for(auto i:s){
if(i==’\n’)s1+=” “;
else s1+=i;
}
// cout<<s1<<endl;
s1+=” “;
int l,m,vv,r,co;
for(long int i = 2;i<s1.size();i++){
if(s1[i]==’ ‘){
l = (s1[i-1]-‘0’);
m = (s1[i-2]-‘0’);
vv = m*10+l;
r = c/20;
co = c%20;
c++;
arr[r][co] = vv;
}
}
}

void print_a(){
int n = 20;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<arr[i][j]<<” “;
}
cout<<endl;
}
}

// driver code
int main()
{

```get_vector(); // print_a(); cout << FindMaxProduct(); return 0; ```

}