X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2021.git/blobdiff_plain/9017e242041b51939c88e7e99221923965e919e1..44ccb9f2e0493b5aa32f10f00ab62a8ec3d860d9:/day16/decoder.sh?ds=inline 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"