day16/decoder.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename=${1:-p1_16.txt}
   6 debug=${2:-0}
   7
   8 exec 3<"${filename}"
   9
  10 declare -A hex_to_binary=( [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" )
  11
  12 read -u 3 hex_string
  13
  14 declare -g __packets=""
  15 for (( a=0; a<${#hex_string}; a++ )); do
  16     __packets+=${hex_to_binary[${hex_string:$a:1}]}
  17 done
  18
  19 declare -g __versions_total=0
  20
  21 declare __packet_offset=0
  22 declare -g __cur_level=0
  23
  24 if [ $debug == "0"  ]; then
  25     echo_verbose() { true; }
  26 else
  27     echo_verbose() { echo "$@" >&2; }
  28 fi
  29
  30 parse_version() {
  31     local level="${1:- 1}"
  32     declare -g __packet_version=$((2#${__packets:$__packet_offset:3}))
  33     ((__packet_offset+=3))
  34     echo_verbose "Packet version: $__packet_version"
  35 }
  36
  37 parse_type() {
  38     local level="${1:- 1}"
  39     declare -g __packet_type=$((2#${__packets:$__packet_offset:3}))
  40     ((__packet_offset+=3))
  41     echo_verbose "Packet type: $__packet_type"
  42 }
  43
  44 parse_literal() {
  45     local level="${1:- 1}"
  46     local keep_going=${__packets:$__packet_offset:1}
  47     local binary_value=""
  48     ((__packet_offset+=1))
  49     while [ $keep_going -eq 1 ]; do
  50         binary_value+=${__packets:$__packet_offset:4}
  51         ((__packet_offset+=4))
  52         keep_going=${__packets:$__packet_offset:1}
  53         ((__packet_offset+=1))
  54     done
  55     # if we're here, we're on to the last group
  56     binary_value+=${__packets:$__packet_offset:4}
  57     ((__packet_offset+=4))
  58     declare -g __packet_value=$((2#$binary_value))
  59     echo_verbose "Packet literal: $__packet_value"
  60 }
  61
  62 parse_operator() {
  63     local level="${1:- 1}"
  64     local ptype="${2:-}"
  65     local len_type=$((2#${__packets:$__packet_offset:1}))
  66     local number=0
  67     ((__packet_offset+=1))
  68
  69     case $len_type in
  70         0)
  71             number=$((2#${__packets:$__packet_offset:15}))
  72             ((__packet_offset+=15))
  73             ;;
  74         1)
  75             number=$((2#${__packets:$__packet_offset:11}))
  76             ((__packet_offset+=11))
  77             ;;
  78     esac
  79
  80     case $ptype in
  81         0)
  82             parse_sum $len_type $number
  83             ;;
  84         1)
  85             parse_product $len_type $number
  86             ;;
  87         2)
  88             parse_minimum $len_type $number
  89             ;;
  90         3)
  91             parse_maximum $len_type $number
  92             ;;
  93         5)
  94             parse_greaterthan $len_type $number
  95             ;;
  96         6)
  97             parse_lessthan $len_type $number
  98             ;;
  99         7)
 100             parse_equal $len_type $number
 101             ;;
 102     esac
 103 }
 104
 105 parse_sum() {
 106     local len_type=$1
 107     local count=$2
 108     local total=0
 109     local id=$__packet_offset
 110     local a=0
 111
 112     echo_verbose "[$id]: Doing a sum ($len_type - $count)"
 113
 114     case $len_type in
 115         0)
 116             local end_offset=$((__packet_offset+$count))
 117             while [ $__packet_offset -lt $end_offset ]; do
 118                 echo_verbose "[$id]: Getting sum sub packet"
 119                 parse_packet
 120                 ((total+=$__packet_value))
 121             done
 122             ;;
 123         1)
 124             for (( a=0; a<$count; a++ )); do
 125                 echo_verbose "[$id]: Getting sum sub packet"
 126                 parse_packet
 127                 ((total+=$__packet_value))
 128             done
 129             ;;
 130     esac
 131
 132     echo_verbose "[$id]: Sum total: $total (offset: $__packet_offset)"
 133
 134     declare -g __packet_value=$total
 135 }
 136
 137 parse_product() {
 138     local len_type=$1
 139     local count=$2
 140     local total=1
 141     local id=$__packet_offset
 142     local a=0
 143
 144     echo_verbose "[$id]: Doing a product ($len_type - $count)"
 145
 146     case $len_type in
 147         0)
 148             local end_offset=$((__packet_offset+$count))
 149             while [ $__packet_offset -lt $end_offset ]; do
 150                 echo_verbose "[$id]: Getting product sub packet"
 151                 parse_packet
 152                 ((total*=$__packet_value))
 153             done
 154             ;;
 155         1)
 156             for (( a=0; a<$count; a++ )); do
 157                 echo_verbose "[$id]: Getting product sub packet"
 158                 parse_packet
 159                 ((total*=$__packet_value))
 160             done
 161             ;;
 162     esac
 163
 164     echo_verbose "[$id]: Product total: $total (offset: $__packet_offset)"
 165
 166     declare -g __packet_value=$total
 167 }
 168
 169 parse_minimum() {
 170     local len_type=$1
 171     local count=$2
 172     local minimum=
 173     local id=$__packet_offset
 174     local a=0
 175
 176     echo_verbose "[$id]: Doing mimimum"
 177
 178     case $len_type in
 179         0)
 180             local end_offset=$((__packet_offset+$count))
 181             while [ $__packet_offset -lt $end_offset ]; do
 182                 echo_verbose "[$id]: Getting minimum sub packet"
 183                 parse_packet
 184                 if [ -z $minimum ] || [ $__packet_value -lt $minimum ]; then
 185                     minimum=$__packet_value
 186                 fi
 187             done
 188             ;;
 189         1)
 190             for (( a=0; a<$count; a++ )); do
 191                 echo_verbose "[$id]: Getting minimum sub packet"
 192                 parse_packet
 193                 if [ -z $minimum ] || [ $__packet_value -lt $minimum ]; then
 194                     minimum=$__packet_value
 195                 fi
 196             done
 197             ;;
 198     esac
 199
 200     echo_verbose "[$id]: Minimum value: $minimum (offset: $__packet_offset)"
 201
 202     declare -g __packet_value=$minimum
 203 }
 204
 205 parse_maximum() {
 206     local len_type=$1
 207     local count=$2
 208     local maximum=
 209     local id=$__packet_offset
 210     local a
 211
 212     echo_verbose "[$id]: Doing maximum ($len_type - $count)"
 213
 214     case $len_type in
 215         0)
 216             local end_offset=$((__packet_offset+$count))
 217             while [ $__packet_offset -lt $end_offset ]; do
 218                 echo_verbose "[$id]: Getting maximum sub packet"
 219                 parse_packet
 220                 if [ -z $maximum ] || [ $__packet_value -gt $maximum ]; then
 221                     maximum=$__packet_value
 222                 fi
 223             done
 224             ;;
 225         1)
 226             for (( a=0; a<$count; a++ )); do
 227                 echo_verbose "[$id]: Getting maximum sub packet"
 228                 parse_packet
 229                 if [ -z $maximum ] || [ $__packet_value -gt $maximum ]; then
 230                     maximum=$__packet_value
 231                 fi
 232             done
 233             ;;
 234     esac
 235
 236     echo_verbose "[$id]: Maximum value: $maximum (offset: $__packet_offset)"
 237
 238     declare -g __packet_value=$maximum
 239 }
 240
 241 parse_greaterthan() {
 242     local len_type=$1
 243     local count=$2
 244     local id=$__packet_offset
 245
 246     echo_verbose "[$id]: Doing >"
 247
 248     # we don't actually care, we know that it's exactly 2 sub packets that we want... so
 249     parse_packet
 250     local val1=$__packet_value
 251     parse_packet
 252     local val2=$__packet_value
 253
 254     if [ $val1 -gt $val2 ]; then
 255         declare -g __packet_value=1
 256     else
 257         declare -g __packet_value=0
 258     fi
 259
 260     echo_verbose "[$id]: Got $__packet_value (offset: $__packet_offset)"
 261 }
 262
 263 parse_lessthan() {
 264     local len_type=$1
 265     local count=$2
 266     local id=$__packet_offset
 267
 268     echo_verbose "[$id]: Doing <"
 269
 270     # we don't actually care, we know that it's exactly 2 sub packets that we want... so
 271     parse_packet
 272     local val1=$__packet_value
 273     parse_packet
 274     local val2=$__packet_value
 275
 276     if [ $val1 -lt $val2 ]; then
 277         declare -g __packet_value=1
 278     else
 279         declare -g __packet_value=0
 280     fi
 281
 282     echo_verbose "[$id]: Got $__packet_valuei (offset: $__packet_offset)"
 283 }
 284
 285 parse_equal() {
 286     local len_type=$1
 287     local count=$2
 288     local id=$__packet_offset
 289
 290     echo_verbose "[$id]: Doing ="
 291
 292     # we don't actually care, we know that it's exactly 2 sub packets that we want... so
 293     parse_packet
 294     local val1=$__packet_value
 295     parse_packet
 296     local val2=$__packet_value
 297
 298     if [ $val1 -eq $val2 ]; then
 299         declare -g __packet_value=1
 300     else
 301         declare -g __packet_value=0
 302     fi
 303
 304     echo_verbose "[$id]: Got $__packet_value (offset: $__packet_offset)"
 305 }
 306
 307 parse_packet() {
 308     parse_version && local pversion=$__packet_version
 309     parse_type && local ptype=$__packet_type
 310
 311     ((__versions_total+=$pversion))
 312
 313     case $ptype in
 314         4)
 315             parse_literal
 316             ;;
 317         *)
 318             parse_operator $__cur_level $ptype
 319             ;;
 320     esac
 321 }
 322
 323 parse_packets() {
 324     local level="${1:- 1}"
 325     # we'll first need the version and the type, so grab those
 326
 327     while [ $__packet_offset -lt ${#__packets} ]; do
 328
 329         parse_packet
 330
 331         if [ $(($__packet_offset+7)) -ge ${#__packets} ]; then
 332             break
 333         fi
 334     done
 335 }
 336
 337 parse_packets
 338
 339 echo "Total: $__versions_total"
 340 echo "End value: $__packet_value"