(7 votes, average: 4.71 out of 5)

## Project Euler Problem 11 Solution

#### Problem Description

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
…Data Continues…

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?

#### Analysis

No other option but to load the matrix into an array and iterate through the rows, columns and diagonals to find four adjacent cells that produce a maximum product.

#### Solution

Runs < 1 second in Python.

```n = [[8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8], [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0], [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65], [52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,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,3,45,2,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,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21], [24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72], [21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95], [78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92], [16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57], [86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58], [19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40], [4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66], [88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69], [4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36], [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16], [20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54], [1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]   maxp = 0 rows, cols, token = 20, 20, 4 for i in range(rows): for j in range(cols-token+1): phv = max(n[i][j] * n[i][j+1] * n[i][j+2] * n[i][j+3], n[j][i] * n[j+1][i] * n[j+2][i] * n[j+3][i]) if i<rows-token: pd = max(n[i][j] * n[i+1][j+1] * n[i+2][j+2] * n[i+3][j+3], n[i][j+3] * n[i+1][j+2] * n[i+2][j+1] * n[i+3][j]) maxp = max(maxp, phv, pd)   print "Answer to PE11 = ",maxp```

This solution could be made more extensible by allowing a variable number of adjacent cells other than 4 to be searched.

## Discussion

### 4 Responses to “Project Euler Problem 11 Solution”

1. My solution works but it’s not beautiful like yours, I created 4 for structures to append to a list named products the products of the lines, columns, primary diagonals e secundary diagonals…

Posted by Murilo Camargos | January 27, 2013, 8:35 AM
2. You should have precised that your solution requires to verify the condition rows = cols, precisely when you compute vertical products.

Posted by Thibault | February 18, 2013, 5:11 AM
• You’re right Thibault, thanks for pointing that out. It would be nice to modify the solution to accommodate the condition rows!=cols.

Posted by Christner | February 18, 2013, 11:13 AM