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

byte2bits(byte)   = digits(byte, base=2, pad=8)
bytes2bits(bytes) = BitVector(mapreduce(byte2bits, vcat, reverse(bytes)))
const hex2bits = bytes2bits ∘ hex2bytes
const read2bits = hex2bits ∘ readchomp


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

function ingest(path)
    return read2bits(path)
end

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

# Types for the different types of packets we might find
abstract type Packet end
struct Literal <: Packet
    version::Int
    value::Int
end
struct Operator <: Packet
    version::Int
    typeid::Int
    packets::Vector{Packet}
end

# Used in lieu of an enum for dispatching which strategy to use for
# parsing the sub-packets of an `Operator` packet.
abstract type SubPacketStrategy end
struct BitwiseStrategy    <: SubPacketStrategy end
struct PacketwiseStrategy <: SubPacketStrategy end


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

# Makes working with the input bits a lot nicer. Since the input bits are 
# arranged in reverse order, we can `pop!()`, to get the first bit and remove
# it from the bits vector. These helpers let us pop multiple bits from the
# bits vector (`popn!()`) or easily extract a decimal number from the end of
# the bits vector (`pop2dec!()`).
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))
popn!(x, n) = [pop!(x) for _ in 1:n]
pop2dec!(x, n) = todecimal(pop!(x) for _ in 1:n)

# Round a BitVector down to the nearest full byte, discarding extra bits. Each
# packet may have extra empty bits at the end, this helps to clean those off
# before searching for the next packet.
function roundtobytes!(bits::BitVector)
    targetlen = (length(bits) ÷ 8) * 8      # Number of bits in full bytes left
    bitstoremove = length(bits) - targetlen 
    popn!(bits, bitstoremove)
end

# Parse a packet off the end of the `bits` BitVector. Start pulling bits from
# the end and working backwards.
function nextpacket!(bits::BitVector; issubpacket = false)::Packet
    version = pop2dec!(bits, 3)
    typeid  = pop2dec!(bits, 3)

    # If the `typeid` is 4, it's a Literal packet. Otherwise, it's an Operator
    packet = if typeid == 4
        value = literalvalue!(bits)
        Literal(version, value)
    else
        # The 'length type ID' mentioned in the puzzle description is a single
        # bit, so either true or false. If it's `1` (true), then we know how
        # many sub-packets we have. Otherwise, we're given the number of bytes
        # in the sub-packets and have to parse from there.
        countingstrategy = pop!(bits) ? PacketwiseStrategy : BitwiseStrategy
        subpackets = subpackets!(countingstrategy, bits)
        Operator(version, typeid, subpackets)
    end

    # Round down to the nearest byte if we're not parsing a sub-packet
    issubpacket || roundtobytes!(bits)

    return packet
end

# The value for a Literal packet comes from the bits following the type ID. The
# bits for the value are split into 5-bit chunks, where the first bit indicates
# whether or not it's the last chunk, and the remaining 4 bits are concatenated
# to provide the binary representation of the final value.
function literalvalue!(bits::BitVector)::Int
    valuebits = BitVector()
    keepgoing = true
    while keepgoing
        keepgoing = pop!(bits)
        append!(valuebits, popn!(bits, 4))
    end
    return todecimal(valuebits)
end

# If we're using the `BitwiseStrategy` for parsing sub-packets (from the 
# 'length type ID' value), then we start by checking the total number 
# of bits left before we start, then parsing bits off the end until we've
# used up the number of bits specified in `bitstoread`.
function subpackets!(::Type{BitwiseStrategy}, bits::BitVector)::Vector{Packet}
    packets = Vector{Packet}()
    bitstoread = pop2dec!(bits, 15)     # Specified in the puzzle description
    bitstostart = length(bits)
    while (bitstostart - length(bits)) < bitstoread
        push!(packets, nextpacket!(bits, issubpacket = true))
    end
    return packets
end

