TheAlgorithms-Python

1
"""
2
Problem 81: https://projecteuler.net/problem=81
3
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right,
4
by only moving to the right and down, is indicated in bold red and is equal to 2427.
5

6
    [131]   673   234    103    18
7
    [201]  [96]  [342]   965   150
8
     630   803   [746]  [422]  111
9
     537   699   497    [121]  956
10
     805   732   524    [37]  [331]
11

12
Find the minimal path sum from the top left to the bottom right by only moving right
13
and down in matrix.txt (https://projecteuler.net/project/resources/p081_matrix.txt),
14
a 31K text file containing an 80 by 80 matrix.
15
"""
16

17
import os
18

19

20
def solution(filename: str = "matrix.txt") -> int:
21
    """
22
    Returns the minimal path sum from the top left to the bottom right of the matrix.
23
    >>> solution()
24
    427337
25
    """
26
    with open(os.path.join(os.path.dirname(__file__), filename)) as in_file:
27
        data = in_file.read()
28

29
    grid = [[int(cell) for cell in row.split(",")] for row in data.strip().splitlines()]
30
    dp = [[0 for cell in row] for row in grid]
31
    n = len(grid[0])
32

33
    dp = [[0 for i in range(n)] for j in range(n)]
34
    dp[0][0] = grid[0][0]
35
    for i in range(1, n):
36
        dp[0][i] = grid[0][i] + dp[0][i - 1]
37
    for i in range(1, n):
38
        dp[i][0] = grid[i][0] + dp[i - 1][0]
39

40
    for i in range(1, n):
41
        for j in range(1, n):
42
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
43

44
    return dp[-1][-1]
45

46

47
if __name__ == "__main__":
48
    print(f"{solution() = }")
49