Day 18

We have fallen into RAM of the big North Pole computer. Read the whole story on the official Day 17 of Advent of Code 2024 website.

Here’s a ChatGPT negotiated illustration of the setup:

Setting up

from misc.helper import verify_answer

example_input_file = "../inputs/example_day_18.txt"
input_file = "../inputs/day_18.txt"

Part 1: Escape the falling bits

Another grid problem! We are in a 2D grid where we need to figure out which positions of the grid are free from the falling bytes.

from pathlib import Path
import numpy as np


def parse_input(input, grid_size=7, n_bytes=12):
    if Path(input).exists():
        with open(input) as file:
            input = file.read()

    input = input.strip().split("\n")
    grid = np.zeros((grid_size, grid_size), dtype=int)
    coord = [(int(y), int(x)) for row in input for x, y in [row.split(",")]]

    if n_bytes > len(coord):
        raise ValueError("n_bytes is larger than the number of coordinates")

    if (
        max(coord, key=lambda x: x[0])[0] >= grid_size
        or max(coord, key=lambda x: x[1])[1] >= grid_size
    ):
        raise ValueError("Coordinates are out of bounds of the grid")

    grid[tuple(zip(*coord[:n_bytes]))] = 1
    return grid


parse_input(example_input_file)


def print_grid_as_str(grid):
    # print 0 as ., 1 as # and 2 as O
    match_dict = {0: ".", 1: "#", 2: "O"}
    print("\n".join("".join(match_dict[elem] for elem in row) for row in grid))


print_grid_as_str(parse_input(example_input_file))

...#...
..#..#.
....#..
...#..#
..#..#.
.#..#..
#.#....

Our task is to find the shortest path in the grid from the top left corner to the bottom right corner. We can only move up, down, left, or right, and we can’t move diagonally. We can only move to a position if it is free from the falling bytes. And then we need to report the number of steps we need to take to reach the bottom right corner.

from collections import deque


def find_shortest_path(grid):
    n, m = grid.shape
    start = (0, 0)
    end = (n - 1, m - 1)

    def bfs(grid, start, end):
        queue = deque([(start, [start])])
        visited = set()

        while queue:
            node, path = queue.popleft()
            if node == end:
                return path

            if node in visited:
                continue

            visited.add(node)
            x, y = node

            for dx, dy in (
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ):
                new_x, new_y = x + dx, y + dy
                if (
                    0 <= new_x < n
                    and 0 <= new_y < m
                    and grid[new_x, new_y] != 1
                ):
                    next_node = (new_x, new_y)
                    if next_node not in visited:
                        queue.append((next_node, path + [next_node]))

        return None

    return bfs(grid, start, end)


def part_one(input, grid_size=7, n_bytes=12):
    grid = parse_input(input, grid_size=grid_size, n_bytes=n_bytes)
    path = find_shortest_path(grid)
    return len(path) - 1


verify_answer(part_one, example_input_file, 22)

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

%time part_one(input_file, grid_size=71, n_bytes=1024)

CPU times: user 8.45 ms, sys: 1.14 ms, total: 9.59 ms
Wall time: 9.91 ms

290

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

Part 2: When there is no escape!

Now we need to figure out at what point there is no escape. I’m going to try the simplest approach with just gradually reading in the new bytes and checking if there is a path from the top left corner to the bottom right corner.

def check_if_path_exist(grid):
    n, m = grid.shape
    start = (0, 0)
    end = (n - 1, m - 1)

    def bfs(grid, start, end):
        queue = deque([start])
        visited = set()
        while queue:
            node = queue.popleft()
            if node == end:
                return True

            if node in visited:
                continue

            visited.add(node)
            x, y = node

            for dx, dy in (
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ):
                new_x, new_y = x + dx, y + dy
                if (
                    0 <= new_x < n
                    and 0 <= new_y < m
                    and grid[new_x, new_y] != 1
                ):
                    next_node = (new_x, new_y)
                    if next_node not in visited:
                        queue.append(next_node)

        return None

    return bfs(grid, start, end)

def part_two(input, grid_size=7, first_n_bytes=12):
    grid = parse_input(input, grid_size=grid_size, n_bytes=first_n_bytes)
    if Path(input).exists():
        with open(input, "r") as file:
            coords = file.readlines()
    else:
        coords = input.strip().split("\n")
    n_lines = len(coords)
    new_byte = first_n_bytes + 1
    while new_byte < n_lines:
        coord_str = coords[new_byte].strip()
        coord = [(y, x) for x, y in [map(int, coord_str.split(","))]][0]

        grid[coord] = 1
        if check_if_path_exist(grid):
            new_byte += 1
        else:
            return coord_str


verify_answer(part_two, example_input_file, "6,1")

✔️ That's right! The answer is 6,1.

%time part_two(input_file, grid_size=71, first_n_bytes=1024)

CPU times: user 3.62 s, sys: 14.7 ms, total: 3.64 s
Wall time: 3.67 s

'64,54'

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