# If we're using the `PacketwiseStrategy`, it means we were given the number of
# sub-packets to parse. So, we just pull that many sub-packets from the end
# of the bits vector. This seems like a superior encoding, honestly.
function subpackets!(::Type{PacketwiseStrategy}, bits::BitVector)::Vector{Packet}
    packetstoread = pop2dec!(bits, 11)  # Specified in the puzzle description
    return [nextpacket!(bits, issubpacket = true) for _ in 1:packetstoread]
end

# This function reads a sequence of packets from the input. Turns out, the 
# actual input is a single large `Operator` containing a bunch of
# sub-packets, so this isn't really necessary. I'm still leaving it in for
# educational purposes, but I don't use it either solution.
function topackets!(bits::BitVector)
    packets = Vector{Packet}()
    while !isempty(bits)
        push!(packets, nextpacket!(bits))
    end
    return packets
end

# Two different functions for summing the versions of a Packet. The sum of 
# versions for a `Literal` packet is just its version number. For an `Operator`, 
# we need to recursively check all the sub-packets and sum their versions.
sumversions(packet::Literal) = packet.version

function sumversions(packet::Operator)
    return packet.version + sum(sumversions(p) for p in packet.packets)
end


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

# Parse the one big packet from our input, then count the versions of all
# its sub-packets (and their sub-packets, and their sub-packets' sub-packets...)
function part1(input)
    bits = deepcopy(input)
    superpacket = nextpacket!(bits)
    return sumversions(superpacket)
end

# Multiple Dispatch! -----------------------------------------------------------

# A new sub-type of `Packet` for each of the Operator types. In a 'real' 
# application, I'd probably re-define Operator as an abstract type and
# sub-type from there. 
struct SumPacket  <: Packet version::Int; packets::Vector{Packet} end
struct ProdPacket <: Packet version::Int; packets::Vector{Packet} end
struct MinPacket  <: Packet version::Int; packets::Vector{Packet} end
struct MaxPacket  <: Packet version::Int; packets::Vector{Packet} end
struct GtPacket   <: Packet version::Int; packets::Vector{Packet} end
struct LtPacket   <: Packet version::Int; packets::Vector{Packet} end
struct EqPacket   <: Packet version::Int; packets::Vector{Packet} end

# Honestly, this is just single dispatch. Define a method for each type of
# Packet that evaluates its value. For `Literal`s, that's just the stored
# value and everything else is evaluated in terms of that.
eval(packet::Literal)    = packet.value
eval(packet::SumPacket)  = sum(eval(sub) for sub in packet.packets)
eval(packet::ProdPacket) = prod(eval(sub) for sub in packet.packets)
eval(packet::MinPacket)  = minimum(eval(sub) for sub in packet.packets)
eval(packet::MaxPacket)  = maximum(eval(sub) for sub in packet.packets)
eval(packet::GtPacket)   = eval(packet.packets[1]) >  eval(packet.packets[2])
eval(packet::LtPacket)   = eval(packet.packets[1]) <  eval(packet.packets[2])
eval(packet::EqPacket)   = eval(packet.packets[1]) == eval(packet.packets[2])

# We need to go back and classify the `Packets` from before according to their
# newly revealed `Operator` sub-type. `Literal`s stay the same.
classify(packet::Literal) = packet
function classify(packet::Operator)
    version = packet.version
    subpackets = [classify(sub) for sub in packet.packets]
    packet.typeid == 0 && return SumPacket(version, subpackets)
    packet.typeid == 1 && return ProdPacket(version, subpackets)
    packet.typeid == 2 && return MinPacket(version, subpackets)
    packet.typeid == 3 && return MaxPacket(version, subpackets)
    packet.typeid == 5 && return GtPacket(version, subpackets)
    packet.typeid == 6 && return LtPacket(version, subpackets)
    packet.typeid == 7 && return EqPacket(version, subpackets)
    error("Could not clasify $packet")
end


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

# Parse the superpacket from our input, identify the sub-types of all the 
# `Packet`s, and evaluate them. In an ideal world, we would have known about the
# `Operator` sub-types ahead of time and included that logic in our `nextpacket!()`
# function.
function part2(input)
    bits = deepcopy(input)
    superpacket = nextpacket!(bits)
    classified = classify(superpacket)
    return eval(classified)
end