2015/advent17.sh

   1 limit=${1-150}
   2 count=0
   3 while read size; do
   4     sizes[$((count++))]=$size
   5 done
   6 i=$((1 << $count))
   7 echo "computing $i combinations of ${#sizes[*]} containers for limit $limit"
   8 solutions=0
   9 best=$count
  10 while ((--i)); do
  11     sum=0
  12     containers=()
  13     for j in ${!sizes[*]}; do
  14         if ((i & (1 << j))); then
  15             containers+=(${sizes[j]})
  16             sum=$((sum + sizes[j]))
  17         fi
  18     done
  19     if [[ $sum == $limit && ${#containers[*]} -le $best ]]; then
  20         echo ${containers[*]}
  21         if [[ $part1 || ${#containers[*]} == $best ]]; then
  22             : $((solutions++))
  23         else
  24             echo "better configuration found"
  25             solutions=1 best=${#containers[*]}
  26         fi
  27     fi
  28 done
  29 echo "$solutions total solutions"