# 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 -------------------------------------------------------------

const TargetRange = @NamedTuple begin
    x_min::Int64
    x_max::Int64
    y_min::Int64
    y_max::Int64
end

function targetrange(vals::Vector{Int64})::TargetRange
    (x_min, x_max, y_min, y_max) = vals
    return (x_min=x_min, x_max=x_max, y_min=y_min, y_max=y_max)
end


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

function ingest(path)
    re = r"x=(-?\d+)\.\.(-?\d+), y=(-?\d+)\.\.(-?\d+)"
    m = match(re, readchomp(path))
    return targetrange([parse(Int, i) for i in m.captures])
end

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

# I find it helpful to name my Types according to their use. 
const Velocity = @NamedTuple{x::Int64, y::Int64}
const Position = @NamedTuple{x::Int64, y::Int64}
const VelocityRange = @NamedTuple{x::UnitRange{Int64}, y::StepRange{Int64,Int64}}

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

# These little functions do a lot of work. 
# - `triangle()` returns the `nth` triangle number (or Gaussian sum), the sum of
#   the sequence of numbers up to and including `n`.
# - `distanceat()` calculates the distance traveled for a given velocity of `V`
#   at time `T`. Because the puzzle description indicates that velocity degrades
#   at a constant rate over time, the general formula for distance is
#   `position at time T = (initial velocity x T) - loss in velocity`, where the
#   loss in velocity at any given time is the sum of all the prior losses.
# - `peak()` returns the maximum distance traveled for initial velocity `V₀`.
#   This corresponds to the distance when the time matches the initial velocity,
#   after which the accumulated velocity loss is larger than `V₀ × T`.
triangle(n)       = (n^2 + n) ÷ 2
distanceat(V₀, T) = (V₀ * T) - triangle(T - 1)
peak(V₀)          =  distanceat(V₀, V₀)

# Given an initial velocity and a time, calculate the position of the launched
# probe at `time`. In the x-direction, this is either the distance at `time`, or
# the peak distance if `time` is greater than the initial velocity (the probe
# will not travel backwards once it reaches peak distance).
function positionat(initial::Velocity, time::Int64)::Position
    (v_x0, v_y0) = initial
    p_yt = distanceat(v_y0, time)
    p_xt = time >= v_x0 ? peak(v_x0) : distanceat(v_x0, time)
    return (x=p_xt, y=p_yt)
end

# Identify the possible initial x and y velocities for a given `target`.
function velocityrange(target::TargetRange)::VelocityRange
    # The smallest possible x velocity that will reach the target is the
    # velocity where `triangle(v_x)` is at least equal to the minimum
    # range of x in the target. Any lower velocity that this will not reach
    # the distance of `target.x_min`. The maximum x velocity is just the
    # maximum range of x in the target, since the probe could theoretically
    # be shot straight at that point.
    v_xmin = 0
    while triangle(v_xmin) < target.x_min; v_xmin += 1; end
    v_xrange = v_xmin:target.x_max

    # The largest possible y velocity is the one that, when reaching the point
    # of y == 0, will not overshoot the target on the next step. This works out
    # to be the absolute value of `target.y_min`. This range is given backwards,
    # since it is assumed that the maximum height will be found at larger values
    # for y velocity.
    v_ymax = abs(target.y_min)
    v_yrange = v_ymax:-1:target.y_min

    return (x=v_xrange, y = v_yrange)
end

# Given the initial velocity of a probe, determine whether that probe will land
# in the target zone. 
function willhit(initial::Velocity, target::TargetRange)::Bool
    # Starting at the initial position of 0, 0 and time 0
    (x_t, y_t) = (0, 0)
    time = 0

    # Check the position of the probe at subsequent times until it reaches a
    # position either to the right or below the target area. If, during this
    # search, the probe position is found to be within the target area, return
    # true. Otherwise, return false.
    while x_t <= target.x_max && y_t >= target.y_min
        x_t >= target.x_min && y_t <= target.y_max && return true
        (x_t, y_t) = positionat(initial, time)
        time += 1
    end
    return false
end

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

# Starting with the range of possible velocities, check each combination of 
# x and y velocities until an x/y velocity is found that lands in the target
# area. Since we're counting down from the maximum possible y velocity, the
# first probe we find that lands in the target will reach the maximum 
# height, so just return the peak of that y velocity.
function part1(input)
    v_range = velocityrange(input)

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        willhit(initial, input) && return peak(v_y)
    end
    error("Could not find maximum Y for $input")
end

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

# This time, just search through the whole range of possible x/y combinations
# and increment the counter for each launch velocity that lands the probe in
# the target area.
function part2(input)
    v_range = velocityrange(input)
    found = 0

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        if willhit(initial, input)
            found += 1
        end
    end

    return found
