Initial commit

3 files changed, 68 insertions, 0 deletions

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()