Advent of Code 2021 day 11

The key thing in day 11's puzzle was being clear about what was happening so I didn't get caught in an infinite loop.

What I had to ensure was that once an octopus had flashed, it wasn't prompted to flash again by its neighbours going off. That meant I needed to store two bits of information for each octopus: it's energy level and a flag for whether it had flashed.

The octopuses are stored in an IArray of points, much the same as day 9.

type Coord = V2 Int
type Grid = Array Coord Octopus

data Octopus = Octopus Int Bool
  deriving (Ord, Eq, Show)

Simulating the octopuses was done with iterate , generating an infinite series of steps paired with a running total of flashes so far. Part 1 pulls out the requested step from the sequence, part 2 keeps going until every octopus has energy zero.

part1 :: Grid -> Int
part1 grid = snd $ (simulate grid) !! 100

part2 :: Grid -> Int
part2 grid = length $ takeWhile notSyncronised $ simulate grid
  where notSyncronised (g, _) = not $ simultaneous g

simultaneous :: Grid -> Bool
simultaneous grid = all zeroOct $ elems grid
  where zeroOct (Octopus 0 _) = True
        zeroOct _ = False

simulate :: Grid -> [(Grid, Int)]
simulate grid = iterate step (grid, 0)

step :: (Grid, Int) -> (Grid, Int)
step (grid0, flashCount0) = (grid3, flashCount0 + numFlashers)
  where grid1 = increment grid0
        triggers = findFlashers grid1
        grid2 = flash grid1 triggers
        flashers = findFlashers grid2
        numFlashers = length flashers
        grid3 = resetFlashers grid2 flashers

Each step does the following for each simulation step:

1. Increment the energy of every octopus
2. Find the octopuses that will flash all on their own
3. Do all the flashing-handling, including triggering neighbours
4. Find which octopuses flashed this generation
5. Reset their energies to 0 and clear their 'flashed' flags.

The flash function is where the bulk of the problem lies. It gets fed an agenda of octopuses where we need to handle each one's flash and its after-effects. Note that not every octopus in the agenda need flash, but we need to check what happens to it.

When we get an octopus in the agenda, there are three cases:

1. This octopus has already flashed and we've handled its effects. In this case, we just move on to the next octopus in the agenda
2. This octopus doesn't have enough energy to flash. In this case, we again move on (an octopus may be added to the agenda more than once, if multiple neighbours flash).
3. This octopus is ready to pop and we need to handle it.

In this third case, we set the octopus's flashed flag, increment the energy of every neighbour, and add all those neighbours to the agenda.

flash :: Grid -> [Coord] -> Grid
flash grid [] = grid
flash grid (here:agenda) 
  -- already flashed, so ignore
  | flashed == True = flash grid agenda
  -- not enough energy to flash, so ignore
  | energy <= 9 = flash grid agenda
  | otherwise = flash grid'' agenda'
  where Octopus energy flashed = grid ! here
        nbrs = neighbours grid here
        -- set this as flashed
        octopus' = Octopus energy True
        grid' = grid // [(here, octopus')]
        -- add negighbours to agenda
        agenda' = nbrs ++ agenda
        -- increment neighbours
        grid'' = incrementSome grid' nbrs

This process will terminate as we only ever set the flag, and ignore octopuses with the flag set. Eventually, we'll run out of octopuses to process. It's only after we've counted the number of flashes that we reset all the octopuses to having zero energy with cleared flags.

It also doesn't matter how high an octopus's energy gets: we only care if it's above 9. That allows us to handle the case where an octopus has multiple neighbours going off.

Code

You can get the code from my locally-hosed Git repo, or from Gitlab.