day16/task.txt

   1 --- Day 16: Packet Decoder ---
   2
   3 As you leave the cave and reach open waters, you receive a transmission from
   4 the Elves back on the ship.
   5
   6 The transmission was sent using the Buoyancy Interchange Transmission System (
   7 BITS), a method of packing numeric expressions into a binary sequence. Your
   8 submarine's computer has saved the transmission in hexadecimal (your puzzle
   9 input).
  10
  11 The first step of decoding the message is to convert the hexadecimal
  12 representation into binary. Each character of hexadecimal corresponds to four
  13 bits of binary data:
  14
  15 0 = 0000
  16 1 = 0001
  17 2 = 0010
  18 3 = 0011
  19 4 = 0100
  20 5 = 0101
  21 6 = 0110
  22 7 = 0111
  23 8 = 1000
  24 9 = 1001
  25 A = 1010
  26 B = 1011
  27 C = 1100
  28 D = 1101
  29 E = 1110
  30 F = 1111
  31
  32 The BITS transmission contains a single packet at its outermost layer which
  33 itself contains many other packets. The hexadecimal representation of this
  34 packet might encode a few extra 0 bits at the end; these are not part of the
  35 transmission and should be ignored.
  36
  37 Every packet begins with a standard header: the first three bits encode the
  38 packet version, and the next three bits encode the packet type ID. These two
  39 values are numbers; all numbers encoded in any packet are represented as binary
  40 with the most significant bit first. For example, a version encoded as the
  41 binary sequence 100 represents the number 4.
  42
  43 Packets with type ID 4 represent a literal value. Literal value packets encode
  44 a single binary number. To do this, the binary number is padded with leading
  45 zeroes until its length is a multiple of four bits, and then it is broken into
  46 groups of four bits. Each group is prefixed by a 1 bit except the last group,
  47 which is prefixed by a 0 bit. These groups of five bits immediately follow the
  48 packet header. For example, the hexadecimal string D2FE28 becomes:
  49
  50 110100101111111000101000
  51 VVVTTTAAAAABBBBBCCCCC
  52
  53 Below each bit is a label indicating its purpose:
  54
  55   • The three bits labeled V (110) are the packet version, 6.
  56   • The three bits labeled T (100) are the packet type ID, 4, which means the
  57     packet is a literal value.
  58   • The five bits labeled A (10111) start with a 1 (not the last group, keep
  59     reading) and contain the first four bits of the number, 0111.
  60   • The five bits labeled B (11110) start with a 1 (not the last group, keep
  61     reading) and contain four more bits of the number, 1110.
  62   • The five bits labeled C (00101) start with a 0 (last group, end of packet)
  63     and contain the last four bits of the number, 0101.
  64   • The three unlabeled 0 bits at the end are extra due to the hexadecimal
  65     representation and should be ignored.
  66
  67 So, this packet represents a literal value with binary representation
  68 011111100101, which is 2021 in decimal.
  69
  70 Every other type of packet (any packet with a type ID other than 4) represent
  71 an operator that performs some calculation on one or more sub-packets contained
  72 within. Right now, the specific operations aren't important; focus on parsing
  73 the hierarchy of sub-packets.
  74
  75 An operator packet contains one or more packets. To indicate which subsequent
  76 binary data represents its sub-packets, an operator packet can use one of two
  77 modes indicated by the bit immediately after the packet header; this is called
  78 the length type ID:
  79
  80   • If the length type ID is 0, then the next 15 bits are a number that
  81     represents the total length in bits of the sub-packets contained by this
  82     packet.
  83   • If the length type ID is 1, then the next 11 bits are a number that
  84     represents the number of sub-packets immediately contained by this packet.
  85
  86 Finally, after the length type ID bit and the 15-bit or 11-bit field, the
  87 sub-packets appear.
  88
  89 For example, here is an operator packet (hexadecimal string 38006F45291200)
  90 with length type ID 0 that contains two sub-packets:
  91
  92 00111000000000000110111101000101001010010001001000000000
  93 VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB
  94
  95   • The three bits labeled V (001) are the packet version, 1.
  96   • The three bits labeled T (110) are the packet type ID, 6, which means the
  97     packet is an operator.
  98   • The bit labeled I (0) is the length type ID, which indicates that the
  99     length is a 15-bit number representing the number of bits in the
 100     sub-packets.
 101   • The 15 bits labeled L (000000000011011) contain the length of the
 102     sub-packets in bits, 27.
 103   • The 11 bits labeled A contain the first sub-packet, a literal value
 104     representing the number 10.
 105   • The 16 bits labeled B contain the second sub-packet, a literal value
 106     representing the number 20.
 107
 108 After reading 11 and 16 bits of sub-packet data, the total length indicated in
 109 L (27) is reached, and so parsing of this packet stops.
 110
 111 As another example, here is an operator packet (hexadecimal string
 112 EE00D40C823060) with length type ID 1 that contains three sub-packets:
 113
 114 11101110000000001101010000001100100000100011000001100000
 115 VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC
 116
 117   • The three bits labeled V (111) are the packet version, 7.
 118   • The three bits labeled T (011) are the packet type ID, 3, which means the
 119     packet is an operator.
 120   • The bit labeled I (1) is the length type ID, which indicates that the
 121     length is a 11-bit number representing the number of sub-packets.
 122   • The 11 bits labeled L (00000000011) contain the number of sub-packets, 3.
 123   • The 11 bits labeled A contain the first sub-packet, a literal value
 124     representing the number 1.
 125   • The 11 bits labeled B contain the second sub-packet, a literal value
 126     representing the number 2.
 127   • The 11 bits labeled C contain the third sub-packet, a literal value
 128     representing the number 3.
 129
 130 After reading 3 complete sub-packets, the number of sub-packets indicated in L
 131 (3) is reached, and so parsing of this packet stops.
 132
 133 For now, parse the hierarchy of the packets throughout the transmission and add
 134 up all of the version numbers.
 135
 136 Here are a few more examples of hexadecimal-encoded transmissions:
 137
 138   • 8A004A801A8002F478 represents an operator packet (version 4) which contains
 139     an operator packet (version 1) which contains an operator packet (version
 140     5) which contains a literal value (version 6); this packet has a version
 141     sum of 16.
 142   • 620080001611562C8802118E34 represents an operator packet (version 3) which
 143     contains two sub-packets; each sub-packet is an operator packet that
 144     contains two literal values. This packet has a version sum of 12.
 145   • C0015000016115A2E0802F182340 has the same structure as the previous
 146     example, but the outermost packet uses a different length type ID. This
 147     packet has a version sum of 23.
 148   • A0016C880162017C3686B18A3D4780 is an operator packet that contains an
 149     operator packet that contains an operator packet that contains five literal
 150     values; it has a version sum of 31.
 151
 152 Decode the structure of your hexadecimal-encoded BITS transmission; what do you
 153 get if you add up the version numbers in all packets?
 154
 155 Your puzzle answer was 945.
 156
 157 --- Part Two ---
 158
 159 Now that you have the structure of your transmission decoded, you can calculate
 160 the value of the expression it represents.
 161
 162 Literal values (type ID 4) represent a single number as described above. The
 163 remaining type IDs are more interesting:
 164
 165   • Packets with type ID 0 are sum packets - their value is the sum of the
 166     values of their sub-packets. If they only have a single sub-packet, their
 167     value is the value of the sub-packet.
 168   • Packets with type ID 1 are product packets - their value is the result of
 169     multiplying together the values of their sub-packets. If they only have a
 170     single sub-packet, their value is the value of the sub-packet.
 171   • Packets with type ID 2 are minimum packets - their value is the minimum of
 172     the values of their sub-packets.
 173   • Packets with type ID 3 are maximum packets - their value is the maximum of
 174     the values of their sub-packets.
 175   • Packets with type ID 5 are greater than packets - their value is 1 if the
 176     value of the first sub-packet is greater than the value of the second
 177     sub-packet; otherwise, their value is 0. These packets always have exactly
 178     two sub-packets.
 179   • Packets with type ID 6 are less than packets - their value is 1 if the
 180     value of the first sub-packet is less than the value of the second
 181     sub-packet; otherwise, their value is 0. These packets always have exactly
 182     two sub-packets.
 183   • Packets with type ID 7 are equal to packets - their value is 1 if the value
 184     of the first sub-packet is equal to the value of the second sub-packet;
 185     otherwise, their value is 0. These packets always have exactly two
 186     sub-packets.
 187
 188 Using these rules, you can now work out the value of the outermost packet in
 189 your BITS transmission.
 190
 191 For example:
 192
 193   • C200B40A82 finds the sum of 1 and 2, resulting in the value 3.
 194   • 04005AC33890 finds the product of 6 and 9, resulting in the value 54.
 195   • 880086C3E88112 finds the minimum of 7, 8, and 9, resulting in the value 7.
 196   • CE00C43D881120 finds the maximum of 7, 8, and 9, resulting in the value 9.
 197   • D8005AC2A8F0 produces 1, because 5 is less than 15.
 198   • F600BC2D8F produces 0, because 5 is not greater than 15.
 199   • 9C005AC2F8F0 produces 0, because 5 is not equal to 15.
 200   • 9C0141080250320F1802104A08 produces 1, because 1 + 3 = 2 * 2.
 201
 202 What do you get if you evaluate the expression represented by your
 203 hexadecimal-encoded BITS transmission?
 204
 205 Your puzzle answer was 10637009915279.
 206
 207 Both parts of this puzzle are complete! They provide two gold stars: **
 208
 209 At this point, you should return to your Advent calendar and try another
 210 puzzle.
 211
 212 If you still want to see it, you can get your puzzle input.
 213