Project Euler Problem 11 Solution

Project Euler Problem 11 Solution

Largest product in a grid

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 11 Statement

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?

Solution

One 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. We can eliminate redundant calculations by only checking right, down, diagonal down–left, and diagonal down–right. The other complementary directions would evaluate to the same product by virtue of the commutative properties of multiplication.

This program assumes a square matrix—the same number of rows and columns. The data is saved to a file, pe11.txt in the repl.it tab.

HackerRank version

HackerRank Project Euler 11 makes no additional demands—same question.

Python Source Code

g = [[int(t) for t in s.split()] for s in open('pe11.txt').readlines()]

maxp = 0
rows, cols, path_size = len(g), len(g[0]), 4
for i in range(rows):
    for j in range(cols - path_size + 1):
        phv = max(g[i][j] * g[i][j+1] * g[i][j+2] * g[i][j+3],
                  g[j][i] * g[j+1][i] * g[j+2][i] * g[j+3][i])
        if i <= rows-path_size:
           pdd = max(g[i][j] * g[i+1][j+1] * g[i+2][j+2] * g[i+3][j+3],
                     g[i][j+3] * g[i+1][j+2] * g[i+2][j+1] * g[i+3][j])
        maxp = max(maxp, phv, pdd)
 
print ("Greatest product of", path_size, "adjacent numbers:", maxp)	

Last Word

The data file, pe11.txt, is available on repl.it page by clicking the files repl.it external files icon in the top left corner.