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

No other option but 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.

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

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

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