Advent of Code 2021 - Day 16: Packet Decoder

packet_decoder.rs

use std::collections::VecDeque;

fn main() {
    let transmission = "20546C8802538E136091C1802689BCD7DA45948D319D1B100747A009C97696E8B4ABFCA6AB8F4F26C401964A6271C80F802D392C01CEDDCE6E5CB829802F600A00021B14E34C361006E0AC418BB2CA6800BE4599BB6A73507002A52BEEB14D201802F600849E64D3369D37C74100866785B3D0ADFD8E601E5EB9DE2366D93ECB8B040142CB8ACE07CCB5CF34CA89380410B6134CE6FEF104A2B200243396976A00401A45004313D68435DBDDDA61CE6428C01491AEBF0C7E580AE00CCC401B86514216880370EE3443D2013DF003750004361343D88800084C4C8B116A679018300740010C8571BA32080350DA0D42800043A3044189AE0174B314D76E1F3ACF3BDAE3EE7298FF134002EF9DBCD0644127E3CAE7FCBA9A80393544F9A927C973DF1A500965A5CEA94C4DDA5658B94C6C3002A798A629CF21280532BAB4F4C7271E45EE6E71D8143A9BC7948804AB94D1D6006AC200EC1E8A10C00010985316A35C3620061E641644D661A4C012993E99208FC60097802F28F528F738606008CA47205400814C89CC8890064D400AB4BE0A66F2BF253E73AE8401424A7BFB16C0037E06CE0641E0013B08010A8930CE2B980351161DC3730066274188B020054A5E16965940057895ADEB5BF56A635ADE2354191D70566273A6F5B078266008D8022200D46E8291C4401A8CF0CE33CEDE55E9F9802BA00B4BD44A5EA2D10CC00B40316800BAE1003580A6D6026F00090E50024007C9500258068850035C00A4012ED8040B400D71002AF500284009700226336CA4980471D655E25D4650888023AB00525CAE5CBA5E428600BE003993778CB4732996E9887AE3F311C291004BD37517C0041E780A7808802AF8C1C00D0CDBE4ACAD69B3B004E13BDF23CAE7368C9F62448F64546008E0034F3720192A67AD9254917454200DCE801C99ADF182575BBAACAC7F8580";

    let mut reader = BitReader::from(transmission);
    let packet = parse_packet(&mut reader);

    println!("Sum of packet versions: {}", packet.sum_versions());
    println!("Evaluated BITS transmission: {}", packet.evaluate());
}

struct BitReader {
    bytes: VecDeque<u8>,
    bits: u64,
    bits_len: usize,
    bits_read: usize,
}

impl From<&str> for BitReader {
    fn from(hex: &str) -> Self {
        let digits = hex
            .chars()
            .map(|c| c.to_digit(16).unwrap())
            .collect::<Vec<_>>();
        Self {
            bytes: digits
                .chunks_exact(2)
                .map(|w| (w[0] << 4 | w[1]) as u8)
                .collect(),
            bits: 0,
            bits_len: 0,
            bits_read: 0,
        }
    }
}

impl BitReader {
    fn read(&mut self, bits: usize) -> u64 {
        while self.bits_len < bits {
            self.bits <<= 8;
            self.bits |= self.bytes.pop_front().unwrap() as u64;
            self.bits_len += 8;
        }

        let mut result = self.bits;
        result >>= self.bits_len - bits;
        result &= 2u64.pow(bits as u32) - 1;

        self.bits_len -= bits;
        self.bits_read += bits as usize;

        result
    }

    fn pos(&self) -> usize {
        self.bits_read
    }
}

enum Operation {
    Sum,
    Product,
    Minimum,
    Maximum,
    GreaterThan,
    LessThan,
    EqualTo,
}

impl From<u64> for Operation {
    fn from(packet_type: u64) -> Self {
        match packet_type {
            0 => Operation::Sum,
            1 => Operation::Product,
            2 => Operation::Minimum,
            3 => Operation::Maximum,
            5 => Operation::GreaterThan,
            6 => Operation::LessThan,
            7 => Operation::EqualTo,
            _ => panic!("Unrecognised operation!"),
        }
    }
}

enum PacketContents {
    Literal(u64),
    Operator(Operation, Vec<Packet>),
}

struct Packet {
    version: u64,
    contents: PacketContents,
}

impl Packet {
    fn sum_versions(&self) -> u64 {
        self.version
            + match &self.contents {
                PacketContents::Literal(_) => 0,
                PacketContents::Operator(_, operands) => {
                    operands.iter().map(|o| o.sum_versions()).sum()
                }
            }
    }

    fn evaluate(&self) -> u64 {
        match &self.contents {
            PacketContents::Literal(value) => *value,
            PacketContents::Operator(operation, operands) => match operation {
                Operation::Sum => operands.iter().map(|o| o.evaluate()).sum(),
                Operation::Product => operands.iter().fold(1, |product, o| product * o.evaluate()),
                Operation::Minimum => operands.iter().map(|o| o.evaluate()).min().unwrap(),
                Operation::Maximum => operands.iter().map(|o| o.evaluate()).max().unwrap(),
                Operation::GreaterThan => (operands[0].evaluate() > operands[1].evaluate()) as u64,
                Operation::LessThan => (operands[0].evaluate() < operands[1].evaluate()) as u64,
                Operation::EqualTo => (operands[0].evaluate() == operands[1].evaluate()) as u64,
            },
        }
    }
}

fn parse_packet(reader: &mut BitReader) -> Packet {
    let version = reader.read(3);
    let packet_type = reader.read(3);

    let contents = match packet_type {
        4 => parse_literal(reader),
        _ => PacketContents::Operator(Operation::from(packet_type), parse_operands(reader)),
    };

    Packet { version, contents }
}

fn parse_literal(reader: &mut BitReader) -> PacketContents {
    let mut value = 0;

    loop {
        let bits = reader.read(5);

        value <<= 4;
        value |= bits & 0b01111;

        if bits & 0b10000 == 0 {
            break;
        }
    }

    PacketContents::Literal(value as u64)
}

fn parse_operands(reader: &mut BitReader) -> Vec<Packet> {
    let length_type = reader.read(1);

    match length_type {
        0 => {
            let length = reader.read(15) as usize;
            parse_sequence_by_length(reader, length)
        }
        1 => {
            let count = reader.read(11) as usize;
            parse_sequence_by_count(reader, count)
        }
        _ => panic!("Invalid length type!"),
    }
}

fn parse_sequence_by_length(reader: &mut BitReader, length: usize) -> Vec<Packet> {
    let mut packets = Vec::new();

    let start_pos = reader.pos();

    while reader.pos() - start_pos != length {
        packets.push(parse_packet(reader));
    }

    packets
}

fn parse_sequence_by_count(reader: &mut BitReader, count: usize) -> Vec<Packet> {
    let mut packets = Vec::new();

    while packets.len() != count {
        packets.push(parse_packet(reader));
    }

    packets
}