2015/advent22.sh

   1 read _ _ boss_hit
   2 read _ boss_damage
   3 echo "input: $boss_hit $boss_damage"
   4 exec 3>&1
   5 debug() {
   6     [[ ! ${DEBUG+set} ]] && return
   7     echo "$*" >&3
   8 }
   9 spells=(missile drain shield poison recharge)
  10 cost=(53 73 113 173 229)
  11 minspent=99999
  12 # battle spell hit mana spent shield poison recharge boss_hit
  13 # return 0 (and sets $spent) for win, 1 for loss/not possible, 2 + output
  14 # to continue, 3 to prune path as non-maximal
  15 battle() {
  16     debug " battle $@" >&3
  17     if [[ $# != 8 ]]; then
  18         echo " invalid input" >&3
  19         return 1
  20     fi
  21     spent=$4
  22     if [[ $spent -gt $minspent ]]; then
  23         debug " not a minimal path, pruning rather than following"
  24         return 3
  25     fi
  26     local spell=$1 hit=$2 mana=$3 shield=$5 poison=$6 recharge=$7 boss=$8
  27     debug "player turn"
  28     debug " player has $hit hit points, $((7*!!shield)) armor, $mana mana"
  29     debug " boss has $boss hit points"
  30     if [[ ! $part1 && $((--hit)) == 0 ]]; then
  31         debug " hard mode, hit points ran out"
  32         return 1
  33     fi
  34     if [[ $shield -gt 0 ]]; then
  35         : $((shield--))
  36         debug " shield effect down to $shield"
  37     fi
  38     if [[ $shield -gt 0 && $spell == 2 ]]; then
  39         debug " shield effect still active"
  40         return 1
  41     fi
  42     if [[ $poison -gt 0 ]]; then
  43         boss=$((boss-3))
  44         : $((poison--))
  45         debug " poison effect down to $poison"
  46     fi
  47     if [[ $poison -gt 0 && $spell = 3 ]]; then
  48         debug " poison effect still active"
  49         return 1
  50     fi
  51     if [[ $recharge -gt 0 ]]; then
  52         mana=$((mana+101))
  53         : $((recharge--))
  54         debug " recharge effect down to $recharge, mana up to $mana"
  55     fi
  56     if [[ $recharge -gt 0 && $spell = 4 ]]; then
  57         debug " recharge effect still active"
  58         return 1
  59     fi
  60     if [[ ${cost[$spell]} -gt $mana ]]; then
  61         debug " not enough mana left"
  62         return 1
  63     fi
  64     debug " casting ${spells[$spell]}"
  65     mana=$((mana - cost[spell]))
  66     spent=$((spent + cost[spell]))
  67     case $spell in
  68         0) boss=$((boss-4)) ;;
  69         1) boss=$((boss-2)) hit=$((hit+2)) ;;
  70         2) shield=6 ;;
  71         3) poison=6 ;;
  72         4) recharge=5 ;;
  73     esac
  74     if [[ $boss -le 0 ]]; then
  75         debug " boss defeated"
  76         return 0
  77     fi
  78
  79     debug "boss turn"
  80     debug " player has $hit hit points, $((7*!!shield)) armor, $mana mana"
  81     debug " boss has $boss hit points"
  82     if [[ $shield -gt 0 ]]; then
  83         : $((shield--))
  84         debug " shield effect down to $shield"
  85     fi
  86     if [[ $poison -gt 0 ]]; then
  87         boss=$((boss-3))
  88         : $((poison--))
  89         debug " poison effect down to $poison"
  90     fi
  91     if [[ $recharge -gt 0 ]]; then
  92         mana=$((mana+101))
  93         : $((recharge--))
  94         debug " recharge effect down to $recharge, mana up to $mana"
  95     fi
  96     if [[ $boss -le 0 ]]; then
  97         debug " boss defeated"
  98         return 0
  99     fi
 100     hit=$((hit - boss_damage + 7*!!shield))
 101     if [[ $hit -le 0 ]]; then
 102         debug " player defeated"
 103         return 1
 104     fi
 105     echo $hit $mana $spent $shield $poison $recharge $boss
 106     return 2
 107 }
 108 hit=${1-50} mana=${2-500}
 109 echo $hit $mana 0 0 0 0 $boss_hit > tmp
 110 gen=0
 111 wins=0
 112 scenarios=0
 113 while [[ -s tmp ]]; do
 114     echo "computing generation $((++gen)) from $(wc -l < tmp) scenarios"
 115     while read line; do
 116         : $((scenarios++))
 117         for i in {0..4}; do
 118             battle $i $line
 119             if [[ $? == 0 ]]; then
 120                 : $((wins++))
 121                 (( spent < minspent )) && minspent=$spent
 122             fi
 123         done
 124     done < tmp > tmp2
 125     sort -k4,4n -k8,8rn < tmp2 | uniq > tmp
 126 done
 127 rm tmp tmp2
 128 echo "traced $scenarios possible sequences over $gen generations"
 129 echo "computed $wins different win paths; cheapest cost $minspent mana"