13.md

Day 13

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?

const input = `
939
7,13,x,x,59,x,31,19
`.trim()

const lines = input.split('\n')
const targetTimestamp = lines[0]
const ids = lines[1]
  .split(',')
  .map((id) => +id)
  .filter((id) => !Number.isNaN(id))
const earliest = ids.reduce(
  (earliest, id) => {
    const departureTime = id * Math.ceil(targetTimestamp / id)
    return earliest.departureTime > departureTime
      ? { id, departureTime }
      : earliest
  },
  { id: 0, departureTime: Infinity }
)

const result = earliest.id * (earliest.departureTime - targetTimestamp)
console.log(result)

Try it out on flems.io

Part 2

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

I first tried looping like this:

const ids = input
  .split('\n')[1]
  .split(',')
  .map((id, i) => ({ id: +id, offset: i }))
  .filter(({ id }) => !Number.isNaN(id))

function getTimestamp() {
  for (let i = 1; true; i++) {
    const timestamp = ids[0].id * i
    const isCorrect = ids.slice(1).every(({ id, offset }) => {
      return (timestamp + offset) % id === 0
    })
    if (isCorrect) return timestamp
  }
}

const timestamp = getTimestamp()
console.log(timestamp)

It worked well for the sample inputs (took only ~30 milliseconds on my machine for the largest sample input), but was unpractically inefficient for the real puzzle input. I even moved the calculations to 10 parallel Web Workers and let them run for an hour or two, but didn't get the result in that time.

Then I noticed in the Advent of Code subreddit that this problem can be solved efficiently using Chinese remainder theorem. After studying a couple of resources, my understanding is that the theorem looks and works like this (in math notation):

x ≡ a₁  (mod n₁)
x ≡ a₂  (mod n₂)
x ≡ a₃  (mod n₃)
...
x ≡ aᵢ  (mod nᵢ)

Thanks to high school, I know that the above is basically the same as this in JavaScript:

x % n1 === a1
x % n2 === a2
x % n3 === a3
// ...
x % ni === ai

For the theorem to be applicable, the variables n₁, n₂, n₃, ..., nᵢ have to be pairwise coprime – no pair can have any positive integer factors in common, aside from 1. Looks like all sample inputs and the real puzzle input match this condition.

x, which is the timestamp in our case, can be solved with this formula:

x = a₁ * b₁ * (N / n₁) +
    a₂ * b₂ * (N / n₂) +
    a₃ * b₃ * (N / n₃) +
    ... +
    aᵢ * bᵢ * (N / nᵢ)   (mod N)

where:

  N = n₁ * n₂ * n₃ * ... * nᵢ

and where the `b` variables can be derived from these:

  b₁ * (N / n₁) ≡ 1  (mod n₁)
  b₂ * (N / n₂) ≡ 1  (mod n₂)
  b₃ * (N / n₃) ≡ 1  (mod n₃)
  ...
  bᵢ * (N / nᵢ) ≡ 1  (mod nᵢ)

Let's take this sample input as an example:

67,7,x,59,61 first occurs at timestamp 1261476.

With these values the theorem looks like this:

x ≡  0      (mod 67)
x ≡  7 - 1  (mod  7)
(the `x` is skipped)
x ≡ 59 - 3  (mod 59)
x ≡ 61 - 4  (mod 61)

The first line is clear because surely the timestamp (x) has to be dividable by the first ID (67). The rest can be derived from these alternate forms:

x     ≡  0  (mod 67)
x + 1 ≡  7  (mod  7)
(the `x` is skipped)
x + 3 ≡ 59  (mod 59)
x + 4 ≡ 61  (mod 61)

The formula for solving x looks like this:

x =   0      * b₁ * (N / 67) +
    ( 7 - 1) * b₂ * (N /  7) +
    (56 - 3) * b₃ * (N / 59) +
    (61 - 4) * b₄ * (N / 61)   (mod N)

where:

  N = 67 * 7 * 59 * 61

and where the `b` variables can be derived from these:

  b₁ * (N / 67) ≡ 1  (mod 67)
  b₂ * (N /  7) ≡ 1  (mod  7)
  b₃ * (N / 59) ≡ 1  (mod 59)
  b₄ * (N / 61) ≡ 1  (mod 61)

Let's solve the N and b variables first:

const n1 = 67
const n2 = 7
const n3 = 59
const n4 = 61

const N = n1 * n2 * n3 * n4 //=> 1_687_931

function solveB(n, i = 1) {
  return (i * (N / n)) % n === 1 ? i : solveB(n, i + 1)
}

const b1 = solveB(n1) //=>  1
const b2 = solveB(n2) //=>  2
const b3 = solveB(n3) //=> 49
const b4 = solveB(n4) //=> 53

And now we actually have everything to solve x! Like so:

x =   0      * b₀ * (N / 67) +
    ( 7 - 1) * b₁ * (N /  7) +
    (59 - 3) * b₂ * (N / 59) +
    (61 - 4) * b₃ * (N / 61)   (mod N)

  =  0 *  1 * (1_687_931 / 67) +
     6 *  2 * (1_687_931 /  7) +
    56 * 49 * (1_687_931 / 59) +
    57 * 53 * (1_687_931 / 61)   (mod N)

  = 0 + 2_893_596 + 78_503_096 + 83_594_091  (mod N)

  = 164_990_783  (mod N)

Finally, when we evalute 164_990_783 % N in JavaScript, we get 1_261_476, which is the correct answer for this sample input. Hooray!

Now we are ready to solve the puzzle with the real input:

const ids = input
  .split('\n')[1]
  .split(',')
  .map((id, i) => ({ id: +id, offset: i }))
  .filter(({ id }) => !Number.isNaN(id))

const N = ids.reduce((product, { id }) => product * id, 1)

function solveB(n, i = 1) {
  return (i * (N / n)) % n === 1 ? i : solveB(n, i + 1)
}

const x =
  ids.reduce(
    (sum, { id, offset }) => sum + (id - offset) * solveB(id) * (N / id),
    0
  ) % N
console.log(x)

flems

It works! And it takes less than 2 milliseconds on my machine! (/^o^)/*\(^o^\) (← That's a high five.)

There are some code smells – for example, the solveB function is relying on N to be in the scope – but I think I have learned enough from this puzzle to not bother refactoring more!

What did I learn?

Wow, math is hard. Or at least time consuming. But ultimately very helpful and useful!

I heard about the Chinese remainder theorem for the first time. I'm not a mathematician, so understanding the theorem well enough to use it in my code took some effort. A couple of hours, actually. 😬