day06/get_orbits.sh

   1 #!/bin/bash
   2
   3 set -u
   4 set -e
   5
   6 declare -A orbits
   7 declare -A reverse_orbits
   8
   9 exec 3<input.txt
  10
  11 while read -u 3 line; do
  12     base_object=${line%)*}
  13     orbit_object=${line#*)}
  14
  15     if [ ${orbits[$base_object]+a} ]; then
  16         orbits[$base_object]+=",$orbit_object"
  17     else
  18         orbits[$base_object]=$orbit_object
  19     fi
  20
  21     if [ ${reverse_orbits[$orbit_object]+a} ]; then
  22         reverse_orbits[$orbit_object]+=",$base_object"
  23     else
  24         reverse_orbits[$orbit_object]=$base_object
  25     fi
  26 done
  27
  28 get_orbits() {
  29     planet=$1
  30     indirect=$2
  31     local total_orbits=0
  32
  33     IFS=","
  34     if [ ${orbits[$planet]+a} ]; then
  35         for p in ${orbits[$planet]}; do
  36             o=$(get_orbits $p $((indirect+1)))
  37             total_orbits=$((total_orbits+$o+$indirect))
  38         done
  39     fi
  40     echo $total_orbits
  41 }
  42
  43 get_path() {
  44     start_point=$1
  45     end_point=$2
  46     last_start=$3
  47     local offset=${4:-0}
  48     local path=${5:-$start_point}
  49     local shortest_path=-1
  50     local shortest_path_text=""
  51
  52     local got_path=0
  53
  54     IFS=","
  55     # check forwards
  56     if [ ${orbits[$start_point]+a} ]; then
  57         for p in ${orbits[$start_point]}; do
  58             if [ "$p" == "$last_start" ]; then
  59                 continue
  60             fi
  61             if [ $p == $end_point ]; then
  62                 shortest_path=$offset
  63                 shortest_path_text="$path $p"
  64                 echo $((shortest_path - 1))
  65                 exit 0
  66             else
  67                 o="$(get_path $p $end_point $start_point $((offset+1)) "$path $p")"
  68                 exit_code=$?
  69                 if [ $exit_code -eq 0 ]; then
  70                     if [ $shortest_path -eq -1 ] || [ $o -lt $shortest_path ]; then
  71                         shortest_path=$o
  72                         shortest_path_text="$path $p"
  73                         got_path=1
  74                     fi
  75                 fi
  76             fi
  77         done
  78     fi
  79
  80     if [ $got_path -eq 1 ]; then
  81         echo $shortest_path
  82         exit 0
  83     fi
  84
  85     # otherwise, time to check other paths
  86     if [ ${reverse_orbits[$start_point]+a} ]; then
  87         for p in ${reverse_orbits[$start_point]}; do
  88             if [ "$p" == "$last_start" ]; then
  89                 continue
  90             fi
  91             if [ "$p" == "$end_point" ]; then
  92                 shortest_path=$offset
  93                 shortest_path_text="$path $p"
  94                 echo $((shortest_path - 1))
  95                 exit 0
  96             else
  97                 o="$(get_path $p $end_point $start_point $((offset+1)) "$path $p")"
  98                 exit_code=$?
  99                 if [ $exit_code -eq 0 ]; then
 100                     if [ $shortest_path -eq -1 ] || [ $o -lt $shortest_path ]; then
 101                         shortest_path=$o
 102                         shortest_path_text="$path $p"
 103                         got_path=1
 104                     fi
 105                 fi
 106             fi
 107         done
 108     fi
 109
 110     if [ $got_path -eq 1 ]; then
 111         echo $shortest_path
 112         got_path=0
 113         exit 0
 114     fi
 115
 116     exit 1
 117 }
 118
 119 echo -n "Orbits: "
 120 get_orbits COM 1
 121
 122 shortest_path=-1
 123 path=$(get_path YOU SAN "")
 124 echo "Shortest path from YOU -> SAN: $path"