aoc-2020/13.py

lines = []

with open("13.input") as f:
    for line in f.readlines():
        lines.append(line.strip())

busses = [int(x) for x in lines[1].split(",") if x != "x"]

my_time = int(lines[0])
times = [x - my_time % x for x in busses]

my_bus = busses[times.index(min(times))]

print("Answer 1: {}".format(my_bus * min(times)))

busses = [(- i % int(x), int(x)) for (i, x) in enumerate(lines[1].split(",")) if x != "x"]

def print_table(start, busses):
    end = start + busses[-1][0]
    for i in range(start, end):
        print("{}: ".format(i), end='')
        for (offset, interval) in busses:
            if i % interval == 0:
                print('D', end='')
            else:
                print('.', end='')
        print("")

# Stolen from: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode
def extended_gcd(a, b):
    (old_r, r) = (a, b)
    (old_s, s) = (1, 0)
    (old_t, t) = (0, 1)

    while r != 0:
        quotient = int(old_r / r)
        (old_r, r) = (r, old_r - quotient * r)
        (old_s, s) = (s, old_s - quotient * s)
        (old_t, t) = (t, old_t - quotient * t)

    return (old_s, old_t)

def combo(pair1, pair2):
    off1, int1 = pair1
    off2, int2 = pair2
    # This is fine since all IDs are primes
    new_int = int1 * int2
    # Find the smallest solution to
    # int1 * x + off1 = int2 * y + off2
    # int1 * x - int2 * y = 1 * (off2 - off1)
    x, y = extended_gcd(int1, -int2)
    # Correct signs
    if int1 * x - int2 * y != 1:
        x = -x
        y = -y
    x *= (off2 - off1)
    y *= (off2 - off1)
    assert int1 * x + off1 == int2 * y + off2
    return ((int1 * x + off1) % new_int, new_int)

result_busses = list(busses)
while len(result_busses) > 1:
    result_busses = [combo(result_busses[0], result_busses[1])] + result_busses[2:]

print("Answer 2: {}".format(result_busses[0][0]))