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

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)

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
struct Operator <: Packet

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

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

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

    return packet

# 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))
    return todecimal(valuebits)

# 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))
    return packets

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

# 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))
    return packets

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

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

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 `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")

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

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!

comments powered by Disqus