From e7c9108b95e39d7ea5a29ae06d619c4727f11027 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Fri, 29 Oct 2021 23:02:39 +0200 Subject: Initial commit --- 2020/13/input | 2 ++ 2020/13/puzzle-1.py | 26 ++++++++++++++++++++++++++ 2020/13/puzzle-2.py | 40 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 68 insertions(+) create mode 100644 2020/13/input create mode 100755 2020/13/puzzle-1.py create mode 100755 2020/13/puzzle-2.py (limited to '2020/13') diff --git a/2020/13/input b/2020/13/input new file mode 100644 index 0000000..59d4d66 --- /dev/null +++ b/2020/13/input @@ -0,0 +1,2 @@ +1006401 +17,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,449,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,607,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29 \ No newline at end of file diff --git a/2020/13/puzzle-1.py b/2020/13/puzzle-1.py new file mode 100755 index 0000000..7b21f96 --- /dev/null +++ b/2020/13/puzzle-1.py @@ -0,0 +1,26 @@ +#!/usr/bin/env python3 + + +def main() -> None: + with open("input", "r") as f: + time = int(f.readline()) + ids = list(map(int, f.readline().replace(",x", "").split(","))) + + ids.sort() + + min = -1 + x = 0 + for bus in ids: + res = (time + ids[0]) % bus + if min < res < ids[0]: + min = res + x = bus + + for i in range(time, time + ids[0]): + if i % x == 0: + print((i - time) * x) + break + + +if __name__ == "__main__": + main() diff --git a/2020/13/puzzle-2.py b/2020/13/puzzle-2.py new file mode 100755 index 0000000..3965488 --- /dev/null +++ b/2020/13/puzzle-2.py @@ -0,0 +1,40 @@ +#!/usr/bin/env python3 + +from functools import reduce + + +def chinese_remainder(n: tuple[int, ...], a: tuple[int, ...]) -> int: + sum = 0 + prod = reduce(lambda a, b: a * b, n) + for n_i, a_i in zip(n, a): + p = prod // n_i + sum += a_i * mul_inv(p, n_i) * p + return sum % prod + + +def mul_inv(a: int, b: int) -> int: + 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 main() -> None: + with open("input", "r") as f: + ids = tuple(map(lambda x: int(x) if x.isdigit() else x, f.readlines()[1].split(","))) + + buses = tuple(filter(lambda x: x != "x", ids)) + modres = tuple(x if (x := bus - ids.index(bus)) != bus else 0 for bus in buses) + + print(chinese_remainder(buses, modres)) + + +if __name__ == "__main__": + main() -- cgit v1.2.3