This is problem 11 in Project Euler:

In the 20 x 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 48The 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 x 20 grid?

This is similar to problem 8, where we had to calculate the greatest product of 5 consecutive digits in a 100 digit number. Using a similar approach to our solution to that problem, we can use the following algorithm:

- Set up a 20 by grid holding these numbers. The grid will consist of 20 rows, each having 20 columns
- Set up a variable to hold the result; call it maxProduct and initialise it to 0
- Set the row number to be 1, and the column number to be 1
- If the column number is less than 18, we can calculate the product of the four numbers across, starting with this number. Replace maxProduct with this product if it is greater.
- If the row number is less than 18, we can calculate the product of the four numbers down, starting with this number. Replace maxProduct with this product if it is greater.
- If the row number is less than 18 and the column number is less than 18, we can calculate the product of the four numbers diagonally down to the right, starting from this number. Replace maxProduct with this product if it is greater.
- If the row number is less than 18 and the column number is greater than 3, we can calculate the product of the four numbers diagonally down to the left, starting from this number. Replace maxProduct with this product if it is greater.
- Increment the column number if it is less than 20, else increment the row number if it is less than 20 and set the column number to 1

The variable maxProduct will hold the required result at the end of this procedure. Here is the Delphi code:

procedure TfrmMain.Problem11; var s: string; maxProduct: int64; x, y: Integer; myGrid : array[1..20, 1..20] of integer; begin //only showing first row s := '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 '; for y := 1 to 20 do for x := 1 to 20 do begin myGrid[y, x] := StrToInt(copy(s, 1, 2)); delete(s, 1, 3); end; maxProduct := 0; for y := 1 to 20 do for x := 1 to 20 do begin //right if x < 18 then maxProduct := max(maxProduct, myGrid[y, x] * myGrid[y, x + 1] * myGrid[y, x + 2] * myGrid[y, x + 3]); //down if y < 18 then maxProduct := max(maxProduct, myGrid[y, x] * myGrid[y + 1, x] * myGrid[y + 2, x] * myGrid[y + 3, x]); //diagonal downright if ((x < 18) and (y < 18)) then maxProduct := max(maxProduct, myGrid[y, x] * myGrid[y + 1, x + 1] * myGrid[y + 2, x + 2] * myGrid[y + 3, x + 3]); //diagonal downleft if ((x > 3) and (y < 18)) then maxProduct := max(maxProduct, myGrid[y, x] * myGrid[y + 1, x - 1] * myGrid[y + 2, x - 2] * myGrid[y + 3, x - 3]); end; ShowMessage(IntToStr(maxProduct)); end;

This code runs in less than 1 minute, as required by Project Euler.

Tags: Mathematics, Programming, Project Euler

Hello, just wanted to say, I liked this article.

It was practical. Keep on posting!