How to Solve Advent of Code 2024 - Day 10 with Python

We're going hiking... or at least we're drawing hiking maps. So back to evaluating grids and counting neighbors again.

But before we get right into the day and my solution for this day's puzzle, here is the info on how I approach this whole event (where my code is, what editor I use, etc):

Advent of Code 2024 - Info Post

It’s the most festive time of the year - Advent of Code! The highlight of every coder’s December 🎄❄️💻🎉 Here’s everything about my participation, I will link to this from every days’ post. What even IS Advent of Code??!! Good question, my friend. Here is this year’s about page: https:

Machine Learning ChroniclesSarah Glasmacher

🎄❄️💻

Day 10 Puzzle

On my blog here, I will go through the puzzle and my way of solving it. If you want, you can jump directly to the code solution here:
GitHub .py script

Here is the challenge, if you want to read the full puzzle:
Advent of Code 2024 - Day 10

We are back in the Lava Production Facility from Advent of Code 2023, Day 15, and a reindeer scorched their hiking map, so we need to redraw all the hiking trails.

A hiking trail is basically just a series of map entries with continually increasing height, which we are identifying on a grid.

Part 1

We get a basic 2-dimensional grid as input and we are supposed to find increasing sequences of numbers in them. Starting at 0 and ending at 9 - however, the sequences can have overlaps or split along the way, like below:

...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9

Read in digit grid (used in previous days already):

def read_int_grid_from_lines(lines: list[str]) -> np.ndarray:
    int_lines = [[int(char) for char in line.strip()] for line in lines]
    return np.array(int_lines)

Solution Approach

• Search for 0 entries.
• For each 0, search for trailends (9) that can be reached from this spot using the search_for_trailends function below.
• Simply add the number of trailends.

def solve_part_1(mode: str = "example"):
    file_lines = read_input_file(day=10, mode=mode)
    topographic_map = read_int_grid_from_lines(file_lines)

    sum_of_trailhead_scores = 0
    for row in range(topographic_map.shape[0]):
        for col in range(topographic_map.shape[1]):
            if topographic_map[row, col] == 0:
                trailhead_score = search_for_trailends(topographic_map, (row, col))
                sum_of_trailhead_scores += trailhead_score
    return sum_of_trailhead_scores

Finding Trailends

• Build a queue of neighbors to visit.
• Mark each visited grid square in a visited grid.
• Look at all 4 neighbors and check if their value is one above the current value.
• Add each qualifying neighbor to the queue.
  (I guess this is a breadth-first search when considering the graph of hike-able paths.)

def search_for_trailends(
    topographic_map: np.ndarray, start_position: tuple[int, int]
) -> int:
    visited = np.zeros_like(topographic_map, dtype=bool)
    visited[start_position] = True
    queue = deque([start_position])
    score = 0
    while queue:
        current_position = queue.pop()
        visited[current_position] = True
        current_value = topographic_map[current_position]
        if current_value == 9:
            score += 1
        for neighbor in get_reachable_neighbors(topographic_map, current_position):
            if not visited[neighbor] and neighbor not in queue:
                queue.append(neighbor)
    return score

Part 2

Here, we don't count the ends (entries with value 9) anymore, but instead all the different paths that lead to such a 9-entry. The method search_for_distinct_trails does not require tracking visited nodes. Each possible trail is explored independently, and there’s no need to avoid revisiting nodes since distinct paths are naturally counted via the traversal.

def solve_part_2(mode: str = "example"):
    file_lines = read_input_file(day=10, mode=mode)
    topographic_map = read_int_grid_from_lines(file_lines)

    sum_of_trailhead_scores = 0
    for row in range(topographic_map.shape[0]):
        for col in range(topographic_map.shape[1]):
            if topographic_map[row, col] == 0:
                trailhead_score = search_for_distinct_trails(
                    topographic_map, (row, col)
                )
                sum_of_trailhead_scores += trailhead_score
    return sum_of_trailhead_scores

Counting Distinct Trails
The logic here is very similar to Part 1:

def search_for_distinct_trails(
    topographic_map: np.ndarray, start_position: tuple[int, int]
) -> int:
    queue = deque([start_position])
    score = 0
    while queue:
        current_position = queue.pop()
        current_value = topographic_map[current_position]
        if current_value == 9:
            score += 1
        for neighbor in get_reachable_neighbors(topographic_map, current_position):
            queue.append(neighbor)
    return score