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.


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

    Neil Smith

    Read more posts by this author.