(20 votes, average: 4.85 out of 5)

## Project Euler 11: Find the greatest product of four adjacent numbers in the same direction in a grid

#### Project Euler 11 Problem Description

Project Euler 11: 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

The best way to solve this problem is to read the matrix into an array and iterate through the rows, columns and diagonals to find four adjacent cells that produce a maximum product. Only right, down, diagonal down-left and diagonal down-right need to be checked because of the commutative nature of multiplication.

This program assumes the same number of rows and columns. The data is saved to a file, pe11.txt in the
Trinket tab next to the main.py tab.

HackerRank makes no additional demands and just asks the same questions with the same parameters.

This program and method
solves all test cases for
Project Euler 11 on HackerRank

#### Project Euler 11 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 11 Solution Python 2.7 source.

#### Afterthoughts

• This solution could be made more extensible by allowing a variable number of adjacent cells other than 4 to be searched.
Project Euler 11 Solution last updated

## Discussion

### 5 Responses to “Project Euler 11 Solution”

1. This blog helps me a lot. Thanks!

Posted by yangwooseong | May 15, 2017, 8:38 PM
• i think line 11 should be “if i < rows – path_size + 1:".

Posted by yangwooseong | May 15, 2017, 11:21 PM
• Yep, line 11 should have been “if i <= rows - path_size:" or your fix. Good thing this wasn't a spacecraft re-entry matrix with the maximum path on the bottom edge. Good find! Thanks!

Posted by Mike Molony | June 20, 2017, 6:13 PM
2. 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