Advent of Code 2020: Day 13 reflection

The day 13 puzzle from last year’s Advent of Code was the first one that left me really flummoxed. Part 1 (the warm-up) was straight-forward enough, but part 2 required left me feeling like there was some really useful math that I didn’t know.

The puzzle was about a set of buses that all take different amounts of time to complete their routes, and keep looping around forever.

After getting past all the flavor text, part 2 of the puzzle boiled down to this: given a set of tuples \( \{(k_i, n_i)\} \), find the smallest non-negative \( t \) such that \[ t \equiv -k_i \pmod{n_i} \] for all \(i\). The problem also gave the hint that \(t\) would exceed \(10^{14}\).

(I think the intention of this hint was to discourage anyone from trying the brute-force solution of checking all possible \( t \) values one by one. Or maybe just a hint that using 32-bit integers would not be sufficient?)

The puzzle description gave a few example problems (with solutions, thankfully). The first one was the set

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

and gave the solution as \( t = 1068781 \).

The modular arithmetic stirred a vague memory in my mind of Fermat’s little theorem, which also made me wonder if all the \(n_i\) in my puzzle input were prime. The problem didn’t specify that this would be the case, but glancing through my input file it seemed that this was indeed true (at least for the puzzle input that I got). But I spent much too long thinking about whether this was useful for the problem, because I couldn’t see that it helped at all.

I didn’t really make any progress until I started looking for ways to reduce the problem to a smaller one.

If the input set consisted of just one tuple, that would be easy enough to solve! If we had just the first tuple \( (0, 7) \) to worry about, I think it’s simple to see that \( t = 0 \) is the solution.

And even adding in the second tuple \( (1, 13) \), it’s not too bad: as long as \( t \) is a multiple of \( 7 \), it will satisfy the condition from the first tuple. So we could start checking all the multiples of \( 7 \), looking for one where \( t \equiv -1 \equiv 12 \pmod{13} \):

But here I got stuck. How do we add in the third tuple \( (4, 59) \)? How can we find candidate solutions that still satisfy the constraints from the first two tuples?

I think I ended up confusing myself here. I was too fixated on the pattern of looking at multiples of the previous candidate solution. But I couldn’t just start looking at multiples of \( 77 \), as they wouldn’t all have the same remainders modulo \( 13 \) any more.

With the benefit of hindsight, obviously I should have focused on addition rather than multiplication.

We can start adding multiples of \( 91 \) — because \( 91 \) is divisible by both \( 7 \) and \( 13 \), this won’t affect congruence \( \gdef\Mod#1{(\mathrm{mod}\ #1)} \Mod{7} \) or \( \Mod{13} \). So we can continue our search like so, looking for a \( t \equiv -4 \equiv 55 \pmod{59} \):

So \( t = 350 \) satisfies all of the first three constraints.

And we can continue on like this. In Python, this approach could look something like this:

def search(start, increment, target, modulus):
    t = start
    while t % modulus != target:
        t += increment
    return t

def solve(tuples):
    ans = 0
    increment = 1
    for k, n in tuples:
        ans = search(ans, increment, -k % n, n)
        increment *= n
    return ans

Note that the increment *= n line probably isn’t correct in general. I think this works only if the set of \( n_i \)s are relatively prime? This should probably be something like increment = math.lcm(increment, n) in the general case.

Otherwise, this appears to work just fine for all of the examples in the puzzle description!

Too clever by half

For some reason I couldn’t come up with this solution when I was first working through this problem. Perhaps I had convinced myself this approach wouldn’t be efficient enough?

I don’t know why; my puzzle input had a total of 9 tuples with a maximum \( n \) value of \( 787 \). That should put us well under 10,000 iterations of the inner while loop in the worst case, which should be no problem (especially if all the values fit in one 64-bit integer, so that there’s no slowdown as we start doing arithmetic with larger and larger numbers).

But no, after much struggle I eventually ended up with a much more complicated solution. I’ll include the core of it here, but I don’t even remember now exactly what I was thinking:

def solve(tuples):
    accum = []
    fs = [(-k % n, n) for k, n in tuples]
    for i in range(len(fs)):
        accum.append(fs[i])
        fs = [(factor(fs[i][1], b[1], (b[0] - fs[i][0]) % b[1]), b[1]) for b in fs]
    return evaluate(accum)

def factor(a, d, q):
    for i in range(1, d+1):
        if a * i % d == q:
            return i

def evaluate(accum):
    if not accum:
        return 0
    return accum[0][0] + accum[0][1] * evaluate(accum[1:])

I think I was trying to express the solution in the form

\[ t = a + n_1(b + n_2(c + n_3(…))) \]

I start with values for the \( a, b, c, … \) coefficients based on the \( k_i \) values from the input tuples, and then keep adjusting them for each of the \( n_i \).

Compared to the simpler solution from above, the factor() method is still doing a linear search for a specific remainder \( \Mod{n_i} \), so it’s not really any more efficient. The only possible advantage I can think of is that we’re working with smaller numbers until the very end, when the evaluate() method computes a final answer based on all the final coefficients. But, it turns out that doesn’t really matter, because for this puzzle as the values fit into 64-bit integers just fine.

Is there a moral to this story? I’m not sure.

Perhaps it’s this: sometimes it’s crucial to have a specific insight for a problem, and you can’t really force insight. It’s fine to take a break and come back to the problem later.