Advent of Code 2020: Day 13 using...a lot of math, and Numpy in Python

Today's challenge is a math-heavy one, though the code is very short.

The Challenge Part 1

Link to challenge on Advent of Code 2020 website

This part of the challenge uses some basic modulo arithmetic - with each bus departing every set period of time, which one is the next bus?

Importing the data

The data is vaguely CSV-like, so we'll just use python's csv library to import it. But We're going to use numpy as well, so...

import csv
import numpy as np

raw = list(csv.reader(open("input.txt")))
departure = int(raw[0][0])
busses = np.array([int(bus) for bus in raw[1] if bus != "x"])

Output (using the demo data):

departure = 939
busses = array([ 7, 13, 59, 31, 19])

Calculating the answer

All we need to do is find the first time at or above the earliest departure time we're give (939 in the example) for which the modulo of the bus schedule is 0. For example, bus number 7 departs at 7, 14, 21, etc. times. i.e. any time for which t % 7 == 0

However, this problem is easier than this, since if we take the modulo of the current time against the bus's schedule, and then subtract that from the bus's schedule, we get the number of minutes remaining until that bus arrives.

For example, at 939 minutes, 939 % 7 = 1. This means it's been 1 minute since the last number 7 departed, and therefore 7-1=6 minutes until the next number 7.

Since we loaded all the busses in numpy, we can calculate this all in one go:

waits = busses - departure % busses

Output:

array([ 6, 10,  5, 22, 11])

This means there are 6 minutes for that first bus in our list, 10 minutes for the next. Clearly the soonest to arrive is the third bus on the list, with 5 minutes to go. We can grab the actual bus number with busses[np.argmin(waits)]

The full code for part 1 is therefore simply:

import csv
import numpy as np

raw = list(csv.reader(open("input.txt")))
departure = int(raw[0][0])

busses = np.array([int(bus) for bus in raw[1] if bus != "x"])
waits = busses - departure % busses
print("answer", busses[np.argmin(waits)] * np.min(waits))

The Challenge Part 2

The second part of the challenge makes things interesting - we're asked to find a time after which each bus leaves in sequence, with the bus in the first position of the list leaving at the time, the second position of the list leaving 1 minute later, and so on. Basically find a time at which each bus leaves some minutes later equal to its position on the list.

The brute force of this solution will take a great deal of time, so we have to math this carefully.

Each bus leaves according to a simple pattern: every few minutes apart. This means Bus 0 can only leave at certain times. We don't have to check the times at which it's impossible for Bus 0 to leave, so that cuts down our search space.

But what happens when we take the first two busses together? At some point in time at time t, Bus 0 will leave at time t and bus 1 will leave at time t+1, fulfilling part of the requirements of the puzzle. This pattern repeats as well. We know that sometime in the future, there will be another time t where Bus 1 leaves one minute after Bus 0. In fact, we know our eventual solution has to be one member of this sequence. Since we know the individual intervals of the two busses, we can calculate the interval that this overall two-bus pattern repeats, as it's the least common multiple of the two busses' intervals.

By no stretch of the imagination, we can find an instance of the above two-bus pattern where additionally, Bus 2 also fits into this pattern. When we do find it, we would now have a 3-bus pattern, and we know its interval is the least common multiple of the previous interval and Bus 2's interval.

So we can iteratively search like this, until all busses fit into the pattern, significantly cutting down on the number of iterations needed to find the answer.

The code

The input code is modified slightly so that we get time-offset/bus pairs:

import csv
import numpy as np

raw = list(csv.reader(open("input.txt")))
data = np.array([[idx, int(bus)] for idx, bus in enumerate(raw[1]) if bus != "x"])

Output (for demo data):

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

And the code?

interval = 1
time = 0
for offset, bus in data:
    while (time + offset) % bus != 0:
        time += interval
    interval = np.lcm(interval, bus)
print("time", time)

That was it - for each bus, try every interval to find a time at which it departs. When finding a match, set the interval to the new least common multiple of the bus's interval and the interval of the pattern before it. Repeat until all busses fall into this pattern.

The full code:

import csv
import numpy as np

raw = list(csv.reader(open("input.txt")))
data = np.array([[idx, int(bus)] for idx, bus in enumerate(raw[1]) if bus != "x"])

interval = 1
time = 0
for offset, bus in data:
    while (time + offset) % bus != 0:
        time += interval
    interval = np.lcm(interval, bus)
print("time", time)

This code only took 317 iterations to find the solution using my puzzle input.

Onward!

Comments

[juliodcs]

Wow! A fast solution that didn't use Chinese remainder theorem.

I used a brute-force approach too, but mine is much slower because I used a 'fixed' block/interval (for 3 biggest buses), which I need to calcculate in before. Sort of the same concept, but I didn't realize I could use a 'varying' interval size.

Great solution! 👏👏👏