Advent of Code, in Erlang: Day 6

It's fun revisiting the earlier puzzles to write about them after having done the later puzzles. Similarities show up that I hadn't considered at the time. For example, Day 6, which has the same sort of modeling-space growth problem as Day 14.

We start off with a list of "fish spawning" timers. We're supposed to calculate how many fish will exist (the original set, plus spawn, spawn of spawn, etc.) at the end of 80 days.

model_fishA(0, Fish) ->
    Fish;
model_fishA(Days, Fish) ->
    model_fishA(
      Days-1,
      lists:foldl(fun(0, Acc) -> [8, 6 | Acc];
                     (F, Acc) -> [F-1 | Acc]
                  end,
                  [], Fish)).

This can be modeled exactly how the puzzle description demonstrates: as a growing list of fish timers. Once per day, iterate through the list timers. If a timer is at anything other than 0, decrement the timer. If it is at zero, reset the timer to 6, and also store a new one at 8. At the end of the requested number of days, the length of the list is the number of fish.

26 = length(puzzle06:model_fishA(18, ExampleFish)).
5934 = length(puzzle06:model_fishA(80, ExampleFish)).

This even works for the full puzzle input (300 starting fish) for Part 1's 80-day request. But then, the same sort of warning as we see again on Day 14, comes in Part 2. We're supposed to calculate the number of fish after 256 days, and the example should produce 26,984,457,539. Even if I used only one byte per fish, that would be 26 gigabytes of them! The counters are small … I could do two fish per byte, so only 13 gigabytes!

No, we need another way. On Day 14, I used memoization to build a table to store results of calculated expansions, so that I could use them again, instead of recalculating them. That works here too.

model_fishB(Days, Fish) ->
    BDays = [ F-6 || F <- Fish ],
    Table = model_fishB(Days, BDays, []),
    lists:sum([ proplists:get_value(F, Table) || F <- BDays ]).

model_fishB(_, [], Table) ->
    Table;
model_fishB(Days, [Fish|Rest], Table) ->
    case proplists:is_defined(Fish, Table) of
        true ->
            model_fishB(Days, Rest, Table);
        false when Fish >= Days ->
            model_fishB(Days, Rest, [{Fish, 1} | Table]);
        false ->
            Spawn = [ F + 2 %% first spawn delay
                      || F <- lists:seq(Fish+7, Days, 7) ],
            NewTable = model_fishB(Days, Spawn, Table),
            Total = lists:sum([ proplists:get_value(S, NewTable) ||
                                  S <- Spawn ]),
            model_fishB(Days, Rest, [{Fish, Total+1} | NewTable])
    end.

I found it easier to work with fish "birthdays" instead of spawning timers. So I first shift all initial timers back by 6, the period at which an "adult" fish reproduces. Then I start producing a table mapping birthdays to how many fish that a fish born on that day will spawn (plus it's spawn's spawn, etc.) by the requested date. The recursive build goes like this:

1. If there are no more birthdays we need to calculate, we're done - return the table.
2. If we already know the answer for a birthday (it's true that the birthday is_defined in the table), we can ignore it - leave the table alone, and calculate the rest of the birthdays.
3. If we don't know the answer for the birthday, but it's at or after the last day we care about (Fish >= Days), just mark it down for 1 fish in the table, and move on to the rest of the birthdays.
4. If all else fails, calculate the dates on which this fish will Spawn. Run the model for those birthdays, so that they'll show up in the table. When those are ready, sum them up, add 1 for this genesis fish, and store that in the table for this birthday.

This table will have a maximum size of the number of days we need modeled (256 for Part 2), plus the spawning period, to account for fish born before day 0. The spawn counts might be light, but even at 64 bits per count, that's only a little over 2 kilobytes. The answer to the puzzle's question, once the table is built is simply the sum of the fish counts for each birthday in the (shifted) input.

26 = puzzle06:model_fishB(18, ExampleFish).
5934 = puzzle06:model_fishB(80, ExampleFish).
26984457539 = puzzle06:model_fishB(256, ExampleFish).

The ability to calculate the answer at all is what matters here. What's the speed difference anyway?

timer:tc(fun() -> length(puzzle06:solveA()) end).
% {104273,…}
%  ^us    ^no-spoilers
timer:tc(fun() -> puzzle06:solveB() end).
%   {7534,…}
%    ^us  ^no-spoilers

Right. The table-model takes nearly 14x less time to solve 300 fish for 256 days than the list-growing model takes to solve 300 fish for 80 day (7.5ms vs. 104ms). Neat trick.

I think there's probably a bit of calculus one could do to solve the problem directly instead of modeling. Did you do that? Send me your explanation if you did: Twitter (@hobbyist)! Is there yet more efficiency I could have squeezed out of this code, or some way I could have made it clearer? Show me how on Github (beerriot).

Categories: Development AdventOfCode