[Advent of Code 2021] Day 16

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:

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:

The three bits labeled V (110) are the packet version, 6.
The three bits labeled T (100) are the packet type ID, 4, which means the packet is a literal value.
The five bits labeled A (10111) start with a 1 (not the last group, keep reading) and contain the first four bits of the number, 0111.
The five bits labeled B (11110) start with a 1 (not the last group, keep reading) and contain four more bits of the number, 1110.
The five bits labeled C (00101) start with a 0 (last group, end of packet) and contain the last four bits of the number, 0101.
The three unlabeled 0 bits at the end are extra due to the hexadecimal representation and should be ignored.

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:

If the length type ID is 0, then the next 15 bits are a number that represents the total length in bits of the sub-packets contained by this packet.
If the length type ID is 1, then the next 11 bits are a number that represents the number of sub-packets immediately contained by this packet.

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

The three bits labeled V (001) are the packet version, 1.
The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

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

The three bits labeled V (111) are the packet version, 7.
The three bits labeled T (011) are the packet type ID, 3, which means the packet is an operator.
The bit labeled I (1) is the length type ID, which indicates that the length is a 11-bit number representing the number of sub-packets.
The 11 bits labeled L (00000000011) contain the number of sub-packets, 3.
The 11 bits labeled A contain the first sub-packet, a literal value representing the number 1.
The 11 bits labeled B contain the second sub-packet, a literal value representing the number 2.
The 11 bits labeled C contain the third sub-packet, a literal value representing the number 3.

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:

8A004A801A8002F478 represents an operator packet (version 4) which contains an operator packet (version 1) which contains an operator packet (version 5) which contains a literal value (version 6); this packet has a version sum of _16_.
620080001611562C8802118E34 represents an operator packet (version 3) which contains two sub-packets; each sub-packet is an operator packet that contains two literal values. This packet has a version sum of _12_.
C0015000016115A2E0802F182340 has the same structure as the previous example, but the outermost packet uses a different length type ID. This packet has a version sum of _23_.
A0016C880162017C3686B18A3D4780 is an operator packet that contains an operator packet that contains an operator packet that contains five literal values; it has a version sum of _31_.

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

Proposed solution: packets representing literals have a looped structure where the first bit in every 5 bits indicates whether it is the last block; operation packets can indicate either the number of sub-packets (immediately nested in the current packet) or the number of bytes of the sub-packets (all nested sub-packets); the idea is to keep a stack indicating this nesting of operator packets with the length_type and then the corresponding length

Time complexity: O(n)

Space complexity: O(n)

#!/usr/bin/env python3
from collections import deque
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

decode_table = {
    "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"
}

file_input = open(sys.argv[1], "r").read().strip().split("\n")
hex_string = file_input[0]
#print(hex_string)

bin_string = ""
for char in hex_string:
    bin_string += decode_table[char]
#print(bin_string)

Basic setup and creating the binary string

Another way to create the binary string is by using the built-in bin function after converting the hex string into an integer. Something like bin(int("deadbeef", 16))[2:].

i = 0
stack = deque()
version_total = 0
unbin = lambda x: int(x, 2)
while i < len(bin_string):
    if len(stack) != 0:
        if stack[-1][0] == 1:
            elem = stack.pop()
            if elem[1] > 1:
                stack.append((elem[0], elem[1]-1))
        else:
            if i == stack[-1][1]:
                stack.pop()
    if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        break
    version = unbin(bin_string[i:i+3])
    version_total += version
    type_id = unbin(bin_string[i+3:i+6])
    if type_id == 4:
        i += 6
        literal = ""
        while unbin(bin_string[i]) == 1:
            literal += bin_string[i+1:i+5]
            i += 5
        literal += bin_string[i+1:i+5]
        i += 5
        continue
    length_type = unbin(bin_string[i+6])
    if length_type:
        length = 11
        num_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, num_subpackets))
    else:
        length = 15
        length_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, i+7+length+length_subpackets))
    i += 7 + length

print("Version Total: {}".format(version_total))

This is just parsing logic

I constructed this just to count the version numbers and sum them together. Each step is just parsing until the binary string is completely enumerated while keeping a stack due to the nested nature of the packets.

    if len(stack) != 0:
        if stack[-1][0] == 1:
            elem = stack.pop()
            if elem[1] > 1:
                stack.append((elem[0], elem[1]-1))
        else:
            if i == stack[-1][1]:
                stack.pop()

Updating top of the stack

Each loop through the outer while loop goes through a single packet (not including respective sub-packets). This first block updates the top element of the stack. These elements in the stack are tuples with the first element being the length type (0 is for number of packets and 1 is for number of bits) and the second it the actual length. For number of packets, this length is decremented and placed back on the stack until the number of sub-packets reaches zero – then it is just popped off. For number of bits, this is actually pushed to the stack with the length + the starting position of the sub-packets which is effectively the end of the packet.

if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        break

Check for extra 0s padded at the end

