Printing Department

Part 1

Another day, another grid puzzle. I was wondering how early we’d see one this year.

I’ll be breaking out the grids module I introduced on 2023 Day 10 for this; it has a parse_grid function which takes a list of rows and returns a mapping between grid points and their tiles.

from collections.abc import Callable, Iterable

type GridPoint = tuple[int, int]
type Grid[Item] = dict[GridPoint, Item]

def parse_grid[Item](
        raw_grid: list[str],
        item_factory: Callable[[str], Item] = str,
        *,
        ignore_chars: Iterable[str] = "",
) -> Grid[Item]:
    result: Grid[Item] = {}
    ignore = set(ignore_chars)
    for row, line in enumerate(raw_grid):
        for col, char in enumerate(line):
            if char in ignore:
                continue
            result[row, col] = item_factory(char)
    return result

I gave this function an ignore_chars parameter, so that any tiles with certain characters in them don’t appear in the final grid. We’re only focusing on the tiles with paper rolls on them, so we can ignore the floor tiles (.). Also, we only care about the locations of the paper tiles (the characters are all the same), so I take the keys of the resulting mapping and put them in a set.

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        rolls = set(parse_grid(self.input, ignore_chars=".").keys())
        ...

My grids module also has a neighbors function which iterates through the neighbors of a grid point. Take a look at the code of the grids module if you want to see how it works, but the basic thing to know is that neighbors(point, num_directions=8) will yield all 8 neighbors of point — up, down, left, right, and the four diagonal directions.

We can use this to write a function to check whether a point on the floor is accessible. neighbors doesn’t check for us whether the points it returns are in the grid, so we have to do that explicitly. So we can easily count a point’s neighboring paper rolls that are in the set of all rolls, and we’ll want to return whether or not this count is less than 4.

def is_accessible(rolls: set[GridPoint], point: GridPoint) -> bool:
    num_neighbors = sum(
        1
        for n in neighbors(point, num_directions=8)
        if n in rolls
    )
    return num_neighbors < 4

With this function in hand, we can use it to count the number of accessible paper rolls.

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        rolls = set(parse_grid(self.input, ignore_chars=".").keys())
        return sum(is_accessible(rolls, point) for point in rolls)

Part 2

Now that we know which paper rolls are accessible, we want to actually remove them. And not just once; we want to remove the paper rolls until we can’t anymore. This isn’t too bad; we just need to remove these paper rolls in a loop, and keep track of a running total of removed paper rolls.

Firstly, we need to find the locations of every accessible paper roll, and immediately break out of the loop if there are none.

...

class Solution(StrSplitSolution):
    def part_2(self) -> int:
        rolls = set(parse_grid(self.input, ignore_chars=".").keys())

        total = 0
        while True:
            accessible_points = {
                point
                for point in rolls
                if is_accessible(rolls, point)
            }
            # Loop until no more rolls are accessible
            if not accessible_points:
                break
            ...
        ...

Then we need to tally up those accessible paper rolls, and remove them from the set of all rolls. (This is why I made accessible_points a set; I can use -= to remove those points from the rolls set!)

...

class Solution(StrSplitSolution):
    def part_2(self) -> int:
        ...
        while True:
            ...
            total += len(accessible_points)
            rolls -= accessible_points

        return total

Finally, we return our running total.

This was surprisingly easy for an AoC grid puzzle… but I’ll take it!