Project Euler - Largest Product In A Grid

Question

My code solves Project Euler problem #011:

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 looked over one of the interview questions for a job in my current workplace and came across this problem and tried to write a solution for it. Since I was told this was a pretty common type of interview question, I brought it here to see what a general response would be to this answer and what I could possibly do to improve it

from functools import reduce
import operator

grid = [
    [8, 49, 81, 52, 22, 24, 32, 67, 24, 21, 78, 16, 86, 19, 4, 88, 4, 20, 20, 1],
    [2, 49, 49, 70, 31, 47, 98, 26, 55, 36, 17, 39, 56, 80, 52, 36, 42, 69, 73, 70],
    [22, 99, 31, 95, 16, 32, 81, 20, 58, 23, 53, 5, 0, 81, 8, 68, 16, 36, 35, 54],
    [97, 40, 73, 23, 71, 60, 28, 68, 5, 9, 28, 42, 48, 68, 83, 87, 73, 41, 29, 71],
    [38, 17, 55, 4, 51, 99, 64, 2, 66, 75, 22, 96, 35, 5, 97, 57, 38, 72, 78, 83],
    [15, 81, 79, 60, 67, 3, 23, 62, 73, 0, 75, 35, 71, 94, 35, 62, 25, 30, 31, 51],
    [0, 18, 14, 11, 63, 45, 67, 12, 99, 76, 31, 31, 89, 47, 99, 20, 39, 23, 90, 54],
    [40, 57, 29, 42, 89, 2, 10, 20, 26, 44, 67, 47, 7, 69, 16, 72, 11, 88, 1, 69],
    [0, 60, 93, 69, 41, 44, 26, 95, 97, 20, 15, 55, 5, 28, 7, 3, 24, 34, 74, 16],
    [75, 87, 71, 24, 92, 75, 38, 63, 17, 45, 94, 58, 44, 73, 97, 46, 94, 62, 31, 92],
    [4, 17, 40, 68, 36, 33, 40, 94, 78, 35, 3, 88, 44, 92, 57, 33, 72, 99, 49, 33],
    [5, 40, 67, 56, 54, 53, 67, 39, 78, 14, 80, 24, 37, 13, 32, 67, 18, 69, 71, 48],
    [7, 98, 53, 1, 22, 78, 59, 63, 96, 0, 4, 0, 44, 86, 16, 46, 8, 82, 48, 61],
    [78, 43, 88, 32, 40, 36, 54, 8, 83, 61, 62, 17, 60, 52, 26, 55, 46, 67, 86, 43],
    [52, 69, 30, 56, 40, 84, 70, 40, 14, 33, 16, 54, 21, 17, 26, 12, 29, 59, 81, 52],
    [12, 48, 3, 71, 28, 20, 66, 91, 88, 97, 14, 24, 58, 77, 79, 32, 32, 85, 16, 1],
    [50, 4, 49, 37, 66, 35, 18, 66, 34, 34, 9, 36, 51, 4, 33, 63, 40, 74, 23, 89],
    [77, 56, 13, 2, 33, 17, 38, 49, 89, 31, 53, 29, 54, 89, 27, 93, 62, 4, 57, 19],
    [91, 62, 36, 36, 13, 12, 64, 94, 63, 33, 56, 85, 17, 55, 98, 53, 76, 36, 5, 67],
    [8, 0, 65, 91, 80, 50, 70, 21, 72, 95, 92, 57, 58, 40, 66, 69, 36, 16, 54, 48]
]

biggest = 0
used = []

for y, row in enumerate(grid):
    for x, column in enumerate(row):
        left = reduce(operator.mul, grid[y][x - 4:x], 1)
        used = grid[y][x - 4:x] if left > biggest else used
        biggest = left if left > biggest else biggest

        right = reduce(operator.mul, grid[y][x:x + 4])
        used = grid[y][x:x + 4] if right > biggest else used
        biggest = right if right > biggest else biggest

        down = reduce(operator.mul, [n[x] for n in grid[y:y + 4]], 1)
        used = [n[x] for n in grid[y:y + 4]] if down > biggest else used
        biggest = down if down > biggest else biggest

        up = reduce(operator.mul, [n[x] for n in grid[y - 4:y]], 1)
        used = [n[x] for n in grid[y - 4:y]] if up > biggest else used
        biggest = up if up > biggest else biggest

        if x + 4 < 20:
            values = [n[x + i] for i, n in enumerate(grid[y - 4:y])]
            forwardDiag = reduce(operator.mul, values, 1)
            used = values if forwardDiag > biggest else used
            biggest = forwardDiag if forwardDiag > biggest else biggest

        values = [n[x - i] if x - i > 0 else 0 for i, n in enumerate(grid[y:y + 4])]
        backwardDiag = reduce(operator.mul, values, 1)
        used = values if backwardDiag > biggest else used
        biggest = backwardDiag if backwardDiag > biggest else biggest

print(biggest, used)

Answer 1

Stylistic it is mostly nice, and I would possibly change two things. First of I would put all of the code within a function allowing for reuse, and secondly I would change some of the names, i.e. backward_diag and forward_diag.

From an algorithmic point of view there are however some more issues with your code:

• Use range(x) when you don't care about the value – Usually it is good to do for column_value in row, but as you dereference using indexes, and don't use the column value at all, I would rather using pure indexing, and let the double loop be:

  for y in range(len(grid)):
      for x in range(len(grid[y])):
  

• What's the point with used? – I don't understand why you store the starting value of the largest value. In itself this value is not useful, as any value could be found multiple places, and you don't store which direction the largest value was used.

  If storing something I would rather store the indices and direction, something similar to (x, y, "left") where you vary the direction accordingly to current search

• Don't repeat the value if a > biggest else biggest – Instead of doubling the if ... else I would rather use a full blown if statement. In other words instead of

  left = reduce(operator.mul, grid[y][x - 4:x], 1)
  used = grid[y][x - 4:x] if left > biggest else used
  biggest = left if left > biggest else biggest
  

  I would rather use:

  left = reduce(operator.mul, grid[y][x - 4:x], 1)
  if left > biggest:
      used = (x, y, "left")
      biggest = left
  

• Don't repeat calculation – As Zack commented upon I wouldn't calculate both the left and right, and similarily the up and down, as these are redundant.
• Strange validation of ranges – The only range you check is the x + 4 < 20, but you don't do any validation on other ranges. This means that you calculate the left even though you don't have 4 values to the left of current value, and so on. This is kind of sloppy, and could easily be avoided.