Day 6 Part 2

[advent-of-code-2019.git] / day6 / get_orbits.sh

diff --git a/day6/get_orbits.sh b/day6/get_orbits.sh
index a6d886fe821b701987b6f9ad1ea72b210fbabd9b..13fbebfbd561f7db33e2dec9702c225d87594006 100644 (file)
--- a/day6/get_orbits.sh
+++ b/day6/get_orbits.sh
@@ -1,5 +1,8 @@
 #!/bin/bash
 
+set -u
+set -e
+
 declare -A orbits
 declare -A reverse_orbits
 
@@ -28,10 +31,12 @@ get_orbits() {
     local total_orbits=0
 
     IFS=","
-    for p in ${orbits[$planet]}; do
-        o=$(get_orbits $p $((indirect+1)))
-        total_orbits=$((total_orbits+$o+$indirect))
-    done
+    if [ ${orbits[$planet]+a} ]; then
+        for p in ${orbits[$planet]}; do
+            o=$(get_orbits $p $((indirect+1)))
+            total_orbits=$((total_orbits+$o+$indirect))
+        done
+    fi
     echo $total_orbits
 }
 
@@ -39,60 +44,81 @@ get_path() {
     start_point=$1
     end_point=$2
     last_start=$3
-    offset=$4
+    local offset=${4:-0}
+    local path=${5:-$start_point}
+    local shortest_path=-1
+    local shortest_path_text=""
 
-    echo "$start_point $end_point $last_start $offset" >&2
+    local got_path=0
 
     IFS=","
     # check forwards
-    if [ ${#orbits[$start_point]} -gt 0 ]; then
+    if [ ${orbits[$start_point]+a} ]; then
         for p in ${orbits[$start_point]}; do
             if [ "$p" == "$last_start" ]; then
                 continue
             fi
             if [ $p == $end_point ]; then
-                echo $((offset+1))
-                if [ $shortest_path -eq -1 ] || [ $offset -lt $shortest_path]; then
-                    shortest_path=$((offset))
-                fi
-                return 0
+                shortest_path=$offset
+                shortest_path_text="$path $p"
+                echo $((shortest_path - 1))
+                exit 0
             else
-                o=$(get_path $p $end_point $start_point $((offset+1)))
-                if [ $? -eq 0 ]; then
+                o="$(get_path $p $end_point $start_point $((offset+1)) "$path $p")"
+                exit_code=$?
+                if [ $exit_code -eq 0 ]; then
                     if [ $shortest_path -eq -1 ] || [ $o -lt $shortest_path ]; then
                         shortest_path=$o
+                        shortest_path_text="$path $p"
+                        got_path=1
                     fi
                 fi
             fi
         done
     fi
 
+    if [ $got_path -eq 1 ]; then
+        echo $shortest_path
+        exit 0
+    fi
+
     # otherwise, time to check other paths
-    for p in ${reverse_orbits[$start_point]}; do
-        if [ "$p" == "$last_start" ]; then
-            continue
-        fi
-        if [ "$p" == "$end_point" ]; then
-            echo $((offset+1))
-            if [ $shortest_path -eq -1 ] || [ $offset -lt $shortest_path]; then
-                shortest_path=$((offset))
+    if [ ${reverse_orbits[$start_point]+a} ]; then
+        for p in ${reverse_orbits[$start_point]}; do
+            if [ "$p" == "$last_start" ]; then
+                continue
             fi
-            return 0
-        else
-            o=$(get_path $p $end_point $start_point $((offset+1)))
-            if [ $? -eq 0 ]; then
-                if [ $shortest_path -eq -1 ] || [ $o -lt $shortest_path ]; then
-                    shortest_path=$o
+            if [ "$p" == "$end_point" ]; then
+                shortest_path=$offset
+                shortest_path_text="$path $p"
+                echo $((shortest_path - 1))
+                exit 0
+            else
+                o="$(get_path $p $end_point $start_point $((offset+1)) "$path $p")"
+                exit_code=$?
+                if [ $exit_code -eq 0 ]; then
+                    if [ $shortest_path -eq -1 ] || [ $o -lt $shortest_path ]; then
+                        shortest_path=$o
+                        shortest_path_text="$path $p"
+                        got_path=1
+                    fi
                 fi
             fi
-        fi
-    done
+        done
+    fi
+
+    if [ $got_path -eq 1 ]; then
+        echo $shortest_path
+        got_path=0
+        exit 0
+    fi
 
-    echo $shortest_path
+    exit 1
 }
 
-#get_orbits COM 1
+echo -n "Orbits: "
+get_orbits COM 1
 
 shortest_path=-1
-get_path YOU SAN "" 0
-
+path=$(get_path YOU SAN "")
+echo "Shortest path from YOU -> SAN: $path"