Project Euler Solution 81: Path sum: two ways

In Problem 81: Path sum: two ways we have to find a special path through a 2D lattice.

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{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} $$

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

As a first step we can load the data such that we got that out of the way. It resembles JSON again, so we can use that library to parse it.

def read_matrix(filename: str) -> list[list[int]]:
    result = []
    with open(filename) as f:
        for line in f:
            result.append(json.loads(f"[{line}]"))
    return result

The paths that we can follow are the same as in Solution 15: Lattice paths. We know that there is a combinatoric number of them, so we cannot compute all of them. The minimum path is very similar to Solution 18: Maximum path sum I. Except of going down-left or down-right, we go down or right. We can combine these insights into applying the algorithm of solution 18 just with propagating the minimum up and left. We need to be a bit careful with the boundaries and we also need to traverse the matrix in the right order.

We take the numbers from the example matrix. We need to propagate the path sum along the red arrows. In order to do this, we need to go through the elements as indicated with the gray pencil marks. We iterate in diagonals from the buttom right to the top left.

For this I have defined an interator to encapsulate this. Again, this can be done test driven with the test on a 3×3 grid first:

def test_iter_diagonally() -> None:
    expected = [(2, 2), (2, 1), (1, 2), (2, 0), (1, 1), (0, 2), (1, 0), (0, 1), (0, 0)]
    actual = list(iter_diagonally(3))
    assert actual == expected

Then let's implement this iterator:

def iter_diagonally(size: int) -> Iterator[tuple[int, int]]:
    row = size - 1
    col = size - 1
    while True:
        yield row, col
        col += 1
        row -= 1
        if row < 0:
            row = col - 2
            col = 0
            if row < 0:
                return
        if col >= size:
            col = row
            row = size - 1

With that iterator in place it is rather straightforward to propagate the path sum along the red arrows:

def solution() -> None:
    matrix = read_matrix("data/p081_matrix.txt")
    size = 80
    for row, col in iter_diagonally(size):
        neighbors = []
        if row < size - 1:
            neighbors.append(matrix[row + 1][col])
        if col < size - 1:
            neighbors.append(matrix[row][col + 1])
        matrix[row][col] += min(neighbors, default=0)
    return matrix[0][0]

The solution is in the top corner of that reduced matrix. This solution computes it in 4.6 ms and I doubt that any brute force version would finish sensibly.