aoc/2020/13/13.py
2020-12-13 01:13:19 -06:00

55 lines
1.3 KiB
Python

def read_file():
with open("input.txt","r") as f:
timestamp, buses = f.read().split('\n')
timestamp = int(timestamp)
buses = buses.split(',')
working_buses = [int(b) for b in buses if b != "x"]
return timestamp, working_buses, buses
def part1(timestamp, buses):
waits = [abs((timestamp % b) - b) for b in buses]
i = waits.index(min(waits))
return buses[i] * (waits[i])
from functools import reduce
def crt(a,n):
sum=0
product =reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n,a):
p = product // n_i
sum += a_i * mul_inv(p, n_i) * p
return sum % product
def mul_inv(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1:
return 1
while a > 1:
q = a // b
a, b = b, (a % b)
x0, x1 = (x1 - q * x0), x0
if x1 < 0:
x1 += b0
return x1
def part2(buses):
r = []
m = []
for i, b in enumerate(buses): # i = wait, b = modulo
if b == "x":
continue
b = int(b)
r.append(b-i) # convert to remainder
m.append(b)
return crt(r,m)
def main():
timestamp, working_buses, all_buses = read_file()
print(part1(timestamp, working_buses), part2(all_buses))
print(part2([17,"x",13,19])) # 3417
print(part2([67,7,59,61])) # 754018
print(part2([67,"x",7,59,61])) # 779210
print(part2([67,7,"x",59,61])) # 1261476
print(part2([1789,37,47,1889])) # 1202161486
if __name__ == "__main__":
main()