49 lines
1.1 KiB
Python
49 lines
1.1 KiB
Python
import fileinput
|
|
|
|
input = fileinput.input()
|
|
|
|
arrival = int(next(input))
|
|
buses = [None if bus == "x" else int(bus) for bus in next(input).split(",")]
|
|
print(arrival, buses)
|
|
|
|
remainders = [-(arrival % (-bus)) if bus else float("inf") for bus in buses]
|
|
print(remainders)
|
|
|
|
print(
|
|
"Part 1:",
|
|
min(enumerate(buses), key=lambda x: remainders[x[0]])[1] * min(remainders),
|
|
)
|
|
|
|
def combine(a_period, a_offset, b_period, b_offset):
|
|
gcd, s, _ = egcd(a_period, b_period)
|
|
diff = a_offset - b_offset
|
|
diff_quot, dif_rem = divmod(diff, gcd)
|
|
assert(dif_rem == 0)
|
|
|
|
combined_period = a_period // gcd * b_period
|
|
combined_offset = (a_offset - s * diff_quot * a_period) % combined_period
|
|
return combined_period, combined_offset
|
|
|
|
def egcd(a, b):
|
|
r_, r = a, b
|
|
s_, s = 1, 0
|
|
t_, t = 0, 1
|
|
while r:
|
|
quot, rem = divmod(r_, r)
|
|
r_, r = r, rem
|
|
s_, s = s, (s_ - quot * s)
|
|
t_, t = t, (t_ - quot * t)
|
|
return r_, s_, t_
|
|
|
|
period = 1
|
|
offset = 0
|
|
|
|
for i, bus in enumerate(buses):
|
|
if bus is None:
|
|
continue
|
|
|
|
period, offset = combine(period, offset, bus, i)
|
|
print(i, bus, period, offset)
|
|
|
|
print(-offset % period)
|