From: Brett Parker <iDunno@sommitrealweird.co.uk>
Date: Tue, 4 Jan 2022 17:44:26 +0000 (+0000)
Subject: Working day16 parser
X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2021.git/commitdiff_plain

Working day16 parser
---

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.
+