Advent of Code 2021 - Day 14

This topic is about Day 14 of the Advent of Code 2021.

We have a private leaderboard (shared with users of the elixir forum):

The entry code is:


I like today’s challenge, very similar to day 6, direct solution for part 1 and then “optimized” for part 2:

main(File) ->
    {ok, RawData} = file:read_file(File),
    [TemplateRaw, RulesRaw] = binary:split(RawData, <<"\n\n">>),
    Rules = [ begin
                  [From, To] = binary:split(R, <<" -> ">>),
                  {binary_to_list(From), hd(binary_to_list(To))}
              end || R <- binary:split(RulesRaw, <<"\n">>, [global, trim]) ],
    Template = binary_to_list(TemplateRaw),
    RulesMap = maps:from_list(Rules),
    io:format("part 1: ~p~n", [solve1(Template, RulesMap)]),
    io:format("part 2: ~p~n", [solve2(Template, RulesMap)]).

solve1(Template, Rules) ->
    NewTemplate = grow(Template, Rules, 10),
    Counts = maps:values(freq(NewTemplate)),
    lists:max(Counts) - lists:min(Counts).

grow(Template, _Rules, 0)    -> Template;
grow(Template,  Rules, Step) ->
    grow(grow(Template, Rules), Rules, Step - 1).

grow([A, B|Rest], Rules) ->
    [A, maps:get([A, B], Rules)|grow([B|Rest], Rules)];
grow([B], _) ->

freq(List) ->
    lists:foldl(fun (K, Acc) -> incr_count(K, 1, Acc) end, #{}, List).

incr_count(Key, V, Map) ->
    Map#{Key => maps:get(Key, Map, 0) + V}.

solve2(Template, Rules) ->
    {_, CountMap} = grow_count(Template, Rules, 40),
    Counts = maps:values(CountMap),
    lists:max(Counts) - lists:min(Counts).

init_maps([B], PairMap, CountMap) ->
    {PairMap, incr_count(B, 1, CountMap)};
init_maps([A, B|Rest], PairMap, CountMap) ->
              incr_count([A, B], 1, PairMap),
              incr_count(A,      1, CountMap)).

grow_count(Template, Rules, Steps) ->
    {PairMap, CountMap} = init_maps(Template, #{}, #{}),
    grow_count(PairMap, CountMap, Rules, Steps).

grow_count(PairMap, CountMap, _Rules, 0)    -> {PairMap, CountMap};
grow_count(PairMap, CountMap,  Rules, Step) ->
    {NewPairMap, NewCountMap}
        = maps:fold(fun (K, V, Acc) -> fold_pair(K, V, Rules, Acc) end,
                    {#{}, CountMap},
    grow_count(NewPairMap, NewCountMap, Rules, Step - 1).

fold_pair([A, B], V, Rules, {PairMap, CountMap}) ->
    C = maps:get([A, B], Rules),
    NewPairMap0 = incr_count([A, C], V, PairMap),
    NewPairMap  = incr_count([C, B], V, NewPairMap0),
    NewCountMap = incr_count(C,      V, CountMap),
    {NewPairMap, NewCountMap}.

They did it again. I seem to be bad at second guessing what needs to be done for Puzzle 2. On some I thought I figured what comes next and provide a more general solution, then it goes off in a different direction and vice versa.


The experience of doing it with a non-functional language for the first time really highlights to me how much more trouble a lot of these implementations would be with immutable data structures, mostly because you have to more carefully pick your data structures and orient them towards one type of solutions.

Here with awk it’s just “am I gonna use strings and regexes, or just some arrays and loops?” and the array+loop approach is right pretty much every time, to an extent that is sort of ridiculous. I can imagine doing today in Erlang using some sort of sequences, maps, or whatever, and a slight variation in the second part just throws that basic data structure out and needs to re-shape the whole solution, in ways that wouldn’t be the case if you had the spec for both parts early on.

Anyway, I don’t know if that’s a parable for functional programming as a whole; the optimizations you need to take something inherently mutable and making it immutable tend to lock you down a bit deeper than otherwise. That being said, whenever a problem calls for recursion (graphs and searches) it’s ridiculous how much simpler this all is with Erlang though.


This was probably my last one this year.

Part 2 of this one was particularly tough. I was stuck. I had to look at one solution from Elixir Forum and then I started again. Even after this help, it took me some time to figure out (same maistake I had done in a previous exercise) that I couldn’t use lists:foldl to update the map.


I’m late to the party!

I’ve been using Advent of Code this year to learn Kotlin, and I was curious to see how the Erlang solution to today’s puzzle would look. I managed to golf it down to under 30 lines, which I think is pretty good.

Having experienced a great deal of pain attempting to finish previous years of Advent of Code with Erlang, I agree with Fred; a lot of these puzzles are easier when you can use mutability and imperative-style programming.