// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (16 votes, average: 4.88 out of 5)
Loading...

Project Euler Solutions

Project Euler 11 Solution

Project Euler 11 Solution

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.
download arrowUse 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.
|70600674|

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

Post a comment