From: Brett Parker <iDunno@sommitrealweird.co.uk>
Date: Sun, 13 Dec 2020 21:13:06 +0000 (+0000)
Subject: Day 13 - forays in to using Diophantine did not go well.
X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2020.git/commitdiff_plain/61a73a00535337fa5b2780440d643052877ca036?ds=sidebyside;hp=b00850e41d65e881da505d79350c06f06b64fcba

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

diff --git a/day13/README b/day13/README
new file mode 100644
index 0000000..4b457b5
--- /dev/null
+++ b/day13/README
@@ -0,0 +1 @@
+files starting p2_ are for testing p2, and the number before .txt is the expected result, likewise, files named p1_ for p1.
diff --git a/day13/get_bus.sh b/day13/get_bus.sh
new file mode 100755
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]}))"
+
diff --git a/day13/input.txt b/day13/input.txt
new file mode 100644
index 0000000..2ff076c
--- /dev/null
+++ b/day13/input.txt
@@ -0,0 +1,2 @@
+1008713
+13,x,x,41,x,x,x,x,x,x,x,x,x,467,x,x,x,x,x,x,x,x,x,x,x,19,x,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,353,x,x,x,x,x,37,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,23
diff --git a/day13/p1_295.txt b/day13/p1_295.txt
new file mode 100644
index 0000000..d76f619
--- /dev/null
+++ b/day13/p1_295.txt
@@ -0,0 +1,2 @@
+939
+7,13,x,x,59,x,31,19
diff --git a/day13/p2_3417.txt b/day13/p2_3417.txt
new file mode 100644
index 0000000..0979fcf
--- /dev/null
+++ b/day13/p2_3417.txt
@@ -0,0 +1,2 @@
+1234
+17,x,13,19
diff --git a/day13/p2_754018.txt b/day13/p2_754018.txt
new file mode 100644
index 0000000..ae171da
--- /dev/null
+++ b/day13/p2_754018.txt
@@ -0,0 +1,2 @@
+12345
+67,7,59,61