day13.Rmd

---
title: "--- Day 13: Shuttle Search ---"
author: Fleur Kelpin
date: Dec 13, 2020
output: github_document
---

```{r message=FALSE, warning=FALSE}
library(tidyverse)
input <- readLines("day13.txt")
timestamp <- as.integer(input[[1]])
buses <- tibble(id = input[[2]]) %>%
  separate_rows(id) %>%
  mutate(row = as.integer(row_number())) %>%
  filter(id != "x") %>%
  type_convert(cols(id = col_integer()))
buses
```
# Part 1

What is the ID of the earliest bus you can take to the airport multiplied by the 
number of minutes you'll need to wait for that bus?

```{r}
first <-
  buses %>%
  mutate(wait = id - timestamp %% id) %>%
  filter(wait == min(wait))
first$id[[1]] * first$wait[[1]]
```
# Part 2

What is the earliest timestamp such that all of the listed bus IDs depart at
offsets matching their positions in the list?

This comes down to solving a series of equations in the shape `x ≡ a_i mod n_i`.
We need an implementation of the chinese rest theorem.
Unfortunately, the one in the numbers package only works for ordinary integers
and works for all examples but overflows on the actual puzzle input.

Hand-rolled implementation adapted from https://codeforces.com/blog/entry/61290
does an extra division to prevent overflow.
```{r message=FALSE, warning=FALSE}
library(numbers)
normalize <- function(x, mod) {
  x <- x %% mod
  if (x < 0) {
    x <- x + mod
  }
  x
}
chinese_no_overflow <- function(a, n) {
  ans <- a[[1]]
  lcm <- n[[1]]
  for (i in 2:length(a)) {
    pom <- extGCD(lcm, n[i])
    d <- pom[[1]]
    x1 <- pom[[2]]
    if ((a[i] - ans) %% d != 0) {
      print("no solutions")
      return(NA)
    }
    
    ans <- normalize(
      ans + x1 * (a[i] - ans) %/% d %% (n[i] %/% d) * lcm,
      (n[i] %/% d) * lcm
    )
    lcm <- LCM(lcm, n[i])
  }
  ans
}
options(digits=22)
buses <- buses %>%
  mutate(mod = (id - row + 1) %% id)
chinese_no_overflow(buses$mod, buses$id)
```