Project Euler Problem 11 Solution: Largest product in a grid

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

Solves all test cases for Hackerrank Project Euler Problem 11

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 icon in the top left corner.