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<Packet> },
51}
52
53impl Packet {
54    fn from(bit_stream: &mut BitStream<'_>) -> Packet {
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            Packet::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            Packet::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    fn helper(packet: &Packet) -> u64 {
95        match packet {
96            Packet::Literal { version, .. } => *version,
97            Packet::Operator { version, packets, .. } => {
98                *version + packets.iter().map(helper).sum::<u64>()
99            }
100        }
101    }
102
103    helper(packet)
104}
105
106pub fn part2(packet: &Packet) -> u64 {
107    fn helper(packet: &Packet) -> u64 {
108        match packet {
109            Packet::Literal { value, .. } => *value,
110            Packet::Operator { type_id, packets, .. } => {
111                let mut iter = packets.iter().map(helper);
112                match type_id {
113                    0 => iter.sum(),
114                    1 => iter.product(),
115                    2 => iter.min().unwrap(),
116                    3 => iter.max().unwrap(),
117                    5 => u64::from(iter.next().unwrap() > iter.next().unwrap()),
118                    6 => u64::from(iter.next().unwrap() < iter.next().unwrap()),
119                    7 => u64::from(iter.next().unwrap() == iter.next().unwrap()),
120                    _ => unreachable!(),
121                }
122            }
123        }
124    }
125
126    helper(packet)
127}
aoc/year2021/day16.rs

aoc/year2021/
day16.rs
