Advent of Code: Day 4

Locality and Peeling: How Simple Neighbor Rules Shape Complex Grids

Pen-and-paper: Part I

We have a grid:

• @ = roll of paper

• . = empty

A roll is accessible if it has fewer than 4 rolls in its 8 neighbors (the 8 squares around it, including diagonals).

So for each @:

• Look at the 8 cells around it.

• Count how many are also @.

• If that count < 4, this roll is forklift-accessible.

Then sum over the whole grid.

In symbols:

• Let the grid be map[row][col].

• For a roll at (r, c) with map[r][c] == ‘@’, define:

\(\text{adj(r,c)} = \#\{(dr,dc) \in \{-1,0,1\}^2 \setminus (0,0) \mid map[r+dr][c+dc] = \text{'@'}\}\)

The roll at (r, c) is accessible if adj(r,c) < 4.

Total answer:

\(\text{answer} = \sum_{r,c} [map[r][c] = \text{'@'} \land adj(r,c) < 4]\)

Implementation-wise, that’s just:

• Scan each cell.

• If it is @, run a tiny 3×3 neighbor loop (skip center).

• Count neighbors, check < 4, increment answer.

No graph theory; just local counting.

---

Pen-and-paper: Part II

We still have the same grid:

• @ = roll of paper

• . = empty

A roll is accessible if it has fewer than 4 neighboring rolls among the 8 surrounding cells.

In Part 2, the process is:

1. Find all accessible rolls.

2. Remove them.

3. Recompute which rolls are now accessible.

4. Repeat until no more rolls can be removed.

We’re asked: how many rolls total get removed?

Mental model

Think of each roll @ as a node in a graph. Edges connect neighboring rolls (8 directions).

• Each roll has a neighbor count = number of adjacent rolls.

• A roll is fragile if neighbor_count < 4.

• When we remove a fragile roll, all its neighbors lose 1 from their neighbor count.

• Some of those neighbors might now become fragile too.

We keep peeling off fragile rolls until what remains (if any) are rolls with neighbor_count >= 4. That remaining set is the 4-core of the graph. Total removed:

\(\text{removed} = \text{initial rolls} - \text{rolls remaining in the 4-core}\)

Algorithmically:

1. For every cell (r, c) with @, count its neighbors adj[r][c] (8 directions).

2. Put all rolls with adj[r][c] < 4 into a queue.

3. While the queue is not empty:

   • Pop a roll (r, c):

     • If already removed, skip.

     • Mark it removed; increment removed.

     • For each neighboring roll (nr, nc) not removed:

       • Decrease adj[nr][nc] by 1.

       • If adj[nr][nc] just dropped from 4 to 3 (or in general < 4), push (nr, nc) into the queue.

4. When the queue stabilizes, no more rolls become fragile. removed is the answer.

This approach matches the example given:

You keep stripping “exposed” rolls until the remaining clump is too dense for forklifts to reach any more.

---

Conclusion

Today’s puzzle taught two big ideas: locality¹ and peeling². In Part 1, we judge each roll of paper using a simple local rule: look at the eight spots around it and count how many neighbors it has. If it has fewer than four, a forklift can reach it. This is a classic local constraint problem (think Conway’s Game of Life): a rule that depends only on what’s right next to something.

In Part 2, we have to keep applying that rule over and over. Consequently, when you remove the easy-to-reach rolls, some of their neighbors suddenly become easy to reach too. This becomes a classic computer-science pattern called peeling: keep removing items that meet a simple rule until nothing more can be removed.

Under the hood, this is the same idea used to simplify networks, clean up data graphs, and find the “strong core” of a structure.

1. https://en.wikipedia.org/wiki/Cellular_automaton

2. https://en.wikipedia.org/wiki/Moore_neighborhood