After 15 days, puzzles are now becoming more and more complex.
Problem description
The input data is an hexadecimal code, representing a BITS (“Buoyancy Interchange Transmission System”, something invented just for the Advent of Code :-)) packet.
All Packets begin with a common header that includes :
- A version number (3 bits).
- A type identifier (3 bits).
According to the type identifier, we can have either a “value packet”, or an “operator packet”.
Value packets payload (after the header) encode an unsigned integer broken into 5-bit groups. These groups contain themselves a flag (1 bit) indicating if the group is the last, and 4 bits for the packet value.
Operator packets include a length field (1 bit for the length type ID, plus 15 bits indicating the total length of subpackets or 11 bits indicating the number of subpackets). Then follow the subpackets. Packets have an arborescent structure, where operator packets are non-terminal nodes, and value packets are leaves.
Part 1
The first task is to calculate the sum of all packet version numbers, to check if our “packet arborescence” is correct.
A little helper function makes the conversion from hexadecimal to an array of bits.
Bits are represented as u8, because this is the smallest integer type available in Rust).
pub fn hex2bin(hex: u8) -> Vec<u8> {
let mut bit_group = Vec::new();
let mut h = hex;
for _i in 0..4 {
bit_group.insert(0, h % 2);
h = h / 2;
}
bit_group
}
A second helper function transforms an array of bits into in unsigned integer.
pub fn bin2int(bits: &[u8]) -> usize {
let mut n = 0;
for i in 0..bits.len() {
n *= 2;
if bits[i] == 1 {
n += 1;
}
}
n
}
Then, let’s define a simple data structure to represent packets. An enumeration seems to be the best design.
In parameters, we only include the packet fields we need for parsing operations, and results calculations. For both packet types, the first parameter is the version id. The second parameter is the value encoded in the payload for “value packets”, and the list of subpackets for “operator packets”.
#[derive(Clone)]
pub enum Packet {
Value(usize, usize), /* version_id, value */
Operator(usize, Vec<Packet>)
}
Naturally, the parsing method and results calculation methods too are recursive.
The parsing method first extracts the version, and the type_id. Then it will either calculate the encoded value,
or calculate the subpackets total length or number before calling the parsing method (recursively)
with the remaining bits in parameter. The packet length must be returned alongside the Packet enumeration.
impl Packet {
pub fn parse(packet_bits: &[u8]) -> (Packet, usize) {
let version = bin2int(&packet_bits[0..3]);
let type_id = bin2int(&packet_bits[3..6]);
if type_id == 4 {
let mut value = 0;
let mut group_idx = 0;
loop {
value = value * 16 + bin2int(&packet_bits[7+5*group_idx..11+5*group_idx]);
if packet_bits[6+5*group_idx] == 0 {
break;
}
group_idx += 1;
}
(Packet::Value(version, value), 6 + 5 * (group_idx + 1))
}
else {
let mut subpackets = Vec::new();
let length_type_id = bin2int(&packet_bits[6..7]);
let mut header_len = 0;
let mut packet_length = 0;
if length_type_id == 0 {
header_len = 22;
let mut start = header_len;
let end = 22 + bin2int(&packet_bits[7..22]);
while start < end {
let (subpacket, length) = Packet::parse(&packet_bits[start..end]);
start += length;
packet_length += length;
subpackets.push(subpacket);
}
}
else if length_type_id == 1 {
header_len = 18;
let mut start = header_len;
for _i in 0..bin2int(&packet_bits[7..18]) {
let (subpacket, length) = Packet::parse(&packet_bits[start..]);
start += length;
packet_length += length;
subpackets.push(subpacket);
}
}
packet_length += header_len;
(Packet::Operator(version, &subpackets), packet_length)
}
}
}
The main function calls the parser method for the outermost packet, and returns the sum of all packets’ versions.
pub fn solve_part1(input: &Vec<String>) -> usize {
let mut packet_bits = Vec::new();
let line = input.iter().cloned().next().unwrap();
for i in 0..line.len() {
packet_bits.append(&mut hex2bin(u8::from_str_radix(&line[i..i+1], 16)
.expect("Hexadecimal digits must be in 0-9 or A-F")));
}
Packet::parse(&packet_bits[..]).0.sum()
}
More than 2 hours were necessary to solve this first part. Fortunately, the puzzle included many test cases, so I could confidently enter my answer after having validated all the tests.
Part 2
Now, additional information on the “BITS” protocol is given. Each type id for “operator packets” corresponds to a mathematical operator (sum, product, min, max and comparisons). The objective now is to evaluate the mathematical expression encoded in the packet.
The structure we defined in part 1 is modified accordingly.
#[derive(Clone, Debug)]
pub enum Packet {
Value(usize, usize), /* version_id, value */
OpAdd(usize, Vec<Packet>), /* version_id, subpackets */
OpMul(usize, Vec<Packet>),
OpMin(usize, Vec<Packet>),
OpMax(usize, Vec<Packet>),
OpGt(usize, Vec<Packet>),
OpLt(usize, Vec<Packet>),
OpEq(usize, Vec<Packet>)
}
The parsing method is almost unchanged. The only change is on the line (Packet::Operator(version, &subpackets), packet_length), replaced
by a call to the following helper function :
pub fn operator(version: usize, type_id: usize, subpackets: &Vec<Packet>) -> Packet {
let sub_clone = subpackets.clone();
match type_id {
0 => Packet::OpAdd(version, sub_clone),
1 => Packet::OpMul(version, sub_clone),
2 => Packet::OpMin(version, sub_clone),
3 => Packet::OpMax(version, sub_clone),
5 => Packet::OpGt(version, sub_clone),
6 => Packet::OpLt(version, sub_clone),
7 => Packet::OpEq(version, sub_clone),
_ => { panic!("This is not an operator"); }
}
}
Finally, we need an evaluation function.
This function returns an u64 and not an usize. Why ? Because the value of the
outermost packet is superior to , the greatest 32-bit unsigned integer. And as
usize has a length of 32 bits on some architectures, like the Raspberry Pi 3B that currently hosts this blog.
, our code would crash.
I recently noticed this problem in the code I wrote last year for the day 20 of the Advent of Code 2020. The code panics on my raspberry Pi due to an overflow For the anecdote, this is the kind of stupid bug that caused the first Ariane 5 rocket failure in 1996.
pub fn value(&self) -> u64 {
match self {
Packet::Value(_, v) => *v as u64,
Packet::OpAdd(_, sub) => sub.iter().map(|x| x.value()).sum::<u64>(),
Packet::OpMul(_, sub) => sub.iter().map(|x| x.value()).product::<u64>(),
Packet::OpMin(_, sub) => sub.iter().map(|x| x.value()).min().unwrap(),
Packet::OpMax(_, sub) => sub.iter().map(|x| x.value()).max().unwrap(),
Packet::OpGt(_, sub) => (sub[0].value() > sub[1].value()) as u64,
Packet::OpLt(_, sub) => (sub[1].value() > sub[0].value()) as u64,
Packet::OpEq(_, sub) => (sub[0].value() == sub[1].value()) as u64,
}
}
The main function is almost the same as in part 1.
pub fn solve_part2(input: &Vec<String>) -> u64 {
let mut packet_bits = Vec::new();
let line = input.iter().cloned().next().unwrap();
for i in 0..line.len() {
packet_bits.append(&mut hex2bin(u8::from_str_radix(&line[i..i+1], 16)
.expect("Hexadecimal digits must be in 0-9 or A-F")));
}
Packet::parse(&packet_bits[..]).0.value()
}
Again, many tests cases were given, covering all operators types. This made the debug much easier.