shuttle search

approach

the input is an earliest departure time and a list of bus ids, with x entries kept as None so their positions still count. part 1 computes, for each bus, how long until its next departure (b - s % b) and multiplies the shortest wait by that bus id.

part 2 needs a time t where the bus at index i departs at t + i, i.e. t ≡ -i (mod b) for every bus. the comments note the ids are primes, hence pairwise coprime, so this is a chinese remainder theorem system. solve builds the answer from the product of the moduli, using a recursive extended euclid (inverse) for the modular inverses.

the trick

each bus is a congruence t ≡ -i (mod id), and coprime ids mean the chinese remainder theorem gives t directly.

def solve(equations):
    _, mods = zip(*equations)
    p, s = reduce(lambda x,y: x * y, mods), 0
    for r, m in equations:
        pi = p // m
        _, inv, _ = inverse(pi, m)
        s += r * pi * inv
    return s % p