If you're looking at the per-day leaderboard (an activity I don't recommend spending too much time on, but is fun anyway), it's easy to see the puzzles are heating up! The longest first time to both stars before this was Day 16 at 9:52. Today, it nearly doubled to 17:13! What's going on?
Day 18's puzzle is the implementation of some operations in a strange number system. I have to say that I laughed when I read it. I've been a little worried about casually dropping terms like "pair" in my descriptions. While popular languages like C++ and Java each have a Pair class ready to use these days, you don't hear those folks talk about them nearly as much as you hear Lisp/Haskell/Erlang and programmers of other languages with syntax for them do. So, I'm glad that I might be more aligned with my audience than I suspected.
I was most worried about the parsing today. Parsing generic lists of things can get quite complex. But after some thinking, it was a suprisingly small amount of code.
parse_snail_number(Line) ->
{Number, <<>>} = parse_snail_number_i(Line),
Number.
parse_snail_number_i(<<$[, Rest/binary>>) ->
{Number1, <<$,, RestB/binary>>} = parse_snail_number_i(Rest),
{Number2, <<$], RestC/binary>>} = parse_snail_number_i(RestB),
{{Number1, Number2}, RestC};
parse_snail_number_i(<<C, Rest/binary>>) when C >= $0, C =< $9->
{C-$0, Rest}.Usually a parser needs to be prepared for unbalanced braces, missing/extra commas, elements of unknown length. Here, there's none of that. If we see an opening brace, we know that we'll read a left element, then a comma, then a right element, and a closing brace. My top-level function (the one without the _i suffix) makes sure that I'm not wrong about this, by returning successfully only if all characters were consumed. My numbers look nearly the same, but with curly braces instead of square brackets (because I decided to use 2-tuples, keeping in form with what I've been calling a "pair" in this series:
puzzle18:parse_snail_number(<<"[[[[1,2],[3,4]],[[5,6],[7,8]]],9]">>).
% {{{{1,2},{3,4}},{{5,6},{7,8}}},9}There are four operations defined in Part 1: add, reduce, explode, and split. Let's start with the first two.
add(N1, N2) -> reduce({N1, N2}).
reduce(N) ->
case maybe_explode(N, 0) of
{true, New, _, _} ->
reduce(New);
false ->
case maybe_split(N) of
{true, New} ->
reduce(New);
false ->
N
end
end.Since I'm working in a language with syntax for pairs, add is just putting the two arguments in a new pair. I included the call to reduce just to save myself some typing in the shell while debugging.
Reduce, I hope, looks just as described by the puzzle. If a number can be exploded, do it, and then check again. If nothing can be exploded, but something can be split, split it, and then check again. If nothing can be exploded, and nothing can be split, the number is fully reduced.
maybe_split(N) when is_integer(N) ->
case N > 9 of
true ->
Left = N div 2,
Right = case Left*2 == N of true -> Left; false -> Left+1 end,
{true, {Left, Right}};
false ->
false
end;
maybe_split({A, B}) ->
case maybe_split(A) of
{true, NewA} ->
{true, {NewA, B}};
false ->
case maybe_split(B) of
{true, NewB} ->
{true, {A, NewB}};
false ->
false
end
end.Split is, by far, the simpler remainin operation. Splitting can happen only on regular numbers, not pairs. So the first clause checks if there is a large regular number (N > 9) that needs splitting. The div operator is a truncating integer division. So, if N is odd, we'll get (N-1)/2, and N/2 if N is even, which is what the puzzle specifies for the left-hand member of a split pair. For the right half, we check which whether we got N/2, and if we did, we use the same value. If we didn't, we add 1. The second clause of maybe_split shows how the recursion works to find a split. We're using the stack to help us reassemble the number after splitting. As the calls return from a successful split, we wrap the new values in new pairs with the other, unsplit half of the original pair.
maybe_explode({A,B}, Depth) when Depth >= 4, is_integer(A), is_integer(B) ->
{true, 0, A, B};
maybe_explode({A,B}, Depth) ->
case maybe_explode(A, Depth+1) of
{true, New, AddA, AddB} ->
{true, {New, add_explode({b, AddB}, B)}, AddA, 0};
false ->
case maybe_explode(B, Depth+1) of
{true, New, AddA, AddB} ->
{true, {add_explode({a, AddA}, A), New}, 0, AddB};
false ->
false
end
end;
maybe_explode(N, _) when is_integer(N) ->
false.
add_explode({_, Add}, Num) when is_integer(Num) ->
Add + Num;
add_explode({b, Add}, {A,B}) ->
{add_explode({b, Add}, A), B};
add_explode({a, Add}, {A,B}) ->
{A, add_explode({a,Add}, B)}.Explode is where I suspect most solvers spent most of their time. I found the description of this operation really hard to follow. "First regular number to the left/right" felt easy to see, but hard to model. After a little cleanup this morning, I think the deduplicated code reads a little easier. Only pairs with with two regular numbers can be split, so once the recursion is deep enough (Depth >= 4, I check the types of the values (is_integer(A), is_integer(B)). The return value takes this format:
{true
(new value for this pair),
(value to add to the "first regular number to the left"),
(value to add to the "first regular number to the right")}
For the pair that exploded, this return ({true, 0, A, B}) is exactly what the puzzle describes: the pair is replaced by the regular number 0, and the value on the left, A, needs to be added to the first regular number to the left, and the value on the right, B, needs to be added to the first regular number to the right. The next function clause, which we encounter when popping the call stack is where the return gets interesting.
The first clause of the case is where we check if the left value would explode. If it did, we know that we have a regular number somewhere in the right half of this pair. If the right half isn't a regular number itself, it's a pair with a regular number, or a pair with a pair with a regular number, etc. We know we'll be adding B to that half of the pair, so the return value gets to set the last value to 0, because any numbers farther to the right don't need modification. It keeps the second-to-last return value (AddA) in-place, because we're still searching for its mate. The seconds clause of this case statement is the same idea when the right-hand value exploded. We know there's a left-hand regular number close by.
The add_explode function is one of those classic naming problems. It needs to know whether to add the value to the left or right value. But do you tell it to add the number to the right/left-hand value, that the number is coming from the right/left, or that the number is moving to the right/left? I decided to note which side of the pair the value had been on. Once you get to a regular number, you don't care where it came from ({_, Add}). But it turns out that when you're looking for "the next number to the right" of a right-hand "B" value, you're actually looking for the left-most "A" value in a pair. This is probably overthinking the problem, but I left this bit for last specifically because I kept confusing myself.
Finally, you can see why the reduce function way above here ignores (_, _) the last to values of a maybe_explode return value. As specified by the puzzle description, if there is no regular number to the left/right, the additional value is discarded.
magnitude(N) when is_integer(N) ->
N;
magnitude({A, B}) ->
3 * magnitude(A) + 2 * magnitude(B).Oh right, there is a fifth operation, magnitude, that provides the actual answer to the puzzle. Looking at this code, it hardly seems worth discussing after "explode". Once again, built-in pair syntax means this code is about as direct of a translation of the described formula as you can get.
ExampleInput = <<"[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]">>.
ExampleNums = [ puzzle18:parse_snail_number(N) || N <- string:split(ExampleInput, <<"\n">>, all) ].
ExampleSum = lists:foldl(fun(B, A) -> puzzle18:add(A, B) end, hd(ExampleNums), tl(ExampleNums)).
% {{{{6,6},{7,6}},{{7,7},{7,0}}},
% {{{7,7},{7,7}},{{7,8},{9,9}}}}
4140 = puzzle18:magnitude(ExampleSum).Part 2 asks for the highest magnitude of the sum of any pair of numbers in the input. It reminds us that addition is not commutative in this sytem, so a naive search will require adding every number to every other number, in both orders. That's N*N comparisons. Do we need to find out some way to predict how summation alters magnitudes to be more efficient than that? How many numbers are we dealing with?
length(RealInputNumbers).
% 100One hundred? N*N = 10,000? As they say, "CPU goes brrrrrrrrr."
largest_magnitude_of(_, [], Mag) ->
Mag;
largest_magnitude_of(A, [B|Rest], Mag) ->
case magnitude(add(A,B)) of
New when New > Mag ->
largest_magnitude_of(A, Rest, New);
_ ->
largest_magnitude_of(A, Rest, Mag)
end.
solveB() ->
Numbers = load_file(),
lists:foldl(fun(I, Mag) ->
{Left, [This|Right]} = lists:split(I, Numbers),
largest_magnitude_of(This, Left++Right, Mag)
end,
0,
lists:seq(0, length(Numbers)-1)).This is exactly the naive aproach. For each number in the input list, find the magnitude of adding it to each other number. Remember the largest magnitude seen as we go along.
3993 = lists:foldl(fun(I, M) ->
{L,[T|R]} = lists:split(I, ExampleNums),
puzzle18:largest_magnitude_of(T, L++R, M)
end,
0,
lists:seq(0, length(ExampleNums)-1)).
timer:tc(puzzle18, solveB, []).
% {90715,…no spoilers…}Less than 100ms to do 10,000 add/reduces (including reading the file from disk and parsing the numbers). That will do.
I found this puzzle interesting, because it reminds me of balancing tree datastructures, but never mentions "tree". Solving both haves took me right at an hour, only 16min off the last position in the leaderboard. That's the closest I've been since Day 16, when I claimed the puzzle was made for Erlang.
The funny thing about this puzzle is it's even more "made for Erlang" than I let on. In fact, Snailfish Numbers are valid Erlang syntax! Instead of parsing the numbers myself, I could have let the Erlang compiler do it for me:
SnailFishNumber = fun(String) ->
{ok, Tokens, _} = erl_scan:string(String),
{ok, [Form]} = erl_parse:parse_exprs(Tokens),
{value, Value, _} = erl_eval:expr(Form, []),
Value
end.
SnailFishNumber("[[[[1,2],[3,4]],[[5,6],[7,8]]],9].").
% [[[[1,2],[3,4]],[[5,6],[7,8]]],9]This leaves pairs as two-element lists instead of 2-tuples. How would this have changed the code? Basically, all {A,B} matches become [A,B] … and that's it. Anyone want to argue that that's a better solution? Bring it to Twitter (@hobbyist), or give the change a try yourself on github (beerriot). For now, I'm headed out to ski.
Categories: Development AdventOfCode
Post Copyright © 2021 Bryan Fink