Advent of Code 2024 day 11

As soon as I say the day 11 puzzle, I knew what part 2 would look like. Unlike yesterday, I guessed right. Today was the return of the lanternfish, even though it took me far, far too long to realise that.

Handling stones

The rules of the game are encoded in one function, that takes a stone as input and returns what it turns into.

expandStone :: Int -> [Int]
expandStone 0 = [1]
expandStone n
  | isEvenLen = [read nS1, read nS2]
  | otherwise = [n * 2024]
  where nStr = show n
        nSL = length nStr
        isEvenLen = nSL `mod` 2 == 0
        (nS1, nS2) = splitAt (nSL `div` 2) nStr

Handling all the stones is done by a concatMap, and the whole simulation is done with iterate.

part1 :: [Int] -> Int
part1 = length . (!! 25) . iterate blink 

blink :: [Int] -> [Int]
blink = concatMap expandStone

Handling many stones

That's enough to handle a few generations, but the number of stones almost doubles every generation. For 75 generations, I'd need something else. (I didn't even bother trying the above naïve approach.)

My first thought was to see if there was a repeated substring of stones in the first 25 steps. If so, I could find how long that repeated section was and duplicate it the requisite number of times. Unfortunately, there was no such repeated substring.

Cue lots of staring into space, thinking about things. My thinking eventually settled on the fact that I only care about the number of stones, and the order doesn't matter. I could re-arrange the stones and get the same result: each stone's evolution is independent of all the others. But as I can re-arrange them, I can just count how many stones are of each value.

And that's when I remembered the infamous "lanternfish" puzzle. Of course the lanternfish would make a reappearance in this tenth-anniversary special.

The key to the solution is to have a multiset (or bag) of stones. Each element counts the number of stones of that value. One generation of stone evolution converts a multiset of stones to another multiset of stones.

part2 = MS.size . (!! 75) . iterate blinkMS . MS.fromList

blinkMS :: IntMultiSet -> IntMultiSet
blinkMS = MS.concatMap expandStone 

Code

You can get the code from my locally-hosted Git repo, or from Codeberg.