From bcb44f33292aa19afb49b6aafb4e60631b7de6cd Mon Sep 17 00:00:00 2001
From: Brett Parker <iDunno@sommitrealweird.co.uk>
Date: Mon, 7 Dec 2020 00:42:29 +0000
Subject: [PATCH] First part
---
day6/get_orbits.sh | 98 ++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 98 insertions(+)
create mode 100644 day6/get_orbits.sh
diff --git a/day6/get_orbits.sh b/day6/get_orbits.sh
new file mode 100644
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
+
--
2.39.5