Day nine of AoC 2021 (available at https://adventofcode.com/2021/day/9) takes us deeper into the caves. We have a height map where smoke flows to the lowest points, and we need to find those local minima.
The input is a grid of single digits (0-9) representing heights.
The Boundary Problem
When checking neighbors in a grid, corners and edges are annoying. A cell in the middle has 4 neighbors; a corner has 2. You end up with ugly boundary checks everywhere:
// Ugly: check if neighbor exists before accessing
if (row > 0 && grid[row-1][col] < current) { ... }
if (col < width-1 && grid[row][col+1] < current) { ... }
My solution: pad the grid with walls.
Parsing with Padding
Surround the input with 9s (the maximum height, effectively walls):
const processInput = async (day: number) => {
const input = await readInputLines(day);
const lines = input.map(line => line.split("").map(n => parseInt(n, 10)));
return lines;
};
Note that the padding happens in the solution functions, not during parsing. This keeps the input clean.
Now every cell has 4 neighbors. The 9s act as walls — no cell is ever lower than them, so they never affect our calculations.
Part One: Finding Low Points
A low point is lower than all four neighbors. We pad with 99 (part one uses a higher value for clarity) and can then start from index 1:
const partOne = (input: number[][], debug: boolean) => {
const expanded = [
Array(input[0].length + 2).fill(99),
...input.map(row => [99, ...row, 99]),
Array(input[0].length + 2).fill(99),
];
let total = 0;
for (let rindex = 1; rindex < expanded.length - 1; rindex++) {
const row = expanded[rindex];
for (let cindex = 1; cindex < row.length - 1; cindex++) {
const cell = row[cindex];
const top = expanded[rindex - 1][cindex];
if (top <= cell) continue;
const left = expanded[rindex][cindex - 1];
if (left <= cell) continue;
const bottom = expanded[rindex + 1][cindex];
if (bottom <= cell) continue;
const right = expanded[rindex][cindex + 1];
if (right <= cell) continue;
total += cell + 1;
}
}
return total;
};
No boundary checks needed — the padding handles it. The early continue statements short-circuit as soon as we find a neighbor that's not higher.
Part Two: Flood Fill
A basin is all cells that flow down to a low point. The puzzle guarantees that 9s act as walls — every basin is distinct, separated by ridges of 9s.
The algorithm: find an unvisited non-wall cell, flood fill from it (counting cells), mark all visited cells as walls.
const partTwo = (input: number[][], debug: boolean) => {
const expanded = [
Array(input[0].length + 2).fill(9),
...input.map(row => [9, ...row, 9]),
Array(input[0].length + 2).fill(9),
];
const basins: number[] = [];
while (true) {
// Find a non-wall cell
let srcx = -1;
let srcy = -1;
for (let rindex = 1; rindex < expanded.length - 1; rindex++) {
const row = expanded[rindex];
for (let cindex = 1; cindex < row.length - 1; cindex++) {
const cell = row[cindex];
if (cell !== 9) {
srcx = rindex;
srcy = cindex;
break;
}
}
if (srcx !== -1) break;
}
if (srcx === -1) break; // No more basins
let basinSize = 0;
const cells = [{x: srcx, y: srcy}];
while (cells.length > 0) {
const {x, y} = cells.shift()!;
const cell = expanded[x][y];
if (cell === 9) continue;
// Enqueue non-wall neighbors
if (expanded[x - 1][y] !== 9) cells.push({x: x - 1, y});
if (expanded[x][y - 1] !== 9) cells.push({x, y: y - 1});
if (expanded[x + 1][y] !== 9) cells.push({x: x + 1, y});
if (expanded[x][y + 1] !== 9) cells.push({x, y: y + 1});
expanded[x][y] = 9; // Mark as visited
basinSize += 1;
}
basins.push(basinSize);
}
basins.sort((a, b) => b - a);
return basins[0] * basins[1] * basins[2];
};
The Double-Counting Bug
My first attempt had a bug: the same cell could be added to the queue multiple times. Consider a cell that's a neighbor to two already-queued cells — it gets queued twice, counted twice.
The fix: check if the cell is already a wall (visited) when dequeuing, not just when enqueuing. If we've already processed it, skip:
if (expanded[row][col] === 9) continue;
This handles duplicates gracefully. We might enqueue a cell 4 times (once from each neighbor), but we only count it once.
Why "Pave Over" Works
Instead of tracking visited cells in a separate data structure, I mutate the grid itself — turning processed cells into 9s (walls). This has a nice property: the flood fill naturally stops at already-processed cells, and the outer loop naturally skips them when searching for the next basin.
It's destructive (we lose the original data), but we don't need it after processing.
Performance
Part one: ~4ms for a 100×100 grid. Simple nested loops.
Part two: ~26ms. The flood fill is efficient, but finding the "first non-wall cell" by scanning from the top-left every time is wasteful. We could optimize by tracking where we left off. But 26ms is fast enough.
The comment in my code:
// Can be optimized by not starting from top-left each time
// but if it's not too slow, don't fix it
Takeaways
Pad grids to avoid boundary checks: Adding a border of "wall" values means every interior cell has all neighbors. Cleaner code, fewer edge cases.
Flood fill is a classic: BFS/DFS to explore connected regions appears constantly in grid problems. Know it cold.
Mutate to mark visited: If you don't need the original data, mutating the grid to mark visited cells is simpler than maintaining a separate visited set.
Check on dequeue, not enqueue: When the same cell can be added to a queue multiple times, filter duplicates when removing, not when adding.
26ms is fast enough: The optimization to continue from the last position would save maybe 12ms. Not worth the added complexity for a one-shot puzzle.
The full solution is available in the repository.