다시 그 시간입니다! 작년과 마찬가지로 Advent of Code 퍼즐에 대한 솔루션을 게시할 예정입니다. 올해는 Julia의 퍼즐을 풀 것입니다. 내 솔루션과 코드를 GitHub에도 게시하겠습니다. 저는 작년에 AoC를 처음에는 R로, 그 다음에는 Rust를 배우기 위한 일련의 연습 문제로 정말 신나게 보냈습니다. 그래서 올해의 퍼즐이 무엇을 가져올지 정말 기대됩니다. 아직 AoC를 사용해보지 않았다면 저와 함께 시도해 보시기 바랍니다!

16일차 - 패킷 디코더

문제 설명을 찾습니다HERE.

입력 - 비트로 읽기

오늘의 퍼즐에 대한 우리의 입력은 긴 16진수 문자열의 형태로 우리에게 다가오고, 우리는 그것을 비트 단위로 분석해야 한다는 말을 들었습니다. 따라서 입력 구문 분석은 16진수 문자열을 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)
end

주목해야 할 한 가지 중요한 점은 BitVector가 역순으로 되어 첫 번째 16진수 문자의 비트가 BitVector의 끝에 있다는 것입니다. 이렇게 하면 처리할 때 끝에서 비트pop!()를 얻을 수 있습니다.

1부 - 패킷 인

이것은 우리가 수신하고 있는 정말 중요한 메시지임에 틀림없으며 가능한 가장 작은 전송, 즉 인코딩에 압축되어야 하는 정보로 가득 차 있습니다. 엘프들이 말해야 했던 것을 볼 수 있도록 해독 작업을 시작합시다! 여기에는 상당한 양의 코드가 포함되어 있지만 주석이 도움이 될 것입니다.

# 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

좋아요, 흥미롭네요... 메시지에 단일Operator 패킷이 포함된 것 같습니다. 이 '작업'이 무엇인지 궁금합니다. 정말 복잡한 메시지여야 합니다. 그것이 무엇인지 알아낼 수 있는지 봅시다.

파트 2 - 부드러운 연산자

'연산'은 수학적 연산입니다. 그래서 메시지는…숫자? 이상하게도 16진수로 직접 인코딩되었을 수 있는 것 같습니다. 음, 그것이 무엇인지 알아봅시다!

# 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

나는 기능 파견을 너무 좋아합니다. 각 Operator 패킷의 유형을 좀 더 구체적인 것으로 변경하여 eval() 함수의 동작을 조정할 수 있어 매우 멋진 코드가 생성됩니다.

마무리

이것은 정말 재미있는 날이었습니다. 특히 '벡터 끝에서 비트 팝' 전략에 대해 영리하다고 느꼈습니다. 이것이 Julia에게 해당되는지 100% 확신할 수는 없지만 일반적으로 벡터의 끝에서 항목을 추가/제거하는 것이 처음부터 추가/제거하는 것보다 계산적으로 더 효율적이라는 것을 알고 있습니다. - 할당합니다. Julia의 구문 및 유형 기반 함수 디스패치에 의해 권장되는 작은 유틸리티 함수는 정말 우아한 코드를 생성합니다.

다른 솔루션을 찾았거나 내 솔루션 중 하나에서 실수를 발견한 경우 저에게 연락해 주세요!