Advent of Code 2025 - Day 4: Paper Roll Removal

#adventofcode #rust #algorithms #programming

Day 4 was about helping elves clear paper rolls so forklifts could break through a wall. The twist? Forklifts can only grab rolls with fewer than 4 neighbors.

The Problem

Given a grid of paper rolls (@) and empty spaces (.):

..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.

Part 1: Count rolls that have fewer than 4 neighbors (checking all 8 surrounding cells).

Part 2: Remove accessible rolls. Once removed, previously blocked rolls might become accessible. Continue until nothing remains to be removed.

Part 1: Counting Accessible Rolls

I parsed the grid (. = 0, @ = 1) and counted neighbors for each roll. The only trick was keeping the 8 direction checks clean:

const DIRECTIONS: [(i32, i32); 8] = [
    (1, 0), (0, 1), (1, 1), (-1, 0),
    (0, -1), (-1, -1), (-1, 1), (1, -1),
];

fn liftable_roll_papers(grid: &Vec<Vec<i32>>) -> i32 {
    let n = grid.len() as i32;
    let m = grid[0].len() as i32;
    let mut liftable = 0;

    for x in 0..n {
        for y in 0..m {
            if grid[x as usize][y as usize] == 1 {
                let mut rolls = 0;
                for direction in DIRECTIONS {
                    let x_new = x + direction.0;
                    let y_new = y + direction.1;
                    if x_new >= 0 && x_new < n && y_new >= 0 && y_new < m {
                        if grid[x_new as usize][y_new as usize] == 1 {
                            rolls += 1;
                        }
                    }
                }
                if rolls < 4 {
                    liftable += 1;
                }
            }
        }
    }
    liftable
}

Loop through the grid, check all 8 neighbors, and count if there are fewer than 4. Nothing fancy.

Example

For the sample grid, rolls at the edges or in sparse areas have fewer neighbors:

..xx.xx@x.   <- These x marks show accessible rolls
x@@.@.@.@@
@@@@@.x.@@
@.@@@@..@.
x@.@@@@.@x
.@@@@@@@.@
.@.@.@.@@@
x.@@@.@@@@
.@@@@@@@@.
x.x.@@@.x.

Part 2: The Chain Reaction

This is where it got interesting. Removing rolls creates a domino effect; rolls that were surrounded might suddenly become accessible.

I took the straightforward approach: scan the entire grid, remove what I could, and repeat until no changes were made.

fn removable_roll_papers(grid: &mut Vec<Vec<i32>>) -> i32 {
    let n = grid.len() as i32;
    let m = grid[0].len() as i32;
    let mut removed = -1;
    let mut total_removed = 0;

    while removed != 0 {
        removed = 0;
        for x in 0..n {
            for y in 0..m {
                if grid[x as usize][y as usize] == 1 {
                    let mut rolls = 0;
                    for direction in DIRECTIONS {
                        let x_new = x + direction.0;
                        let y_new = y + direction.1;
                        if x_new >= 0 && x_new < n && y_new >= 0 && y_new < m {
                            if grid[x_new as usize][y_new as usize] == 1 {
                                rolls += 1;
                            }
                        }
                    }
                    if rolls < 4 {
                        grid[x as usize][y as usize] = 0;
                        removed += 1;
                    }
                }
            }
        }
        total_removed += removed;
    }
    total_removed
}

The loop tracks removed each pass. When it hits zero, we're done.

How It Works

Starting with the same example grid:

Pass 1: Remove 13 rolls (the initially accessible ones)

..xx.xx@x.
x@@.@.@.@@
@@@@@.x.@@
@.@@@@..@.
x@.@@@@.@x
.@@@@@@@.@
.@.@.@.@@@
x.@@@.@@@@
.@@@@@@@@.
x.x.@@@.x.

Pass 2: More rolls become accessible as their neighbors disappear, remove 12 more

.......x..
.@@.x.x.@x
x@@@@...@@
x.@@@@..x.
.@.@@@@.x.
.x@@@@@@.x
.x.@.@.@@@
..@@@.@@@@
.x@@@@@@@.
....@@@...

Continue until nothing changes.

Why This Works

Could I have used a queue to track "maybe accessible" cells? Sure. Could I have been smarter about which cells to recheck? Probably.

But here's the thing: the grid isn't massive, and the number of passes needed is small. Rolls get removed in waves, and the whole thing converges fast. The simple "scan everything until stable" approach was easier to write and easier to debug than trying to be clever.

I mutated the grid in-place because tracking a separate "removed" set felt unnecessary. The grid changes, the code reflects that. Done.