Advent of Code 2025 - Day 4: Printing Department

2025-12-04 942 words 5 minutes

Contents

Day 4 brought us back to grid problems. The task involved identifying paper rolls on a grid that forklifts could access, where accessibility is determined by how many neighboring rolls surround each position.

Part 1: Finding Accessible Rolls

Grids are back, and so is my helper library fred.py. The problem is straightforward: count how many paper rolls (@) have fewer than 4 neighboring rolls in the 8 adjacent positions (including diagonals).

The brute force approach works perfectly here:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


def part1():
    grid = toGrid(input_f)
    directions = ['up','down','left','right','up-left','up-right','down-left','down-right']
    score = 0

    for ydx, y in enumerate(grid):
        for xdx, x in enumerate(y):
            if get_value_in_direction(grid, (xdx, ydx)) == '@':
                limit = 0
                for d in directions:
                    val = get_value_in_direction(grid, (xdx, ydx), d)
                    if val == '@':
                        limit += 1
                if limit < 4:
                    score += 1
    return score

Loop through every position, check all 8 neighbors, count the ones with rolls. If fewer than 4 neighbors have rolls, this position is accessible.

First try!

Part 2: Cascade Removal

Part 2 was easier than expected. Once you remove accessible rolls, new rolls might become accessible. Keep removing until no more rolls can be removed.

The Naive Approach

My first implementation used copy.deepcopy() to create a snapshot of the grid, removed all accessible rolls in one pass, then repeated:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


def part2(): 
    grid = toGrid(input_f)
    directions = ['up','down','left','right','up-left','up-right','down-left','down-right']
    score = 0
    prev_score = 1  # Set to 1 to avoid exiting instantly
    
    while score != prev_score:
        prev_score = score
        new_grid = copy.deepcopy(grid)  # Snapshot to avoid mid-iteration changes
        
        for ydx, y in enumerate(grid):
            for xdx, x in enumerate(y):
                if get_value_in_direction(grid, (xdx, ydx)) == '@':
                    limit = 0
                    for d in directions:
                        val = get_value_in_direction(grid, (xdx, ydx), d)
                        if val == '@':
                            limit += 1
                    if limit < 4:
                        score += 1
                        new_grid[xdx][ydx] = 'X'
        
        grid = copy.deepcopy(new_grid)
    
    return score

This works. It gave the right answer, but it took 21,146ms - over 21 seconds. On the example it was fine, but the 135x135 input grid made the repeated full-grid scans painful.

The Optimized Approach

The problem with the naive solution is checking every position on every iteration. Most positions don’t change between passes. Why not track only the positions that matter?

The key insight: use a queue. Add all initially accessible rolls to the queue, then:

Pop a roll from the queue
Remove it (increment count)
Check its neighbors - if removing this roll made any neighbor accessible, add that neighbor to the queue
Repeat until queue is empty

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


def part2_optimized(): 
    grid = toGrid(input_f)
    queue = []
    score = 0
    
    offsets = {
        'up': (-1, 0), 'down': (1, 0),
        'left': (0, -1), 'right': (0, 1),
        'up-left': (-1, -1), 'up-right': (-1, 1),
        'down-left': (1, -1), 'down-right': (1, 1)
    }
    
    # Find all initially accessible rolls
    for ydx, y in enumerate(grid):
        for xdx, x in enumerate(y):
            values, center = get_values_in_dir(grid, (xdx, ydx))
            if center == '@' and sum(v == '@' for v in values.values()) < 4:
                queue.append((xdx, ydx))
    
    # Process queue
    while len(queue) > 0:
        (x, y) = queue.pop()
        grid[x][y] = '.'
        score += 1
        
        neighbors, center = get_values_in_dir(grid, (x, y))
        
        for key, value in neighbors.items():
            if value == '@':
                pos = addTuples((x, y), offsets[key])
                values, center = get_values_in_dir(grid, pos)
                if sum(value == '@' for value in values.values()) < 4:
                    if pos not in queue:
                        queue.append(pos)
    
    return score

The helper function get_values_in_dir() returns all 8 neighbors and the center value:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


def get_values_in_dir(grid: list, position: set):
    values = {}
    x, y = position
    
    offsets = {
        'up': (-1, 0), 'down': (1, 0),
        'left': (0, -1), 'right': (0, 1),
        'up-left': (-1, -1), 'up-right': (-1, 1),
        'down-left': (1, -1), 'down-right': (1, 1)
    }
    
    for key, value in offsets.items():
        dx, dy = value
        new_x, new_y = x + dx, y + dy
        if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[new_x]):
            values[key] = grid[new_x][new_y]
    
    return values, grid[x][y]

Results:

Optimized: 367ms
Naive: 21,146ms

That’s a 57x speedup. Instead of scanning the entire 135x135 grid repeatedly, we only check positions that could have changed.

Performance Analysis

For a 135x135 grid, the naive approach does:

Full grid scan: 135 x 135 = 18,225 checks per iteration
43 iterations until convergence, for my input
Total: ~893,000 checks

The optimized approach:

One initial scan: 18,225 checks
Queue processing: only checks positions that become accessible (8,890 total)
Each removal checks at most 8 neighbors
Total: ~18,225 + (8,890 x 8) = ~89,000 checks

If the grid were larger, the naive approach would scale quadratically with grid size, while the optimized approach scales with the number of removable rolls.

The Lesson

This is a classic BFS/queue problem disguised as a grid simulation. The naive “keep scanning until nothing changes” approach works but misses the structure of the problem. Once you recognize that accessibility changes propagate locally (only to neighbors of removed rolls), the queue-based solution becomes obvious.

The helper library paid off today. Functions like toGrid(), get_value_in_direction(), and addTuples() made the grid manipulation clean. Building up these utilities over previous years of Advent of Code makes later problems faster to solve.

Eight stars total. Both parts solved on first try, then optimized for fun.