## 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.

#### 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*

This blog helps me a lot. Thanks!

i think line 11 should be “if i < rows – path_size + 1:".

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!

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…

Thanks Murilo, glad it helped you.