Advent of code 2021: Day 11
 6 minutes read  1180 wordsAdvent of Code 2021 day 11 felt a little bit like a repeat of Day 9. In both cases, we got a 2dimensional map with single digit values. In case of day 9 it was a height map, this time round we’ve got a 10x10 grid of bioluminescent Octopi. Each of those critters has an energy level that increases each round. Once that level goes past 9, it lets off a flash, which then imparts extra energy into the surrounding 8legged creatures. In a departure from Day 9, this time the diagonals were classed as adjacent.
First task
For the first task, we had to count how many flashes go off after 100 rounds. Again, rather than using a matrix, I opted for a Map that would map a point to the energy level:


Then I looked at implementing a function that would increase every point on the FlashMap
by 1
energy level. First, a helper to define all the neighbours of a given point:


Pretty straightforward! Then I figured that I should split the “energy increase” and the “count how many flashes and reset the counters” into two stages. That would prevent me from double counting flashes, if the energy level increased over 9 multiple times if more than one neighbour flashes.
To start with, I looked at increasing the energy level for a single point:


There’s a lot in two functions (which recursively call each other). So first looking at incOne
:
 The
updateLookupWithKey
method on the haskellMap
looks up the value for they keyp
(the coordinates of the current point), if it finds something it runs the\p f > Just (f+1)
lambda, which returns an increased value which is updated in the map, and the looked up value AND the new map (remember, everything is immutable) are returned as a tuple.  That tuple (looked up value and new map) is then fed to
triggerNeighbours
as well as the pointp
. Using pattern matching, we then check whether the new value is10
 and therefore a flash is triggered. If that’s the case we callincOne
for each of theneighbours
. I find thatfoldl
is very useful here, because it passes thefm
Flash Map along to deal with all of the neighbours. Note, that by usingupdateLookupWithKey
we automatically deal with coordinates at the edge of the map. The lookup will not find anything, which will just return aNothing
and that in turn is covered by thetriggerNeighbours _ (_, fm) = fm
pattern. That just returns thefm
unchanged.
Now that we’ve increased the energy levels for a single point, we can use that function to increase the energy levels in every point:


Again, the foldl
(read as “fold left”) will process each of the points in the map (all the keys
).
Next, we deal with counting the number of flashes and resetting the counter after the all the energy levels have been increased. The flashes can be counted by any points in the map that have a level greater than 9. And then we want to change those points back to 0 at the same time.
Initially I thought, maybe a state monad will be helpful there (and I was looking forward to learning about them!) but
then I discovered the mapAccum
function, which both changes each value of the map as well as allowing to get an
accumulated value. Ideal, for the flash counting and energy level resetting:


The countFlashAndReset'
function (it still feels strange to have '
as part of a symbol, but I kind of like that
mathematical feel of the function notation as it makes it clear that the '
function is just related to the non'
function  but I digress) uses the mapAccum
function and starts with an acc
accumulator value of 0
and then for
every flash, it increases it by one (first value in the tuple) and resets the map value (second value of the tuple).
Now all that was left to do was to bring it all together. First I defined a function for a single iteration:


It combines incAll
, then feeds that into countFlashAndReset
and then just adds the output together. This then allows
us to iterate for n
iterations recursively:


Second part
For the second part of the puzzle, we needed to find out how many iterations need to pass before all flashes go off
at the same time. This meant we’re no longer interested in counting the number of flashes, which means countFlashAndReset
could be replaced with:


And we needed a way of checking whether all the flashes had gone off. This could be done by checking whether all the
values in the FlashMap
were zero:


That can then be called recursively to keep iterating until allZero
was true:


Rest of the solution on GitHub
Conclusion
This puzzle taught me something about the wealth of functions available in haskell and that Maps and Hackage were very very useful resources. I guess I had to wait for my first foray into Monads for another time. After all, how hard can it be, monads are only monoids in the category of endofunctors after all!
Tags functional haskell adventofcodeIf you'd like to find more of my writing, why not follow me on Twitter or Mastodon?