# Advent of Code 2021 - Day 16

By Eric Burden | December 17, 2021

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 16 - Packet Decoder

Find the problem description HERE.

## The Input - Read to Bits

Our input for today’s puzzle comes to us in the form of a long string of hexadecimal characters, and we’re told we’ll need to analyze it bit-by-bit, as it were. So, our input parsing converts the hex string into a BitVector.

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

bytes2bits(bytes) = BitVector(mapreduce(byte2bits, vcat, reverse(bytes)))
const hex2bits = bytes2bits ∘ hex2bytes

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

function ingest(path)
end


One important thing to note is that the BitVector will be in reverse order, such that the bits for the first hex character will be at the end of the BitVector. This will allow us to pop!() bits from the end as we process them.

## Part One - Packet In

This must be a really important message we’re receiving, full of information that needed to be packed into the smallest possible transmission, hence the encoding. Let’s get to work decoding it so we can see what the elves had to say! There’s a fair amount of code involved here, but the comments should help.

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


Ok, interesting… It looks like our message contains a single Operator packet. I wonder what these ‘operations’ are? Must be a really complicated message. Let’s see if we can figure out what it is.

## Part Two - Smooth Operator

Turns out the ‘operations’ are mathematical operations. So, the message is a…number? Odd, seems like that could have been encoded in hex directly. Oh well, let’s figure out what it is!

# 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 Literals, 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. Literals 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
# Packets, 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


I love function dispatching so much. By changing the Type of each Operator packet to something a bit more specific, we’re able to adjust the behavior of the eval() function, which results in some incredibly nice-looking code.

# Wrap Up

This was a really fun day. I felt particularly clever for the ‘pop bits from the end of the vector’ strategy. I’m not 100% sure if this holds true for Julia, but in general I know that adding/removing items from the end of a vector is more computationally efficient than adding/removing from the beginning, since we don’t need to re-allocate. The small utility functions that are encouraged by Julia’s syntax and Type-based function dispatch really results in some elegant code.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!