Day 13. Shuttle Search

Problem statement

https://adventofcode.com/2020/day/13 (mirror)

My solution

Part A is easy enough. For each bus ID from the input, we need to cacluate earliest possible departure from a specific time (inclusive)! We do that with a simple calculation:

int NextDeparture(int timestamp, int id) 
    => timestamp % id == 0 ? timestamp : timestamp - timestamp % id + id;

If timestamp is divisble by bus ID, then bus departs exactly at the specified timestamp. Else, we subtract the remainder of timestamp modulo ID from the timestamp (timestamp - timestamp % id) to get the multiple of ID immediately smaller than timestamp, and then add ID to get the multiple of ID immediately greater than timestamp.

Note that if timestamp is divisible by ID, than the result of timestamp - timestamp % id + id is still the first multiple of ID greater than timestamp, and the following implementation would not produce a correct answer:

int NextDeparture(int timestamp, int id) => timestamp - timestamp % id + id;

Part B is just a convoluted way of describing the Chinese remainder theorem.

If a bus with ID id is supposed to depart o (offset) minutes after timestamp t, then id, o and t must all satsify the following condition:

t + o % id == 0     ⇔     t ≡ -o (mod id)

Since a bus always departs at timestamp divisble by id, then t + o must also be divisible by id. In other words: the remainder of t modulo id is equal to -o.

Now, we can observe that all bus IDs are actually prime numbers, so the condition that all divisors from the theorem are coprime is met. In terms of the theorem, bus IDs are divisors (moduli), and the offsets (positions of bus ID in the input list) define the remainders.

For example, if we consider the example input data: 7,13,x,x,59,x,31,19, we are looking for such timestamp t, which satisfies the congruence system:

t ≡ 0  (mod 7)
t ≡ -1 (mod 13)
t ≡ -4 (mod 59)
t ≡ -6 (mod 31)
t ≡ -7 (mod 19)

Note that in the example the offset of bus with ID 59 is 4, not 2! Also, we want a remainder to be a number greater or equal to 0 and lesser than bus ID, so we wrap it with the following calculation:

remainders[i] = (( (-buslist[i].offset) % buslist[i].busId) + buslist[i].busId) % buslist[i].busId;

Fortunately, this is a well known problem, so we can simply borrow a solver for it from, for example, Rosetta Code.