# Project Euler 11: Largest product in a grid, Python3

Project Euler #11

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

I've seen some of the solutions of the problem and although they are in Python3, my solution has some differences.

Pylint rates it 7.27/10 and I will add docstring eventually. Some of the lines are too long(104/100) and fl is not a good name for a file and I agree.

The main issues are comparing product and product_temp and calculating the sum for a diagonal from down left to upper right is inconsistent with the calculating the other products.

The code:

#!/bin/env python3

"""
https://projecteuler.net/problem=11

In a 20x20 matrix iterate over all the rows, columns,
diagonals(left up -> down right, down left -> upper right)
and find the largest product of 4 numbers in the same direction

"""

def list_ints():
with open('./textfiles/grid2020.txt') as fl:
array = [[int(x) for x in line.split()] for line in fl]
return array

def biggest_product():
grid = list_ints()
product = 0
product_temp = 0

col = 20
row = 20
for i in range(row):
for j in range(col):
#for row
if i + 3 < 20:
product_temp = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j]

if product < product_temp:
product = product_temp

#for column
if j + 3 < 20:
product_temp = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3]

if product < product_temp:
product = product_temp

#for diagonal from upper left to down right
if i + 3 < 20 and j + 3 < 20:
product_temp = grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3]

if product < product_temp:
product = product_temp

#another loop from the other diagonal
#diagonal left to upeer right
for i in range(20, -1, -1):
for j in range(20):
if i + 3 < 20 and j - 3 >= 0:
product_temp = grid[i][j] * grid[i + 1][j - 1] * grid[i + 2][j - 2] * grid[i + 3][j - 3]

if product < product_temp:
product = product_temp
return product

if __name__ == '__main__':
print(biggest_product())


Edit: Now I see the comments for calculating row and col comments are reversed.

• There was a bug in the initial code I've posted, but thanks to ChatterOne I've managed to fix it. Please give the improved version a try. – alecxe Mar 9 '17 at 19:12

One of the potential improvements would be to extract the logic of generating the 4 numbers in each of the directions (let's even generalize it for k numbers). What if we would create a generator that would do this for an arbitrary square matrix and k input numbers:

def generate_adjacent_items(grid, k):
"""
For a square grid, generates lists of all possible k numbers in every direction
(up, down, left, right and diagonally).
"""
size = len(grid)
for row in range(size):
for col in range(size):
# left -> right
if row + k - 1 < size:
yield [grid[row + index][col] for index in range(k)]

# top -> bottom
if col + k - 1 < size:
yield [grid[row][col + index] for index in range(k)]

# diagonal: top-left -> bottom-right
if row + k - 1 < size and col + k - 1 < size:
yield [grid[row + index][col + index] for index in range(k)]

# diagonal: bottom - left -> top - right
if row - k + 1 >= 0 and col + k - 1 < size:
yield [grid[row - index][col + index] for index in range(k)]


Then, you can iterate over the generator and get your maximum number, e.g.:

from operator import mul
from functools import reduce

K = 4

# list_ints and generate_adjacent_items function definitions here

if __name__ == '__main__':

max_sublist = max(sub_lists, key=lambda x: reduce(mul, x))
print(max_sublist, reduce(mul, max_sublist))


Note that I'm using functools.reduce(), operator.mul and the built-in max() to determine the maximum of the multiplications, but you can do it "manually" the way you were doing it in your presented solution.

For the provided sample input, it prints:

[87, 97, 94, 89] 70600674

• By "sample input" you mean the grid at the question link? Because the OP's code prints 70600674 (because [89, 94, 97, 87]) with that input, while yours prints 51267216. OP's solution seems correct to me, am I missing something? – ChatterOne Mar 9 '17 at 8:37
• @ChatterOne stupid me, you are absolutely right, there was a bug. I've added a fix, thanks so much! – alecxe Mar 9 '17 at 14:33
• The generators part is what I needed. – Bor Mar 10 '17 at 9:25