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
17struct BitStream<'a> {
18    available: u64,
19    bits: u64,
20    read: u64,
21    iter: Bytes<'a>,
22}
23
24impl BitStream<'_> {
25    fn from(s: &str) -> BitStream<'_> {
26        BitStream { available: 0, bits: 0, read: 0, iter: s.bytes() }
27    }
28
29    fn next(&mut self, amount: u64) -> u64 {
30        while self.available < amount {
31            self.available += 4;
32            self.bits = (self.bits << 4) | self.hex_to_binary();
33        }
34
35        self.available -= amount;
36        self.read += amount;
37
38        let mask = (1 << amount) - 1;
39        (self.bits >> self.available) & mask
40    }
41
42    fn hex_to_binary(&mut self) -> u64 {
43        let b = self.iter.next().unwrap();
44        u64::from(if b.is_ascii_digit() { b - b'0' } else { b - b'A' + 10 })
45    }
46}
47
48pub enum Packet {
49    Literal { version: u64, value: u64 },
50    Operator { version: u64, type_id: u64, packets: Vec<Self> },
51}
52
53impl Packet {
54    fn from(bit_stream: &mut BitStream<'_>) -> Self {
55        let version = bit_stream.next(3);
56        let type_id = bit_stream.next(3);
57
58        if type_id == 4 {
59            let mut todo = true;
60            let mut value = 0;
61
62            while todo {
63                todo = bit_stream.next(1) == 1;
64                value = (value << 4) | bit_stream.next(4);
65            }
66
67            Self::Literal { version, value }
68        } else {
69            let mut packets = Vec::new();
70
71            if bit_stream.next(1) == 0 {
72                let target = bit_stream.next(15) + bit_stream.read;
73                while bit_stream.read < target {
74                    packets.push(Self::from(bit_stream));
75                }
76            } else {
77                let sub_packets = bit_stream.next(11);
78                for _ in 0..sub_packets {
79                    packets.push(Self::from(bit_stream));
80                }
81            }
82
83            Self::Operator { version, type_id, packets }
84        }
85    }
86}
87
88pub fn parse(input: &str) -> Packet {
89    let mut bit_stream = BitStream::from(input);
90    Packet::from(&mut bit_stream)
91}
92
93pub fn part1(packet: &Packet) -> u64 {
94    match packet {
95        Packet::Literal { version, .. } => *version,
96        Packet::Operator { version, packets, .. } => {
97            *version + packets.iter().map(part1).sum::<u64>()
98        }
99    }
100}
101
102pub fn part2(packet: &Packet) -> u64 {
103    match packet {
104        Packet::Literal { value, .. } => *value,
105        Packet::Operator { type_id, packets, .. } => {
106            let mut iter = packets.iter().map(part2);
107            match type_id {
108                0 => iter.sum(),
109                1 => iter.product(),
110                2 => iter.min().unwrap(),
111                3 => iter.max().unwrap(),
112                5 => u64::from(iter.next().unwrap() > iter.next().unwrap()),
113                6 => u64::from(iter.next().unwrap() < iter.next().unwrap()),
114                7 => u64::from(iter.next().unwrap() == iter.next().unwrap()),
115                _ => unreachable!(),
116            }
117        }
118    }
119}
aoc/year2021/day16.rs

aoc/year2021/
day16.rs
