Reindeer Maze

Part 1

Another day, another grid puzzle. A pathfinding puzzle, in fact… which reminds me a bit of 2023 Day 17. That day, we were also trying to minimize some metric in a path through a grid, where doing different things had different costs in that metric.

In my solution to 2023 Day 17, I thought of the grid as a weighted graph, where moving to different nodes incurred different “weights”; that way, I could use Dijkstra’s algorithm or the A* algorithm to find the shortest (i.e. lowest-weight) path in the weighted graph. Today, the point values of the Reindeer moving forward and turning can be thought of the “weights” in a weighted graph, so I’ll be using the same approach here.

To handle these sorts of pathfinding puzzles, I created a custom pathfinding module with a function called find_shortest_paths. It uses either Dijkstra’s algorithm or A*, depending on whether you provide a “heuristic” function that estimates the distance between two states. You can see the code for it below, and you can read my writeup of 2023 Day 17 for an explanation of how it works.

30 collapsed lines
# pyright: reportArgumentType=false
from collections import defaultdict
from collections.abc import Callable, Hashable, Iterable
from dataclasses import dataclass
from heapq import heapify, heappop, heappush
from math import inf
from typing import Protocol

class PathState[Node](Hashable, Protocol):
    """
    Protocol defining the interface for states used in pathfinding.
    """
    @property
    def node(self) -> Node: ...

# HACK The type checker complains when I constrain the generic typevar
# State by PathState[Node], since Node is also a generic typevar. The
# only thing I can do about this seems to be to ignore it. (This will
# happen repeatedly throughout this module.)
@dataclass(frozen=True)
class PathResult[Node, State: PathState[Node]]:  # pyright: ignore[reportGeneralTypeIssues]
    """
    Result of `find_shortest_paths`.
    """
    distance: int

# Custom exception: no path exists
class NoPathError(Exception):
    """No path exists from the start states to the end node."""
    pass

def find_shortest_paths[Node, State: PathState[Node]](  # pyright: ignore[reportGeneralTypeIssues]
        start_states: Iterable[State],  # must be non-empty
        end_node: Node,
        *,
        get_transitions: Callable[[State], Iterable[tuple[State, int]]],
        heuristic: Callable[[Node, Node], int] | None = None,
) -> PathResult[Node, State]:
8 collapsed lines
    start_states_set: set[State] = set(start_states)
    if not start_states_set:
        raise ValueError("start_states must be non-empty")
    # Verify all start states have the same node
    start_node = next(iter(start_states_set)).node
    if not all(s.node == start_node for s in start_states_set):
        raise ValueError("all start states must have the same node")

    distances: dict[State, int | float] = defaultdict(
        lambda: inf,
        {(s, 0) for s in start_states_set},
    )

    # NOTE For A*, priority = distance + heuristic; for Dijkstra,
    # priority is distance.
    def get_priority(distance: int, node: Node) -> int:
        return distance + (heuristic(node, end_node) if heuristic else 0)

    priority_queue: list[tuple[int, int, State]] = [
        (get_priority(0, s.node), 0, s)
        for s in start_states_set
    ]
    heapify(priority_queue)
    shortest_distance: int | None = None

    while priority_queue:
        _, distance, state = heappop(priority_queue)

        # If we've found an end state, record the distance
        if state.node == end_node:
            shortest_distance = distance
            break

        # Skip if we've already found this state with a lower distance
        if distances[state] < distance:
            continue

        for next_state, distance_to_next_state in get_transitions(state):
            prev_distance = distances[next_state]
            next_distance = distance + distance_to_next_state

            # If this is a lower-distance way to get here
            if next_distance < prev_distance:
                # Update distances and continue searching from here
                distances[next_state] = next_distance
                priority = get_priority(next_distance, next_state.node)
                heappush(priority_queue, (priority, next_distance, next_state))

    if shortest_distance is None:
        raise NoPathError(
            f"no path exists from {start_node!r} to {end_node!r}"
        )

    return PathResult(
        distance=shortest_distance,
    )

The hard part is already done, so let’s quickly finish up Part 1!

To use my find_shortest_paths function, we have to tell it a few things:

