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 102638 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 956394 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 177878 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 351400 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 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.

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

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 🙂

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

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

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

😀

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.

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

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

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.

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.

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.

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.

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)

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

here is my solution in objective C

http://nghialuong.github.io/code/Project-Euler-Problem-11-using-Objective-C/

Happy coding.

Anyone have the code in c++?