Page Contents
- Why Naive Grid Loops Collapse in Part 2
- Simultaneous Grid Evolution
- The
CounterNeighbour-Convolution Trick for Sparse N-Dimensional Grids - Infinite Grids with Alternating Void Polarity
- Cascading Flash Waves and Multi-Phase Automata
- AoC Examples
Why Naive Grid Loops Collapse in Part 2
Cellular automata puzzles start out deceptively cosy. You parse a neat little 2D map of # and ., check each cell’s eight neighbours, and update a grid.
Then Part 2 pulls the rug out from under your array:
- The universe grows a fourth dimension (2020 Day 17), turning a modest cube into an expanding 4D hypercube where an unoptimised nested loop easily leaves you grabbing a coffee while Python chews through millions of dead empty coordinates.
- An infinite image toggles its entire background from dark to blindingly lit on every odd step (2021 Day 20), breaking any sparse solver that assumes everything outside the bounding box stays
.. - Sparse agents scatter outward across an unbounded grove (2022 Day 23) until nobody has a neighbour left within reach.
“Can’t I just allocate a bigger NumPy array and pad the edges?” “Sure — until a puzzle adds a 4th dimension, goes unbounded, or wastes 99% of your runtime scanning empty space.”
The clean architectural fix rests on two habits: strict double-buffering (always read generation t while writing generation t + 1) and sparse coordinate sets paired with collections.Counter so your simulation only ever touches active cells and their immediate neighbourhood.
Simultaneous Grid Evolution
The golden invariant of every cellular automaton is simultaneous state transition: every cell in generation t + 1 depends strictly on generation t. Mutating a list-of-lists or Grid in place breaks that invariant mid-loop — top-left updates silently bleed into bottom-right neighbour counts during the same step.
Before writing a single loop, decide whether your puzzle wants a dense Grid (from aoc_common) or a sparse set[tuple[int, ...]]:
| Representation | Best Fit | Examples | Why It Wins |
|---|---|---|---|
Dense Grid[T] |
Fixed rectangular arena where every cell holds rich state (energy levels 0..9, walls, floors, seats) |
2021 Day 11, 2020 Day 11 | Built-in bounds checks (neighbours_of) and O(1) coordinate indexing |
Sparse set[Coord] |
Unbounded space, 3D/4D coordinates, sparse moving agents, binary active/inactive cells | 2015 Day 18, 2020 Day 17, 2022 Day 23 | Zero memory wasted on empty void; dimension-agnostic tuple coordinates |
(Even with dense grids, build a fresh snapshot or separate flashed tracking set rather than overwriting generation t while still reading it.)
The Counter Neighbour-Convolution Trick for Sparse N-Dimensional Grids
Back in 2020, my first Conway Cubes implementation checked every active cell’s neighbours, then re-checked their neighbours using repeated set intersections. It worked — yet inspecting overlapping inactive regions repeatedly wastes huge amounts of work.
Flipping the direction of work is much cleaner. Instead of asking “how many live neighbours does every candidate cell have?”, let every active cell emit +1 to each of its 3^d - 1 neighbours inside a collections.Counter:

