Day 16

Return to main page

Ah, yes, welcome to recursive function hell. I tend to hate these assignments because they are such a pain to debug. Today I compounded the issue by getting into a type overflow issues because I combined numpy mathematical operators with Python types. Note to self: do all numpy or all base Python. In the end it worked out, it is very similar to parsing headers of binary files and I have ample experience with that now.

Part 1

As you leave the cave and reach open waters, you receive a transmission from the Elves back on the ship.

The transmission was sent using the Buoyancy Interchange Transmission System (BITS), a method of packing numeric expressions into a binary sequence. Your submarine’s computer has saved the transmission in hexadecimal (your puzzle input).

The first step of decoding the message is to convert the hexadecimal representation into binary. Each character of hexadecimal corresponds to four bits of binary data:

0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
A = 1010
B = 1011
C = 1100
D = 1101
E = 1110
F = 1111

The BITS transmission contains a single packet at its outermost layer which itself contains many other packets. The hexadecimal representation of this packet might encode a few extra 0 bits at the end; these are not part of the transmission and should be ignored.

Every packet begins with a standard header: the first three bits encode the packet version, and the next three bits encode the packet type ID. These two values are numbers; all numbers encoded in any packet are represented as binary with the most significant bit first. For example, a version encoded as the binary sequence 100 represents the number 4.

Packets with type ID 4 represent a literal value. Literal value packets encode a single binary number. To do this, the binary number is padded with leading zeroes until its length is a multiple of four bits, and then it is broken into groups of four bits. Each group is prefixed by a 1 bit except the last group, which is prefixed by a 0 bit. These groups of five bits immediately follow the packet header. For example, the hexadecimal string D2FE28 becomes:

110100101111111000101000
VVVTTTAAAAABBBBBCCCCC

Below each bit is a label indicating its purpose:

So, this packet represents a literal value with binary representation 011111100101, which is 2021 in decimal.

Every other type of packet (any packet with a type ID other than 4) represent an operator that performs some calculation on one or more sub-packets contained within. Right now, the specific operations aren’t important; focus on parsing the hierarchy of sub-packets.

An operator packet contains one or more packets. To indicate which subsequent binary data represents its sub-packets, an operator packet can use one of two modes indicated by the bit immediately after the packet header; this is called the length type ID:

Finally, after the length type ID bit and the 15-bit or 11-bit field, the sub-packets appear.

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

After reading 11 and 16 bits of sub-packet data, the total length indicated in L (27) is reached, and so parsing of this packet stops.

As another example, here is an operator packet (hexadecimal string EE00D40C823060) with length type ID 1 that contains three sub-packets:

11101110000000001101010000001100100000100011000001100000
VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC

After reading 3 complete sub-packets, the number of sub-packets indicated in L (3) is reached, and so parsing of this packet stops.

For now, parse the hierarchy of the packets throughout the transmission and add up all of the version numbers.

Here are a few more examples of hexadecimal-encoded transmissions:

Decode the structure of your hexadecimal-encoded BITS transmission; what do you get if you add up the version numbers in all packets?

The main tricky thing is that Python will get rid of any leading zeros when converting to binary strings, e.g. 2 in hexidecimal notation will be 10 instead of 0010. As such I convert every character individually and use zfill to add back the leading zeros. Of course strip the empty spaces such as newlines first.

def _parse_data(self, input_data: str) -> Any:
    return "".join([bin(int(x, 16))[2:].zfill(4) for x in input_data.strip()])

In the end I combined all the logic into a single function that I use for both part 1 and part 2, a recursive parse_packet function. It first looks at the type and decides on the literal vs. operator branches. Then the tricky part of the exercise is that the operator part has two different behaviors, which need slightly different treatment: for the operator using bit length, you need to check whether the index exceeds the length. The operator that uses the number of subpackets is a bit simpler, you simply loop over the number.

def _solve_part1(self, parsed_data: Any) -> Any:
    return self._parse_packet(parsed_data, 0, 0)[1]

Part 2

Now that you have the structure of your transmission decoded, you can calculate the value of the expression it represents.

Literal values (type ID 4) represent a single number as described above. The remaining type IDs are more interesting:

Using these rules, you can now work out the value of the outermost packet in your BITS transmission.

For example:

What do you get if you evaluate the expression represented by your hexadecimal-encoded BITS transmission?

The main logic was in port 1, but still part 2 took me most time due to some stupid integer overflow with the numpy operators. After I switched to pure Python it worked out. The main addition is a simple list of if statements. Probably this could have been done nice with a dictionary and a map, but I didn’t feel like working on it anymore :).

def _solve_part2(self, parsed_data: Any) -> Any:
    return self._parse_packet(parsed_data, 0, 0)[2]

Return to main page