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.

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:

There are four operations defined in Part 1: add, reduce, explode, and split. Let's start with the first two.

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.

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.

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.

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.

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?

One hundred? N*N = 10,000? As they say, "CPU goes brrrrrrrrr."

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.

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:

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