Advent of Code 2020 - Day 13

https://adventofcode.com/2020/day/13 ('Shuttle Search')

Part 1 requires us to look for the bus number that has the smallest multiple greater than or equal to the minimum time.

One way to think about this is to look at the number of complete circuits of its route each bus has done by the minute before the minimum time. Knowing this we can determine the next departure time and this will be the first departure equal to or greater than the minimum time.

If the minimum time is min_time and the bus number is bus_no then the number of circuits completed by min_time - 1 will be (min_time - 1) // bus_no. The next departure time will be the time of completion of the next circuit, and we get this by adding 1 to the previous result (for one more circuit) and multiplying by the bus number: ((min_time - 1) // bus_no + 1) * bus_no.

Note that using min_time - 1 here ensures that we handle the possibility of min_time itself being the next possible departure time for one of the buses.

In Python this looks like:

def part1():
    # Puzzle input is sufficiently small there's no need to 
    # read in from a file.
    min_time = 1003681
    bus_nos = [int(n) for n in '23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,409,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29'.split(',') if n != 'x']
    # Map each bus number to a pair of (bus_no, next_departure)
    # and then find the pair with the minimum next_departure 
    # value.
    (first_bus, departure_time) = min(((bus_no, ((min_time - 1) // bus_no + 1) * bus_no) for bus_no in bus_nos), key=lambda x: x[1])
    # Calculate the waiting time and multiply by the bus number.
    return (departure_time - min_time) * first_bus

Part 2 wants to do things the other way round: instead of looking for bus departures around a particular timestamp, we need to find a timestamp that has a certain pattern of departures around it.

First let's understand exactly what's being asked: we are looking for a timestamp t such that the bus at index i in the list has a departure at t + i. In other words, if [(i_0, b_0), (i_1, b_1), ..., (i_n, b_n)] is a list of pairs of index and bus number for the n buses, we are looking for t such that:

(t + i_n) % b_n = 0  for all n

The simplest approach now would be to start at t = 0 and for each t check whether (t + i_n) % b_n = 0 for all n. However, this being part 2 of an Advent of Code puzzle it's extremely likely this won't complete in a sensible time!

It turns out that there is a much quicker way to solve a system of equations like this, but first we need to rearrange them into the form

t % b_n = r_n  for all n

The original set of equations is the same as:

((t % b_n) + (i_n % b_n)) % b_n = 0  for all n

From this we can move the i_n % b_n to the right hand side, making it negative. However as we're working modulo b_n we are free to add on b_n to keep things positive:

t % b_n = (b_n - i_n % b_n) % b_n  for all n

so we have r_n = (b_n - i_n % b_n) % b_n.

The example from the puzzle has the following (i_n, b_n) index/bus number pairs:

[(0, 7), (1, 13), (4, 59), (6, 31), (7, 19)]

Calculating r_n for each pair we get the following (r_n, b_n) pairs:

[(0, 7), (12, 13), (55, 59), (25, 31), (12, 19)]

In this example we're therefore looking for a value of t such that:

t % 7 = 0
t % 13 = 12
t % 59 = 55
t % 31 = 25
t % 19 = 12

What do we do now?

The first thing that sticks out is that all the bus numbers in the example are prime. A quick check shows that this is also the case for the puzzle input, and this is great as it means we can apply something called the Chinese Remainder Theorem to find the solution!

Getting to the answer will be fastest if we start with the largest bus number and work our way down, so lets re-order the equations:

t % 59 = 55
t % 31 = 25
t % 19 = 12
t % 13 = 12
t % 7 = 0

First, let's find a solution that works for the first two buses in the list. t = 55 will obviously satisfy the first equation, but so will t = 55 + 59, t = 55 + 59 * 2 etc. If we keep adding 59 we should eventually get to a value of t where we also find that the second equation holds. Let's call this t_2, so:

t_2 % 59 = 55
t_2 % 31 = 25

Now comes the clever trick: if we add 59 * 31 to t_2 we get another value of t that satisfies these two equations: we've added on a whole number of 59s so the remainder when dividing by 59 won't change, but we've also added on a whole number of 31s so the remainder when dividing by 31 doesn't change either. In fact, we can add on any multiple of 59 * 31 we like without changing things. This gives us a way to keep exploring for values of t that satisfy the third equation while making sure we don't break equations one and two. Let's say that after adding on 59 * 31 to t_2 a sufficient number of times we get to a value of t that works for the first three equations - call this t_3.

If we take a step back, we can see that the above process is exactly what we would have done when solving the first two equations if they had looked like:

t % (59 * 31) = t_2
t % 19 = 12

We can now do the same thing to look for a value t_4 that'll satisfy the fourth equation by starting with t_3 and repeatedly adding on 59 * 31 * 19. This is equivalent to solving the pair of equations:

t % (59 * 31 * 19) = t_3
t % 13 = 12

Finally we repeatedly add on 59 * 31 * 19 * 13 to t_4 to find a value t_5 that satisfies the fifth equation - i.e. we're solving:

t % (59 * 31 * 19 * 13) = t_4
t % 7 = 0

Therefore we need a function that will solve a pair of equations of the form:

x % p_1 = a_1
x % p_2 = a_2

This looks like:

def solve(p_1, a_1, p_2, a_2):
    x = a_1
    while x % p_2 != a_2:
        x += p_1
    return x

Now we can follow all these steps to solve part 2:

def part2():
    # Get the bus numbers from the input along with the 
    # corresponding indices.
    buses = [(i, int(n)) for (i, n) in enumerate('23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,409,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29'.split(',')) if n != 'x']

    # Figure out for each bus the remainder t must have 
    # when divided by the bus number.
    buses = [((b - i % b) % b, b) for (i, b) in buses]

    # Sort in decreasing order of bus number.
    buses.sort(key=lambda bus: -bus[1])

    # Starting with the first two equations, repeatedly 
    # solve to generate a new equation t % p = a where p is the
    # product of the moduli used so far and a is the result of 
    # solving the previous pair of equations.
    (a, p) = buses[0]
    for (remainder, bus_no) in buses[1:]:
        a = solve(p, a, bus_no, remainder)
        p *= bus_no

    return a

When originally doing this puzzle I'd completely forgotten about the Chinese Remainder Theorem, but the fact that the bus numbers were all prime indicated that something was up. I knew there were a few things in modulo arithmetic that were only true if the various moduli in use were coprime (i.e. share no common factors other than 1), and a quick rummage through Wikipedia pointed to the Theorem.