Day eleven of AoC 2021 (available at https://adventofcode.com/2021/day/11) introduces us to bioluminescent octopuses (octopi? octopodes?) in a cavern. Each octopus has an energy level from 0 to 9, and when it exceeds 9, it flashes — increasing all eight neighbors' energy by one.
The cascading nature is the interesting part: if a neighbor's energy goes above 9 from a flash, it also flashes, potentially triggering more flashes. But each octopus can only flash once per step.
Parsing the Input
The input is a 10×10 grid of single digits:
const processInput = async (day: number) => {
const input = await readInputLines(day);
const lines = input.map(line => line.split("").map(char => parseInt(char, 10)));
return lines;
};
The Cascading Flash Problem
The tricky part is handling the cascade correctly:
- Increment all energy levels by 1
- Any octopus with energy > 9 flashes
- Flashing increases all 8 neighbors
- Neighbors that exceed 9 also flash
- Each octopus can only flash once per step
- After all flashes, reset flashed octopuses to 0
The "only flash once" constraint is critical. If octopus A flashes and triggers B, then B flashes and would trigger A again — A shouldn't flash twice.
The Padding Trick (Again)
Just like Day 9, I pad the grid to avoid boundary checks. A 10×10 grid becomes 12×12, with zeros around the border:
const executeStep = (grid: number[][]): [number[][], number] => {
const fillValue = 0;
const expanded = [
Array(grid[0].length + 2).fill(fillValue),
...grid.map(row => [fillValue, ...row, fillValue]),
Array(grid[0].length + 2).fill(fillValue),
];
// ...
};
Why is zero safe for the border? Corner cells have only 3 real neighbors, edge cells have 5. Even if all neighbors flash, the border cell reaches at most 5 — never exceeding 9. And we recreate the border each step anyway.
The Sentinel Value Trick
Here's the clever part: when an octopus flashes, I set its energy to -100 instead of 0. Why?
const fulls = [];
let flashes = 0;
// First pass: increment everything, find initial flashers
for (let rindex = 1; rindex < expanded.length - 1; rindex++) {
const row = expanded[rindex];
for (let cindex = 1; cindex < row.length - 1; cindex++) {
row[cindex] += 1;
if (row[cindex] > 9) {
fulls.push({x: rindex, y: cindex});
}
}
}
// Process cascading flashes
while (fulls.length > 0) {
const {x, y} = fulls.shift();
if (expanded[x][y] < 0) {
continue; // Already flashed
}
expanded[x][y] = -100; // Mark as flashed
flashes += 1;
// Increase all 8 neighbors and queue if they exceed 9
expanded[x-1][y] += 1;
if (expanded[x-1][y] > 9) {
fulls.push({x: x-1, y: y});
}
expanded[x+1][y] += 1;
if (expanded[x+1][y] > 9) {
fulls.push({x: x+1, y: y});
}
// ... (6 more neighbors)
}
The -100 sentinel serves two purposes:
- Prevents re-flashing: The
if (expanded[x][y] < 0) continuecheck skips already-flashed octopuses - Survives multiple triggers: An octopus can be added to the queue up to 8 times (once per neighbor). Even if triggered 8 times, -100 + 8 = -92, still negative.
After processing, reset all negative values to zero:
for (let rindex = 1; rindex < expanded.length - 1; rindex++) {
const row = expanded[rindex];
for (let cindex = 1; cindex < row.length - 1; cindex++) {
if (row[cindex] < 0)
row[cindex] = 0;
}
}
The Eight Neighbors
Yes, the code explicitly handles all 8 neighbors. It's verbose but clear:
expanded[x-1][y] += 1; // top
expanded[x+1][y] += 1; // bottom
expanded[x][y-1] += 1; // left
expanded[x][y+1] += 1; // right
expanded[x-1][y-1] += 1; // top-left
expanded[x+1][y-1] += 1; // bottom-left
expanded[x-1][y+1] += 1; // top-right
expanded[x+1][y+1] += 1; // bottom-right
Could use nested loops from -1 to +1, but it wouldn't be any prettier. Sometimes explicit is better than clever.
Part One: Counting Flashes
Run 100 steps, sum all flashes:
const partOne = (input: number[][], debug: boolean) => {
let grid = input;
let flashes = 0;
let totalFlashes = 0;
for (let index = 0; index < 100; index++) {
[grid, flashes] = executeStep(grid);
totalFlashes += flashes;
}
return totalFlashes;
};
The destructuring assignment [grid, flashes] = executeStep(grid) unpacks the tuple returned by executeStep.
Part Two: Synchronization
I suspected this was coming: find the first step where all 100 octopuses flash simultaneously. When that happens, all energy levels are zero.
const partTwo = (input: number[][], debug: boolean) => {
let grid = input;
let flashes = 0;
let index = 0;
while (true) {
[grid, flashes] = executeStep(grid);
index += 1;
const gridSum = grid.reduce((acc, row) => acc + row.reduce((acc, cell) => acc + cell, 0), 0);
if (gridSum === 0) {
break;
}
}
return index;
};
The check is elegant: if the sum of all cells is zero, every octopus is at zero, meaning they all just flashed. A nested reduce computes the sum.
Performance
Part one runs in about 18ms, part two in about 24ms. The example synchronizes at step 195; my input synchronized at step 354.
I noted in the video that this could be problematic if the synchronization took billions of steps — but the puzzle designers are kind. The inputs are chosen to converge reasonably quickly.
A Bug I Almost Made
In my first attempt, I accidentally referenced the original grid variable instead of expanded in the processing loop. TypeScript caught it immediately when I renamed the variable — the undeclared reference became a compile error. TypeScript to the rescue.
Takeaways
Sentinel values prevent re-processing: Using -100 instead of 0 for flashed octopuses elegantly handles the "flash once per step" constraint.
Padding matrices generalizes well: This is the third time (days 5, 9, 11) this pattern has been useful. Worth having in your toolkit.
Tuples for multiple return values: TypeScript's tuple destructuring makes it clean to return both the new grid and the flash count.
Sum-to-zero is a clever sync check: Instead of checking 100 individual cells, sum them. Zero sum means all zeros.
Trust the puzzle designers: The synchronization could theoretically take forever, but AoC puzzles are designed to be solvable. Don't over-engineer for edge cases that won't appear.
The full solution is available in the repository.