summer warmup sesh part 2

1 files changed, 46 insertions, 0 deletions

diff --git a/2020/aoc2020-d13.py b/2020/aoc2020-d13.py
new file mode 100644
index 0000000..dd0d0d1
--- /dev/null
+++ b/2020/aoc2020-d13.py
@@ -0,0 +1,46 @@
+#advent of code 2020
+#day 13
+#kinda cheated, the chinese remainder theorem (CRT) was copy-pasted from google search results
+#the source where I was reading how it works didn't really provide a good example
+#will definitely look it up later :)
+
+def gcd_extended(a, b):
+    if a == 0:
+        return b, 0, 1
+    gcd, x1, y1 = gcd_extended(b % a, a)
+    x = y1 - (b // a) * x1
+    y = x1
+    return gcd, x, y
+
+def find_min_x(num, rem):
+    prod = 1
+    for n in num:
+        prod *= n
+    result = 0
+    for i in range(len(num)):
+        prod_i = prod // num[i]
+        _, inv_i, _ = gcd_extended(prod_i, num[i])
+        result += rem[i] * prod_i * inv_i
+    return result % prod
+
+PuzzleInput = open("13.in","r").read().split("\n");
+timestamp = int(PuzzleInput[0]);
+buses = PuzzleInput[1].split(",");f b != "x"];
+
+times = dict();
+BusList = [];
+OffsetList = [];
+for index, bus in enumerate(buses):
+	if bus == "x": continue;
+	bus = int(bus);
+	BusList.append(bus);
+	OffsetList.append(bus-index);
+	d = timestamp%bus;
+	NextStop = timestamp-d+bus;
+	times[NextStop] = (bus,bus-d);
+
+busID, WaitTime = times[min(times)];
+p1 = busID * WaitTime;
+p2 = find_min_x(BusList,OffsetList); #CRT
+print("part 1 =",p1);
+print("part 2 =",p2);