Advent of Code: Day 18
This weekend is quite different from the last one! Tasks are much harder this time, and I’m also out of the town without my laptop. So I’m writing this on my phone!1 I’m doing it in Emacs, installed inside Termux, which thankfully has a lot of packages, that allow me to continue working even without a laptop. And the craziest thing, that I was solving the eighteenth task on my phone too! JDK17 was recently added as a package to the main Termux repository, and this means that Clojure now can be installed directly on my phone too. This means, that I have Clojure, Emacs, and CIDER everywhere I go!
Sure, typing on the phone’s keyboard is not as pleasant as on a physical one, but I’m pretty decent at it. I was developing things on my phone for years now - almost half of the commits on my GitHub profile before the pandemic were made from the phone. So solving the AoC puzzle on the phone should not be too hard to do, especially since I can use full-blown Clojure IDE!
So let’s jump right into it!
Snailfish
Our journey to finding the sleigh keys may finally be over! Some snailfish says that they’ve seen the sleigh keys, but they won’t tell us where. Unless we’ll help them with their math homework. I guess we can, we really need every bit of information about these keys, and math should not be too complicated, given how deep we’re are already. But it turns out that snailfish numbers aren’t like our numbers at all. Each number is represented as a pair:
[1,2]
[[1,2],3]
[1,[2,3]]
[[1,2] [3,4]]
And so on. These numbers nest arbitrarily, but there are exactly two numbers in a pair.
Now, this looks like trees! Such tree can be represented by using an open square bracket as a node marker, and numbers or other square brackets will be leafs:
[
/ \
1 [
/ \
2 3
This is great because Clojure has a library for navigating tree-like structures, called zippers! I’ve always wanted to look at zippers, but unfortunately, there were no tasks that required tree traversal.
Now, back to the numbers.
The addition of two numbers is simple enough.
To add two numbers [1,1]+[2,2] we just wrap them into another set pf square brackets: [[1,1],[2,2]].
However, it’s not all.
Numbers need to be reduced when some conditions apply.
A number must be reduced if it has any pair nested at fourth level: [[[[[1,2],3],4],5],6].
In the case of this number, the [1,2] pair is deep enough to “explode”.
An explosion of a pair is the first reduction step that we need to perform.
To do so we must add the left number from the pair with the first left number outside the pair if any.
The same is done to the right one.
Then the pair itself is replaced with a single 0.
So for this number [[[[[1,2],3],4],5],6] the steps are:
[1,2]needs to explode.1has no number on the left, so nothing happens with it. The number so far:[[[[[1,2],3],4],5],6].2has3on the right side, so we replace3with5. The number so far:[[[[[1,2],5],4],5],6]- Addition was completed, and now the
[1,2]is replaced with0. Resulting number:[[[[0,5],4],5],6].
The same happens if there are only numbers from the left side, but no addition is done for the right number. And if there are numbers on both sides, they both are replaced by the sum, and the pair itself is replaced with zero.
The second reduction step happens when any number is greater than 9.
Such a number splits into its own pair.
The left part is computed by dividing the number by 2 and rounding it down.
For the right part, the process is the same but rounded up.
So a number like [10,3] becomes [[5,5],3], and a number like [11,3] becomes [[5,6],3].
There’s one more thing for the reduction process. There are only two steps, but we must repeat the first one until there’s nothing left to explode. Then, if there are any numbers that can be split, we split the leftmost one. Then we go to the previous step. If the number remains unchanged in both steps, it means we’ve reached the end of the reduction process.
Phew, snailfish numbers are surely complicated. But since we, hopefully, understood the reduction process, we can begin by reading the input:
day17> (ns day18
(:require [clojure.zip :as z]
[clojure.string :as str]))
nil
day18> (defn read-input []
(-> "inputs/day18"
slurp
(str/join "[]")
read-string))
#'day18/read-input
Wait, that’s cheating!
You might say that, but thankfully, Clojure can read snailfish numbers directly, as these are valid syntax!
Commas are ignored by the reader (thanks, Rich!) and square brackets represent vectors.
So to read the list of numbers into a list of vectors, we only need to join the "[]" string with a string of numbers as a separator!
This is a neat trick:
day18> (str/join "," "abcd") ; comma is a separator
"a,b,c,d"
day18> (str/join "abcd" "[]") ; "abcd" is a separator now
"[abcd]"
Now we can begin the homework.
The first thing we need to do is to find the leftmost pair that needs to explode. To do that, we can use zippers, and track how deep we’ve descended into the tree with a simple loop:
day18> (defn exploding-node [root]
(loop [level 0
loc (z/vector-zip root)]
(cond (and (= level 4) (z/branch? loc))
loc
(z/branch? loc)
(recur (inc level) (z/down loc))
(z/right loc) (recur level (z/right loc))
:else
(let [[level loc]
(loop [level (dec level)
loc (z/up loc)]
(cond (and (= level 0) (not (z/right loc)))
[level nil]
(not (z/right loc))
(recur (dec level) (z/up loc))
:else
[level (z/right loc)]))]
(when loc
(recur level loc))))))
#'day18/exploding-node
This function accepts a number and uses the vector-zip function on it.
Then we traverse the tree, tracking when we go down and up.
Once we’ve found the needed node, we return it’s location as a zipper:
day18> (exploding-node [[[[[1,2],3],4],5],6])
[[1 2]
{:l [],
:pnodes
[[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4] [[1 2] 3]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5]],
:ppath
{:l [], :pnodes [[[[[[1 2] 3] 4] 5] 6]], :ppath nil, :r (6)},
:r (5)},
:r (4)},
:r (3)}]
Now, we need a way of finding numbers to the left and to the right of this pair.
Since there’s no number to the left right now, let’s write the find-right function first:
day18> (defn find-right [loc]
(when-not (= (z/root loc) (z/node loc))
(if-let [right (z/right loc)]
(if (z/branch? right)
(loop [loc right]
(if (z/branch? loc)
(recur (z/next loc))
loc))
right)
(recur (z/up loc)))))
#'day18/find-right
This function accepts a location in the tree and starts from it.
We only do the search for nodes that are not the root ones, as the root has no numbers outside of it.
First, we check if there’s a number to the right of the current location.
If not we simply ascend.
If there is a number, it means that we never need to ascend again, so we check whether it is a branch?, meaning that we’re looking at another pair.
If not, we’ve found our number, so we return it.
If it is a branch we loop moving to the next element until we find one that is not a branch.
Let’s try it:
day18> (find-right (exploding-node [[[[[1,2],3],4],5],6]))
[3
{:l [[1 2]],
:pnodes
[[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4] [[1 2] 3]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5] [[[1 2] 3] 4]],
:ppath
{:l [],
:pnodes [[[[[[1 2] 3] 4] 5] 6] [[[[1 2] 3] 4] 5]],
:ppath
{:l [], :pnodes [[[[[[1 2] 3] 4] 5] 6]], :ppath nil, :r (6)},
:r (5)},
:r (4)},
:r nil}]
The return value is another location in the tree.
Now, let’s do the same for the left number.
It’s a bit trickier, as we need to find the right number on the left side.
E.g. for this number [[7,6],[[[[5,4],3],2],1]] the exploding pair is [5,4], and the left number is 6:
day18> (defn find-left [loc]
(when-not (= (z/root loc) (z/node loc))
(if-let [left (z/left loc)]
(if (z/branch? left)
(loop [loc (z/next left)]
(let [loc (z/rightmost loc)]
(if (z/branch? loc)
(recur (z/next loc))
loc)))
left)
(recur (z/up loc)))))
#'day18/find-left
day18> (z/node (exploding-node [[7,6],[[[[5,4],3],2],1]]))
[5 4]
day18> (z/node (find-left (exploding-node [[7,6],[[[[5,4],3],2],1]])))
6
This function also ascends until there’s something on the left side, but then it descends to the rightmost element of each level.
It returns the location of the left number, which we render with the node function, to keep the output short.
Now we can find the required numbers:
day18> (let [loc (exploding-node [[7,6],[[[[5,4],3],2],1]])
left (find-left loc)
right (find-right loc)]
(println (format "exploding pair: %s\nleft: %s\nright: %s"
(z/node loc)
(z/node left)
(z/node right))))
exploding pair: [5 4]
left: 6
right: 3
nil
Good!
Now let’s implement the explosion step of the reduction process.
To do that, we need to change the tree.
Thankfully, zippers, while being immutable, support tree editing.
To change the tree, we need to find a location that is ready to be exploded and side numbers.
The structure of the numbers tells us that there will always be at least one number to the side.
So we can check which one is there, replace it with the sum, and then replace the location itself with 0:
day18> (defn explode [root]
(if-let [loc (exploding-node root)]
(let [[a b] (z/node loc)
left (find-left loc)
right (find-right loc)]
(-> (cond (not left) (z/edit right + b)
(not right) (z/edit left + a)
:else (-> left
(z/edit + a)
z/root
exploding-node
find-right
(z/edit + b)))
z/root
exploding-node
(z/replace 0)
z/root))
root))
#'day18/explode
day18> (explode [[7,6],[[[[5,4],3],2],1]])
[[7 11] [[[0 7] 2] 1]]
In case where both numbers are available we have to do additional searches.
Unfortunately zippers are new to me, so maybe there’s a more optimal way of doing this, but I wasn’t able to find it.
My guess was to use the path function, but it seems that there’s no way to navigate to a certain location in the changed zipper, but to search it from the root again.
Maybe I could write such function, but the semantics of the task allow me to just find the same exploding node from the root again.
This number explodes correctly, and we now have a number that can be split.
Let’s write a function, that finds the leftmost number that is greater than 9:
day18> (defn splittable-node [root]
(loop [loc (z/vector-zip root)]
(when-not (z/end? loc)
(cond (z/branch? loc)
(recur (z/next loc))
(> (z/node loc) 9)
loc
:else
(recur (z/next loc))))))
#'day18/splittable-node
day18> (z/node (splittable-node *2))
11
Seems correct. Now let’s write another function, that splits the given location:
day18> (defn split [root]
(if-let [loc (splittable-node root)]
(-> loc
(z/edit (juxt #(int (Math/floor (/ % 2)))
#(int (Math/ceil (/ % 2)))))
z/root)
root))
#'day18/split
day18> (split [[7 11] [[[0 7] 2] 1]])
[[7 [5 6]] [[[0 7] 2] 1]]
It’s always so pleasant when you can use the juxt function.
Now we only need to implement addition with all necessary reduction steps:
day18> (defn sum [a b]
(loop [x [a b]]
(let [x' (explode x)]
(if (= x' x)
(let [x' (split x')]
(if (= x x')
x'
(recur x')))
(recur x')))))
#'day18/sum
day18> (sum [7,6] [[[[5,4],3],2],1])
[[7 [5 6]] [[[0 7] 2] 1]]
This loop will explode the number until the number remains the same as before the explosion.
Then it will split a single number, and repeat.
If the number is unchanged after a split, means we’ve finished.
To actually compute the answer, we need to implement another function that calculates the magnitude. To do that we need to multiply the left part of the pair by 3 and the right pair by 2, then add them:
day18> (defn magnitude' [loc]
(cond (z/end? loc)
(z/root loc)
(z/branch? loc)
(let [loc (z/next loc)
left (magnitude' loc)
right (magnitude' (z/right loc))]
(z/replace loc (+ (* 3 (z/node left)) (* 2 (z/node right)))))
:else
loc))
#'day18/magnitude'
day18> (defn magnitude [root]
(z/node (magnitude' (z/vector-zip root))))
#'day18/magnitude
Finally, given that we have a list of numbers we need to add together, we can use reduce on it with our sum function, and then compute the magnitude for the final answer:
day18> (defn part-1 [input]
(->> input
(reduce sum)
magnitude))
#'day18/part-1
day18> (part-1 (read-input))
3763
This grants us the first gold star!
Part two
For the second part, we need to find the largest magnitude across all numbers.
The catch is that snailfish addition is not commutative, which means that a+b is not necessarily equal to b+a, so we need to check all variants.
It’s quite simple in Clojure, thanks to for:
day18> (defn part-2 [input]
(->> (for [a input
b input]
(when-not (= a b)
(magnitude (sum a b))))
(filter some?)
(apply max)))
#'day18/part-2
day18> (part-2 (read-input))
4664
Here checking if the numbers are the same to avoid adding them.
This introduces elements that are nil in our final list, so we filter them out.
Then we just find the max value, and get the second gold star!
Day 18 thoughts
Phew, this was challenging! Writhing all of this on the phone, while simultaneously learning about zippers, is definitively something. The task itself wasn’t as hard, but there were some tricky parts with finding the correct number, which was extremely hard to debug, especially on the phone’s screen:
Since I’m editing this and it’s already December 19th, I saw the task for the 19th day, and I’m not sure if I’ll be able to finish it by today and write a post as well.
Going out of the town threw me off my rhythm, so expect some lag, I guess.
With that, until tomorrow today?
Tomorrow?
I don’t know!
-
I’ve edited the post on PC once I came back in town, that’s why I wasn’t able to publish it on the same day as the task. ↩︎