advent-2020-13b-iterative-crt.py

with open('in.txt') as f:
  _, buses = f.read().splitlines()

def iterative_crt(a1, n1, a2, n2):
  return pow(n1, -1, n2) * (a2 - a1) * n1 + a1

residues = 0
moduli = 1
for i, bus in enumerate(buses.split(',')):
  if bus != 'x':
    bus = int(bus)
    residue = bus - i
    modulus = bus
    residues = iterative_crt(residues, moduli, residue, modulus)
    moduli *= modulus

print(residues)