Project Euler: Problem 11

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 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 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:

  1. Set up a 20 by grid holding these numbers. The grid will consist of 20 rows, each having 20 columns
  2. Set up a variable to hold the result; call it maxProduct and initialise it to 0
  3. Set the row number to be 1, and the column number to be 1
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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: , ,

One Response to “Project Euler: Problem 11”

  1. Hello, just wanted to say, I liked this article.
    It was practical. Keep on posting!