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

Today's challenge tackles Day 10's puzzle, a 2D grid similar to Day 6, but requiring exploration of multiple paths. This puzzle elegantly showcases the power of depth-first search (DFS).

An AI-generated illustration of the puzzle

The map is represented as a dictionary; keys are (x, y) coordinates, and values are single-digit integers (0-9) indicating height, with 9 representing the peak. The parsing function efficiently handles this data structure:

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)
    }

Trails ascend from trailheads (height 0) to the peak (height 9), increasing height by exactly 1 per step. The next_step function identifies valid next steps:

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)
        )
    )

Trailheads (height 0) are located using find_trailheads:

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)

The core of the solution is the climb function, which implements a depth-first search. Following Wikipedia's definition of DFS, we explore each branch fully before backtracking.

A visual representation of depth-first search

Map points are our "nodes," and we ascend one height level at a time. The climb function manages the DFS process:

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 dead ends, preventing infinite loops. The function returns all paths from each trailhead to the peak.

Part 1 counts the unique peak destinations:

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

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

Part 2 counts all unique paths:

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

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

While alternative approaches exist (e.g., integrating trailhead detection into parsing), this solution's performance is acceptable. Recent job search setbacks haven't dampened my spirits; I remain hopeful. If you're seeking a mid-senior Python developer, please reach out. Until next week!

The above is the detailed content of Climbing a depth-first search hill, Advent of Code day 10. For more information, please follow other related articles on the PHP Chinese website!