day 13

ah yes, we love buses. i am incredibly grateful that every number involved in this was a distinct prime since i went for a highly mathematical solution (i don't know how efficiently it's implemented, but it's a huge improvement on '13b - slow.py' which basically just went through times and checked when buses arrived)

so bus n arrives every n minutes. the input was two lines: one was an integer, and the next was a list of either integers or the letter x.

# input
with open('13.txt', 'r') as file:
    input = file.read()
# turn the input into a list - this has when you arrive and the list of buses
input_list = list(input.split('\n'))
arrival_time = int(input_list[0])
# get your buses
buses_str = input_list[1].split(',')

for part a, the first line gives the earliest time that you can catch a bus, and the second line gives a list of buses where a bus that is not in service is given by x, and you need to see which bus you can catch first and how many minutes you have to wait. we start by getting bus numbers with some cheeky list comprehension:

# limit to the ones in service (not x)
buses = [int(bus_str) for bus_str in buses_str if not bus_str == 'x']

we now set the time to the time that you arrive at the bus stop, and start a while loop that continues incrementing this time by 1. for each time, it checks if any buses have arrived (since they're every n minutes starting from 0, this is equivalent to checking if the current time is a multiple of any bus number). if a bus has arrived, it prints the answer to part a; else it just goes to the next minute.

# now look at buses
time = arrival_time
while 1:
    # check each bus
    for bus in buses:
        # has the bus arrived? 
       if time % bus == 0:
            print('got bus ' + str(bus) + ' at time ' + str(time))
            print('part a answer (bus num * time waited): ' + str(bus*(time-arrival_time)))
            break
    else: # did not break
        # increment time
        time += 1
        continue
    # for loop broke => we get to here
    break

now for part b... the arrival time (first line) becomes irrelevant, and the x's in the second line of the input become relevant, now showing the minutes where there are no rules for buses. for example, '29,x,x,13,x,3' means that you want bus 29 to arrive, then bus 13 to arrive 3 minutes later, then bus 3 to arrive 2 minutes after that - the answer you want is the first time t such that bus 29 arrives at time t and you get this entire pattern. this time i read in the input differently, so that each bus would be represented by a tuple with the bus number and the number of minutes between t and that bus arriving.

dt gives the number of minutes that the bus arrives after t; i take -dt since t is dt minutes before this bus arrives, and then the modulo by the bus number (least positive residue) since it's effectively equivalent in this case - if bus 7 arrives 4 minutes after t, then it will also arrive 3 minutes before t.

(i also imported reduce and math for later)

from functools import reduce
import math
# input
with open('13.txt', 'r') as file:
    input = file.read()
# turn the input into a list - this has when you arrive and the list of buses
input_list = list(input.split('\n'))
# get your buses
buses_str = input_list[1].split(',')
# turn the ones in service into ints and gets the dt we need
buses = []
dt = 0
for bus_str in buses_str:
    if not bus_str == 'x':
        buses.append((int(bus_str), (-dt) % int(bus_str)))
    dt += 1
print(buses)

now it's time to implement the chinese remainder theorem (https://en.wikipedia.org/wiki/Chinese_remainder_theorem) - until i say otherwise, everything from here is in the function

def crt(a, b):

 the CRT takes in two simultaneous equations with modulos in them, such as

z = a[1] mod a[0] (equivalently, a[0] divides z - a[1])

z = b[1] mod b[0] (equivalently, b[0] divides z - b[1]

and then it returns the value of z (mod a[0]*b[0] - i.e. you can add on any multiple of a[0]*b[0] to z and both of the statements above stay true, but if you add anything that isn't a multiple then at least one of the statements will fail).

for this to be true, we need a[0] and b[0] to be coprime (their greatest common divisor is 1) - luckily this is always going to be true here since our inputs are pairwise distinct primes, but i threw in this anyway:

# throw out non-coprime case (won't come up here but whatever)
if not math.gcd(a[0],b[0]) == 1:
    print('attempted to do crt with non-coprime integers!!!')
    print('a = ' + str(a))
    print('b = ' + str(b))
    return

the next step is implementing the extended euclidean algorithm (EEA) - honestly just check the wikipedia page at https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm if you want an explanation of how it works (after years of maths i still do it with the exact steps in front of me), but effectively it takes in a[0] and b[0] and gives two numbers x and y such that a[0]*x + b[0]*y = 1. (the algorithm actually gives x and y up to sign, and when doing it manually you'd just check which combination of signs works - i just tried all combos of ±x and ±y to see if the sum ended up being 1, and replaced x by -x / y by -y if needed.

# extended euclidean to get x, y such that a[0]x + b[0]y = 1
# NOTE - stop at remainder = 0, above is what we want
quot = [0, 0] # no quotient at first
# when doing this by hand you'd put larger one first, but it works either way
rem = [a[0], b[0]]
# bezout coefficients
s = [1, 0]
t = [0, 1]
# current position in list
i = 2
# run the algorithm
while 1:
    quot.append(math.floor(rem[i-2] / rem[i-1]))
    rem.append(rem[i-2] - (quot[i] * rem[i-1]))
    s.append(s[i-2] - (quot[i] * s[i-1]))
    t.append(t[i-2] - (quot[i] * t[i-1]))
    if rem[i] == 0: # the remainder is 0
        break
    i += 1
# s[i-1] and t[i-1] are the x and y we want, up to sign
x_maybe = [s[i-1], -s[i-1]]
y_maybe = [t[i-1], -t[i-1]]
# get correct sign
for xm in x_maybe:
    for ym in y_maybe:
        if a[0] * xm + b[0] * ym == 1:
            x = xm
            y = ym
            break
    else:
        continue
    break

now that we have these values, we can use them to finish the algorithm for CRT, since we can get the value of z using the six variables we have (a[0], a[1], b[0], b[1], x, y).

# now we can get the remainder modulo a[0]*b[0]
# z = a[1] mod a[0]
# z = b[1] mod b[0]
# a[0]*x + b[0]*y = 1
z = a[1] * y * b[0] + b[1] * x * a[0]
# z is the smallest positive integer such that z = a[1] mod a[0] and z = b[1] mod b[0]
return (a[0]*b[0], z)

we can verify that this is the correct value of z by direct calculation: for example, to verify that z = a[1] mod a[0]:

z = a[1] * y * b[0] + b[1] * x * a[0] (mod a[0])

z = a[1] * y * b[0] (mod a[0]) - since the second summand is a product of a[0]

z = a[1] * (1 - a[0] * x) (mod a[0]) - by substituting in the equation we got from the EEA

z = a[1] - a[1] * a[0] * x (mod a[0]) - expanding brackets

z = a[1] (mod a[0]) - second summand is a product of a[0]

this is the end of the crt() function. when implementing CRT for more than 2 simultaneous equations we proceed by turning a pair of simultaneous equations into one using CRT for two equations, and then implementing CRT on this and another equation - probably explained better in https://en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case. with the above case, we would be passing in (a[0]*b[0], z) to represent the equation

n = z (mod a[0]*b[0])

and then applying CRT on this and another n = something (mod somethingelse). this process is effectively the same as reducing:

ans = reduce(lambda a,b:crt(a,b),buses)

so if buses = [a,b,c,d], this runs crt(crt(crt(a,b),c),d). our output from this is a tuple (s,t) where s is the product of all of the bus numbers and t gives a timestamp at which the pattern we want happens. so the answer we want is t % s, which gives the earliest time at which the pattern occurs:

print('(part b) earliest time = ' + str(ans[1] % ans[0]))

i faced a few issues with implementing this just because EEA and CRT are somewhat finicky - there are several variables involved and you have to make absolutely sure you're using the right one, which is why i've never been able to memorise the algorithm (except for one number theory module.. and even then i forgot it as soon as i finished the exam lmao).

i also forgot the actual problem partway through and ended up feeding the times in as the remainders... so my solution kept coming out as the first timestamp where the buses arrived that many minutes before that time instead of that many minutes after, so it was the end of the reverse of the pattern instead of the start of the pattern

my maths brain and my python brain need to learn to work together haha