Look closely at the L-tromino example above:
- On the left, each of the three active cells emits
+1into its eight surrounding cells viaCounter. - On the right, the three original live cells (gold) each tally a neighbour count of
2, so all three survive. - Meanwhile, the single inactive corner cell highlighted in teal collects a count of
3and activates, turning the L-tromino into a stable 2x2 block in a single pass. Every empty cell across the rest of the infinite plane collects0votes and is never even instantiated!
Better yet, itertools.product((-1, 0, 1), repeat=dimensions) generates all neighbour offsets for any number of dimensions (2D, 3D, 4D, or higher). Using a PEP 695 type Coord = tuple[int, ...] alias gives us one clean, dimension-agnostic function:
from collections import Counter
from itertools import product
type Coord = tuple[int, ...]
def step_conway(active: set[Coord], dimensions: int) -> set[Coord]:
"""Advance an N-dimensional Conway grid by one simultaneous generation."""
offsets = [delta for delta in product((-1, 0, 1), repeat=dimensions) if any(delta)]
counts: Counter[Coord] = Counter(
tuple(c + d for c, d in zip(cell, delta, strict=True))
for cell in active
for delta in offsets
)
return {
cell
for cell, n in counts.items()
if n == 3 or (n == 2 and cell in active)
}
def parse_sparse(lines: list[str], dimensions: int) -> set[Coord]:
"""Convert 2D ASCII lines into sparse N-dimensional coordinates."""
pad = (0,) * (dimensions - 2)
return {
(x, y, *pad)
for y, row in enumerate(lines)
for x, ch in enumerate(row)
if ch == "#"
}
# 1. Verify the L-tromino diagram transition in 2D
tromino: set[Coord] = {(1, 1), (1, 2), (2, 2)}
assert step_conway(tromino, dimensions=2) == {(1, 1), (1, 2), (2, 1), (2, 2)}
# 2. Switch from 3D to 4D (2020 Day 17) with zero algorithm changes
sample_cube = [".#.", "..#", "###"]
cubes_3d = parse_sparse(sample_cube, dimensions=3)
for _ in range(6):
cubes_3d = step_conway(cubes_3d, dimensions=3)
assert len(cubes_3d) == 112
cubes_4d = parse_sparse(sample_cube, dimensions=4)
for _ in range(6):
cubes_4d = step_conway(cubes_4d, dimensions=4)
assert len(cubes_4d) == 848

