It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!
Day 18 - Snailfish
Find the problem description HERE.
The Input - Strange Numbers
Input parsing is a big part of today’s puzzle. There are a couple of different approaches you could take here, either producing a tree-based structure or a list of (value, depth) pairs, where the depth indicates the nesting depth of each number. Both approaches have their pros and cons, making some operations easier and others more difficult. I eventually settled on the tree-like structure when I realized I could traverse back up the tree if I included a link to the parent node from each child node, essentially producing a “doubly-linked” binary tree.
# Helper Functions -------------------------------------------------------------
# Get the index of the middle comma in the string representation of a
# Snailfish number. This is the point to split the string when parsing it
# into a binary tree.
function middleidx(s::AbstractString)
depth = 0
for (idx, char) in enumerate(s)
if char == '['; depth += 1; end
if char == ']'; depth -= 1; end
if char == ',' && depth <= 1
return idx
end
end
return nothing
end
# Data Structures --------------------------------------------------------------
# Store the Snailfish numbers in a binary tree, with the possibility of nodes
# being empty. In reality, they won't be at the end, but in wile building up
# the tree, some of the nodes may be temporarily `nothing` while they're being
# initialized.
abstract type Node end
const MaybeNode = Union{Nothing,Node}
# The `Leaf` nodes contain the numeric values
mutable struct Leaf <: Node
parent::MaybeNode
value::Int64
end
Leaf(s::AbstractString) = Leaf(nothing, parse(Int, s))
Leaf(parent::Node, s::AbstractString) = Leaf(parent, parse(Int, s))
# The `Branch` nodes provide the structure, containing a left and right `Node`,
# either a `Leaf`, a `Branch`, or possibly `nothing`
mutable struct Branch <: Node
parent::MaybeNode
left::MaybeNode
right::MaybeNode
end
Branch(left::Node, right::Node) = Branch(nothing, left, right)
Branch(::Nothing) = Branch(nothing, nothing, nothing)
Branch(parent::Node) = Branch(parent, nothing, nothing)
function Branch(s::AbstractString, parent = nothing)
all(isnumeric, s) && return Leaf(parent, s)
middle = middleidx(s)
(leftstr, rightstr) = (s[2:middle-1], s[middle+1:end-1])
newbranch = Branch(parent)
newbranch.left = Branch(leftstr, newbranch)
newbranch.right = Branch(rightstr, newbranch)
return newbranch
end
# A `Tree` is the binary tree, just contains the root `Branch`
struct Tree
root::Node
end
function Tree(s::AbstractString)
root = Branch(s)
return Tree(root)
end
# Ingest the Data ==============================================================
function ingest(path)
return open(path) do f
[Tree(line) for line in readlines(f)]
end
end
This is the third version of the parsing code. My first attempt used a binary tree without the links back to the parent nodes. My second attempt switched to a flat list (which worked but involved some ugly hacks that wouldn’t necessarily work on every input). Once I settled on the current data structure, it made a lot of the rest of the code easier to write and reason about. Our final input is a list of Tree objects, where each Tree represents a snailfish number.
Part One - Math Mangling
Look, I’m just going to put this out there: If snailfish are solving math problems with these kinds of numbers without the assistance of a computer, they they’re either way smarter than us humans, or way more patient. Either way, we should probably watch our backs. At least they don’t breed as prolifically as lanternfish…
There’s quite a bit of code to go through below, but it’s not doing anything clever that isn’t described in the puzzle description.
# Helper Functions =============================================================
# Helper functions for splitting a value according to the puzzle rules,
# rounding one half down and one half up.
splitleft(value)::Int = floor(value / 2)
splitright(value)::Int = ceil(value / 2)
splitvalue(value) = (splitleft(value), splitright(value))
# Binary Tree Functions ========================================================
# Leaf -------------------------------------------------------------------------
# Functions to allow add-assign operations for `Leaf` values.
function add!(a::Leaf, b::Leaf)
a.value += b.value
end
function add!(a::Leaf, b::Int64)
a.value += b
end
# Node (Leaf/Branch) -----------------------------------------------------------
# Recursively traverse a binary tree structure starting with a given
# node, printing the values and depths of leaf nodes when they are found.
# Useful for debugging!
function traverse(node::Node, depth = 0)
if node isa Leaf
println("($(node.value), $depth)")
return nothing
end
traverse(node.left, depth + 1)
traverse(node.right, depth + 1)
end
# Given a node in the binary tree, recursively search for the leftmost leaf
function firstleaf(node::Node)
node isa Leaf && return node
return firstleaf(node.left)
end
# Given a node in the binary tree, recursively search for the rightmost leaf
function lastleaf(node::Node)
node isa Leaf && return node
return lastleaf(node.right)
end
# Given a node in the binary tree, recursively search for the rightmost leaf
# that occurs prior to the current node. Return `nothing` if there are no `Leaf`
# nodes to the left of the current node.
function previousleaf(node::Node)
# If we hit the root node, there is no previous leaf
isnothing(node.parent) && return nothing
if node.parent.left == node
# If this is the left node, travel up the tree one level and check for
# a previous value starting at the parent node.
return previousleaf(node.parent)
else
# If it's not the left node, then start searching for the rightmost
# leaf starting with this node's left sibling.
return lastleaf(node.parent.left)
end
end
# Given a node in the binary tree, recursively search for the leftmost leaf
# that occurs after the current node. Return `nothing` if there are no `Leaf`
# nodes to the right of the current node.
function nextleaf(node::Node)
# If we hit the root node, there is no previous leaf
isnothing(node.parent) && return nothing
if node.parent.right == node
# If this is the right node, travel up the tree one level and check for
# a next value starting at the parent node.
return nextleaf(node.parent)
else
# If it's not the right node, then start searching for the leftmost
# leaf starting with this node's right sibling
return firstleaf(node.parent.right)
end
end
# Recursively search starting at a give node for a `Node` with a depth of 4.
# This will find the leftmost node that can be 'exploded' first.
function explosivenode(node::Node, depth = 0)
node isa Leaf && return nothing
depth == 4 && return node
left = explosivenode(node.left, depth + 1)
isnothing(left) && return explosivenode(node.right, depth + 1)
return left
end
# 'Explode' a node that has two `Leaf`s as its children, adding the value of its
# left leaf to the rightmost leaf that occurs prior to the exploding node and
# adding the value of its right leaf to the leftmost leaf that occurs after the
# exploding node (basically what the puzzle instructions say).
function explode!(node::Node)
(parent, left, right) = (node.parent, node.left.value, node.right.value)
# Add the left value to the previous leaf
previous = previousleaf(node)
if !isnothing(previous)
add!(previous, left)
end
# Add the right value to the subsequent leaf
next = nextleaf(node)
if !isnothing(next)
add!(next, right)
end
# The `Leaf` left after exploding needs to go into the same 'slot'
# as the exploded Node.
if parent.left == node
parent.left = Leaf(parent, 0)
else
parent.right = Leaf(parent, 0)
end
end
# Recursively search starting at a given node for a 'Leaf' with a value greater
# than `9`, indicating it needs to be split. This search will find the leftmost
# `Leaf` that can be split. Return `nothing` if there are no `Leaf`s that can
# be split.
function splitnode(node::Node)
if node isa Leaf
node.value > 9 && return node
return nothing
end
# Search down the left side of the current node
left = splitnode(node.left)
left isa Leaf && return left
# If nothing is found down the left side, search down the right side
# of the current node
right = splitnode(node.right)
right isa Leaf && return right
# If nothing is found on either side, return `nothing`
return nothing
end
# Split a `Leaf` node, replacing it with a `Branch` whose children have the split
# value of the previous `Leaf`.
function split!(leaf::Leaf)
(leftval, rightval) = splitvalue(leaf.value)
splitnode = Branch(leaf.parent)
splitnode.left = Leaf(splitnode, leftval)
splitnode.right = Leaf(splitnode, rightval)
# The new `Node` needs to go into the same 'slot' as the `Leaf`
# that was split up.
if leaf.parent.left == leaf
leaf.parent.left = splitnode
else
leaf.parent.right = splitnode
end
end
# Recursively calculate the magnitude of a tree, starting at a given node.
function magnitude(node::Node)
node isa Leaf && return node.value
left = magnitude(node.left) * 3
right = magnitude(node.right) * 2
return left + right
end
# Tree -------------------------------------------------------------------------
# Combine two trees, adding each of their root nodes as the children of a
# new root node.
function combine(a::Tree, b::Tree)
root = Branch(nothing)
root.left = a.root
root.left.parent = root
root.right = b.root
root.right.parent = root
return Tree(root)
end
# Overload the `+` operator to combine two trees and `simplify!()` (what the
# puzzle description calls 'reducing') the new tree.
function Base.:+(a::Tree, b::Tree)
tree = combine(a, b)
simplify!(tree)
return tree
end
# Convenience method to call `traverse()` on a tree, for debugging.
traverse(tree::Tree) = traverse(tree.root)
# If there is a pair of values nested 4 or more deep, explode that pair and
# return true. Otherwise, return false.
function explode!(tree::Tree)
explosive = explosivenode(tree.root)
isnothing(explosive) && return false
explode!(explosive)
return true
end
# If there is a `Leaf` with a value greater than 9, split that `Leaf` into a
# new `Branch` and return true. Otherwise, return false.
function split!(tree::Tree)
splitat = splitnode(tree.root)
isnothing(splitat) && return false
split!(splitat)
return true
end
# Simplify (reduce) a snailfish number represented by a `Tree`. Repeatedly
# searches for nodes to explode, then explodes them. If there are no nodes to
# explode, search for a `Leaf` to split and split it. Stops when there are
# no nodes that need to be exploded or split.
function simplify!(tree::Tree)
while true
explode!(tree) && continue
split!(tree) && continue
break
end
end
# Convenience method to calculate the magnitude of a `Tree`
magnitude(tree::Tree) = magnitude(tree.root)
# Solve Part One ===============================================================
# Take the input, then sum all the snailfish numbers. Because we overloaded the
# `+` operator, we can just use the `sum()` method to perform an add-reduce over
# the list of `Tree`s from the input. Finally, we return the magnitude of the
# resulting `Tree`.
function part1(input)
input = deepcopy(input)
finalnumber = sum(input)
return magnitude(finalnumber)
end
This was where having the right data structure really came in handy. There are a lot of different, small operations to perform for this puzzle, but by breaking down each operation into one or more smaller functions, each of which does something understandable with our chosen data structure, we can follow the logic quite handily.
Part 2 - Add All The Things!
Part 2 asks us this seemingly innocuous question: “What is the largest magnitude you can get from adding only two of the snailfish numbers?”. It then informs us that snailfish math is not commutative, such that a + b != b + a. Not sure what that says about snailfish intelligence in general, but it means that we already have everything we need to churn out an answer.
# Solve Part Two ===============================================================
# Add each pair of snailfish numbers, forwards and backwards, and report the
# largest magnitude of a sum that we can find.
function part2(input)
input = deepcopy(input)
maxmagnitude = 0
# For each unique pair of numbers (each of which is represented by a `Tree`)
for (a, b) in Iterators.product(input, input)
# Add `b` to `a` to make a new tree
template = combine(a, b)
# Copy that tree, simplify it, then check its magnitude
tree1 = deepcopy(template)
simplify!(tree1)
mag1 = magnitude(tree1)
# 'Flip' the `template` tree, copy it, simplify, then check the
# magnitude again.
(template.root.left, template.root.right) = (template.root.right, template.root.left)
tree2 = deepcopy(template)
simplify!(tree2)
mag2 = magnitude(tree2)
# If either magnitude is larger than the largest found so far, it
# becomes the new largest
maxmagnitude = max(maxmagnitude, mag1, mag2)
end
return maxmagnitude
end
By having our functionality broken up into small, discrete functions already, we didn’t need to go back and split any of those functions apart for part 2. Yay!
Wrap-Up
This day is the reason I paused so long between blog posts. A big part of the delay was getting to a solution I was happy with. At first, I tried to represent snailfish numbers with a binary tree that didn’t have the parent link in each Node, and getting the explode logic right was really tricky, ugly, and hard to reason about. So, I scrapped that in order to use a flat array of (value, depth) pairs, which made the ‘explode’ and ‘split’ logic easy enough, but which didn’t retain enough information to reliably calculate magnitude (there were edge cases where my calculation would get stuck or return the wrong answer). I ended up needing to write in some special case code to just give up on calculating magnitude in certain circumstances, which didn’t affect my ability to solve the puzzles but definitely could have. Finally, after trying to incorporate the left/right information back into the flat list, it occurred to me that a binary tree that I could travel up as well as down from any given node would, in fact, match what I was trying to accomplish much better. From there, the puzzle almost solved itself. The logic for figuring out which Leaf to add exploded values to took a few minutes to suss out, but once I realized how it could be done, it made a lot of sense! All in all, this was a very satisfying (if painstaking) puzzle to solve!
If you found a different solution (or spotted a mistake in one of mine), please drop me a line!
Top comments (0)