Day 13 - forays in to using Diophantine did not go well.

[advent-of-code-2020.git] / day13 / get_bus.sh

diff --git a/day13/get_bus.sh b/day13/get_bus.sh
new file mode 100755 (executable)
index 0000000..6df9693
--- /dev/null
+++ b/day13/get_bus.sh
@@ -0,0 +1,68 @@
+#!/bin/bash
+
+read_file() {
+    local filename="$1"
+    local IFS=","
+    declare -g earliest_leave_time
+    declare -g -a buses
+    exec 3<"$filename"
+    read -u 3 earliest_leave_time
+    read -u 3 -a buses
+}
+
+filename=${1:-p1_295.txt}
+
+read_file "$filename"
+
+echo "Earliest leave_time: $earliest_leave_time"
+echo "Buses: ${buses[@]}"
+
+bus_to_catch=0
+time_difference=-1
+
+for bus in ${buses[@]}; do
+    if [ "$bus" == "x" ]; then
+        continue
+    fi
+    # work out how many times this goes in
+    # to earliest time stamp
+    multiplier=$(($earliest_leave_time / $bus))
+    while [ $((bus * $multiplier)) -lt $earliest_leave_time ]; do
+        multiplier=$((multiplier+1))
+    done
+    if [ $(((bus*multiplier)-$earliest_leave_time)) -lt $time_difference ] || [ $time_difference -eq -1 ]; then
+        time_difference=$(((bus*$multiplier)-$earliest_leave_time))
+        bus_to_catch=$bus
+    fi
+done
+
+echo "Part 1:"
+echo "  Bus to catch: $bus_to_catch"
+echo "  Gotta wait: $time_difference"
+echo "  Answer: $((bus_to_catch * $time_difference))"
+
+echo "Part 2:"
+
+# screw it, we've got prime bus numbers, lets
+# just loop a bit, and make the step the multiple
+
+loop=1
+offset=0
+step=${buses[0]}
+for a in "${buses[@]:1}"; do
+    count=0
+    if [ $a == "x" ]; then
+        loop=$((loop+1))
+        continue
+    fi
+    # we need to check a multiple of steps past the offset
+    while [ $((((($offset*${buses[0]}) + ($count*$step)) + $loop) % $a)) -ne 0 ]; do
+        count=$((count+1))
+    done
+    offset=$(($offset + (($count*$step)/${buses[0]})))
+    step=$((step*$a)) # our steps are going to be a product of what we had
+    loop=$((loop+1))
+done
+
+echo "  Timestamp: $((offset*${buses[0]}))"
+