Project Euler 81 (minimum path sum through a matrix)

Problem Statement:


In the 5 by 5 matrix below,

131   673 234 103 18
201   96  342 965 150
630   803 746 422 111
537   699 497 121 956
805   732 524 37  331

the minimal path sum from the top left to
the bottom right, by only moving to the right and down, is

131 → 201 → 96 → 342 → 746 → 422 → 121 → 37 → 331

and is equal to 2427.


Find the minimal path sum, in matrix.txt, a 31K text file containing a 80 by 80 matrix,
from the top left to the bottom right by only moving right and down.

Algorithm:

I used a dynamic programming approach to this problem

• Accumulate the sum for the top row (going right till the end)

• Accumulate the sum for the left column (going down till the end)

• For each (i, j) pair, I add the minimum of the left cell and the upper cell

• The result is stored in the last (i, j) pair

Code:

from itertools import accumulate # Note this was added in Python 3.3

def min_path_sum(matrix):
    """Returns the minimum path sum of a matrix moving only down and right"""
    size = len(matrix)
    if size == 0:
        return 0

    matrix[0] = list(accumulate(matrix[0][i] for i in range(size)))

    for i in range(1, size):
        matrix[i][0] += matrix[0][i-1]

    for i in range(1, size):
        for j in range(1, size):
            matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])
    return matrix[size-1][size-1]

if __name__ == '__main__':
    with open("matrix.txt") as file:
        matrix = []
        for line in file:
            matrix.append(list(map(int, line.strip().split(","))))
        print(min_path_sum(matrix))

I'm looking for a general code review.

That's a nice, elegant algorithm! I can only nitpick.

file is not a good name for a file handle because it shadows a built-in with the same name. (I use fh for this kind of thing.)

It would be good to extract the file reading logic from the if __name__:

def read_matrix_from_path(path):
    with open(path) as fh:
        return [list(map(int, line.strip().split(","))) for line in fh]

if __name__ == '__main__':
    print(min_path_sum(read_matrix_from_path("matrix.txt")))

Perhaps most importantly, you can blend this loop into the other one:

for i in range(1, size):
    matrix[i][0] += matrix[0][i-1]

Like this:

for i in range(1, size):
    matrix[i][0] += matrix[0][i-1]
    for j in range(1, size):
        matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])

StackExchange Code Review Q#60930, answer score: 5