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:
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?
# Python imports
import textwrap
from collections import Counter, defaultdict
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Set, Tuple
import numpy as np
# Paths to data
testpath1 = Path("day16_test1.txt")
testpath2 = Path("day16_test2.txt")
testpath3 = Path("day16_test3.txt")
testpath4 = Path("day16_test4.txt")
testpath5 = Path("day16_test5.txt")
testpath6 = Path("day16_test6.txt")
testpath7 = Path("day16_test7.txt")
testpath8 = Path("day16_test8.txt")
testpath15 = Path("day16_test15.txt")
datapath = Path("day16_data.txt")
Reading the input was interesting. Python can convert a string to an int in any base, which is handy for hex to bin - but we also have to left-pad with zeros, and use .zfill(), which was new to me.
def load_input(fpath: Path) -> str:
"""Returns contents of hex file as a binary string
:param fpath: Path to data file
"""
with fpath.open("r") as ifh:
hexlist = list(ifh.read().strip())
# Convert hex to binary
bindata = [str(bin(int(_, 16)))[2:].zfill(4) for _ in hexlist]
return "".join(bindata)
This reminds me of the intcode problems from two years ago, except we have to write pretty much the whole thing at once! I had a hard time debugging some of this.
opdict = {0: "sum", 1: "prod", 2: "min", 3: "max", 4: "value", 5: ">", 6: "<", 7: "=="}
class Packet:
def __init__(self, bindata):
self._subpackets = list()
self._literal, self._value = None, None
self._bindata = bindata
self.__parse()
if self._packettype == 4: # literal value
self.__read_value()
def __parse(self):
self._packetver = int(self._bindata[:3], 2)
self._packettype = int(self._bindata[3:6], 2)
if self._packettype == 4:
self._lengthtype = None
self._packetdata = self._bindata[6:]
else:
self.__parse_subpackets()
def __parse_subpackets(self):
self._lengthtype = int(self._bindata[6])
if self._lengthtype == 0: # Subpackets in region with given length
self._lengthval = int(self._bindata[7:22], 2)
self._packetdata = self._bindata[22:22+self._lengthval]
payload = self._packetdata
while len(payload):
packet = Packet(payload)
self._subpackets.append(packet)
payload = payload[len(packet):]
else: # There are a given number of subpackets
self._lengthval = int(self._bindata[7:18], 2)
self._packetdata = self._bindata[18:]
payload = self._packetdata
while len(self._subpackets) < self._lengthval:
packet = Packet(payload)
self._subpackets.append(packet)
payload = payload[len(packet):]
def __read_value(self):
chunks = []
cur = 0 # cursor in data
state = "read"
while state == "read":
chunk = self._packetdata[cur:cur + 5]
if chunk[0] == "0":
state = "end"
chunks.append(chunk)
cur += 5
self._literal = "".join([_[1:] for _ in chunks])
self._packetdata = self._packetdata[:len(chunks) * 5]
self._value = int(self._literal, 2)
def __len__(self):
if self._lengthtype == 0:
return 7 + 15 + sum([len(_) for _ in self._subpackets])
elif self._lengthtype == 1:
return 7 + 11 + sum([len(_) for _ in self._subpackets])
else:
return 6 + len(self._packetdata)
def __str__(self):
outstr = [f"Packet Version: {self._packetver}",
f"Packet Type: {self._packettype} ({opdict[self._packettype]})",
f"Value: {self.value} ({[_.value for _ in self._subpackets]})",
f"len(packet): {len(self)}"]
if len(self._packetdata) > 40:
outstr.append(f"Data: {self._packetdata[:15]}...{self._packetdata[-15:]}")
else:
outstr.append(f"Data: {self._packetdata}")
if self._packettype == 4:
outstr.append(f"Literal: {self._literal}")
else:
outstr += [f"Length Type: {self._lengthtype}",
f"Length: {self._lengthval}"]
outstr.append(f"Subpackets: {len(self._subpackets)}")
return "\n".join(outstr)
@property
def longprint(self):
outstr = [str(self)]
for subpacket in self._subpackets:
for line in str(subpacket).split("\n"):
outstr.append("\t" + line)
return "\n".join(outstr)
@property
def packet(self):
if self._packettype == 4:
return f"Packet: {self._packetver:03b} {self._packettype:03b} {' '.join(textwrap.wrap(self._packetdata, 5))}"
return (f"Packet: {self._packetver:03b} {self._packettype:03b} {self._lengthtype:b} "
f"{self._packetdata}")
@property
def prettyprint(self):
outstr = [self.shortprint]
for subpacket in self._subpackets:
for line in str(subpacket.prettyprint).split("\n"):
outstr.append("\t" + line)
return "\n".join(outstr)
@property
def shortprint(self):
return f"Version: {self._packetver}, Type: {self._packettype}, Value: {self.value}"
@property
def value(self):
if self._packettype == 0:
return sum([_.value for _ in self._subpackets])
elif self._packettype == 1:
return np.prod([_.value for _ in self._subpackets])
elif self._packettype == 2:
return min([_.value for _ in self._subpackets])
elif self._packettype == 3:
return max([_.value for _ in self._subpackets])
elif self._packettype == 4:
return self._value
elif self._packettype == 5:
if self._subpackets[0].value > self._subpackets[1].value:
return 1
else:
return 0
elif self._packettype == 6:
if self._subpackets[0].value < self._subpackets[1].value:
return 1
else:
return 0
elif self._packettype == 7:
if self._subpackets[0].value == self._subpackets[1].value:
return 1
else:
return 0
else:
return None
@property
def versionsum(self):
return self._packetver + sum([_.versionsum for _ in self._subpackets])
In the above, the textwrap.wrap() function was new to me. I don't like a lot of the above code - the long if/else chain could be a distribution dictionary, keyed by self._packettype. The various packet string representations were useful for debugging (of which there was a lot!).
Happily, there were also a lot of examples to test the class out on:
print(load_input(testpath1))
packet = Packet(load_input(testpath1))
print(packet)
110100101111111000101000 Packet Version: 6 Packet Type: 4 (value) Value: 2021 ([]) len(packet): 21 Data: 101111111000101 Literal: 011111100101 Subpackets: 0
packet = Packet(load_input(testpath2))
print(f"{packet}\n")
print(packet.prettyprint)
Packet Version: 1 Packet Type: 6 (<) Value: 1 ([10, 20]) len(packet): 49 Data: 110100010100101001000100100 Length Type: 0 Length: 27 Subpackets: 2 Version: 1, Type: 6, Value: 1 Version: 6, Type: 4, Value: 10 Version: 2, Type: 4, Value: 20
packet = Packet(load_input(testpath3))
print(f"{packet}\n")
print(packet.prettyprint)
Packet Version: 7 Packet Type: 3 (max) Value: 3 ([1, 2, 3]) len(packet): 51 Data: 01010000001100100000100011000001100000 Length Type: 1 Length: 3 Subpackets: 3 Version: 7, Type: 3, Value: 3 Version: 2, Type: 4, Value: 1 Version: 4, Type: 4, Value: 2 Version: 1, Type: 4, Value: 3
packet = Packet(load_input(testpath4))
print(f"{packet}\n")
print(packet.prettyprint)
print(f"\nVersion Sum: {packet.versionsum}")
Packet Version: 4 Packet Type: 2 (min) Value: 15 ([15]) len(packet): 69 Data: 001010100000000...111010001111000 Length Type: 1 Length: 1 Subpackets: 1 Version: 4, Type: 2, Value: 15 Version: 1, Type: 2, Value: 15 Version: 5, Type: 2, Value: 15 Version: 6, Type: 4, Value: 15 Version Sum: 16
packet = Packet(load_input(testpath5))
print(f"{packet}\n")
print(packet.prettyprint)
print(f"\nVersion Sum: {packet.versionsum}")
Packet Version: 3 Packet Type: 0 (sum) Value: 46 ([21, 25]) len(packet): 102 Data: 000000000000000...000111000110100 Length Type: 1 Length: 2 Subpackets: 2 Version: 3, Type: 0, Value: 46 Version: 0, Type: 0, Value: 21 Version: 0, Type: 4, Value: 10 Version: 5, Type: 4, Value: 11 Version: 1, Type: 0, Value: 25 Version: 0, Type: 4, Value: 12 Version: 3, Type: 4, Value: 13 Version Sum: 12
packet = Packet(load_input(testpath6))
print(f"{packet}\n")
print(packet.prettyprint)
print(f"\nVersion Sum: {packet.versionsum}")
Packet Version: 6 Packet Type: 0 (sum) Value: 46 ([21, 25]) len(packet): 106 Data: 000000000000000...110000010001101 Length Type: 0 Length: 84 Subpackets: 2 Version: 6, Type: 0, Value: 46 Version: 0, Type: 0, Value: 21 Version: 0, Type: 4, Value: 10 Version: 6, Type: 4, Value: 11 Version: 4, Type: 0, Value: 25 Version: 7, Type: 4, Value: 12 Version: 0, Type: 4, Value: 13 Version Sum: 23
packet = Packet(load_input(testpath7))
print(f"{packet}\n")
print(packet.prettyprint)
print(f"\nVersion Sum: {packet.versionsum}")
Packet Version: 5 Packet Type: 0 (sum) Value: 54 ([54]) len(packet): 113 Data: 001000100000000...111101010001111 Length Type: 0 Length: 91 Subpackets: 1 Version: 5, Type: 0, Value: 54 Version: 1, Type: 0, Value: 54 Version: 3, Type: 0, Value: 54 Version: 7, Type: 4, Value: 6 Version: 6, Type: 4, Value: 6 Version: 5, Type: 4, Value: 12 Version: 2, Type: 4, Value: 15 Version: 2, Type: 4, Value: 15 Version Sum: 31
Finally, I could try the class out on the actual puzzle data:
packet = Packet(load_input(datapath))
print(packet)
print(f"\nVersion Sum: {packet.versionsum}")
Packet Version: 2 Packet Type: 0 (sum) Value: 911945136934 ([0, 53906196960, 171, 9, 3902, 0, 0, 0, 2348, 75, 12261074, 13, 43399, 3, 13566083486, 0, 0, 436152, 16740, 1033616, 225, 1017104, 14634355, 2875238311, 586960, 0, 27427, 4665051, 9996, 1662, 18592055, 822126805971, 1433, 148, 241, 6, 1933, 5, 0, 0, 0, 0, 0, 2490, 123349, 2148824802, 159702409, 1536, 4557000, 0, 17097035226, 911, 7228380]) len(packet): 5249 Data: 100001000000000...101011000000000 Length Type: 1 Length: 53 Subpackets: 53 Version Sum: 929
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?
I implemented the code for the solution in my class for part 1, and the answer is in the last code cell output above.