1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
--- Day 16: Packet Decoder ---
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 [1m[97mpacket[0m 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
[1m[97mversion[0m, and the next three bits encode the packet [1m[97mtype ID[0m. 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 [1m[97mliteral value[0m. 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
[1m[97moperator[0m 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 [1m[97mlength type ID[0m:
- If the length type ID is 0, then the next [1m[97m15[0m bits are a number that represents the [1m[97mtotal length
in bits[0m of the sub-packets contained by this packet.
- If the length type ID is 1, then the next [1m[97m11[0m bits are a number that represents the
[1m[97mnumber of sub-packets immediately contained[0m 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 [1m[97madd up all of the
version numbers[0m.
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 [1m[97m16[0m.
- 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 [1m[97m12[0m.
- 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 [1m[97m23[0m.
- 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
[1m[97m31[0m.
Decode the structure of your hexadecimal-encoded BITS transmission; [1m[97mwhat do you get if you add up
the version numbers in all packets?[0m
|
