Python Implementation of Problem 81

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 81

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

\[\begin{split}\begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix}\end{split}\]

Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

python.src.p0081.min_path_sum(matrix: Sequence[Sequence[int]], cache: MutableMapping[Sequence[Sequence[int]], int]) → int
python.src.p0081.main() → int
 1"""
 2Project Euler Problem 81
 3
 4In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and
 5down, is indicated in bold red and is equal to 2427.
 6
 7.. math::
 8
 9    \\begin{pmatrix}
10    \\color{red}{131} & 673 & 234 & 103 & 18\\\\
11    \\color{red}{201} & \\color{red}{96} & \\color{red}{342} & 965 & 150\\\\
12    630 & 803 & \\color{red}{746} & \\color{red}{422} & 111\\\\
13    537 & 699 & 497 & \\color{red}{121} & 956\\\\
14    805 & 732 & 524 & \\color{red}{37} & \\color{red}{331}
15    \\end{pmatrix}
16
17Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right
18click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
19"""
20from typing import List, MutableMapping, Sequence
21
22from .lib.utils import get_data_file
23
24
25def min_path_sum(
26    matrix: Sequence[Sequence[int]],
27    cache: MutableMapping[Sequence[Sequence[int]], int]
28) -> int:
29    if matrix in cache:
30        return cache[matrix]
31    if len(matrix[0]) == 1:
32        result = sum(row[0] for row in matrix)
33    elif len(matrix) == 1:
34        result = sum(matrix[0])
35    else:
36        result = matrix[0][0] + min(
37            min_path_sum(matrix[1:], cache),
38            min_path_sum(tuple(row[1:] for row in matrix), cache)
39        )
40    cache[matrix] = result
41    return result
42
43
44def main() -> int:
45    setup: List[Sequence[int]] = []
46    for raw_line in get_data_file('p0081_matrix.txt').splitlines():
47        line = raw_line.rstrip('\\n')
48        setup.append(tuple(int(x) for x in line.split(',')))
49    return min_path_sum(tuple(setup), {})

Tags: path-finding, shortest-path, file-io