Project Euler 11: Largest product in a grid, Python3

Question

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

• alecxe: 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.

Answer 1

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

_{(please recheck for off-by-ones)}

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__':
 sub_lists = generate_adjacent_items(list_ints(), K)
 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

• ChatterOne: 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?
• alecxe: @ChatterOne stupid me, you are absolutely right, there was a bug. I've added a fix, thanks so much!
• Bor: The generators part is what I needed.