Advent of code 2021: Day 16

This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.

Part 1

Feel free to read the puzzle text yourself, because it’s quite the book to read. The input is a hexadecimal number, which needs to be converted to binary in a very specific way. The binary contains a packet, which itself contains many packets. The data-structure is: packets within packets within packets within a packet (did anybody say recursion?). The first part is to parse the entire hierarchy of the packet structure and sum all the version numbers (bits 0 till 3 of a packet).

Initially, I began by taking the hexadecimal string and turning it into a binary. According to the puzzle, each hexadecimal character needs to be transformed into a 4-bits binary:

``````let mut start = String::from("");

for b in bytes {
if b < &11 { continue };
let s = format!("{}", *b as char);
let binary = format!("{:04b}", int);

start.push_str(&binary);
}
``````

Next up I started taking string slices, like such:

``````let version = &binary_string[0..3];
let type_id = &binary_string[3..6];
// etc.
``````

However, this becomes very tedious when 11 or 15 bits have to be read consecutively. If only Rust had some sort of `StringIO`? It turns out it does, it is called `Cursor` in Rust. With `Cursor` I was able to parse the entire structure rather easily. First I defined a `read_ahead` method, which was able to move the cursor ahead a bunch of bytes, and turn said buffer into an integer (which is what needed to happen most of the reads):

``````fn read_ahead(cursor: &mut Cursor<String>, bytes: usize) -> u64 {
let mut buf = vec![0; bytes];
let version = str::from_utf8(&buf).unwrap();
}
``````

Another little read-method I needed was one which could parse literal values, which are packets with `type_id` 4. Feel free to look up what that means in the original puzzle text, but here is how that functions:

``````fn read_literal_value(cursor: &mut Cursor<String>) -> u64 {
let mut total = String::new();
loop {
let mut buf = vec![0; 5];
let version = str::from_utf8(&buf).unwrap();

total.push_str(&version[1..5]);

if &version[..1] == "0" {
break;
}
}
}
``````

Next up I needed, a parse-method which can parse the full structure, with all its quirks and little edge-cases:

``````pub fn parse(cursor: &mut Cursor<String>, counter: &mut u64) {

*counter += version;

if type_id == 4 {
} else {

if type_length_id == 0 {
} else if type_length_id == 1 {
parse_with_packet_limit(cursor, number_of_packs, counter);
}
}
}

cursor: &mut Cursor<String>,
limit: u64,
counter: &mut u64
) {
let curr_poss = cursor.position();
let limit = curr_poss + limit;

while cursor.position() < limit {
parse(cursor, counter);
}
}

fn parse_with_packet_limit(
cursor: &mut Cursor<String>,
limit: u64,
counter: &mut u64
) {
let mut count = 0;

while count < limit {
parse(cursor, counter);
count += 1;
}
}
``````

To successfully resolve part 1 of this adventure:

``````let bytes = display_string.as_bytes();
let mut cursor = bytes_to_bin(&bytes);
let mut counter = 0;
p1::parse(&mut cursor, &mut counter);
println!("The sum of version numbers is: {}", counter);
``````

The first part was quite a lot of reading, but nothing too hard. I did learn how to use `Cursor` in Rust and how to deal with a thing I know as `StringIO` in Ruby.

Part 2

This is where things get really, really juicy. It turns out that packets have `types`. In part 1 we already touched upon packets of type 4, which meant they were literal values, but in part 2 we get to learn what the others do. There are in total 8 types of operation packets (feel free to look up in the original puzzle text what each operation packet type is supposed to represent). The operation packets each execute a different operation on their sub-packets. The way to resolve this puzzle is as follows:

• Make a tree-structure of all the packets
• Recursively collapse each branch of operation-packets with literal value packets as direct descendants.

One little problem: I have to do this in Rust. Rust is one of the most memory-safe languages out there and will throw a tantrum - and rightfully so - when your code is not memory safe. To make a tree in Rust; I wasn’t sure if I was ready for that one just yet, but I gave it a try. After some research online (and finding many copied articles of other articles, I found a tree structure that I could reasonably use):

``````#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Instruction {
No,
Number(u64),
Op(u64)
}

#[derive(Debug)]
pub struct Node {
children: Vec<Rc<RefCell<Node>>>,
instruction: Instruction
}
``````

The first trick is extending the code from part 1 and creating an entire tree out of it. The second trick is collapsing the subtrees. The way I collapsed the tree I’ll explain next. Imagine you have just parsed your operation tree:

``````          9
/
+ - 8
/
max
\
* - 7
\
5
``````

The first trick is to find a node whose children are all “leaf”-nodes (and therefor numbers). The first node in my example which follows this rule is the +-node (the other being the *-node). To collapse this bit into a different tree, we need to parse it onto another tree. We can’t edit the existing tree because we’d have to change the parent-node (`max`), to which we don’t have access (thanks Rust). To visualize this process:

Step 1: Read the full tree we just parsed (incl. the root-node):

``````                 9
/
+ - 8
/
root - max
\
* - 7
\
5
``````

Step 2: Create a new tree, and step by step add nodes to it (in order of depth) until you reach a node where the children are all leafs. Execute the operation on those children as specified in the puzzle, and you’ll be left with this:

``````After step 1:

root

After step 2:

root - max

After step 3:

17
/
root - max
\
35
``````

Because there are no more nodes to loop over, the loop stops. Obviously, we have to repeat this cycle until we are left with `root - value`. That `value` is going to be the answer to part 2.

There’s a bit too much code to reasonably copy/paste around, so feel free to check the GitHub-link down below. I learned a lot about trees in Rust and how to collapse them onto different trees.

This was the hardest, yet most enjoyable Advent of code puzzle I encountered so far (I’m not looking at you Day 6). I claimed this star gladly.

The full solution is available on GitHub.