From 44ccb9f2e0493b5aa32f10f00ab62a8ec3d860d9 Mon Sep 17 00:00:00 2001 From: Brett Parker Date: Tue, 4 Jan 2022 17:44:26 +0000 Subject: [PATCH] Working day16 parser --- day16/decoder.sh | 278 ++++++++++++++++++++++++++++++++++++---- day16/input-twitter.txt | 1 + day16/p2_0-ne.txt | 1 + day16/p2_0-ngt.txt | 1 + day16/p2_1-2sums.txt | 1 + day16/p2_1.txt | 1 + day16/p2_3.txt | 1 + day16/p2_54.txt | 1 + day16/p2_7.txt | 1 + day16/p2_9.txt | 1 + day16/task.txt | 213 ++++++++++++++++++++++++++++++ 11 files changed, 478 insertions(+), 22 deletions(-) create mode 100644 day16/input-twitter.txt create mode 100644 day16/p2_0-ne.txt create mode 100644 day16/p2_0-ngt.txt create mode 100644 day16/p2_1-2sums.txt create mode 100644 day16/p2_1.txt create mode 100644 day16/p2_3.txt create mode 100644 day16/p2_54.txt create mode 100644 day16/p2_7.txt create mode 100644 day16/p2_9.txt create mode 100644 day16/task.txt diff --git a/day16/decoder.sh b/day16/decoder.sh index fe67cbd..cdf8166 100755 --- a/day16/decoder.sh +++ b/day16/decoder.sh @@ -19,6 +19,7 @@ done declare -g __versions_total=0 declare __packet_offset=0 +declare -g __cur_level=0 if [ $debug == "0" ]; then echo_verbose() { true; } @@ -27,18 +28,21 @@ else fi parse_version() { + local level="${1:- 1}" declare -g __packet_version=$((2#${__packets:$__packet_offset:3})) ((__packet_offset+=3)) echo_verbose "Packet version: $__packet_version" } parse_type() { + local level="${1:- 1}" declare -g __packet_type=$((2#${__packets:$__packet_offset:3})) ((__packet_offset+=3)) echo_verbose "Packet type: $__packet_type" } parse_literal() { + local level="${1:- 1}" local keep_going=${__packets:$__packet_offset:1} local binary_value="" ((__packet_offset+=1)) @@ -51,49 +55,278 @@ parse_literal() { # if we're here, we're on to the last group binary_value+=${__packets:$__packet_offset:4} ((__packet_offset+=4)) - declare -g __packet_literal=$((2#$binary_value)) - echo_verbose "Packet literal: $__packet_literal" + declare -g __packet_value=$((2#$binary_value)) + echo_verbose "Packet literal: $__packet_value" } parse_operator() { + local level="${1:- 1}" + local ptype="${2:-}" local len_type=$((2#${__packets:$__packet_offset:1})) + local number=0 ((__packet_offset+=1)) case $len_type in 0) - __packets_length=$((2#${__packets:$__packet_offset:15})) + number=$((2#${__packets:$__packet_offset:15})) ((__packet_offset+=15)) ;; 1) - __packets_count=$((2#${__packets:$__packet_offset:11})) + number=$((2#${__packets:$__packet_offset:11})) ((__packet_offset+=11)) ;; esac + + case $ptype in + 0) + parse_sum $len_type $number + ;; + 1) + parse_product $len_type $number + ;; + 2) + parse_minimum $len_type $number + ;; + 3) + parse_maximum $len_type $number + ;; + 5) + parse_greaterthan $len_type $number + ;; + 6) + parse_lessthan $len_type $number + ;; + 7) + parse_equal $len_type $number + ;; + esac +} + +parse_sum() { + local len_type=$1 + local count=$2 + local total=0 + local id=$__packet_offset + local a=0 + + echo_verbose "[$id]: Doing a sum ($len_type - $count)" + + case $len_type in + 0) + local end_offset=$((__packet_offset+$count)) + while [ $__packet_offset -lt $end_offset ]; do + echo_verbose "[$id]: Getting sum sub packet" + parse_packet + ((total+=$__packet_value)) + done + ;; + 1) + for (( a=0; a<$count; a++ )); do + echo_verbose "[$id]: Getting sum sub packet" + parse_packet + ((total+=$__packet_value)) + done + ;; + esac + + echo_verbose "[$id]: Sum total: $total (offset: $__packet_offset)" + + declare -g __packet_value=$total +} + +parse_product() { + local len_type=$1 + local count=$2 + local total=1 + local id=$__packet_offset + local a=0 + + echo_verbose "[$id]: Doing a product ($len_type - $count)" + + case $len_type in + 0) + local end_offset=$((__packet_offset+$count)) + while [ $__packet_offset -lt $end_offset ]; do + echo_verbose "[$id]: Getting product sub packet" + parse_packet + ((total*=$__packet_value)) + done + ;; + 1) + for (( a=0; a<$count; a++ )); do + echo_verbose "[$id]: Getting product sub packet" + parse_packet + ((total*=$__packet_value)) + done + ;; + esac + + echo_verbose "[$id]: Product total: $total (offset: $__packet_offset)" + + declare -g __packet_value=$total +} + +parse_minimum() { + local len_type=$1 + local count=$2 + local minimum= + local id=$__packet_offset + local a=0 + + echo_verbose "[$id]: Doing mimimum" + + case $len_type in + 0) + local end_offset=$((__packet_offset+$count)) + while [ $__packet_offset -lt $end_offset ]; do + echo_verbose "[$id]: Getting minimum sub packet" + parse_packet + if [ -z $minimum ] || [ $__packet_value -lt $minimum ]; then + minimum=$__packet_value + fi + done + ;; + 1) + for (( a=0; a<$count; a++ )); do + echo_verbose "[$id]: Getting minimum sub packet" + parse_packet + if [ -z $minimum ] || [ $__packet_value -lt $minimum ]; then + minimum=$__packet_value + fi + done + ;; + esac + + echo_verbose "[$id]: Minimum value: $minimum (offset: $__packet_offset)" + + declare -g __packet_value=$minimum +} + +parse_maximum() { + local len_type=$1 + local count=$2 + local maximum= + local id=$__packet_offset + local a + + echo_verbose "[$id]: Doing maximum ($len_type - $count)" + + case $len_type in + 0) + local end_offset=$((__packet_offset+$count)) + while [ $__packet_offset -lt $end_offset ]; do + echo_verbose "[$id]: Getting maximum sub packet" + parse_packet + if [ -z $maximum ] || [ $__packet_value -gt $maximum ]; then + maximum=$__packet_value + fi + done + ;; + 1) + for (( a=0; a<$count; a++ )); do + echo_verbose "[$id]: Getting maximum sub packet" + parse_packet + if [ -z $maximum ] || [ $__packet_value -gt $maximum ]; then + maximum=$__packet_value + fi + done + ;; + esac + + echo_verbose "[$id]: Maximum value: $maximum (offset: $__packet_offset)" + + declare -g __packet_value=$maximum +} + +parse_greaterthan() { + local len_type=$1 + local count=$2 + local id=$__packet_offset + + echo_verbose "[$id]: Doing >" + + # we don't actually care, we know that it's exactly 2 sub packets that we want... so + parse_packet + local val1=$__packet_value + parse_packet + local val2=$__packet_value + + if [ $val1 -gt $val2 ]; then + declare -g __packet_value=1 + else + declare -g __packet_value=0 + fi + + echo_verbose "[$id]: Got $__packet_value (offset: $__packet_offset)" +} + +parse_lessthan() { + local len_type=$1 + local count=$2 + local id=$__packet_offset + + echo_verbose "[$id]: Doing <" + + # we don't actually care, we know that it's exactly 2 sub packets that we want... so + parse_packet + local val1=$__packet_value + parse_packet + local val2=$__packet_value + + if [ $val1 -lt $val2 ]; then + declare -g __packet_value=1 + else + declare -g __packet_value=0 + fi + + echo_verbose "[$id]: Got $__packet_valuei (offset: $__packet_offset)" +} + +parse_equal() { + local len_type=$1 + local count=$2 + local id=$__packet_offset + + echo_verbose "[$id]: Doing =" + + # we don't actually care, we know that it's exactly 2 sub packets that we want... so + parse_packet + local val1=$__packet_value + parse_packet + local val2=$__packet_value + + if [ $val1 -eq $val2 ]; then + declare -g __packet_value=1 + else + declare -g __packet_value=0 + fi + + echo_verbose "[$id]: Got $__packet_value (offset: $__packet_offset)" +} + +parse_packet() { + parse_version && local pversion=$__packet_version + parse_type && local ptype=$__packet_type + + ((__versions_total+=$pversion)) + + case $ptype in + 4) + parse_literal + ;; + *) + parse_operator $__cur_level $ptype + ;; + esac } parse_packets() { + local level="${1:- 1}" # we'll first need the version and the type, so grab those - local pversion - local ptype while [ $__packet_offset -lt ${#__packets} ]; do - parse_version - parse_type - version=$__packet_version - ptype=$__packet_type - - ((__versions_total+=$version)) - - echo_verbose "Remaining: ${__packets:$__packet_offset}" - case $ptype in - 4) - parse_literal - ;; - *) - parse_operator - ;; - esac + parse_packet if [ $(($__packet_offset+7)) -ge ${#__packets} ]; then break @@ -104,3 +337,4 @@ parse_packets() { parse_packets echo "Total: $__versions_total" +echo "End value: $__packet_value" diff --git a/day16/input-twitter.txt b/day16/input-twitter.txt new file mode 100644 index 0000000..2fadfd6 --- /dev/null +++ b/day16/input-twitter.txt @@ -0,0 +1 @@ +005173980232D7F50C740109F3B9F3F0005425D36565F202012CAC0170004262EC658B0200FC3A8AB0EA5FF331201507003710004262243F8F600086C378B7152529CB4981400B202D04C00C0028048095070038C00B50028C00C50030805D3700240049210021C00810038400A400688C00C3003E605A4A19A62D3E741480261B00464C9E6A5DF3A455999C2430E0054FCBE7260084F4B37B2D60034325DE114B66A3A4012E4FFC62801069839983820061A60EE7526781E513C8050D00042E34C24898000844608F70E840198DD152262801D382460164D9BCE14CC20C179F17200812785261CE484E5D85801A59FDA64976DB504008665EB65E97C52DCAA82803B1264604D342040109E802B09E13CBC22B040154CBE53F8015796D8A4B6C50C01787B800974B413A5990400B8CA6008CE22D003992F9A2BCD421F2C9CA889802506B40159FEE0065C8A6FCF66004C695008E6F7D1693BDAEAD2993A9FEE790B62872001F54A0AC7F9B2C959535EFD4426E98CC864801029F0D935B3005E64CA8012F9AD9ACB84CC67BDBF7DF4A70086739D648BF396BFF603377389587C62211006470B68021895FCFBC249BCDF2C8200C1803D1F21DC273007E3A4148CA4008746F8630D840219B9B7C9DFFD2C9A8478CD3F9A4974401A99D65BA0BC716007FA7BFE8B6C933C8BD4A139005B1E00AC9760A73BA229A87520C017E007C679824EDC95B732C9FB04B007873BCCC94E789A18C8E399841627F6CF3C50A0174A6676199ABDA5F4F92E752E63C911ACC01793A6FB2B84D0020526FD26F6402334F935802200087C3D8DD0E0401A8CF0A23A100A0B294CCF671E00A0002110823D4231007A0D4198EC40181E802924D3272BE70BD3D4C8A100A613B6AFB7481668024200D4188C108C401D89716A080 diff --git a/day16/p2_0-ne.txt b/day16/p2_0-ne.txt new file mode 100644 index 0000000..6055bef --- /dev/null +++ b/day16/p2_0-ne.txt @@ -0,0 +1 @@ +9C005AC2F8F0 diff --git a/day16/p2_0-ngt.txt b/day16/p2_0-ngt.txt new file mode 100644 index 0000000..eb83c7b --- /dev/null +++ b/day16/p2_0-ngt.txt @@ -0,0 +1 @@ +F600BC2D8F diff --git a/day16/p2_1-2sums.txt b/day16/p2_1-2sums.txt new file mode 100644 index 0000000..4ced67a --- /dev/null +++ b/day16/p2_1-2sums.txt @@ -0,0 +1 @@ +9C0141080250320F1802104A08 diff --git a/day16/p2_1.txt b/day16/p2_1.txt new file mode 100644 index 0000000..408badd --- /dev/null +++ b/day16/p2_1.txt @@ -0,0 +1 @@ +D8005AC2A8F0 diff --git a/day16/p2_3.txt b/day16/p2_3.txt new file mode 100644 index 0000000..0ab8df5 --- /dev/null +++ b/day16/p2_3.txt @@ -0,0 +1 @@ +C200B40A82 diff --git a/day16/p2_54.txt b/day16/p2_54.txt new file mode 100644 index 0000000..08def75 --- /dev/null +++ b/day16/p2_54.txt @@ -0,0 +1 @@ +04005AC33890 diff --git a/day16/p2_7.txt b/day16/p2_7.txt new file mode 100644 index 0000000..c4d0ebb --- /dev/null +++ b/day16/p2_7.txt @@ -0,0 +1 @@ +880086C3E88112 diff --git a/day16/p2_9.txt b/day16/p2_9.txt new file mode 100644 index 0000000..985c72d --- /dev/null +++ b/day16/p2_9.txt @@ -0,0 +1 @@ +CE00C43D881120 diff --git a/day16/task.txt b/day16/task.txt new file mode 100644 index 0000000..00fdc60 --- /dev/null +++ b/day16/task.txt @@ -0,0 +1,213 @@ +--- 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 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? + +Your puzzle answer was 945. + +--- Part Two --- + +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? + +Your puzzle answer was 10637009915279. + +Both parts of this puzzle are complete! They provide two gold stars: ** + +At this point, you should return to your Advent calendar and try another +puzzle. + +If you still want to see it, you can get your puzzle input. + -- 2.39.5