Advent of Code 2021 - Day 6

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Once we strip this of the lanternfish, we have an array. Each element is an int which decreases by 1 at each step. If one element would decrease below 0, a new one with a value of 8 is added at the end of the array, and the element that would pass below 0 resets to 6. The initial values in the array are the puzzle input.

Reading the initial array is trivial (strip, split on comma, cast each element to int).

Part 1

How many elements will there be in the array after 80 steps? We will try the simple solution of directly simulating the process as described. Probably enough for this part, and not for part 2, but we don't know if that's the case, so let's avoid premature optimization.

The simulation of a step is straightforward: run along the array; if an element is 0, set it to 6 and add a new element of value 8 at the end; if it's other value, just decrement it by one. Since we will be modifying the array as we traverse it, we loop over the indices with the initial length, so that we do not go into the elements newly added at this step.

Rinse and repeat 80 times.

Part 2

The direct simulation will not do for 256 steps with the hinted exponential growth. We have to get clever. Maybe it's the fish, but this smells of recursion.

For each element, we can try to calculate the size of the population it will spawn in the remaining time. At first we have a population of one (the item itself). We decrease the remining time by the initial value of the element (the steps needed to reach 0), and enter the loop of spawning. The loop ends when there is no remaining time, which can be even before it is entered (if the initial value is greater than the remaining time). This is the base case of the recursion, where no recursive call is made . Inside the loop, we add the population of the newly spawned item: this is the recursive call, using the current remaining time, and an initial value of 9 (starting from eight down to, and including, zero). We keep adding population of new elements after removing 7 steps from the remaining time, and the recursion keeps track of all the details for us.

Since there can be many recursive calls inside each calculation, and many number will repeat even in the initial step, we could calculate the population for each value 0-6, and apply that to the initial array. Instead, we will just call the function on each element and adding them up, which is easier to understand. To avoid repeating calculations, and probably even beyond the initial values, we just cache the recursive function.