First part

diff --git a/day6/get_orbits.sh b/day6/get_orbits.sh
new file mode 100644 (file)
index 0000000..a6d886f
--- /dev/null
+++ b/day6/get_orbits.sh
@@ -0,0 +1,98 @@
+#!/bin/bash
+
+declare -A orbits
+declare -A reverse_orbits
+
+exec 3<input.txt
+
+while read -u 3 line; do
+    base_object=${line%)*}
+    orbit_object=${line#*)}
+
+    if [ ${orbits[$base_object]+a} ]; then
+        orbits[$base_object]+=",$orbit_object"
+    else
+        orbits[$base_object]=$orbit_object
+    fi
+
+    if [ ${reverse_orbits[$orbit_object]+a} ]; then
+        reverse_orbits[$orbit_object]+=",$base_object"
+    else
+        reverse_orbits[$orbit_object]=$base_object
+    fi
+done
+
+get_orbits() {
+    planet=$1
+    indirect=$2
+    local total_orbits=0
+
+    IFS=","
+    for p in ${orbits[$planet]}; do
+        o=$(get_orbits $p $((indirect+1)))
+        total_orbits=$((total_orbits+$o+$indirect))
+    done
+    echo $total_orbits
+}
+
+get_path() {
+    start_point=$1
+    end_point=$2
+    last_start=$3
+    offset=$4
+
+    echo "$start_point $end_point $last_start $offset" >&2
+
+    IFS=","
+    # check forwards
+    if [ ${#orbits[$start_point]} -gt 0 ]; 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
+            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
+                    fi
+                fi
+            fi
+        done
+    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))
+            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
+                fi
+            fi
+        fi
+    done
+
+    echo $shortest_path
+}
+
+#get_orbits COM 1
+
+shortest_path=-1
+get_path YOU SAN "" 0
+