1. The starting path states. They must have the same “node” — location in the grid — but they can have different attributes such as facing direction.
2. The ending node. Once a path state reaches this node, the path is finished.
3. How to transition from one path state to another, and the associated weights of those transitions. This will be in the form of a get_transitions function, which takes a path state and yields each possible next state and the weight of transitioning to it.
4. Optionally, you can provide a “heuristic” function that estimates the distance between two states. If you can find a good choice of heuristic, it could speed up the search considerably.¹

First, we’ll parse the grid and find the start and end nodes. I have a custom grids module to handle this; you can read my writeups for Days 4, 6, 8, 10, 12, and 15 to see how it works.

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        grid = parse_grid(self.input, ignore_chars="#")
        start_node = next(k for k, v in grid.items() if v == "S")
        end_node = next(k for k, v in grid.items() if v == "E")
        ...

Next, we need a good way to represent the Reindeer. They all have a location in the grid and a facing direction, so the Position class from my grids module is a good choice. (In fact, because my find_shortest_paths needs our states to have a node property, we’ll want to create a subclass of Position that has such a property.)

class State(Position):
    # NOTE find_shortest_paths needs a state with a node property.
    @property
    def node(self) -> GridPoint:
        return self.point

We’ll also want to know which states the Reindeer can transition to and their respective point totals. They can rotate in place clockwise or counter-clockwise for 1,000 points, or if they’re not in front of a wall, they can step forward for 1 point.

from collections.abc import Iterator

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        ...
        def get_transitions(s: State) -> Iterator[tuple[State, int]]:
            # Turn 90 degrees clockwise = 1000 points
            yield s.rotate("CW"), 1000
            # Turn 90 degrees counter-clockwise = 1000 points
            yield s.rotate("CCW"), 1000
            # Move forward = 1 point
            if s.next_point in grid:
                yield s.step(), 1
        ...

Finally, we can put it all together with a call to find_shortest_paths. (The Reindeer start at the start node facing right; this is our only starting state.)

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        ...
        path_result = find_shortest_paths(
            [State(start_node, Direction.RIGHT)],
            end_node,
            get_transitions=get_transitions,
        )
        return path_result.distance

The distance property of the result will have the lowest point total the Reindeer can achieve! Looks like my pathfinding module greatly simplified our code here.

Part 2

Before, my pathfinding module simply returned the distance of the shortest path. But for this puzzle, I think it’s a good idea to rework it to return the shortest path itself — or all shortest paths, if more than one exists.² So let’s do that first.

Before we proceed, let’s modify my PathResult class to not just store the distance, but the actual paths (as lists of path states).

from collections.abc import Callable, Hashable, Iterable, Iterator
from dataclasses import dataclass
from typing import Protocol

class PathState[Node](Hashable, Protocol):
    """
    Protocol defining the interface for states used in pathfinding.
    """
    @property
    def node(self) -> Node: ...

@dataclass(frozen=True)
class PathResult[Node, State: PathState[Node]]:  # pyright: ignore[reportGeneralTypeIssues]
    """
    Result of `find_shortest_paths`.
    """
    distance: int
    paths: Iterator[list[State]]

First, we need to change how we handle finding an end state. Currently, we break out of the main loop as soon as we find a single end state; we’ll want to change this to find all possible end states, as long as they end some shortest path. The end states we reach will be saved in an end_states list for our convenience.

...

def find_shortest_paths[Node, State: PathState[Node]](  # pyright: ignore[reportGeneralTypeIssues]
        start_states: Iterable[State],  # must be non-empty
        end_node: Node,
        *,
        get_transitions: Callable[[State], Iterable[tuple[State, int]]],
        heuristic: Callable[[Node, Node], int] | None = None,
) -> PathResult[Node, State]:
    ...
    end_states: list[State] = []

    while priority_queue:
        _, distance, state = heappop(priority_queue)
        # If we've found an end state, record the distance
        if state.node == end_node:
            if shortest_distance is None:
                shortest_distance = distance
            # Continue until we exceed the shortest distance (so we find
            # all ending states at the same distance)
            if distance > shortest_distance:
                break
            end_states.append(state)
            continue
        ...
    ...

