# Data Structures --------------------------------------------------------------

# We'll store each `Beacon` as a Tuple of (x, y, z) coordinates, each `Scanner`
# as a Set of `Beacon`s, and maintain a collection of `Scanner`s as a Dict where
# each key is the scanner ID and value is the set of beacons associated with
# that scanner.
const Beacon = NTuple{3,Int}
const Scanner = Set{Beacon}
const Scanners = Dict{Int,Scanner}


# Helper Functions -------------------------------------------------------------

# Functions to help parse a chunk of the input into an (<ID>, `Scanner`) pair

# Parse a line starting a scanner chunk into the scanner ID
scannerid(s) = parse(Int, match(r"--- scanner (\d+) ---", s)[1])

# Parse a line containing beacon coordinates into a `Beacon`
parsebeacon(s) = NTuple{3,Int}(parse(Int,n) for n in split(s, ","))

# Parse a "scanner chunk" (from the "--- scanner ## ---" line to the next blank
# line) into an (<ID>, `Scanner`) pair, for conversion into a Dict entry.
function parsescanner(f)
	id = readline(f) |> scannerid
	beacons = Set(parsebeacon(s) for s in split(readuntil(f, "\n\n")))
	return (id, beacons)
end



# Ingest the Data -------------------------------------------------------------

# Parse scanner chunks until the file is empty!
function ingest(path)
    return open(path) do f
		entries = []
		while !eof(f); push!(entries, parsescanner(f)); end
		Scanners(entries)
    end
end

# Some Useful Data Structures --------------------------------------------------

# The cosines for each 90° rotation: 0° => 1, 90° => 0, 180° => -1, 270° => 0
const COS = Dict{Int,Int}([(0,1), (90,0), (180,-1), (270, 0)])

# The sines for each 90° rotation: 0° => 0, 90° => 1, 180° => 0, 270° => -1
const SIN = Dict{Int,Int}([(0,0), (90,1), (180, 0), (270,-1)])

# These are all the rotations that can place a scanner into any of the 24
# orientations described in the puzzle input, starting with no rotation.
const ROTATIONS = [
    (0,   0,   0), (90,   0,   0), (180,   0,   0), (270,   0,   0),
    (0,  90,   0), (90,  90,   0), (180,  90,   0), (270,  90,   0),
    (0, 180,   0), (90, 180,   0), (180, 180,   0), (270, 180,   0),
    (0, 270,   0), (90, 270,   0), (180, 270,   0), (270, 270,   0),
    (0,   0,  90), (90,   0,  90), (180,   0,  90), (270,   0,  90),
    (0,   0, 270), (90,   0, 270), (180,   0, 270), (270,   0, 270)
]

# Describes the unit vector for a 3D system
const Basis = NTuple{3, NTuple{3,Int}}


# Helper Functions -------------------------------------------------------------

# The formula to rotate a vector about the x axis in 3 dimensions:
# - x′ = x
# - y′ = y × cos(θ) - z × sin(θ)
# - z′ = y × sin(θ) + z × cos(θ)
rotabout_x(x, y, z, θ) = (x, y*COS[θ] - z*SIN[θ], y*SIN[θ] + z*COS[θ])

# The formula to rotate a vector about the y axis in 3 dimensions:
# - x′ = x × cos(θ) + z × sin(θ)
# - y′ = y
# - z′ = z × cos(θ) - x × sin(θ)
rotabout_y(x, y, z, θ) = (x*COS[θ] + z*SIN[θ], y, z*COS[θ] - x*SIN[θ])

# The formula to rotate a vector about the z axis in 3 dimensions:
# - x′ = x × cos(θ) - y × sin(θ)
# - y′ = x × sin(θ) + y × cos(θ)
# - z′ = z
rotabout_z(x, y, z, θ) = (x*COS[θ] - y*SIN[θ], x*SIN[θ] + y*COS[θ], z)

# Rotate a vector about the x, y, and z axes in sequence
function rotabout_xyz(x, y, z, xθ, yθ, zθ)
    (x, y, z) = rotabout_x(x, y, z, xθ)
    (x, y, z) = rotabout_y(x, y, z, yθ)
    return rotabout_z(x, y, z, zθ)
end

