7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – alecxe Mar 9 '17 at 19:12
5
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – ChatterOne Mar 9 '17 at 8:37
  • \$\begingroup\$ @ChatterOne stupid me, you are absolutely right, there was a bug. I've added a fix, thanks so much! \$\endgroup\$ – alecxe Mar 9 '17 at 14:33
  • \$\begingroup\$ The generators part is what I needed. \$\endgroup\$ – Bor Mar 10 '17 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.