Second, we need to record some more information during the main loop. In order to reconstruct the shortest paths, we’re going to store the previous states for all states we visit, so we can eventually build each shortest path going backwards from the end to the start.

We’ll do this by creating a dict mapping path states to a set of all of its previous path states; first we clear this set if our current path to this state is more optimal than before, and then we add the previous state to this set if our current path is at least as optimal as before.

from collections import defaultdict
...

def find_shortest_paths[Node, State: PathState[Node]](  # pyright: ignore[reportGeneralTypeIssues]
        start_states: Iterable[State],  # must be non-empty
        end_node: Node,
        *,
        get_transitions: Callable[[State], Iterable[tuple[State, int]]],
        heuristic: Callable[[Node, Node], int] | None = None,
) -> PathResult[Node, State]:
    ...
    end_states: list[State] = []
    prev_states: dict[State, set[State]] = defaultdict(set)

    while priority_queue:
        ...
        # Skip if we've already found this state with a better distance
        if distances[state] < distance:
            continue

        for next_state, distance_to_next_state in get_transitions(state):
            prev_distance = distances[next_state]
            next_distance = distance + distance_to_next_state

            # If this is a lower-distance way to get here
            if next_distance < prev_distance:
                # Update distances and continue searching from here
                distances[next_state] = next_distance
                priority = get_priority(next_distance, next_state.node)
                heappush(priority_queue, (priority, next_distance, next_state))
                # No other path to here has been optimal yet
                prev_states[next_state].clear()

            # If this isn't a higher-distance way to get here
            if next_distance <= prev_distance:
                # The state we got here from is on an optimal path
                prev_states[next_state].add(state)
    ...

And finally, we need to use this new information to construct every possible shortest path. Each shortest path can be walked through in reverse by taking our previous-states dict, starting at an ending state, and moving backwards until we reach a starting state; we can therefore find all shortest paths by finding all possible previous-state paths from an ending state to a starting state.

To do this, I created a small paths_ending_at function which takes a path state and yields all paths ending at that state. This is easy to do using recursion:

• Base case: If the current path state is a starting state, the result is a path consisting of only that starting state itself.
• Recursive case: First, find all paths ending at all previous states; then, the results will be each of those paths with the current state appended to them.

To get all paths to all ending states, I simply map that function over all the ending states we’ve seen, and use itertools.chain.from_iterable to collect all the paths into a single iterable for easy consumption.

from itertools import chain
...

def find_shortest_paths[Node, State: PathState[Node]](  # pyright: ignore[reportGeneralTypeIssues]
        start_states: Iterable[State],  # must be non-empty
        end_node: Node,
        *,
        get_transitions: Callable[[State], Iterable[tuple[State, int]]],
        heuristic: Callable[[Node, Node], int] | None = None,
) -> PathResult[Node, State]:
    ...
    if shortest_distance is None:
        raise NoPathError(
            f"no path exists from {start_node!r} to {end_node!r}"
        )

    # Generate all paths lazily
    def paths_ending_at(state: State) -> Iterator[list[State]]:
        """Generate all paths ending at `state`."""
        if state in start_states_set:
            yield [state]
            return
        for prev_state in prev_states[state]:
            for path in paths_ending_at(prev_state):
                yield path + [state]

    all_paths = chain.from_iterable(map(paths_ending_at, end_states))

    return PathResult(
        distance=shortest_distance,
        paths=all_paths,
    )

And just like that, we now have an efficient way to not just find the distance of the shortest paths in a weighted graph, but the shortest paths themselves! This will be extremely useful for any pathfinding problem we come across.

The fact that we can now obtain every lowest-point path through the grid makes Part 2 almost trivial; we can collect all nodes from all such paths into a set and return its length using len.

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        ...
        path_result = find_shortest_paths(
            [State(start_node, Direction.RIGHT)],
            end_node,
            get_transitions=get_transitions,
        )
        all_nodes = set(
            state.node
            for path in path_result.paths
            for state in path
        )
        return path_result.distance, len(all_nodes)

Don’t you just love useful modules like this that do all the hard work for you? Well, I hope this shows you that even you could create such a module, piece by piece, for your own tasks! It’s a very rewarding and fulfilling experience.