If the iterator is not at the end of the bit string and the rest of the bin string is all 0s and smaller than the minimum packet length, just break out since this is just padding.

    version = unbin(bin_string[i:i+3])
    version_total += version
    type_id = unbin(bin_string[i+3:i+6])
    if type_id == 4:
        i += 6
        literal = ""
        while unbin(bin_string[i]) == 1:
            literal += bin_string[i+1:i+5]
            i += 5
        literal += bin_string[i+1:i+5]
        i += 5
        continue

Version, type, and processing literals

This first section parses the version, packet type, and if the packet type is a literal (has a value of 4) then, loop through blocks of 5 bits until hitting the last block.

    length_type = unbin(bin_string[i+6])
    if length_type:
        length = 11
        num_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, num_subpackets))
    else:
        length = 15
        length_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, i+7+length+length_subpackets))
    i += 7 + length

Operation packets and adding sub-packet information to the stack

The last block is for operation packets. Based on length-type, push the corresponding length value to the stack. Again, for bit length we calculate the end of the packet before pushing.

❯ python3 solution16.py input16
Version Total: 873

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:

Packets with type ID 0 are sum packets - their value is the sum of the values of their sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.
Packets with type ID 1 are product packets - their value is the result of multiplying together the values of their sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.
Packets with type ID 2 are minimum packets - their value is the minimum of the values of their sub-packets.
Packets with type ID 3 are maximum packets - their value is the maximum of the values of their sub-packets.
Packets with type ID 5 are greater than packets - their value is 1 if the value of the first sub-packet is greater than the value of the second sub-packet; otherwise, their value is 0. These packets always have exactly two sub-packets.
Packets with type ID 6 are less than packets - their value is 1 if the value of the first sub-packet is less than the value of the second sub-packet; otherwise, their value is 0. These packets always have exactly two sub-packets.
Packets with type ID 7 are equal to packets - their value is 1 if the value of the first sub-packet is equal to the value of the second sub-packet; otherwise, their value is 0. These packets always have exactly two sub-packets.

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

For example:

C200B40A82 finds the sum of 1 and 2, resulting in the value _3_.
04005AC33890 finds the product of 6 and 9, resulting in the value _54_.
880086C3E88112 finds the minimum of 7, 8, and 9, resulting in the value _7_.
CE00C43D881120 finds the maximum of 7, 8, and 9, resulting in the value _9_.
D8005AC2A8F0 produces 1, because 5 is less than 15.
F600BC2D8F produces 0, because 5 is not greater than 15.
9C005AC2F8F0 produces 0, because 5 is not equal to 15.
9C0141080250320F1802104A08 produces 1, because 1 + 3 = 2 * 2.

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

Proposed solution: same idea but now having to do actual calculations based on the literals and operation packets; we have to store more information for each operation packet on the stack (like the cumulative result and the number of bits already iterated over)

Time complexity: O(n)

Space complexity: O(n)

#!/usr/bin/env python3
from collections import deque
from math import prod
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

decode_table = {
    "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"
}

operator_map = {
    0: lambda x: sum(x),
    1: lambda x: prod(x),
    2: lambda x: min(x),
    3: lambda x: max(x),
    5: lambda x: int(x[0] > x[1]),
    6: lambda x: int(x[0] < x[1]),
    7: lambda x: int(x[0] == x[1])
}

file_input = open(sys.argv[1], "r").read().strip().split("\n")
hex_string = file_input[0]
#print(hex_string)

bin_string = ""
for char in hex_string:
    bin_string += decode_table[char]
#print(bin_string)

stack = deque()
unbin = lambda x: int(x, 2)
result, num_packets, version_total, i = 0, 0, 0, 0
while i < len(bin_string):
    if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        # break out of loop when we hit trailing zeroes less than minimum packet length
        break
    start_i = i
    version = unbin(bin_string[i:i+3]) # first three bits are version
    version_total += version
    type_id = unbin(bin_string[i+3:i+6]) # next three bits are packet type id
    if type_id != 4:
        # process operator packets
        length_type = unbin(bin_string[i+6])
        length = 11 if length_type else 15
        length_num = unbin(bin_string[i+7:i+7+length])
        i += 7 + length # move i to start of first sub-packet
        if len(stack) != 0:
            # track new bits and sub-packets in parent packet
            stack[-1]["num_bits"] += i - start_i
            stack[-1]["num_packets"] += 1
        stack.append({
            "result": [],
            "length_type": length_type,
            "length_num": length_num,
            "type_id": type_id,
            "num_bits": 0,
            "num_packets": 0
        })
        continue
    # process literals and stack reduction
    i += 6 # move i to the start of the literal
    literal = ""
    while unbin(bin_string[i]) == 1:
        # loop until we hit the last block
        literal += bin_string[i+1:i+5]
        i += 5
    literal += bin_string[i+1:i+5]
    literal = unbin(literal)
    i += 5
    if len(stack) == 0:
        # if packet is just a literal, we're done
        result = literal
        break
    stack[-1]["result"].append(literal) # track literal in top of operator stack

    if len(stack) != 0:
        # track new bits and sub-packets in parent operator packet
        stack[-1]["num_bits"] += i - start_i
        stack[-1]["num_packets"] += 1
    while len(stack) != 0:
        top = stack[-1]
        if not (top["length_type"] and top["length_num"] == top["num_packets"]) \
                and not (not top["length_type"] and top["length_num"] == top["num_bits"]):
            # if we are not finished with the top operator packet, continue
            break
        top = stack.pop()
        operation_result = operator_map[top["type_id"]](top["result"])
        if len(stack) == 0:
            # when done with our top-level operator packet, we are done
            result = operation_result
        else:
            # bubble up new bits to parent operator packet
            # note: no need to bubble up num_packets since we care about immediate children
            stack[-1]["num_bits"] += top["num_bits"]
            # take operation result from current packet and append to parent operator
            stack[-1]["result"].append(operation_result)

