Advent of Code 2024 Day 16: Reindeer Maze

Dec 16, 2024 at 8:38 PM · Advent of Code

Advent of Code 2024

This post is part 16 in the series "Advent of Code 2024":

On the third day of Christmas, Eric Wastl gave to me…three reindeer mazes, two lanternfish warehouses, and a picture of a Christmas tree.

I’m solving the Advent of Code challenges in Python. If all you want is my code for this, you can look for it on my GitHub repository. But if you want to hear me explain my solutions, stick around.

Attention

Spoiler alert! This page, and my GitHub repo, contain full working solutions to Advent of Code challenges. If you want to solve these challenges yourself (and I’d highly recommend it), stop reading now and get coding!

Don’t worry, I’ll probably still be here when you get back.

Challenge

The Reindeer Olympics¹ are happening again – after 9 years, apparently – and you and The Historians are attending the big event: the Reindeer Maze. (Perhaps they’re taking a break from looking for the missing Chief Historian? Or maybe he’s in the audience?)

You look at a map of the Reindeer Maze to figure out the best place to sit. In the event, the Reindeer start on the tile marked S facing east, and are trying to reach the tile marked E.

They incur points along the way: they get 1 point for moving forward one tile (taking care to avoid walls, marked with # characters), and they get 1000 points for turning to their left or right. The lowest score wins.

Here’s an example of what the maze might look like.

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############

Although there are several paths in this maze, the best paths will incur a score of 7036 (remember, lowest score wins!). Here’s one of these best paths:

###############
#.......#....E#
#.#.###.#.###^#
#.....#.#...#^#
#.###.#####.#^#
#.#.#.......#^#
#.#.#####.###^#
#..>>>>>>>>v#^#
###^#.#####v#^#
#>>^#.....#v#^#
#^#.#.###.#v#^#
#^....#...#v#^#
#^###.#.#.#v#^#
#S..#.....#>>^#
###############

Here’s a larger example:

#################
#...#...#...#..E#
#.#.#.#.#.#.#.#.#
#.#.#.#...#...#.#
#.#.#.#.###.#.#.#
#...#.#.#.....#.#
#.#.#.#.#.#####.#
#.#...#.#.#.....#
#.#.#####.#.###.#
#.#.#.......#...#
#.#.###.#####.###
#.#.#...#.....#.#
#.#.#.#####.###.#
#.#.#.........#.#
#.#.#.#########.#
#S#.............#
#################

In this maze, following one of the best paths (such as this one) incurs 11,048 points (including 1,000 points for an immediate left turn at the very start):

#################
#...#...#...#..E#
#.#.#.#.#.#.#.#^#
#.#.#.#...#...#^#
#.#.#.#.###.#.#^#
#>>v#.#.#.....#^#
#^#v#.#.#.#####^#
#^#v..#.#.#>>>>^#
#^#v#####.#^###.#
#^#v#..>>>>^#...#
#^#v###^#####.###
#^#v#>>^#.....#.#
#^#v#^#####.###.#
#^#v#^........#.#
#^#v#^#########.#
#S#>>^..........#
#################

For Part 1, you want to figure out the lowest score that a Reindeer can possibly get.

Once you figure out what the best paths look like, you want to be able to sit near them, so you can catch a glimpse of all the top reindeer athletes.

The first example has 45 tiles that are part of some best path through it (marked here with O characters):

###############
#.......#....O#
#.#.###.#.###O#
#.....#.#...#O#
#.###.#####.#O#
#.#.#.......#O#
#.#.#####.###O#
#..OOOOOOOOO#O#
###O#O#####O#O#
#OOO#O....#O#O#
#O#O#O###.#O#O#
#OOOOO#...#O#O#
#O###.#.#.#O#O#
#O..#.....#OOO#
###############

Meanwhile, the second example has 64 tiles that are part of some best path:

#################
#...#...#...#..O#
#.#.#.#.#.#.#.#O#
#.#.#.#...#...#O#
#.#.#.#.###.#.#O#
#OOO#.#.#.....#O#
#O#O#.#.#.#####O#
#O#O..#.#.#OOOOO#
#O#O#####.#O###O#
#O#O#..OOOOO#OOO#
#O#O###O#####O###
#O#O#OOO#..OOO#.#
#O#O#O#####O###.#
#O#O#OOOOOOO..#.#
#O#O#O#########.#
#O#OOO..........#
#################

For Part 2, you want to figure out how many tiles are on at least one of the best paths through the maze.

My solution

Another day, another grid-based puzzle. Well, at least this time, it gives me an excuse to break out an algorithm I used for an Advent of Code challenge a year ago (almost to the day!).

Before we get to that, however, we need to get some things out of the way. First, some imports, some type aliases, and a parsing function like usual.

from collections import defaultdict
from collections.abc import Callable, Iterable, Iterator
from functools import partial
from heapq import heappop, heappush
from typing import TypeAlias


# NOTE I would make the coordinates be complex numbers, but comparisons
# with them raise a TypeError, and heapq will make comparisons with
# tuples that contain these "vectors".
Vector: TypeAlias = tuple[int, int]
Grid: TypeAlias = defaultdict[Vector, str]
# PathState is a tuple of position and direction
PathState: TypeAlias = tuple[Vector, Vector]


def parse_input(lines: Iterable[str]) -> tuple[Grid, Vector, Vector]:
    """
    Parse the input, and return a grid, a starting position, and an
    ending position.
    """
    grid: Grid = defaultdict(lambda: "#")
    start_pos, end_pos = None, None
    for r, row in enumerate(lines):
        for c, tile in enumerate(row):
            pos = (r, c)
            if tile == "S":
                start_pos = pos
            elif tile == "E":
                end_pos = pos
            grid[pos] = tile
    assert start_pos is not None and end_pos is not None
    return grid, start_pos, end_pos

Next, I define a helper function for the algorithm that finds all the shortest paths. Given a “path state” (a position and facing direction) and a grid, it yields every possible next state that could result from it. In this case, that’s turning to the right, turning to the left, and moving forward (if the reindeer wouldn’t move into a wall).

def iter_next_states(
        state: PathState,
        grid: Grid,
) -> Iterator[tuple[int, PathState]]:
    """
    Iterate through the possible next states for the current path state,
    and their weights.
    """
    (node_r, node_c), (dir_r, dir_c) = state
    # Try turning 90 degrees to the right (1000 points)
    yield 1000, ((node_r, node_c), (dir_c, -dir_r))
    # Try turning 90 degrees to the left (1000 points)
    yield 1000, ((node_r, node_c), (-dir_c, dir_r))
    # Try moving forward (1 point)
    next_node = (node_r + dir_r, node_c + dir_c)
    if grid[next_node] != "#":
        yield 1, (next_node, (dir_r, dir_c))

The algorithm I’m using to find the shortest paths is called Dijkstra’s algorithm, which is for finding the shortest paths in a weighted graph. The Reindeer Maze can be modelled as a weighted graph: turning is like moving along an edge with weight 1000, and moving forward is like moving along an edge with weight 1.

This is a pretty standard implementation of Dijkstra’s algorithm in Python (which I modified from my solution to 2023 Day 17), so I don’t have much to explain about it. If you want to know the gist of how it works, there’s an excellent YouTube video from Spanning Tree that illustrates it nicely.

However, I did modify it a bit to keep track of all the previous search states along the best paths to each search state; that way, to get all of the best paths, I can use those saved states to walk backwards along each path back to the start.

def find_shortest_paths(
        start_state: PathState,
        end_pos: Vector,
        get_next_states: Callable[
            [PathState], Iterable[tuple[int, PathState]]
        ],
) -> tuple[int, Iterator[list[PathState]]]:
    """
    Find the shortest path between two points in a weighted graph using
    Dijkstra's algorithm.

    In this case, the path states include the current facing direction.
    The search concludes when `end_pos` is reached, regardless of the
    rest of the path state. For each possible next path state,
    `get_next_states` should return both its cost and the state itself.
    """
    # Lowest costs to get to each state
    costs: dict[PathState, int] = {}
    # Queue of states left to search from
    # NOTE Using the heapq library, we can treat this like a priority
    # queue, which allows the minimum item to be efficiently removed
    # in each iteration of the search.
    priority_queue: list[tuple[int, PathState]] = [(0, start_state)]
    # Previous states for each visited state
    # NOTE This will help in reconstructing each path later; this could
    # be omitted if that isn't needed.
    prev_states: defaultdict[PathState, set[PathState]] = defaultdict(set)

    while priority_queue:
        cost, state = heappop(priority_queue)
        # Stop searching if end position was reached
        pos, *_ = state
        if pos == end_pos:
            break
        # For each possible next state and its weight
        for weight, next_state in get_next_states(state):
            prev_cost = costs.get(next_state, float("inf"))
            next_cost = cost + weight
            # If we've found a lower-cost way to get to this state
            if next_cost < prev_cost:
                # Update its cost and continue searching from here
                costs[next_state] = next_cost
                heappush(priority_queue, (next_cost, next_state))
                # Reset the previous states (they didn't count)
                prev_states[next_state] = {state}
            # If we've found a same-cost way to get to this state
            elif next_cost == prev_cost:
                # This state is the next state's previous state
                prev_states[next_state].add(state)
    else:
        raise RuntimeError("no path exists!")

    start_node, *_ = start_state
    # Walk backwards down each path from the end to the start
    # NOTE Making this function return an iterator instead of a list
    # means the paths won't be walked down unless we tell it to, making
    # it faster if we don't need the paths.
    def walk(state: PathState) -> Iterator[list[PathState]]:
        node, *_ = state
        if node == start_node:
            yield [state]
            return
        for prev_state in prev_states[state]:
            for path in walk(prev_state):
                yield path + [state]

    return cost, walk(state)

Tip

This is the first time this year that I’m using the standard library module heapq. heapq provides functions that allows you to treat a list as a “min heap” – a data structure that allows for extracting its minimum item very efficiently.²

This is commonly used when an algorithm calls for a “priority queue”, as Dijkstra’s algorithm does.

My solutions for Part 1 and Part 2 become very short with these functions defined.

def aoc2024_day16_part1(lines: Iterable[str]) -> int:
    grid, start_pos, end_pos = parse_input(lines)
    cost, _ = find_shortest_paths(
        # The reindeer starts moving east
        start_state=(start_pos, (0, 1)),
        end_pos=end_pos,
        get_next_states=partial(iter_next_states, grid=grid),
    )
    return cost


def aoc2024_day16_part2(lines: Iterable[str]) -> int:
    grid, start_pos, end_pos = parse_input(lines)
    _, paths = find_shortest_paths(
        # The reindeer starts moving east
        start_state=(start_pos, (0, 1)),
        end_pos=end_pos,
        get_next_states=partial(iter_next_states, grid=grid),
    )
    # Count unique positions along all paths
    return len({pos for path in paths for pos, _ in path})

Tip

My iter_next_states() function takes two arguments – a path state, and a grid. But when I pass it to my find_shortest_paths() function, it expects a function that takes one argument – a path state.

To solve this problem, I’m using functools.partial() from the standard library. It creates a version of a function with some arguments already filled in; for example, functools.partial(int, base=2) creates a version of the int() function that always calls it with the keyword argument base=2.

In this case, the function I create fills in the grid keyword argument that the iter_next_states() function needs, so that it can be used by the find_shortest_paths() function which expects to only fill in the path state.

They missed a big opportunity to call them the “Reindeer Games”. ↩
The way I’m implementing Dijkstra’s algorithm is by storing tuples (representing graph nodes that are visited) in a list, which heapq is treating as a heap. However, heapq’s functions only work if comparisons work between the items.

I wanted to use complex numbers to represent coordinates, just like I did yesterday – if I did, then rotating the reindeer would be a single multiplication! – but I couldn’t put them in the heap, because comparisons between complex numbers raise a TypeError. (They work just fine with tuples of ints, though, so I went with those instead.)

Now, Python’s docs do recommend some ways to use heapq to be able to treat a heap more like a “priority queue”, and I very well could’ve used one of those techniques in particular to solve this problem. But in this case, it would’ve been a bit too complex (pardon the pun) and hard to explain for very little benefit. ↩