By Eric Burden | December 14, 2020
In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.
Also, as a general convention, whenever the puzzle has downloadable input, I’m
saving it in a file named input.txt.
Day 13 - Shuttle Search
Find the problem description HERE.
Part One - Waiting Game
For this part, we’re keeping track of ’timestamps’ as integers and attempting to identify the next bus to arrive and how long in ‘minutes’ we’ll need to wait for that bus. We’ll use vectorization to calculate the wait times for all the buses and pick the one that’s smallest.
test_input <- c(
"939",
"7,13,x,x,59,x,31,19"
)
real_input <- readLines('input.txt')
# Helper function, given the lines from the input file `input`,
# returns a list containing the departure time and a list of the
# bus schedules ([7, 13, 59, 31, 19] from the test input)
parse_input <- function(input) {
depart_time <- as.numeric(input[1])
bus_schedule <- as.numeric(strsplit(input[2], ',[x,]*')[[1]])
list(depart_time = depart_time, bus_schedule = bus_schedule)
}
# Helper function, given your desired departure time `depart_time` and a bus's
# schedule `bus_interval`, returns the 'timestamp' of that bus's next arrival
# time immediately following `depart_time`, vectorized
get_next_arrival_time <- function(depart_time, bus_interval) {
ceiling(depart_time/bus_interval)*bus_interval
}
# Helper function, given your desired departure time `depart_time` and a bus's
# schedule `bus_interval`, returns the time between `depart_time` and the
# bus's next arrival 'timestamp', vectorized
get_wait_time <- function(depart_time, bus_interval) {
next_arrival <- get_next_arrival_time(depart_time, bus_interval)
next_arrival - depart_time
}
notes <- parse_input(real_input) # Parse the input
# Calculate the wait time for all buses
wait_time <- get_wait_time(notes$depart_time, notes$bus_schedule)
next_bus <- notes$bus_schedule[which.min(wait_time)] # The bus with shortest wait
answer1 <- next_bus * min(wait_time)
No sweat! If today is like day 12, this should be a fairly quick part 2.
Part Two - I Was Wrong
OK, first off, let me be clear: I do not understand how this works. I have some
vague notion that there should be some mathematical way to calculate the
point at which a set of repeating numbers intersect. The internet tells me that,
given a set of numbers that are
pairwise co-prime
and their offsets (moduli) from some unknown number, the
chinese remainder theorem
is the approach for finding that unknown number. Got it. Here’s the thing, after
reading multiple articles on this approach, watching a couple of YouTube
videos, and implementing this algorithm in R based on an example in pseudocode,
it failed spectacularly. Over and over again. My solution worked on several
example problems, but not on the AoC input. After several days, several
failures, and too much research, I realized that the issue was R’s default
floating point precision was insufficient for this problem! Gragh!!! Thankfully,
the Rmpfr library saved the day. Here’s the result:
library(Rmpfr)
# Helper function, given an integer `a` and modulo `m`, calculate the modular
# multiplicative inverse. Based on the Extended Euclidean Algorithm :
# https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
multiplicative_inverse <- function(a, m) {
original_m <- m
old_t <- 0L
t <- 1L
if (m == 1) return(1L)
while(a > 1){
quotient <- a %/% m
temp <- m
m <- a %% m
a <- temp
temp <- old_t
old_t <- t - quotient * old_t
t <- temp
}
if (t < 0) t <- t + original_m
return(t)
}
# Helper function, given a list of numbers `n` and a list of offsets `a` from
# some unknown number, calculate the value of the unknown number. Based on
# the Chinese Remainder Theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
chinese_remainder <- function(n, a) {
all_prod <- prod(n)
remainders <- all_prod/n
mult_inverses <- mapply(multiplicative_inverse, remainders, n)
remainders <- mpfr(remainders, precBits = 60)
sum(remainders * a * mult_inverses) %% all_prod
}
# Main function, given a list of bus ids/route times `bus_schedule`, returns the
# first number that satisfies the puzzle requirements
bus_route_intersection <- function(bus_schedule) {
offsets <- which(bus_schedule != 'x') - 1
buses <- as.numeric(bus_schedule[bus_schedule != 'x'])
offset_mods <- -buses %% offsets
chinese_remainder(buses, offsets)
}
bus_schedule <- unlist(strsplit(real_input[2], ",")) # Parse the input
answer2 <- bus_route_intersection(bus_schedule) # Get the answer
It works.
Wrap-Up
I’m not sure how to feel about this one. I feel like this was the sort of problem where there was absolutely no way I could have come up with a solution on my own and I would have either needed to have heard about Chinese Remainder Theorem before (maybe from my non-existent CS degree) or gotten lucky with my Googling (because I didn’t start out with the right terms for this problem.) I’m happy to have learned something interesting, but it wasn’t a fun process.
If you found a different solution (or spotted a mistake in one of mine), please drop me a line!