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

aoc/year2021/
day16.rs
