2015/advent24.sh

   1 count=0
   2 sum=0
   3 while read line; do
   4     size[count++]=$line
   5     sum=$((sum+line))
   6 done
   7 if [[ $part1 ]]; then
   8     target=$((sum/3))
   9 else
  10     target=$((sum/4))
  11 fi
  12 echo "read $count lines, summing to $sum; target $target"
  13 # sum n... # set $sum, return 0 for exact, 1 for too high, 2 for too low
  14 sum() {
  15     sum=0
  16     for i; do
  17         sum=$((sum+i))
  18     done
  19     if [[ $sum -gt $target ]]; then
  20         return 1
  21     elif [[ $sum -lt $target ]]; then
  22         return 2
  23     fi
  24     return 0
  25 }
  26 # product n... # set $product, possibly $min
  27 product() {
  28     product=1
  29     for i; do
  30         product=$((product*i))
  31     done
  32     ((product < min)) && min=$product
  33 }
  34 min=$((1<<50))
  35 calls=0
  36 # pick n prefix sum list... # choose n more items from list, add to prefix/sum
  37 # output the list on success, return 1 if no output issued
  38 pick() {
  39     # echo "  pick $@"
  40     local n=$1 p=$2 s=$3 i l r=1
  41     shift 3
  42     if [[ $n == 1 ]]; then
  43         : $((calls++))
  44         ((calls % 10000)) || echo "   $calls"
  45         case " $* " in
  46             *" $((target-s)) "*)
  47                 echo $p $((target-s))
  48                 product $p $((target-s))
  49                 return 0 ;;
  50         esac
  51         return 1
  52     fi
  53     i=$(($#-n+1))
  54     while (( i-- )); do
  55         l=$1
  56         shift
  57         pick $((n-1)) "$l $p" $((s+l)) $* && r=0
  58     done
  59     return $r
  60 }
  61 # shave off early rounds
  62 tail=1
  63 while { sum ${size[*]: -$tail}; [[ $? == 2 ]]; }; do
  64     : $((tail++))
  65 done
  66 echo "last $tail items give sum of $sum, skipping to combinations of $tail"
  67 # iterate until we find a winner
  68 while ! pick $tail '' 0 ${size[*]}; do
  69     : $((tail++))
  70 done
  71 echo "made $calls calls, lowest quantum in group of $tail is $min"