2015/advent13.sh

   1 debug() {
   2     [[ ! ${DEBUG+set} ]] && return
   3     echo "$*"
   4 }
   5 indent=
   6 # http://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/
   7 # _permute size n # helper for permute, munges $arr
   8 _permute() {
   9     debug "$indent in _permute $@ ${arr[*]}"
  10     indent+=" "
  11     if [[ $1 == 1 ]]; then
  12         shift 2
  13         echo ${arr[*]}
  14         indent=${indent%?}
  15         return
  16     fi
  17     local size=$1 n=$2 tmp i
  18     i=0
  19     while [[ $i -lt $size ]]; do
  20         _permute $((size-1)) $n
  21         if [[ $((size%2)) == 1 ]]; then
  22             debug "$indent $size odd, swapping first and last"
  23             tmp=${arr[0]}
  24             arr[0]=${arr[$((size-1))]}
  25             arr[$((size-1))]=$tmp
  26         else
  27             debug "$indent $size even, swapping $i and last"
  28             tmp=${arr[$i]}
  29             arr[$i]=${arr[$((size-1))]}
  30             arr[$((size-1))]=$tmp
  31         fi
  32         i=$((i+1))
  33     done
  34     debug "$indent leaving $size $n ${arr[*]}"
  35     indent=${indent%?}
  36 }
  37 # permute n # outputs n! lines, for each possible permutation
  38 permute() {
  39     local arr=() i=0
  40     while [[ $i -lt $1 ]]; do
  41         arr+=($i)
  42         i=$((i+1))
  43     done
  44     _permute $1 $1
  45 }
  46
  47 unset people change
  48 declare -A change
  49 count=0 lines=0
  50 while read a amt b; do
  51     : $((lines++))
  52     case " ${people[*]} " in
  53         *" $a "*) ;;
  54         *) people[$((count++))]=$a ;;
  55     esac
  56     change[$a.$b]=$amt
  57 done < <(sed 's/would gain //; s/would lose /-/; s/happ.*next to //; s/.$//')
  58 echo "read $lines lines, found ${#change[*]} rules among ${#people[*]} people:"
  59 echo ${people[*]}
  60 [[ ! $part1 ]] && people+=("you")
  61 max=0
  62 while read first rest; do
  63     echo trying $first $rest
  64     sum=0
  65     set $rest $first
  66     prev=$first
  67     for next; do
  68         sum=$((${change[${people[$prev]}.${people[$next]}]}+sum))
  69         sum=$((${change[${people[$next]}.${people[$prev]}]}+sum))
  70         prev=$next
  71     done
  72     echo $sum
  73     [[ $sum -gt $max ]] && max=$sum
  74 done < <(permute ${#people[*]})
  75 echo "max happiness $max"