part1 (6976B)
1--- Day 16: Packet Decoder --- 2 3As you leave the cave and reach open waters, you receive a transmission from the Elves back on the 4ship. 5 6The transmission was sent using the Buoyancy Interchange Transmission System (BITS), a method of 7packing numeric expressions into a binary sequence. Your submarine's computer has saved the 8transmission in hexadecimal (your puzzle input). 9 10The first step of decoding the message is to convert the hexadecimal representation into binary. 11Each character of hexadecimal corresponds to four bits of binary data: 12 130 = 0000 141 = 0001 152 = 0010 163 = 0011 174 = 0100 185 = 0101 196 = 0110 207 = 0111 218 = 1000 229 = 1001 23A = 1010 24B = 1011 25C = 1100 26D = 1101 27E = 1110 28F = 1111 29 30The BITS transmission contains a single [1m[97mpacket[0m at its outermost layer which itself contains many 31other packets. The hexadecimal representation of this packet might encode a few extra 0 bits at the 32end; these are not part of the transmission and should be ignored. 33 34Every packet begins with a standard header: the first three bits encode the packet 35[1m[97mversion[0m, and the next three bits encode the packet [1m[97mtype ID[0m. These two values are numbers; all 36numbers encoded in any packet are represented as binary with the most significant bit first. For 37example, a version encoded as the binary sequence 100 represents the number 4. 38 39Packets with type ID 4 represent a [1m[97mliteral value[0m. Literal value packets encode a single binary 40number. To do this, the binary number is padded with leading zeroes until its length is a multiple 41of four bits, and then it is broken into groups of four bits. Each group is prefixed by a 1 bit 42except the last group, which is prefixed by a 0 bit. These groups of five bits immediately follow 43the packet header. For example, the hexadecimal string D2FE28 becomes: 44 45110100101111111000101000 46VVVTTTAAAAABBBBBCCCCC 47 48Below each bit is a label indicating its purpose: 49 50 51 - The three bits labeled V (110) are the packet version, 6. 52 53 - The three bits labeled T (100) are the packet type ID, 4, which means the packet is a literal 54value. 55 56 - The five bits labeled A (10111) start with a 1 (not the last group, keep reading) and contain the 57first four bits of the number, 0111. 58 59 - The five bits labeled B (11110) start with a 1 (not the last group, keep reading) and contain 60four more bits of the number, 1110. 61 62 - The five bits labeled C (00101) start with a 0 (last group, end of packet) and contain the last 63four bits of the number, 0101. 64 65 - The three unlabeled 0 bits at the end are extra due to the hexadecimal representation and should 66be ignored. 67 68 69So, this packet represents a literal value with binary representation 011111100101, which is 2021 in 70decimal. 71 72Every other type of packet (any packet with a type ID other than 4) represent an 73[1m[97moperator[0m that performs some calculation on one or more sub-packets contained within. Right now, the 74specific operations aren't important; focus on parsing the hierarchy of sub-packets. 75 76An operator packet contains one or more packets. To indicate which subsequent binary data represents 77its sub-packets, an operator packet can use one of two modes indicated by the bit immediately after 78the packet header; this is called the [1m[97mlength type ID[0m: 79 80 81 - If the length type ID is 0, then the next [1m[97m15[0m bits are a number that represents the [1m[97mtotal length 82in bits[0m of the sub-packets contained by this packet. 83 84 - If the length type ID is 1, then the next [1m[97m11[0m bits are a number that represents the 85[1m[97mnumber of sub-packets immediately contained[0m by this packet. 86 87 88Finally, after the length type ID bit and the 15-bit or 11-bit field, the sub-packets appear. 89 90For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 91that contains two sub-packets: 92 9300111000000000000110111101000101001010010001001000000000 94VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB 95 96 97 - The three bits labeled V (001) are the packet version, 1. 98 99 - The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator. 100 101 - The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number 102representing the number of bits in the sub-packets. 103 104 - The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27. 105 106 - The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10. 107 108 - The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20. 109 110 111After reading 11 and 16 bits of sub-packet data, the total length indicated in L (27) is reached, 112and so parsing of this packet stops. 113 114As another example, here is an operator packet (hexadecimal string EE00D40C823060) with length type 115ID 1 that contains three sub-packets: 116 11711101110000000001101010000001100100000100011000001100000 118VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC 119 120 121 - The three bits labeled V (111) are the packet version, 7. 122 123 - The three bits labeled T (011) are the packet type ID, 3, which means the packet is an operator. 124 125 - The bit labeled I (1) is the length type ID, which indicates that the length is a 11-bit number 126representing the number of sub-packets. 127 128 - The 11 bits labeled L (00000000011) contain the number of sub-packets, 3. 129 130 - The 11 bits labeled A contain the first sub-packet, a literal value representing the number 1. 131 132 - The 11 bits labeled B contain the second sub-packet, a literal value representing the number 2. 133 134 - The 11 bits labeled C contain the third sub-packet, a literal value representing the number 3. 135 136 137After reading 3 complete sub-packets, the number of sub-packets indicated in L (3) is reached, and 138so parsing of this packet stops. 139 140For now, parse the hierarchy of the packets throughout the transmission and [1m[97madd up all of the 141version numbers[0m. 142 143Here are a few more examples of hexadecimal-encoded transmissions: 144 145 146 - 8A004A801A8002F478 represents an operator packet (version 4) which contains an operator packet 147(version 1) which contains an operator packet (version 5) which contains a literal value (version 1486); this packet has a version sum of [1m[97m16[0m. 149 150 - 620080001611562C8802118E34 represents an operator packet (version 3) which contains two 151sub-packets; each sub-packet is an operator packet that contains two literal values. This packet has 152a version sum of [1m[97m12[0m. 153 154 - C0015000016115A2E0802F182340 has the same structure as the previous example, but the outermost 155packet uses a different length type ID. This packet has a version sum of [1m[97m23[0m. 156 157 - A0016C880162017C3686B18A3D4780 is an operator packet that contains an operator packet that 158contains an operator packet that contains five literal values; it has a version sum of 159[1m[97m31[0m. 160 161 162Decode the structure of your hexadecimal-encoded BITS transmission; [1m[97mwhat do you get if you add up 163the version numbers in all packets?[0m 164 165