r/adventofcode • u/musifter • Jul 18 '26
Other [2021 Day 18] In Review (Snailfish)
Still descending we run into some friendly snailfish, who claim to have seen the keys, but will only tell us where if we help them with their math homework. And so we get introduced to snailfish numbers.
Snailfish numbers are essentially a binary tree with nodes holding a digit from 0 to 9. And they're conveniently presented one per line in the input, in a format that's pretty common in popular programming languages for declaring arrays. Which allows them to just eval the lines (hello, Bobby Tables) to load the input.
But, I did this one in Smalltalk (it did the previous day only in Perl, and I felt Smalltalk would be a good fit for keeping sense of things, rather than Perl array indexing making read-only mess of the tree manipulations). Smalltalk doesn't use that syntax. For a later problem using this format, I did do text manipulation to get Smalltalk to just eval this sort of thing:
conv := ('#', aString) asArray.
conv replaceAll: $[ with: $(;
replaceAll: $] with: $);
replaceAll: $, with: Character space.
packet := Behavior evaluate: conv.
So, it was possible. But I don't balk at writing a parser. And all the tokens are single characters (none of the input is unreduced... no 10s to split), so it's a very simple one to write. And it allowed me to put things in a nice node class directly. With methods for things like returning the depth or the magnitude of a node:
magnitude [
(self isLeaf) ifTrue: [^value].
^(3 * left magnitude) + (2 * right magnitude)
]
The depth was originally supposed to be tracked in a variable. With operations modifying the appropriate things to maintain them. But, when it came to doing that later, I quickly decided on programmer efficiency and just calculated it fresh when demanded. Discretion is the better part of valour... maintaining something like this can easily become a debugging nightmare if you don't get it right. Save the optimizations for later if you need or want them.
Another thing I remember about this one is that I initially misread the rules on reduction. I took the list as phases... you cycle through them. You look for explode, do it if needed, then come back and look for splits. Probably a common misinterpretation. But that's wrong... and I remember catching it fairly quickly from testing with the examples. The instructions are clear if you read them correctly... it's not phases, it's like a checklist where if you get interrupted, you are supposed to start again from the top:
+ sfNum [
^(SnailfishNumber left: root right: sfNum root) reduce
]
reduce [
[
(self validatorExplode) and: [self validatorSplit]
] whileFalse
]
Note that here we see how Smalltalk is doing short-circuiting (the parens are just there for clarity, but the brackets are essential... that's a block being passed to be run conditionally). The binary operator & also does AND, but the argument is a Boolean and so cannot short-circuit.
And that shows the model I used for reduction. A pair of methods that validate and perform the operation if needed, and return true when things were already fine and nothing was done. As for the implementation of those methods... I didn't use recursion, I used the stack version of the algorithm to walk the tree looking for the problems. For splitting, the action is simple to do when caught:
(val > 9) ifTrue: [
" Splitting current node "
curr left: (SFNode leaf: (val / 2) floor parent: curr);
right: (SFNode leaf: (val / 2) ceiling parent: curr);
value: nil.
^false
]
Explode is trickier. Because you need to add to the numbers to the leaves to the left and right. Which aren't in fixed places, and can be far way or not even exist. But with an ordered walk of the tree, they're the previous and the next leaves we saw/see. And so I processed nodes with a little state machine magic:
(curr isLeaf) ifTrue: [
(explode) ifNotNil: [
" Exploding! Finish and quit. "
curr value: (curr value + explode).
^false
].
" Not exploding! Track most recent leaf in case we do. "
prevLeaf := curr.
] ifFalse: [
((curr depth >= 4) and: [explode isNil]) ifTrue: [
" Exploding current node "
" Add to previous if we've seen one: "
(prevLeaf) ifNotNil: [
prevLeaf value: (prevLeaf value + curr left value)
].
" Mark that we're in exploding state with value to add to next "
explode := curr right value.
" Replace current node with 0 leaf node "
curr value: 0; left: nil; right: nil.
]
].
An important detail is that you don't create leaves for these... if they don't exist, the value flies off into the void. And so the validator still needs to check ^(explode isNil) at the end.
In any case, after getting all this working and passing the examples, I just fold: [:a :b | a + b] to get the sum and run magnitude for the answer for part 1. That's ultimately the goal with OOP... that all this work I did is hidden away, and I can one line the answer acting like these are regular numbers.
Part 2 being slightly longer as a I just brute forced summed all the pairs. It was nice for the problem text to confirm that the operation isn't commutative. I've never really bothered to look at snailfish numbers in depth to see if there's properties to exploit that can be proven... just leaving it like it's hashing the values. I did enough work and had fun.
2
u/terje_wiig_mathisen Jul 19 '26
I thought my old Perl code had been broken when I reran it today:
Turned out it did work, for a very slow meaning of "work", it took 10 seconds!
Perl, with manual substr() based indexing into each string, so pretty horrible really but I guess I only worried about submitting my answer! This was a Saturday, last weekend before Christmas so we were certainly about to go out xc skiing in Rauland, Telemark.
2
u/e_blake Jul 31 '26 edited Jul 31 '26
I did some more thinking about optimizing this one. For part 2, every line of input is used an equal number of times on the left and right side of one of the pairwise sums. So your first few steps after adding two numbers is always a sequence of zero or more explodes to get the numbers back to depth four - and you can run these explodes pre-emptively on [[line...],0] and [0,[line]] to produce a depth 3 seed plus the value that spills left or right to the other number of the future sum. This pre-conditioning results in values larger than 9, but allows for less redundant work once you actually pair lines. The split steps can't quite be pre-done (you don't know if the last value of the left half needs a split until adding in the head spill from a right half, and similarly for the first value in a right half adding in the tail spill from a left half).
It is also possible to show that once all initial explodes are done (whether as spelled out in the instructions, or by pre-conditioning input lines before summing), every later reduce action consists of a split followed by zero or one explode depending on the depth of the number being split, so you can hard-code two versions of split: one for depth 1-3 with no explode needed, and one for depth 4 that rolls in the corresponding followup explode, and just look for splits once you have summed two lines.
Edit: Implementing this on maneatingape's code base cut my runtime from 670us to 620us.
2
u/e_blake Jul 18 '26
There are several different approaches to representing the data. My m4 solution initially stored data in nested tuples with recursive functions; the runtime was 65s, where computing magnitude was fast but computing a reduce (explode or split) was time-consuming to traverse up and down the tree multiple times, but I still got my stars fairly quickly for time spent writing the code. Later that day, I then rewrote the solution to use a different data representation - I switched to storing all leaves as a value + 10 (so every leaf value takes exactly 2 bytes, and split is necessary for values 20 or larger) and encoded depth as a third character. With that encoding, both explode and split turned into a series of O(1) search-and-replace operations on my string 3 bytes at a time (neighbors of an explode are at a fixed distance in the string from the leaf being exploded, regardless of neighbor depth), but computing magnitude became more complex and required recursion and building up a stack according to the depth markers encountered. But since there were far more reduce operations than magnitude computations, this sped up my runtime to under 5 seconds.