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.

In this article I'll be solving: Advent of code 2021: Day #16.

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 int = u64::from_str_radix(&s, 16).unwrap();
    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 _c = cursor.read_exact(&mut buf);
    let version = str::from_utf8(&buf).unwrap();
    u64::from_str_radix(&version, 2).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 _c = cursor.read_exact(&mut buf);
        let version = str::from_utf8(&buf).unwrap();

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

        if &version[..1] == "0" {
            break;
        }
    }
    u64::from_str_radix(&total, 2).unwrap()
}

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) {
    let version = read_ahead(cursor, 3);
    let type_id = read_ahead(cursor, 3);

    *counter += version;

    if type_id == 4 {
        let _value = read_literal_value(cursor);
    } else {
        let type_length_id = read_ahead(cursor, 1);

        if type_length_id == 0 {
            let total_length = read_ahead(cursor, 15);
            parse_with_read_limit(cursor, total_length, counter);
        } else if type_length_id == 1 {
            let number_of_packs = read_ahead(cursor, 11);
            parse_with_packet_limit(cursor, number_of_packs, counter);
        }
    }
}

fn parse_with_read_limit(
    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:

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):

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.

17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1