end

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

const TargetRange = @NamedTuple begin
    x_min::Int64
    x_max::Int64
    y_min::Int64
    y_max::Int64
end

function targetrange(vals::Vector{Int64})::TargetRange
    (x_min, x_max, y_min, y_max) = vals
    return (x_min=x_min, x_max=x_max, y_min=y_min, y_max=y_max)
end


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

function ingest(path)
    re = r"x=(-?\d+)\.\.(-?\d+), y=(-?\d+)\.\.(-?\d+)"
    m = match(re, readchomp(path))
    return targetrange([parse(Int, i) for i in m.captures])
end

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

# I find it helpful to name my Types according to their use. 
const Velocity = @NamedTuple{x::Int64, y::Int64}
const Position = @NamedTuple{x::Int64, y::Int64}
const VelocityRange = @NamedTuple{x::UnitRange{Int64}, y::StepRange{Int64,Int64}}

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

# These little functions do a lot of work. 
# - `triangle()` returns the `nth` triangle number (or Gaussian sum), the sum of
#   the sequence of numbers up to and including `n`.
# - `distanceat()` calculates the distance traveled for a given velocity of `V`
#   at time `T`. Because the puzzle description indicates that velocity degrades
#   at a constant rate over time, the general formula for distance is
#   `position at time T = (initial velocity x T) - loss in velocity`, where the
#   loss in velocity at any given time is the sum of all the prior losses.
# - `peak()` returns the maximum distance traveled for initial velocity `V₀`.
#   This corresponds to the distance when the time matches the initial velocity,
#   after which the accumulated velocity loss is larger than `V₀ × T`.
triangle(n)       = (n^2 + n) ÷ 2
distanceat(V₀, T) = (V₀ * T) - triangle(T - 1)
peak(V₀)          =  distanceat(V₀, V₀)

# Given an initial velocity and a time, calculate the position of the launched
# probe at `time`. In the x-direction, this is either the distance at `time`, or
# the peak distance if `time` is greater than the initial velocity (the probe
# will not travel backwards once it reaches peak distance).
function positionat(initial::Velocity, time::Int64)::Position
    (v_x0, v_y0) = initial
    p_yt = distanceat(v_y0, time)
    p_xt = time >= v_x0 ? peak(v_x0) : distanceat(v_x0, time)
    return (x=p_xt, y=p_yt)
end

# Identify the possible initial x and y velocities for a given `target`.
function velocityrange(target::TargetRange)::VelocityRange
    # The smallest possible x velocity that will reach the target is the
    # velocity where `triangle(v_x)` is at least equal to the minimum
    # range of x in the target. Any lower velocity that this will not reach
    # the distance of `target.x_min`. The maximum x velocity is just the
    # maximum range of x in the target, since the probe could theoretically
    # be shot straight at that point.
    v_xmin = 0
    while triangle(v_xmin) < target.x_min; v_xmin += 1; end
    v_xrange = v_xmin:target.x_max

    # The largest possible y velocity is the one that, when reaching the point
    # of y == 0, will not overshoot the target on the next step. This works out
    # to be the absolute value of `target.y_min`. This range is given backwards,
    # since it is assumed that the maximum height will be found at larger values
    # for y velocity.
    v_ymax = abs(target.y_min)
    v_yrange = v_ymax:-1:target.y_min

    return (x=v_xrange, y = v_yrange)
end

# Given the initial velocity of a probe, determine whether that probe will land
# in the target zone. 
function willhit(initial::Velocity, target::TargetRange)::Bool
    # Starting at the initial position of 0, 0 and time 0
    (x_t, y_t) = (0, 0)
    time = 0

    # Check the position of the probe at subsequent times until it reaches a
    # position either to the right or below the target area. If, during this
    # search, the probe position is found to be within the target area, return
    # true. Otherwise, return false.
    while x_t <= target.x_max && y_t >= target.y_min
        x_t >= target.x_min && y_t <= target.y_max && return true
        (x_t, y_t) = positionat(initial, time)
        time += 1
    end
    return false
end

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

# Starting with the range of possible velocities, check each combination of 
# x and y velocities until an x/y velocity is found that lands in the target
# area. Since we're counting down from the maximum possible y velocity, the
# first probe we find that lands in the target will reach the maximum 
# height, so just return the peak of that y velocity.
function part1(input)
    v_range = velocityrange(input)

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        willhit(initial, input) && return peak(v_y)
    end
    error("Could not find maximum Y for $input")
end

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

# This time, just search through the whole range of possible x/y combinations
# and increment the counter for each launch velocity that lands the probe in
# the target area.
function part2(input)
    v_range = velocityrange(input)
    found = 0

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        if willhit(initial, input)
            found += 1
        end
    end

    return found
end