4
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review. I added a simple quotation to describe what your code actually does! Hope you'll get a good review! \$\endgroup\$ – holroy Feb 27 '16 at 5:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Zack Feb 27 '16 at 5:17
4
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Thank you for the extremely indepth analysis! Really useful feedback. Cheers. \$\endgroup\$ – Jordan Doyle Feb 27 '16 at 13:02

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.