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

• holroy: Welcome to Code Review. I added a simple quotation to describe what your code actually does! Hope you'll get a good review!
• Zack: Some of your searching is redundant. Searching down is the same as searching up, starting from a lower position. The same applies to left and right.

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.

• Jordan Doyle: Thank you for the extremely indepth analysis! Really useful feedback. Cheers.