We are building a lanternfish simulator. Each lanternfish is a little discrete automaton which reproduces under certain conditions. We have a whole collection of them, and each “day” is a step for all the lanternfish. At the moment, the only thing that characterizes a fish is its “internal timer”, a natural number between 0 and 8 which tells us how many days we have until the fish reproduces:
type Fish = ℕ
school_day : [Fish] → [Fish]
school_day steps a list of fish (i.e. their counters), adding any newly-spawned ones. Since an individual fish can reproduce, the day function takes a single fish to either one or two fish (“chain” reproductions can’t occur, since new lanternfish start at the maximum timer count). For convenience, we use a list instead of a sum:
day : Fish → [Fish]
We then define
school_day = concat ∘ List day
Enthusiasts will recognize the list monad; we’ll remember this detail for when things get more complicated in Part 2. We want to be able to run our simulation for a given number of days; this is a classic function-power application,
run_days : ℕ → [Fish] → [Fish]
run_days n = power n school_day
where power n f = fⁿ.
All that remains is to write day, which is just a matter of transcribing the informal semantics we’re given.
day 0 = [6, 8] -- reset, spawn
day (Succ n) = [n]
The population size after 80 steps is given by
length ∘ run_days 80
Executable Haskell implementation
Rather than giving us a more interesting system to simulate, Wastl has decided to try to melt our hardware. I’m disappointed, but it did give an opportunity to think about how to represent this simple-but-enormous situation.
Running the simulation of even the five-fish example for 256 days will give us billions of fish, so we clearly can’t simulate the school in O(n) (in current population) space with existing computers. Instead, we can simply describe the system by a count of the fish at each timer stage, since they have no other properties and we’re only interested in population size.
type School = [ℕ]
(Treating a list as a 9-tuple, in this case.) The initial state of the example would be, for example, [0, 1, 1, 2, 3, 0, 0, 0, 0]. school_day is then:
school_day : School → School
school_day [z, o, tw, th, fr, fv, sx, sv, e] =
[o, tw, th, fr, fv, sx, sv + z, e, z]
Ungainly though it is, this encodes in a single expression the same rules for the simulation as the previous program’s day, etc. functions. On each day, the population of fish at 0 (given by z) first drops to zero, the same number of fish “come into being” at 6 and 8, then the existing populations “shift down” (“ones” become “zeros”, and so on).
This allows us to describe the system in space independent of its size. We have to convert the puzzle input (lists of fish-counters) to this population-count form; this is a simple but, again, ungainly fold, specified by
pop_count ns = [count (== 0) ns, …, count (== 8) ns]
This can be calculated with the banana split theorem, but the details are left to the hard-nosed (see my discussion of Day 3). It’s pretty easy to see how it works, I think.
The solution is then given by:
sum ∘ power school_day 256 ∘ pop_count