From: Brett Parker 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 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