59 lines
1.3 KiB
Python
59 lines
1.3 KiB
Python
from functools import reduce
|
|
|
|
|
|
test = (
|
|
939,
|
|
"7,13,x,x,59,x,31,19",
|
|
)
|
|
|
|
data = (
|
|
1002462,
|
|
"37,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,601,x,x,x,x,x,x,x,x,x,x,x,19,x,x,x,x,17,x,x,x,x,x,23,x,x,x,x,x,29,x,443,x,x,x,x,x,x,x,x,x,x,x,x,13",
|
|
)
|
|
|
|
|
|
def part1(departure, bus_ids):
|
|
buses = [int(x) for x in bus_ids.split(",") if x != "x"]
|
|
distances = [(departure // x + 1) * x - departure for x in buses]
|
|
idx = distances.index(min(distances))
|
|
return buses[idx], distances[idx]
|
|
|
|
|
|
def part2(bus_ids):
|
|
# t = bus_id % bus_id - idx
|
|
buses = [int(0 if x == "x" else x) for x in bus_ids.split(",")]
|
|
p = [x - buses.index(x) for x in buses if x != 0]
|
|
n = [x for x in buses if x != 0]
|
|
cr = chinese_remainder(n, p)
|
|
return cr
|
|
|
|
|
|
def chinese_remainder(n, p):
|
|
prod = reduce(lambda a,b: a*b, n)
|
|
|
|
sum = 0
|
|
for div, rem in zip(n, p):
|
|
pp = prod // div
|
|
i = pow(pp, -1, div)
|
|
sum += rem * pp * i
|
|
|
|
return sum % prod
|
|
|
|
|
|
id, wait = part1(*test)
|
|
assert id*wait == 295
|
|
|
|
id, wait = part1(*data)
|
|
print(f"1: Answer is {id*wait}")
|
|
|
|
assert chinese_remainder([3, 5, 7], [2, 3, 2]) == 23
|
|
|
|
assert part2(test[1]) == 1068781
|
|
assert part2("17,x,13,19") == 3417
|
|
assert part2("67,7,59,61") == 754018
|
|
assert part2("67,x,7,59,61") == 779210
|
|
assert part2("67,7,x,59,61") == 1261476
|
|
assert part2("1789,37,47,1889") == 1202161486
|
|
|
|
ts = part2(data[1])
|
|
print(f"2: Answer is {ts}")
|