Climbing a depth-first search hill, Advent of Code 2024, day 10

Today, we’re diving into the Day 10 puzzle. Like Day 6, it’s a 2D grid, but this time, we need to consider multiple paths. It’s fascinating to see how depth-first search comes into play here.

A helpful AI illustration of the puzzle by Copilot

Each point on the map is represented by a single-digit integer indicating its height, ranging from 0 to 9, with 9 being the peak. For efficient height lookups, the map is stored as a dictionary with (x, y) coordinates as keys and corresponding heights as values.

def parse(input: str) -> dict[tuple[int, int], int | None]:
    return {
        (x, y): int(item) if item.isdigit() else None
        for y, row in enumerate(input.strip().splitlines())
        for x, item in enumerate(row)
    }

The puzzle defines trails that ascend from trailheads (points with a height of 0) to a peak height of 9. Each step along a trail must increase the height by exactly 1. The following code implements this step logic:

TRAIL_MAX = 9

def next_step(
    topo_map: dict[tuple[int, int], int | None], x: int, y: int
) -> tuple[tuple[int, int], ...]:
    assert topo_map[(x, y)] != TRAIL_MAX

    return tuple(
        incoming
        for incoming in (
            (x + 1, y),
            (x, y + 1),
            (x - 1, y),
            (x, y - 1),
        )
        if (
            isinstance(topo_map.get(incoming), int)
            and isinstance(topo_map.get((x, y)), int)
            and (topo_map[incoming] - topo_map[(x, y)] == 1)
        )
    )

To find the trailheads (points with height TRAILHEAD), we use the following function. While it would be more efficient to identify trailheads during the initial map parsing, this separate function performs sufficiently well for this puzzle, so I've opted to keep it as-is for simplicity in this article:

TRAILHEAD = 0

def find_trailheads(
    topo_map: dict[tuple[int, int], int | None],
) -> tuple[tuple[int, int], ...]:
    return tuple(key for key, value in topo_map.items() if value == TRAILHEAD)

Next, we implement depth first search, according to Wikipedia

Depth-first search ( DFS ) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

An animated example of depth first search (image from Wikipedia)

In this puzzle, our “nodes” are points on the map, and we “traverse” by ascending one height level at a time from a trailhead. When we encounter multiple possible next steps (a “branch”), we record them for later exploration. The climb function implements this depth-first search:

def climb(
    topo_map: dict[tuple[int, int], int | None], trailheads: tuple[tuple[int, int], ...]
) -> dict[
    tuple[tuple[int, int], tuple[int, int]], tuple[tuple[tuple[int, int], ...], ...]
]:
    candidates: list[tuple[tuple[int, int], ...]] = [(head,) for head in trailheads]

    result = {}

    while candidates:
        current = candidates.pop()
        while True:
            if topo_map[current[-1]] == TRAIL_MAX:
                result[(current[0], current[-1])] = result.get(
                    (current[0], current[-1]), ()
                ) + (current,)
                break

            elif steps := next_step(topo_map, *current[-1]):
                incoming, *rest = steps

                candidates.extend([current + (step,) for step in rest])

                current = current + (incoming,)
            else:
                break

    return result

The else clause's break handles cases where a path reaches a dead end (no valid next steps) before reaching the peak. This prevents infinite loops and ensures we only consider paths that lead to the peak.

This function returns all possible trails from each trailhead to the peak. While this might be considered overkill, as we are ultimately only interested in the number of paths, the memory usage remains manageable for the given puzzle input (a foreshadowing of potential out-of-memory issues in later puzzles). With this function, we can now determine the solutions for both parts of the puzzle.

Part 1 requires us to find the total number of unique peak destinations reachable from all trailheads. Since the climb function returns a dictionary where keys are (trailhead, peak) pairs, the solution is simply the number of entries in this dictionary:

def part1(input: str) -> int:
    topo_map = parse(input)

    return len(climb(topo_map, find_trailheads(topo_map)))

Part 2 asks for the total number of unique trails between all trailhead-peak pairs. The climb function returns a dictionary where each value is a tuple of trails for a given (trailhead, peak) key. Therefore, we sum the number of trails for each key:

def part2(input: str) -> int:
    topo_map = parse(input)

    return sum(
        len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values()
    )

Reflecting on my approach to these puzzles, particularly comparing earlier strategies to later ones (I finally completed Day 23 this past weekend!), has been a valuable learning experience. While I now see several ways I could have approached things differently (such as including trailheads in the parsing stage), I’m pleased that the code performs within a reasonable timeframe.

On a more personal note, I’ve recently experienced another setback in my job search with a week of unproductive negotiations. I remain optimistic about finding a suitable role. If your team is seeking a mid-senior Python developer, please feel free to contact me.

But for now, thank you for reading, and I shall write again, next week.