Changing dimensions=2 (as in 2015 Day 18, simply clipping to 0 <= x < width and 0 <= y < height plus OR-ing stuck corners) to dimensions=3 or dimensions=4 (hypercube_v2_only_active.py) takes zero changes to step_conway. That is the payoff of keeping coordinate tuples dimension-agnostic.
Proposal-Collision Sparse Movement with Counter
The exact same Counter trick shines in sparse agent-movement automata like 2022 Day 23 (Unstable Diffusion). Every round splits cleanly into two phases:
- Propose: Each elf checks its 8 neighbours in the
elvesset; if isolated, it stays put. Otherwise, it checks the 4 rotating directional rules (collections.dequerotated by-1each round) and recordsproposals[elf] = target. - Resolve collisions with
Counter: Countdest_counts = Counter(proposals.values()). Only elves whose proposed destination hasdest_counts[target] == 1actually move — anyone colliding stays put!
from collections import Counter, deque
type Point2D = tuple[int, int]
ALL_8_DIRS: tuple[Point2D, ...] = (
(-1, -1), (0, -1), (1, -1),
(-1, 0), (1, 0),
(-1, 1), (0, 1), (1, 1),
)
def simulate_diffusion(lines: list[str], rounds: int) -> int:
"""Simulate sparse proposal-collision movement and return empty tiles in bounding box."""
elves: set[Point2D] = {
(x, y)
for y, row in enumerate(lines)
for x, ch in enumerate(row)
if ch == "#"
}
rules: deque[tuple[tuple[Point2D, ...], Point2D]] = deque([
(((-1, -1), (0, -1), (1, -1)), (0, -1)), # North
(((-1, 1), (0, 1), (1, 1)), (0, 1)), # South
(((-1, -1), (-1, 0), (-1, 1)), (-1, 0)), # West
(((1, -1), (1, 0), (1, 1)), (1, 0)), # East
])
for _ in range(rounds):
proposals: dict[Point2D, Point2D] = {}
for x, y in elves:
if not any((x + dx, y + dy) in elves for dx, dy in ALL_8_DIRS):
continue
for checks, (mx, my) in rules:
if not any((x + cx, y + cy) in elves for cx, cy in checks):
proposals[(x, y)] = (x + mx, y + my)
break
if not proposals:
break
dest_counts = Counter(proposals.values())
elves = {
target if (target := proposals.get(elf)) is not None and dest_counts[target] == 1 else elf
for elf in elves
}
rules.rotate(-1)
xs = [x for x, _ in elves]
ys = [y for _, y in elves]
area = (max(xs) - min(xs) + 1) * (max(ys) - min(ys) + 1)
return area - len(elves)
grove_sample = [
"....#..",
"..###.#",
"#...#.#",
".#...##",
"#.###..",
"##.#.##",
".#..#..",
]
assert simulate_diffusion(grove_sample, rounds=10) == 110
Infinite Grids with Alternating Void Polarity
Sparse sets normally rely on one cosy assumption: the infinite void outside our bounding box is empty and stays empty.
In 2021 Day 20 (Trench Map), each pixel looks at its 3x3 window (9 bits -> index 0..511) into an enhancement lookup table. On the puzzle’s sample input, index 0 (000000000) maps to . and index 511 (111111111) maps to #, so the void stays dark forever. On the real input, index 0 maps to # and index 511 maps to .!
On step 1, every infinite pixel far from your image sees 000000000 -> # and flashes ON. On step 2, every infinite pixel sees 111111111 -> . and flashes OFF again!
The clean pattern is tracking (lit, bounds, void_lit):
litstores all#pixels strictly inside the current finite bounding box(min_x, max_x, min_y, max_y).void_litrecords the uniform polarity (Falsefor.,Truefor#) of every pixel outside those bounds.- On each step, expand the box by
1in every direction, evaluate each cell inside the expanded box (readinglitinside the old bounds andvoid_litoutside them), and flipvoid_lit = algo[511 if void_lit else 0] == "#".
type Point2D = tuple[int, int]
def enhance_step(
lit: set[Point2D],
bounds: tuple[int, int, int, int],
void_lit: bool,
algo: str,
) -> tuple[set[Point2D], tuple[int, int, int, int], bool]:
"""Enhance an infinite 2D pixel grid while tracking toggling void polarity."""
min_x, max_x, min_y, max_y = bounds
new_bounds = (min_x - 1, max_x + 1, min_y - 1, max_y + 1)
new_lit: set[Point2D] = set()
for y in range(new_bounds[2], new_bounds[3] + 1):
for x in range(new_bounds[0], new_bounds[1] + 1):
idx = 0
for dy in (-1, 0, 1):
for dx in (-1, 0, 1):
nx, ny = x + dx, y + dy
if min_x <= nx <= max_x and min_y <= ny <= max_y:
bit = 1 if (nx, ny) in lit else 0
else:
bit = 1 if void_lit else 0
idx = (idx << 1) | bit
if algo[idx] == "#":
new_lit.add((x, y))
next_void_lit = algo[511 if void_lit else 0] == "#"
return new_lit, new_bounds, next_void_lit
toggling_algo = "#" + "." * 510 + "."
tiny_lit: set[Point2D] = {(0, 0)}
tiny_bounds = (0, 0, 0, 0)
tiny_void = False
tiny_lit, tiny_bounds, tiny_void = enhance_step(tiny_lit, tiny_bounds, tiny_void, toggling_algo)
assert tiny_void is True # Infinite dark background flipped ON
tiny_lit, tiny_bounds, tiny_void = enhance_step(tiny_lit, tiny_bounds, tiny_void, toggling_algo)
assert tiny_void is False # Infinite lit background flipped OFF again
assert tiny_lit == {(0, 0)} # Centre cell saw 9 dark neighbours (index 0 -> '#')
Always check assert not void_lit before reporting len(lit) — on odd steps with a toggling lookup rule, the number of lit pixels in the universe is infinite!
Cascading Flash Waves and Multi-Phase Automata
Not every grid automaton fits a single simultaneous sweep. Three recurring variations deserve their own clean idioms:
Intra-Step Queue Cascades
In 2021 Day 11 (Dumbo Octopus), cells gain +1 energy together, then any cell exceeding 9 flashes, boosting all eight neighbours — potentially triggering a chain reaction within the same step, while each octopus may flash at most once per step.
Instead of rescanning the entire grid in a while changed: loop, use a FIFO collections.deque (see LIFO, FIFO, and deques) plus a flashed: set[Point] guard on top of aoc_common.Grid:
from collections import deque
from aoc_common import Grid, Point
def step_octopi(grid: Grid[int]) -> int:
"""Advance octopus energy levels by one step and process BFS-style flash cascades."""
flashed: set[Point] = set()
queue: deque[Point] = deque()
for pt in grid.all_points():
grid[pt] += 1
if grid[pt] > 9:
flashed.add(pt)
queue.append(pt)
while queue:
pt = queue.popleft()
for nbr in grid.neighbours_of(pt, include_diagonals=True):
if nbr not in flashed:
grid[nbr] += 1
if grid[nbr] > 9:
flashed.add(nbr)
queue.append(nbr)
for pt in flashed:
grid[pt] = 0
return len(flashed)
octo_grid = Grid([
[int(c) for c in row]
for row in [
"5483143223",
"2745854711",
"5264556173",
"6141336146",
"6357385478",
"4167524645",
"2176841721",
"6882881134",
"4846848554",
"5283751526",
]
])
assert sum(step_octopi(octo_grid) for _ in range(100)) == 1656
Line-of-Sight Ray Scanning
In 2020 Day 11 (seat_modelling.py), Part 1 checks the eight immediate neighbours around each seat (L/#). Part 2 switches to line-of-sight visibility: floor tiles . are transparent, so each seat looks outward along all eight unit vectors until it hits the grid edge or the first chair.
A clean speed-up when geometry is static: precompute visible_neighbours[seat] once before the simulation loop starts. Chairs never turn into floor, so every subsequent generation simply counts occupied chairs in that precomputed list.
Alternating Directional Substeps
In 2021 Day 25 (Sea Cucumber), two herds migrate on a toroidal wrap-around grid ((x + 1) % width, (y + 1) % height) — first all east-facing cucumbers (>) step simultaneously, and only then do all south-facing cucumbers (v) step simultaneously against the updated snapshot:
type Point2D = tuple[int, int]
def step_cucumbers(
east: set[Point2D],
south: set[Point2D],
width: int,
height: int,
) -> tuple[set[Point2D], set[Point2D], bool]:
"""Run east-then-south toroidal substeps and report whether any herd moved."""
occupied = east | south
next_east: set[Point2D] = set()
moved = False
for x, y in east:
nxt = ((x + 1) % width, y)
if nxt not in occupied:
next_east.add(nxt)
moved = True
else:
next_east.add((x, y))
occupied = next_east | south
next_south: set[Point2D] = set()
for x, y in south:
nxt = (x, (y + 1) % height)
if nxt not in occupied:
next_south.add(nxt)
moved = True
else:
next_south.add((x, y))
return next_east, next_south, moved
cucumber_sample = [
"v...>>.vv>",
".vv>>.vv..",
">>.>v>...v",
">>v>>.>.v.",
"v>v.vv.v..",
">.>>..v...",
".vv..>.>v.",
"v.v..>>v.v",
"....v..v.>",
]
h, w = len(cucumber_sample), len(cucumber_sample[0])
e_herd = {(x, y) for y, row in enumerate(cucumber_sample) for x, ch in enumerate(row) if ch == ">"}
s_herd = {(x, y) for y, row in enumerate(cucumber_sample) for x, ch in enumerate(row) if ch == "v"}
steps = 0
while True:
steps += 1
e_herd, s_herd, did_move = step_cucumbers(e_herd, s_herd, w, h)
if not did_move:
break
assert steps == 58
Representing each herd as a set keeps membership testing O(1), guarantees east moves never collide with stale snapshots, and checks convergence with a single did_move boolean.
AoC Examples
| Puzzle | Automaton Pattern | Key Data Structure | Walkthrough / Code |
|---|---|---|---|
| 2015 Day 18 | Bounded 2D Game of Life + stuck corners | Sparse set[Coord] + Counter |
2015 Day 18 |
| 2020 Day 11 | Adjacent seats -> 8-ray line-of-sight | Static visible neighbour cache + double buffer |
2020 Index / seat_modelling.py |
| 2020 Day 17 | 3D & 4D Conway Cubes | Dimension-agnostic Counter convolution |
2020 Index / hypercube_v2_only_active.py |
| 2021 Day 11 | Dumbo Octopus energy flashes | Grid[int] + deque cascade + flashed set |
2021 Day 11 |
| 2021 Day 20 | Infinite image enhancement | (lit, bounds, void_lit) polarity toggle |
2021 Day 20 |
| 2021 Day 25 | Toroidal east-then-south herds | Two sparse set[Point2D] snapshots |
2021 Day 25 |
| 2022 Day 23 | Unstable Diffusion scattering | Rotating deque rules + Counter collisions |
2022 Day 23 |