Advent of Code 2021 - Day 11Dumbo Octopus

| Problem statement | Source code | Tags: BFS/DFS

Part 1

We just need to take care to not double-count flashes in a single step. For each new flash, it should affect its neighbors, which may cause more flashes. This is still a flood fill kind of problem, so I still use DFS. I have a stack of flashers to process. Each time a new octopus flashes, we add it to the stack. When processing a flasher, we increase the energy level of its neighbors, and new flashers are added to the stack. Continue until there are no more flashers to process.

function step(grid: number[][]): number[][] {
  const newGrid: number[][] = grid.map((row) => row.slice());
  const flashers: [number, number][] = [];
  for (let x = 0; x < grid.length; x++) {
    for (let y = 0; y < grid[0].length; y++) {
      newGrid[x][y] = (newGrid[x][y] + 1) % 10;
      if (newGrid[x][y] === 0) {
        flashers.push([x, y]);
      }
    }
  }
  while (flashers.length > 0) {
    const [fx, fy] = flashers.pop()!;
    for (const [nx, ny] of neighbors(fx, fy, grid.length, grid[0].length)) {
      if (newGrid[nx][ny] !== 0) {
        newGrid[nx][ny] = (newGrid[nx][ny] + 1) % 10;
        if (newGrid[nx][ny] === 0) {
          flashers.push([nx, ny]);
        }
      }
    }
  }
  return newGrid;
}

Part 2

Given the step function from part 1, we can just keep stepping until all octopuses flash simultaneously, which is when all energy levels are 0.