2015/advent15.sh

   1 # visit n limit prefix... # output all visits of n items that sum to limit
   2 visit() {
   3     local n=$1 limit=$2 i
   4     shift 2
   5     if [[ $n == 1 ]]; then
   6         echo $* $limit
   7         return
   8     fi
   9     i=0
  10     while [[ $i -le $limit ]]; do
  11         visit $((n - 1)) $((limit - i)) $* $i
  12         : $((i++))
  13     done
  14 }
  15 debug() {
  16     [[ ! ${DEBUG+set} ]] && return
  17     echo "$*"
  18 }
  19
  20 count=0
  21 regex='(.*): capacity (.*), durability (.*), flavor (.*),'
  22 regex+=' texture (.*), calories (.*)'
  23 while read line; do
  24     [[ $line =~ $regex ]] || { echo 'unable to parse line'; exit 1; }
  25     name[$count]=${BASH_REMATCH[1]}
  26     cap[$count]=${BASH_REMATCH[2]}
  27     dur[$count]=${BASH_REMATCH[3]}
  28     fla[$count]=${BASH_REMATCH[4]}
  29     tex[$count]=${BASH_REMATCH[5]}
  30     cal[$count]=${BASH_REMATCH[6]}
  31     : $((count++))
  32 done
  33 echo "parsed details on $count ingredients"
  34 # score values... # set score to the combination of the values
  35 score() {
  36     local key=$*
  37     debug "score for weights $key: "
  38     if [[ $# != $count ]]; then
  39         echo "wrong number of weights"; exit 1
  40     fi
  41     local weight=0 count=0 i
  42     c=0 d=0 f=0 t=0 C=0
  43     for i; do
  44         if [[ $1 -lt 0 || $(($1 + weight)) -gt 100 ]]; then
  45             echo "huh? $1 $i $weight"
  46             score=0
  47             return
  48         fi
  49         weight=$((weight + $1))
  50         c=$((c + $1 * ${cap[$count]}))
  51         d=$((d + $1 * ${dur[$count]}))
  52         f=$((f + $1 * ${fla[$count]}))
  53         t=$((t + $1 * ${tex[$count]}))
  54         C=$((C + $1 * ${cal[$count]}))
  55         : $((count++))
  56         shift
  57     done
  58     if [[ $C != 500 ]]; then
  59         score=0
  60     elif case $c$d$f$t in *-*) score=0; false ;; *) : ;; esac; then
  61         score=$((c * d * f * t))
  62     fi
  63     debug "$score"
  64 }
  65 best=0 tries=0
  66 while read line; do
  67     ! ((tries % 1000)) && echo $tries
  68     : $((tries++))
  69     score $line
  70     [[ $best -lt $score ]] && best=$score
  71 done < <(visit $count 100)
  72 echo "after $tries tries, best score is $best"