2015/advent9.sh

   1 unset places distances
   2 declare -A places distances
   3 count=0
   4 while read a to b eq l; do
   5     if [[ ! ${places[$a]+set} ]]; then
   6         places[$a]=$a
   7         list[$count]=$a
   8         count=$((count+1))
   9     fi
  10     if [[ ! ${places[$b]+set} ]]; then
  11         places[$b]=$b
  12         list[$count]=$b
  13         count=$((count+1))
  14     fi
  15     distances[$a.$b]=$l
  16     distances[$b.$a]=$l
  17 done
  18 echo "parsed ${#list[*]} places: ${list[*]}"
  19 attempt=0
  20 indent=
  21 shortest=9999999999999
  22 longest=0
  23 # debug message
  24 debug() {
  25     [[ ! ${DEBUG+set} ]] && return
  26     echo "$*"
  27 }
  28 # visit seed places...
  29 visit() {
  30     debug "${indent}visit $@"
  31     indent+=" "
  32     local seed=$1 place
  33     shift
  34     for place; do
  35         compute $seed $place $*
  36     done
  37     indent=${indent%?}
  38 }
  39 # compute seed start places... # places includes start
  40 compute() {
  41     debug "${indent}compute $@"
  42     indent+=" "
  43     if [[ $# == 3 ]]; then
  44         debug "${indent}computed $1"
  45         try[$attempt]=$1
  46         [[ $1 -lt $shortest ]] && shortest=$1
  47         [[ $1 -gt $longest ]] && longest=$1
  48         attempt=$((attempt+1))
  49         indent=${indent%?}
  50         return
  51     fi
  52     local sublist=() seed=$1 start=$2 place
  53     shift 2
  54     for place; do
  55         [[ $place != $start ]] && sublist+=($place)
  56     done
  57     for place in ${sublist[*]}; do
  58         try $seed $start $place ${sublist[*]}
  59     done
  60     indent=${indent%?}
  61 }
  62 # try seed start dest places... # places includes dest, but not start
  63 try() {
  64     debug "${indent}try $@"
  65     indent+=" "
  66     local seed=$1 start=$2
  67     shift 2
  68     compute $(($seed+${distances[$start.$1]})) $*
  69     indent=${indent%?}
  70 }
  71 visit 0 ${list[*]}
  72 echo "computed $attempt permutations, shortest $shortest, longest $longest"