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
step does the following for each simulation step:
- Increment the energy of every octopus
- Find the octopuses that will flash all on their own
- Do all the flashing-handling, including triggering neighbours
- Find which octopuses flashed this generation
- Reset their energies to 0 and clear their 'flashed' flags.
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:
- 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
- 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).
- 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.