Advent of Code 2021, Day 6
Day 6 promises to be an interesting one. While it may be day 7 today, I’m still playing catchup. Solution in the usual place.
What we have is a population of fish. Lanternfish! Lanternfish are pretty fascinating. It’s thought that they make up nearly two thirds of the deep sea biomass. There are so many of them down there that, at first, scientists looking at their sonar readings thought they were reading an entire layer of water or even the seabed itself. They called it the Deep Scattering Layer, and it’s almost all Lanternfish. Untold billions of them.
But for the test data, we’re starting off with five of them and three simple rules: a lanternfish makes another lanternfish every 7 days, presumably via fission; new lanternfish have to wait an extra two days before they start reproducing; and the initial fish start at different points in their cycles.
If we only had the first rule to deal with, this would be trivial. The population would be 2^floor(n/7) after n days. Rule 2 means it’ll be lower than that. Rule 3 means it’ll be slightly higher than the first two would suggest, but probably still lower than the simple rule 1 answer.
The obvious thing to do here, so obvious they use it in the example, is to go stepwise day by day, decrementing each fish’s internal counter until the day it divides and resets, with an independent counter for each fish.
The actual data includes a starting population of 300 and part 1 asks how many there are after 80 days. The naive approach isn’t going to work.
The next most obvious approach would be to have 9 counters, each noting how many fish are in each stage and cycling the fish through each “pool” day by day, adding into the last pool as necessary. That’ll work for part 1, but if past years are any experience, with this sort of puzzle, it’ll ask for an infeasibly long simulation period for part 2. No, we need to cheat.
Importantly, I can still work with the 7-day period. The behaviour of the fish is such that I should still be able to advance by 7 days at a time. But instead of just doubling the number of fish in each pool, I add their number to the pool two indices above it, and then move those that were already in pools 7 and 8 down to 0 and 1 respectively.
That’ll get me from the initial state to day 80 in just 14 simulation steps (11 7-day steps to get to day 77, and then 3 1-day steps), and could get me to day 1000 in 148.
Since these numbers are going to get silly, I’ll need to store them as long integers and might need to make use of one of the specialised big number classes for part 2 depending on how far it wants to take the simulation.
With all this established, I can now write the tests: one to check 1-day steps work correctly, one to test that 7-day steps are equivalent to 7 of those, one to check that it takes the right number of steps when given an arbitrary number, one to check that it correctly sums the population from its pool numbers, and finally one to test the complete part 1 solution.
With all these in place, I also write my step functions. The 1-day step just moves every fish down a pool and duplicates the pool 0 fish (those that will divide today) into pools 6 and 8:
// Move every fish into the next lower pool
System.arraycopy(pool, 1, nextPool, 0, 8);
// Re add the ones that fell out of pool 0 back into pool 6
nextPool[6] += pool[0];
// Add a new fish in the now empty pool 8 for each that was in pool 0
nextPool[8] = pool[0];
// And finally copy it all back into the main pool
System.arraycopy(nextPool, 0, pool, 0, 9);
Notice the use of System.arraycopy. This is an extremely fast function in Java and can be used to move large amounts of data around effectively, though since we’re only using 9 pools the improvement is marginal at best.
The 7-day step is a little more complicated, but not much. Almost all of the pools get numbers that are a sum of two other pools:
// Pools 0 and 1 get their existing populations plus those from 7 and 8 respectively
nextPool[0] = pool[0] + pool[7];
nextPool[1] = pool[0] + pool[8];
// Pools 2–6 keep their original population plus new fish for those two pools down
nextPool[2] = pool[2] + pool[0];
nextPool[3] = pool[3] + pool[1];
nextPool[4] = pool[4] + pool[2];
nextPool[5] = pool[5] + pool[3];
nextPool[6] = pool[6] + pool[4];
// Pools 7 and 8 get new fish only
nextPool[7] = pool[5];
nextPool[8] = pool[6];
// And finally copy it all back into the main pool
System.arraycopy(nextPool, 0, pool, 0, 9);
Most of my tests pass first time, and after I fix the typo that made the 7-step function fail (see that 0 where there should be a 1 on line 3?), it’s all good. This is why TDD is good.
I could’ve done this with three loops and probably avoided that typo, but again, I expect part 2 to involve a large number of simulation steps, and unrolling loops like this is very slightly more efficient.
And finally, I run it with my real data to get my final answer: 390 011.
On to part 2! And yes, it’s the same but with more simulation steps! It wants me to run for… 256 days. That’s less than I expected, and well within my simulator’s capabilities. Run it for the larger number, and get 1 746 710 169 834. Over a trillion fish.
This is probably somewhere around the right number for the actual number of lanternfish in the ocean. Since this is an entirely accurate simulation of fish biology, and we know for a solid fact that the Earth is exactly 256 days old, this seems like the right number!