Advent of Code, in Erlang: Day 10

Ah, parenthesis/brace/bracket balancing. A classic. Using the right-hand-rule on Day 19, was not the first time the Advent of Code has given me college flashbacks. Day 10 could have come off a 6.001 problem set.

We need to find the first non-matching closing character. The typical stack solution looks something like this in Erlang:

score_corruption(<<$(, Rest/binary>>, Acc) ->
    score_corruption(Rest, [$(|Acc]);
score_corruption(<<$), Rest/binary>>, [$(|Acc]) ->
    score_corruption(Rest, Acc);
score_corruption(<<$), _/binary>>, [_|_]) ->
    3;

Copy and paste this three times, replace $( and $) with $[ and $], ${ and $}, and $< and $> (as well as the scores for each), and you have the full solution. Push every opening character onto the head of an accumulated list (the "stack"). When you come across a closing character, check if the matching opening character is at the head of the list. If it is, pop it off and keep going. If it's not, you've found a corruption.

Part 2 is exactly the same, except what to do when you get to the end of the input. For Part 1, we were ignoring incomplete inputs, so when we reached the end of a line, we just threw away any accumulated list of opening characters that was left.

score_closing(<<>>, Acc) ->
    {true, lists:foldl(fun(C, Score) ->
                               Score*5 + case C of
                                             $( -> 1;
                                             $[ -> 2;
                                             ${ -> 3;
                                             $< -> 4
                                         end
                       end,
                       0,
                       Acc)};

When the input ends, pop each remaining character off the accumulated list of openers, and add its score to the total.

26397 = lists:sum([ puzzle10:score_corruption(L, []) || L <- Lines ]).

Closings = lists:filtermap(fun puzzle10:score_closing/1, Lines).
288957 = lists:nth(length(Closings) div 2 + 1, lists:sort(Closings)).

The filtermap is used when collecting the unclosed line scores, because the other difference between score_corruption and score_closing is that the latter returns false if the line is corrupt, instead of just unclosed (full code here).

Whew! Just one more historical write-up to go.

Categories: Development AdventOfCode