print("Version Total: {}".format(version_total))
print("Packet Result: {}".format(result))

I'm really glad I added comments for this one

I defined some lambdas in a map to easily call operations based on which operator packet is being dealt with.

operator_map = {
    0: lambda x: sum(x),
    1: lambda x: prod(x),
    2: lambda x: min(x),
    3: lambda x: max(x),
    5: lambda x: int(x[0] > x[1]),
    6: lambda x: int(x[0] < x[1]),
    7: lambda x: int(x[0] == x[1])
}

A map of operator packet types to corresponding lambdas

We maintain the same check for extra padding 0s to break out early instead of interpreting the 0s as another packet.

    if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        # break out of loop when we hit trailing zeroes less than minimum packet length
        break

Padded 0s be gone

I switched it around for part 2 and processed operator packets earlier in the loop. It is straight forward with the new stack elements (dictionaries to store some additional information).

    start_i = i
    version = unbin(bin_string[i:i+3]) # first three bits are version
    version_total += version
    type_id = unbin(bin_string[i+3:i+6]) # next three bits are packet type id
    if type_id != 4:
        # process operator packets
        length_type = unbin(bin_string[i+6])
        length = 11 if length_type else 15
        length_num = unbin(bin_string[i+7:i+7+length])
        i += 7 + length # move i to start of first sub-packet
        if len(stack) != 0:
            # track new bits and sub-packets in parent packet
            stack[-1]["num_bits"] += i - start_i
            stack[-1]["num_packets"] += 1
        stack.append({
            "result": [],
            "length_type": length_type,
            "length_num": length_num,
            "type_id": type_id,
            "num_bits": 0,
            "num_packets": 0
        })
        continue

Operator packets just got easier

For the new elements, result is a list of literals from resulting sub-packets. These will be passed to the actual operation lambda once the end of the packet has been reached (these will bubble up until all packets have been processed). length_type, length_num, and type_id are the respective values from the operation packet. num_bits and num_packets track the number of bits and packets coming from sub-packets of the element added to the stack. Even the operation packets will update these values for the nested opeartion above it – only if the stack is not empty meaning that it is not the first packet.

    # process literals and stack reduction
    i += 6 # move i to the start of the literal
    literal = ""
    while unbin(bin_string[i]) == 1:
        # loop until we hit the last block
        literal += bin_string[i+1:i+5]
        i += 5
    literal += bin_string[i+1:i+5]
    literal = unbin(literal)
    i += 5
    if len(stack) == 0:
        # if packet is just a literal, we're done
        result = literal
        break
    stack[-1]["result"].append(literal) # track literal in top of operator stack

    if len(stack) != 0:
        # track new bits and sub-packets in parent operator packet
        stack[-1]["num_bits"] += i - start_i
        stack[-1]["num_packets"] += 1

Just literals, literally cool... literally

The last blocks of the while loop are skipping for operator packets, meaning that these blocks are only run while processing literals. This calculates the value of the current literal and sets it as the result if the stack is empty – meaning that it is the only packet in the input. Otheriwse, it appends the literal value to the parent operation's result list. Also, track the number of bits and packets in the parent operation's element on the stack.

    while len(stack) != 0:
        top = stack[-1]
        if not (top["length_type"] and top["length_num"] == top["num_packets"]) \
                and not (not top["length_type"] and top["length_num"] == top["num_bits"]):
            # if we are not finished with the top operator packet, continue
            break
        top = stack.pop()
        operation_result = operator_map[top["type_id"]](top["result"])
        if len(stack) == 0:
            # when done with our top-level operator packet, we are done
            result = operation_result
        else:
            # bubble up new bits to parent operator packet
            # note: no need to bubble up num_packets since we care about immediate children
            stack[-1]["num_bits"] += top["num_bits"]
            # take operation result from current packet and append to parent operator
            stack[-1]["result"].append(operation_result)

Bubble up

The last section bubbles up the result from the stack. If the operation at the top of the stack has all of its sub-packets processed, then it runs the corresponding operation lambda on the result list and the operational_result is added to the parent operator's result list – also the num_bits. The num_packets does not need to be bubbled up since only the immediate (one layer nested) sub-packets matter for that length type. This process is repeated until hitting an operation that is not done being processed on the stack or the stack is empty meaning that the entire packet has been processed.

❯ python3 solution16.py input16
Version Total: 873
Packet Result: 402817863665

Stack based operations

[Advent of Code 2021] Day 16 | Packet Decoder

Part 1

Part 2