Python Implementation of Problem 81
View source code here on GitHub!
Includes
Problem Solution
Project Euler Template
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.
<uncopyable>
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
1"""
2Project Euler Template
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<uncopyable>
8
9Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right
10click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
11"""
12from typing import List, MutableMapping, Sequence
13
14from .lib.utils import get_data_file
15
16
17def min_path_sum(
18 matrix: Sequence[Sequence[int]],
19 cache: MutableMapping[Sequence[Sequence[int]], int]
20) -> int:
21 if matrix in cache:
22 return cache[matrix]
23 if len(matrix[0]) == 1:
24 result = sum(row[0] for row in matrix)
25 elif len(matrix) == 1:
26 result = sum(matrix[0])
27 else:
28 result = matrix[0][0] + min(
29 min_path_sum(matrix[1:], cache),
30 min_path_sum(tuple(row[1:] for row in matrix), cache)
31 )
32 cache[matrix] = result
33 return result
34
35
36def main() -> int:
37 setup: List[Sequence[int]] = []
38 for raw_line in get_data_file('p0081_matrix.txt').splitlines():
39 line = raw_line.rstrip('\n')
40 setup.append(tuple(int(x) for x in line.split(',')))
41 return min_path_sum(tuple(setup), {})