day6/get_orbits.sh

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