Project Euler Solution 83: Path sum: four ways

Project Euler Problem 83: Path sum: four ways moves Problem 81 and 82 to the next level, now we can go into all directions.

The problem is basically the same, we have an 80×80 matrix with numbers. We are to find a path through the matrix such that the sum of values along it is minimized. This time we can go up, down, right and left. We do start at the top left and end at the bottom right, so at least the source and target is fixed.

We cannot do the same reduction trick that we used for Solution 81: Path sum: two ways and Solution 82: Path sum: three ways. Instead we need to use something more versatile.

I have heard of Dijkstra's algorithm before. It can find the shortest path through a graph. In principle the A* search algorithm would be even more powerful, but it would be more difficult to implement. So I have chosen the basic Dijkstra algorithm and it works sufficiently well.

We again use the example to have a test case:

def test_four_way_path_sum() -> None:
    matrix = [
        [131, 673, 234, 103, 18],
        [201, 96, 342, 965, 150],
        [630, 803, 746, 422, 111],
        [537, 599, 497, 121, 956],
        [805, 732, 524, 37, 331],
    ]
    assert four_way_path_sum(matrix) == 2297

The Dijkstra algorithm works as follows:

• Create a set of unvisited nodes, initially it will contain all the nodes.
• Mark all nodes in the graph with infinite distance. In my case I don't have an infinite integer. But using the sum of all values in the matrix plus one will certainly be larger than all the paths through the matrix.
• Mark the distance of the start node as zero.
• While there are unvisited nodes (or the target node is still unvisited):
  • Take the unvisited node with the minimum distance as the current node. In the first step that is the start node by construction.
  • Look at every neighboring node via all the edges that leave the current node. The distance to the neighbor via the current node is the current distance plus the weight of the edge. If that is lower than the distance of the neighbor, set the neighbor's distance to that. Otherwise leave it.
  • Remove the current node from the unvisited set.
• Return the distance of the target node.

In our case the weights are not on the edges but rather on the nodes themselves. This is not a problem, we just need to change the distance computation a bit. The distance is the current distance plus the neighbor's weight.

I haven't used arrays for the unvisited set and the distances, I just used a set of tuples for the unvisited set and a dict of tuples to integers for the distances. This made it much easier to check whether all neighbors even exist because I can just check the unvisited set.

def four_way_path_sum(matrix: list[list[int]]) -> int:
    size = len(matrix)
    node_weights = {
        (row, col): matrix[row][col] for row in range(size) for col in range(size)
    }
    infinity = sum(node_weights.values()) + 1
    unvisited = {(row, col) for row in range(size) for col in range(size)}
    distances = {(row, col): infinity for row in range(size) for col in range(size)}
    distances[(0, 0)] = matrix[0][0]
    target = (size - 1, size - 1)
    while target in unvisited:
        current = min(unvisited, key=lambda node: distances[node])
        current_row, current_col = current
        up = (current_row - 1, current_col)
        down = (current_row + 1, current_col)
        left = (current_row, current_col - 1)
        right = (current_row, current_col + 1)

        for neighbor in [up, down, left, right]:
            if neighbor in unvisited:
                distances[neighbor] = min(
                    distances[neighbor], distances[current] + node_weights[neighbor]
                )

        unvisited.remove(current)

    return distances[target]

The solution driver is pretty trivial now:

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

This finishes in 2.6 s, which is okay given the implementation with dicts and sets. One could very likely implement this much better. Also the A* search algorithm might be faster because it might need to evaluate fewer directions. Still, this was a fun occasion to finally learn about and apply the Dijkstra algorithm myself. It is an algorithm which is used for many things like routing and also text layout with LaTeX or code formatting with Clang Format. I had assumed that it was much more complicated, but it turns out to be rather straightforward once one has seen it in action.