Day 16

Today we are spectators to the Reindeer Olympics – specifically the Reindeer Maze. Check out the full back story and problem setup on the official Day 16 of Advent of Code 2024 website.

And here’s the ChatGPT generated graphic of how the elves are traveling in their submarine to get us started:

Setting up

from misc.helper import verify_answer

example_input_file_1 = "../inputs/example_day_16_1.txt"
example_input_file_2 = "../inputs/example_day_16_2.txt"
input_file = "../inputs/day_16.txt"

Part 1: Cheapest path

In this task, we are given a maze and need to determine the cheapest path from the start (S) to the end (E). The maze is a grid where every movement has an associated cost.

Movement Rules:

1. Starting Point: We begin at S, facing East.
   
2. Moving Forward: A step in the current direction costs 1.
   
3. Turning: Changing direction either clockwise or counterclockwise costs 1000.
   
4. Walls: Movement into walls is not allowed.

The objective is to find the path from S to E with the minimum cost.

Example Maze

Consider the following grid:

Example Solution

There are two possible paths from S to E:

1. The first path involves 2 rotations and 6 steps, resulting in a total cost of 2006.
2. The second path involves 2 rotations and 4 steps, resulting in a total cost of 2004.

Thus, the cheapest path has a cost of 2004.

First, let’s parse the input data and represent the maze as an array.

import numpy as np

simple_grid = """
#####
#.E.#
#.#.#
#.#.#
#S..#
#####
"""


def parse_input(grid):
    grid = grid.strip().split("\n")
    grid_mat = np.zeros((len(grid), len(grid[0])))
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell == "S":
                start = (i, j)
            elif cell == "E":
                end = (i, j)
            grid_mat[i, j] = 1 if cell == "#" else 0
    return grid_mat, start, end


parse_input(simple_grid)

(array([[1., 1., 1., 1., 1.],
        [1., 0., 0., 0., 1.],
        [1., 0., 1., 0., 1.],
        [1., 0., 1., 0., 1.],
        [1., 0., 0., 0., 1.],
        [1., 1., 1., 1., 1.]]),
 (4, 1),
 (1, 2))

Next, I will use the Dijkstra’s algorithm to find the cheapest path from S to E. I will leverage heapq to implement the priority queue required for Dijkstra’s algorithm.

import heapq


def find_cheapest_path(grid, start, end, initial_dir=(0, 1)):
    n, m = grid.shape
    clockwise = np.array([[0, 1], [-1, 0]])
    counterclockwise = np.array([[0, -1], [1, 0]])

    # priority queue: (cost, (i, j), direction)
    pq = []
    heapq.heappush(pq, (0, start, np.array(initial_dir)))

    # make note of visited cells
    visited = set()

    while pq:
        cost, (i, j), dir = heapq.heappop(pq)

        # if at the end, return the cost
        if (i, j) == end:
            return cost

        visited.add((i, j, tuple(dir)))

        # forward
        new_i, new_j = i + dir[0], j + dir[1]
        if 0 <= new_i < n and 0 <= new_j < m and grid[new_i, new_j] != 1:
            if (new_i, new_j, tuple(dir)) not in visited:
                heapq.heappush(pq, (cost + 1, (new_i, new_j), tuple(dir)))

        for new_dir in [clockwise @ dir, counterclockwise @ dir]:
            new_i, new_j = i + new_dir[0], j + new_dir[1]
            if 0 <= new_i < n and 0 <= new_j < m and grid[new_i, new_j] != 1:
                if (new_i, new_j, tuple(new_dir)) not in visited:
                    heapq.heappush(
                        pq, (cost + 1001, (new_i, new_j), tuple(new_dir))
                    )
    return -1  # no path found

Finally, I will assemble the functions into part_one to solve the problem.

from pathlib import Path


def part_one(input: str) -> int:
    if Path(input).is_file():
        with open(input, "r") as f:
            grid = f.read()
    else:
        grid = input

    return find_cheapest_path(*parse_input(grid))

I will test the solution on the example above and the ones provided in the problem statement.

verify_answer(part_one, simple_grid, 2004)

✔️ That's right! The answer is 2004.

verify_answer(part_one, example_input_file_1, 7036)

✔️ That's right! The answer is 7036.

verify_answer(part_one, example_input_file_2, 11048)

✔️ That's right! The answer is 11048.

Since the solutions are correct, I will proceed to solve the actual problem.

%time part_one(input_file)

CPU times: user 1.13 s, sys: 7.71 ms, total: 1.14 s
Wall time: 1.17 s

102488

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.

Part 2: All visited cells

In this part, we need to count the number of cells visited by while walking from S to E using any of the cheapest path. In the example case, we would count 5 cells.

This time, I will modify the solution to include noting all paths that have the same minimum cost. I will then create a set of all visited cells and return the count.

def find_cheapest_path_with_visited(grid, start, end, initial_dir=(0, 1)):
    n, m = grid.shape
    clockwise = np.array([[0, 1], [-1, 0]])
    counterclockwise = np.array([[0, -1], [1, 0]])

    # priority queue: (cost, (i, j), direction as tuple, path)
    pq = []
    heapq.heappush(pq, (0, start, tuple(initial_dir), [start]))

    # dictionary to store visited states
    visited = {}

    # store all paths with the cheapest cost
    all_paths = []
    cheapest_cost = None

    while pq:
        cost, (i, j), dir, path = heapq.heappop(pq)

        state = (i, j, dir)

        # if already visited, skip if this path is more expensive
        if state in visited:
            if cost > visited[state]:
                continue
        visited[state] = cost

        # if at the end, store the path
        if (i, j) == end:
            if cheapest_cost is None:
                cheapest_cost = cost
            if cost == cheapest_cost:
                all_paths.append(path)
            continue

        # move forward
        new_i, new_j = i + dir[0], j + dir[1]
        if 0 <= new_i < n and 0 <= new_j < m and grid[new_i, new_j] != 1:
            heapq.heappush(
                pq, (cost + 1, (new_i, new_j), dir, path + [(new_i, new_j)])
            )

        for turn in [clockwise, counterclockwise]:
            new_dir = turn @ np.array(dir)
            new_i, new_j = i + new_dir[0], j + new_dir[1]
            if 0 <= new_i < n and 0 <= new_j < m and grid[new_i, new_j] != 1:
                heapq.heappush(
                    pq,
                    (
                        cost + 1001,
                        (new_i, new_j),
                        tuple(new_dir),
                        path + [(new_i, new_j)],
                    ),
                )

    return len(set(sum(all_paths, [])))

Now, I will assemble the functions into part_two to solve the problem.

def part_two(input: str) -> int:
    if Path(input).is_file():
        with open(input, "r") as f:
            grid = f.read()
    else:
        grid = input

    return find_cheapest_path_with_visited(*parse_input(grid), (0, 1))

Couple of tests to ensure the solution is working as expected:

verify_answer(part_two, example_input_file_1, 45)

✔️ That's right! The answer is 45.

verify_answer(part_two, example_input_file_2, 64)

✔️ That's right! The answer is 64.

Since the tests passed, I will now run the solution on the input data.

%time part_two(input_file)

CPU times: user 4.63 s, sys: 42.6 ms, total: 4.67 s
Wall time: 4.71 s

559

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.