Advent of code 2021: Day 18- 10 minutes read - 1921 words
Day 18 of Advent of Code 2021 took rather a long time to get right. Half of the problem was that there were a couple of gotchas in the requirements and the choice of data structure hugely impacted how easy it was to come up with a solution. Just like Day 17 I was using TDD and this helped me root out some blind alleys nicely.
The story was roughly as follows: In order to continue on the Advent of Code submarine journey, we had to solve snailfish number problems. The issue with snailfish numbers is that they’re unlike other numbers, and are built using number pairs:
[1,2] [[1,2],3] [9,[8,7]] [[1,9],[8,5]]
Pairs can have pairs nested inside them. To add snailfish numbers, the following rules had to be followed:
- If any single number is greater than or equal to 10, it is replaced by a pair of numbers. This is called a split.
- If any pair is nested more than 4 levels deep, then the pair is added to neighbouring numbers and replaced with a
0. This is called exploding.
My initial thought was that having pairs and nested pairs sounds exactly like a tree. So I started building a parser to read in the numbers and build a tree structure.
First, the data type:
So an element is either a
Lit literal with an integer value or a
Pair of elements. Building on my experience
with parsing on Day 16, turning the raw strings into a tree felt easy:
This would give me a tree as this test demonstrates:
My next step was going to be to implement the split and explode functions. And that’s where I hit my first issue.
Split was going to be straightforward enough, I would traverse my tree and just replace any
Lit that has a value
greater than or equal to 10 and replace it with a pair. But on the exploding function, it wouldn’t be so
straightforward. In order to explode, we had to:
- Replace the pair with a
- Add the left element of the pair to the first occurring
Litthat is to the right in the tree (can be on the same or a different level)
- Same with the right element, that gets pushed right.
The tree structure wasn’t going to work for me there. In an imperative language where we’d have references to different objects, it would have been possible to go backwards and forwards in the tree and mutate the values in-place. But in Haskell this wouldn’t be so simple as the tree is immutable.
Eventually - after attempting some solutions with keeping state and pushing values left and right, I had a solution that was not very elegant and frankly smelled a bit. I was prepared to let that go to get my answers in, but as it turned out my unit tests uncovered that the exploding wasn’t working like the examples.
Back to the drawing board
Eventually I figured that the tree was not the right data structure. In order to push the exploding numbers left and right, something like a list felt more natural. Eventually - after a lot of trying different approaches - I settled on a data structure where I’d use the “path” from the root of the tree down to the leaf.
So if I had a (crudely drawn) tree as such
Pair / \ Lit 1 Pair / \ Lit 2 Lit 3
Then for each
Pair, I would record whether I take the left or right branch by a 0 or 1. So the above tree
would be represented by a list
I’m only listing the leaves of the tree, not the internal nodes. To convert from my tree to this list, I used the following
Now I had my data structure right, the split operation was quite straightforward:
This operation recursively goes through each of the elements in the list until it finds the first node where the value is greater or equal 10. If that’s the case, it replaces that single element by a pair (by adding 0 and 1 to the “path”).
The explode function was a little more complicated, first I built a helper to check whether two paths are for elements that would explode:
That can then be plugged into:
The main logic is in the
explode' function. It works as follows:
- It has two parameters: a list of elements that have already been visited and a list that are still to be visited.
- It then recursively goes through the list, picking out the first two elements.
- If those two elements are to explode, it uses the
addToFirsthelper to add the left element of the pair (
x1) to the last element that was visited (as it is more efficient to add to lists at the front than append at the back, I am reversing the list of already visited nodes)
- The right element (
x2) is added to the first element of the list of not yet processed nodes
- The two elements are replaced by a single value.
Initially, when I was writing this I was playing with a “findExplodingPair” function that would get me the position of the first exploding pair, then I was going to have a second pass to add the left value to the first element whose path was smaller than the found path, and a third pass… I didn’t like it, so I was quite pleased when I managed to turn that into a single block.
One more gotcha
I had implemented the above and still my tests were not passing. Eventually, I figured out that I needed to read the instructions again:
To reduce a snailfish number, you must repeatedly do the first action in this list that applies to the snailfish number:
- If any pair is nested inside four pairs, the leftmost such pair explodes.
- If any regular number is 10 or greater, the leftmost such regular number splits.
My initial reading of this was to implement:
repeatUntil helper takes two things of the same type and a function. If the two inputs are the same, then
we’re finished and return it. If they are not the same, it would call the function and then itself. In Java
this would be a while loop. I did like the function composition there that allowed me to call
the input didn’t change anymore and then
That’s where I had a subtle bug though. I was calling
split until I couldn’t split anymore. That resulted in
failing tests. When I changed it to
it started working!
Finally, to be able to enter the solution into the AOC website, we had to calculate the magnitude of a snailfish number. The magnitude was defined as
The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.
Now this would be easy if we were using our tree structure:
So I wrote a further function to convert from my element list, back to my tree:
list2tree function is:
- called with the empty string initially,
- then it tries to lookup the value of that path
- if that exists it is turned into a
- if it does not exist, then we must be at a
- list2tree gets called recursively to fill in either branch
Finally, I was able to find the magnitude of adding all the numbers together!
For part two, we needed to find the highest magnitude when adding each pair of numbers together. To get all the permutations of numbers I use a list comprehension:
That worked by combining all the numbers and only picking out the ones where the first number is not equal to the second. Note, this is working on my element list - as Haskell lists are automatically comparable. Neat!
Rest of the solution on GitHub
This was a very interesting challenge as it demonstrated something I picked up a long time ago, if something does not feel elegant, then there’s a better solution somewhere. Call it intuition or experience, but it is often very useful to keep tinkering if something is not as simple as it can be. Note also, I’m sure there’s lots of ways this could still be simplified further, I just don’t know Haskell well enough yet.Tags functional haskell advent-of-code
If you'd like to find more of my writing, why not follow me on Twitter or Mastodon?