Advent of Code 2020 - Day 13
Published: 2021-11-28 02:17:51

---
title: Advent of Code 2020 - Day 13
published: true
date: 2020-12-14 00:00:00 UTC
tags: 
canonical_url: https://ericburden.work/blog/2020/12/14/advent-of-code-2020-day-13/
---

In the spirit of the holidays (and programming), I’ll be posting my solutions to the [Advent of Code 2020](https://adventofcode.com/) 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](https://adventofcode.com/2020/day/13).

## 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.

```r
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](https://en.wikipedia.org/wiki/Coprime_integers#Coprimality_in_sets) and their offsets (moduli) from some unknown number, the [chinese remainder theorem](https://shainer.github.io/crypto/math/2017/10/22/chinese-remainder-theorem.html) 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:

```r
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!