Project Euler 81 (minimum path sum through a matrix)

Question

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.

Answer 1

Your solution works, but I consider it impolite for min_path_sum() to trash the contents of the matrix as it works, especially when it does so without any indication in the docstring. Since the algorithm works row by row, you can remedy that behaviour using just one row's worth of additional storage.

You've unnecessarily hard-coded the assumption of a square matrix.

Hard-coding the input filename makes your program less generally useful. To read the input, I suggest using fileinput so that it either opens the file specified on the command line or sys.stdin.

import fileinput
from itertools import accumulate

def min_path_sum(matrix):
    """Returns the minimum path sum of a matrix moving only down and right"""
    if not matrix:
        return 0                                # 0 rows

    rows = iter(matrix)
    best = list(accumulate(next(rows)))
    if not best:
        return 0                                # 0 columns

    for row in rows:
        best[0] += row[0]
        for j in range(1, len(row)):
            best[j] = row[j] + min(best[j-1],   # approaching from the left
                                   best[j])     # approaching from above
    return best[-1]

if __name__ == '__main__':
    matrix = [
        [int(n) for n in line.strip().split(',')] for line in fileinput.input()
    ]
    print(min_path_sum(matrix))

Bonus material: Alternate ending

To handle a very large problem, you wouldn't even have to read the entire matrix at once — you could even process one row at a time.

def matrix(fileinput):
    for line in fileinput.input():
        yield [int(n) for n in line.strip().split(',')]

if __name__ == '__main__':
    print(min_path_sum(matrix(fileinput)))

Answer 2

The generator expression here is redundant

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

because a list is an iterable:

matrix[0] = list(accumulate(matrix[0]))

Answer 3

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