Advent of code 2020 day 13

# Part 1
def earliest_bus(s):
  time = int(s.split('\n')[0])
  buses = [int(e) for e in s.split('\n')[1].split(',') if e != 'x']
  next_times = [((time - 1) // bus + 1) * bus for bus in buses]
  earliest_time, earliest_bus = min(zip(next_times, buses))
  return (earliest_time - time) * earliest_bus

# Part 2
def extended_gcd(a: int, b: int):
  """Finds the greatest common divisor using the extended Euclidean algorithm.

  Returns the tuple (gcd(a, b), x, y) where 'x' and 'y' have the property that
  a * x + b * y = gcd(a, b).

  For the case that a and b are coprime, i.e. gcd(a, b) = 1,
  applying "modulo b" to both sides results in
  (a * x) % b == 1,
  and hence 'x' is the modular multiplicative inverse of 'a' with respect to
  the modulus 'b'.
  See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
  """
  prev_x, x = 1, 0
  prev_y, y = 0, 1
  while b:
    q = a // b
    x, prev_x = prev_x - q * x, x
    y, prev_y = prev_y - q * y, y
    a, b = b, a % b
  x, y = prev_x, prev_y
  return a, x, y

def modulo_inverse(a: int, b: int) -> int:
  return extended_gcd(a, b)[1]

# Given [(b_i, r_i)], where b_i are coprime, we want to find x such that
#  x % b_i = r_i  for all i,  (where initial r_i = -i % b_i)
# We can work by reduction, merging pairs of buses.

# Given a pair of buses (b1, r1) and (b2, r2),
# we want to find a new equivalent bus (b1 * b2, r) such that
#  0 <= r < b1 * b2
#  r % b1 = r1
#  r % b2 = r2

# Let r = k * b1 + r1  for some unknown k.
# Then, (k * b1 + r1) % b2 = r2
# Therefore, k = inv(b1, b2) * (r2 - r1 % b2)
#  where inv(b1, b2) is the multiplicative inverse of b1 wrt to modulus b2.

def earliest_consecutive(s):
  buses = [int(e) for e in s.replace('x', '1').split(',')]

  def merge_buses(bus1, bus2):
    (b1, r1), (b2, r2) = bus1, bus2
    k = modulo_inverse(b1, b2) * (r2 - r1 % b2)
    r = (k * b1 + r1) % (b1 * b2)
    return b1 * b2, r

  bus_remainders = [(bus, -i % bus) for i, bus in enumerate(buses) if bus > 1]
  _, r = functools.reduce(merge_buses, bus_remainders)
  return r