Project Euler Solution 82: Path sum: three ways

In Problem 82: Path sum: three ways we have the same basic task as in the previous problem, we just have to deal with movements in three directions now.

We are given another 80×80 matrix of numbers and now have to look at the sum of numbers along paths. This time we can start at any position on the left column and have to end at any position on the right column. We can move right, up and down.

The idea of the previous solution still applies, we just have to extend it a bit. We will work with the columns starting from the right side. We start in the second last column. We will take each cell in the column as a start and try all paths to each cell on the right. We sum up all the nodes from above or below and the one node on the right. The ways that we consider to compute the cost for the encircled node are marked with arrows. The total cost is written in numbers above the arrows.

Here we can see that the optimal path is to go down once to the 37 and then go right to the 331. Going right first and then down or up doesn't make any sense, we would already have reached the right edge after stepping right.

We compute this for all the cells in the column and then replace the weight with the minimum of all the values that we have found. One has to be a bit careful not to overwrite the value directly but first compute all new values and update them afterwards.

This reduction of a column can then be expressed as a bunch of nested list comprehensions; I felt like functional programming there.

def reduce_column(matrix: list[list[int]], col: int) -> None:
    assert col > 0
    new_entries = [
        min(
            sum(
                matrix[cell][col - 1]
                for cell in range(min(row, target), max(row, target) + 1)
            )
            + matrix[target][col]
            for target in range(len(matrix))
        )
        for row in range(len(matrix))
    ]
    for row, value in enumerate(new_entries):
        matrix[row][col - 1] = value

The three way path sum then is just the reduction of the columns from the right to the left.

def three_way_path_sum(matrix: list[list[int]]) -> int:
    for col in range(len(matrix) - 1, 0, -1):
        reduce_column(matrix, col)
    return min(matrix[row][0] for row in range(len(matrix)))

The example given in the problem statement can serve as a test:

def test_three_way_path_sum() -> None:
    matrix = [
        [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],
    ]
    assert three_way_path_sum(matrix) == 994

We use the matrix reading function from Solution 81: Path sum: two ways. Otherwise there is not much to do to form the solution:

def solution() -> None:
    matrix = read_matrix("data/p082_matrix.txt")
    return three_way_path_sum(matrix)

And that's it. It runs in 1.1 s, so that should be fast enough.