aoc/year2021/
day16.rs

1//! # Packet Decoder
2//!
3//! [`BitStream`] is the key to making this problem tractable. It works like an iterator, allowing
4//! us to consume an arbitrary number of bits from the input and convert this to a number.
5//!
6//! It works by maintaining an internal `u64` buffer. If the requested number of bits is larger than
7//! the buffer's current size then additional bits are added to the buffer 4 at a time from each
8//! hexadecimal digit of the input data.
9//!
10//! Additionally, it keeps track of the total number of bits consumed so far. This is needed when
11//! parsing packets that use the total length in bits to determine sub-packets.
12//!
13//! The decoded packet data is stored as a tree-like struct allowing recursive solutions to part one
14//! and part two to reuse the same decoded input.
15use std::str::Bytes;
16
17use crate::util::parse::*;
18
19struct BitStream<'a> {
20    available: u64,
21    bits: u64,
22    read: u64,
23    iter: Bytes<'a>,
24}
25
26impl BitStream<'_> {
27    fn from(s: &str) -> BitStream<'_> {
28        BitStream { available: 0, bits: 0, read: 0, iter: s.bytes() }
29    }
30
31    fn next(&mut self, amount: u64) -> u64 {
32        while self.available < amount {
33            self.available += 4;
34            self.bits = (self.bits << 4) | self.hex_to_binary();
35        }
36
37        self.available -= amount;
38        self.read += amount;
39
40        let mask = (1 << amount) - 1;
41        (self.bits >> self.available) & mask
42    }
43
44    fn hex_to_binary(&mut self) -> u64 {
45        let b = self.iter.next().unwrap();
46        if b.is_ascii_digit() { b.to_decimal() } else { u64::from(b - b'A' + 10) }
47    }
48}
49
50pub enum Packet {
51    Literal { version: u64, value: u64 },
52    Operator { version: u64, type_id: u64, packets: Vec<Self> },
53}
54
55impl Packet {
56    fn from(bit_stream: &mut BitStream<'_>) -> Self {
57        let version = bit_stream.next(3);
58        let type_id = bit_stream.next(3);
59
60        if type_id == 4 {
61            let mut todo = true;
62            let mut value = 0;
63
64            while todo {
65                todo = bit_stream.next(1) == 1;
66                value = (value << 4) | bit_stream.next(4);
67            }
68
69            Self::Literal { version, value }
70        } else {
71            let mut packets = Vec::new();
72
73            if bit_stream.next(1) == 0 {
74                let target = bit_stream.next(15) + bit_stream.read;
75                while bit_stream.read < target {
76                    packets.push(Self::from(bit_stream));
77                }
78            } else {
79                let sub_packets = bit_stream.next(11);
80                for _ in 0..sub_packets {
81                    packets.push(Self::from(bit_stream));
82                }
83            }
84
85            Self::Operator { version, type_id, packets }
86        }
87    }
88}
89
90pub fn parse(input: &str) -> Packet {
91    let mut bit_stream = BitStream::from(input);
92    Packet::from(&mut bit_stream)
93}
94
95pub fn part1(packet: &Packet) -> u64 {
96    match packet {
97        Packet::Literal { version, .. } => *version,
98        Packet::Operator { version, packets, .. } => {
99            *version + packets.iter().map(part1).sum::<u64>()
100        }
101    }
102}
103
104pub fn part2(packet: &Packet) -> u64 {
105    match packet {
106        Packet::Literal { value, .. } => *value,
107        Packet::Operator { type_id, packets, .. } => {
108            let mut iter = packets.iter().map(part2);
109            match type_id {
110                0 => iter.sum(),
111                1 => iter.product(),
112                2 => iter.min().unwrap(),
113                3 => iter.max().unwrap(),
114                5 => u64::from(iter.next().unwrap() > iter.next().unwrap()),
115                6 => u64::from(iter.next().unwrap() < iter.next().unwrap()),
116                7 => u64::from(iter.next().unwrap() == iter.next().unwrap()),
117                _ => unreachable!(),
118            }
119        }
120    }
121}
aoc/year2021/day16.rs

aoc/year2021/
day16.rs
