2015/advent19.sh

   1 final=false
   2 count=0
   3 declare -A elements
   4 longest=0
   5 while read line; do
   6     if $final; then
   7         target=$line
   8     elif [[ ! $line ]]; then
   9         final=:
  10     else
  11         regex='([A-Z][a-z]*) => +([A-Za-z ]*)'
  12         [[ $line =~ $regex ]] || { echo "failed to parse"; exit 1; }
  13         elements[${BASH_REMATCH[1]}]=${BASH_REMATCH[1]}
  14         set ${BASH_REMATCH[2]}
  15         [[ $longest -gt $# ]] || longest=$#
  16         eval "${BASH_REMATCH[1]}+=('"$*"')"
  17         : $((count++))
  18     fi
  19     # cheat: after pre-reading the input, all elements start with capital
  20     # except 'e', but 'e' does not occur in target or any substitution.
  21     # Break input into per-element chunks
  22 done < <(sed 's/e/E/g; s/\([A-Z]\)/ \1/g')
  23 echo "read $count rules for ${elements[*]}, longest expansion $longest"
  24 exec 3>&1
  25 debug() {
  26     [[ ! ${DEBUG+set} ]] && return
  27     echo "$*" >&3
  28 }
  29 # contract n list... # output all contractions of the nth element of list
  30 contract() {
  31     debug "  contract: $@"
  32     local n=$1
  33     shift
  34     prefix=${@:1:$n}
  35     debug " prefix: $prefix"
  36     shift $n
  37     local el i tail=$*
  38     for el in ${elements[*]}; do
  39         [[ $el == E && ( $prefix || $# -gt 2) ]] && continue # trivial prune
  40         declare -n arr=$el
  41         for i in ${!arr[*]}; do
  42             case $tail" " in
  43                 ${arr[i]}" "*)
  44                     debug " matched $el[$i] (${arr[i]})"
  45                     echo $prefix $el ${tail#${arr[i]}}
  46             esac
  47         done
  48     done
  49 }
  50 list=$target
  51 gen=0
  52 nl=$'\n'
  53 while case "$nl$list$nl" in *"${nl}E$nl"*) false;; *) : ;; esac; do
  54     echo " generation $gen, list has $(echo "$list" | wc -l) lines"
  55     while read start; do
  56         set $start
  57         i=0
  58         while [[ $i -lt $# && $i -lt $longest ]]; do
  59             contract $i $start
  60             : $((i++))
  61         done
  62     done <<< "$list" > tmp
  63     list=$(sed '/^ /d' < tmp | sort -u)
  64     debug "list is:"$'\n'"$list"
  65     : $((gen++))
  66 done
  67 rm tmp
  68 echo "found target in $gen steps"