# Pre-calculate the rotation matrices for each of the 24 possible Scanner
# facings. The unit vector for 'no rotation' is `standard` below. Each rotation
# matrix can be used to translate points from one scanner facing to another
# scanner facing.
const BASES = begin
    standard = ((1,0,0), (0,1,0), (0,0,1))
    (sx, sy, sz) = standard
    unitvectors = []

    for rotation in ROTATIONS
        unitvector = (
            rotabout_xyz(sx..., rotation...),
            rotabout_xyz(sy..., rotation...),
            rotabout_xyz(sz..., rotation...),
        )
        push!(unitvectors, unitvector)
    end
    unitvectors
end

# Translate the location of a given beacon using another basis vector. This is
# basically just a matrix right multiply:
# https://cseweb.ucsd.edu/classes/wi18/cse167-a/lec3.pdf
function translate(beacon::Beacon, basis::Basis)
    (bx1, by1, bz1) = basis[1]
    (bx2, by2, bz2) = basis[2]
    (bx3, by3, bz3) = basis[3]
    (x, y, z) = beacon

    newx = x*bx1 + y*by1 + z*bz1
    newy = x*bx2 + y*by2 + z*bz2
    newz = x*bx3 + y*by3 + z*bz3

	return (newx, newy, newz)
end

# Translate all the beacon locations for one scanner to what their locations
# would be if the scanner had a different facing.
function translate(scanner::Scanner, basis::Basis) 
    return Set(translate(beacon, basis) for beacon in scanner)
end

# Identify the beacons detected in common between two scanners. This is a pretty
# intensive process:
# - For each possible scanner facing...
#   - Translate all the `Beacon`s for Scanner `b` to the given facing
#   - For each combination of a `Beacon` detected by Scanner `a` and a `Beacon`
#     detected by Scanner `b`...
#     - Calculate the distance between the `Beacon` from `a` and the `Beacon`
#       from `b`, called `offset`
#     - Add the `offset` to all the `Beacon` locations from Scanner `b`
#     - Check how many of the offset Beacons from Scanner `b` are matched by a 
#       Beacon detected by Scanner `a`
#     - If 12 or more beacon locations match, then we have determined the
#       relative location of Scanner `b` from Scanner `a`
function incommon(a::Scanner, b::Scanner)
    for basis in BASES
        translated_b = translate(b, basis)
        for (a_beacon, b_beacon) in Iterators.product(a, translated_b)
            offset = a_beacon .- b_beacon
            shifted_b = Set(beacon .+ offset for beacon in translated_b)
            length(a ∩ shifted_b) >= 12 && return (shifted_b, offset)
        end
    end
    return Iterators.repeated(nothing)
end


# To map all the Scanners, we check each Scanner against every other Scanner, 
# adding scanners to `mapped` when we identify (and apply) the appropriate
# offset of between the two scanners.
function mapscanners(scanners)
    mapped = Dict(0 => scanners[0])
    offsets = [(0,0,0)]
    searched = Set()

    while length(setdiff(keys(scanners), keys(mapped))) > 0
        for id1 in keys(scanners)
            (id1 ∈ searched || id1 ∉ keys(mapped)) && continue

            for (id2, scanner2) in scanners
                (id2 ∈ keys(mapped) || id1 == id2) && continue
                (common, offset) = incommon(mapped[id1], scanner2)

                if !isnothing(common)
                    mapped[id2] = common
                    push!(offsets, offset)
                end
            end

            push!(searched, id1)
        end
    end
    return (mapped, offsets)
end


# Solve Part One ---------------------------------------------------------------

# Given the mapping of scanners from `mapscanners()`, count the total number of
# beacons. Since they've all been translated and offset relative to the initial
# scanner, this just means union-reducing the sets of beacons.
function part1(mapped)
    allbeacons = reduce(∪, values(mapped))
    return length(allbeacons)
end

# Solve Part Two ---------------------------------------------------------------

# Calculate the manhattan distance between two beacons
distance(a::Beacon, b::Beacon) = mapreduce(abs, +, a .- b)

# Given the offsets from `mapbeacons()`, calculate the manhattan distance between
# all pairs of offsets and return the largest value.
function part2(offsets)
    maxdistance = 0
    for (offset1, offset2) in Iterators.product(offsets, offsets)
        distance = mapreduce(abs, +, offset1 .- offset2)
        maxdistance = max(maxdistance, distance)
    end
    return maxdistance
end

# 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

# 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

# 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

# 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

# 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

# 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