day 13

2 files changed, 40 insertions, 0 deletions

diff --git a/20/README b/20/README
index 1ab06a1..976822f 100644
--- a/20/README
+++ b/20/README
@@ -14,6 +14,7 @@ Day     Time            Ans     Time            Ans
  10    0.027           2046    0.161  1157018619904
  11  432.343           2338  580.579           2134
  12    0.257           1645    0.279          35292
+ 13    0.006           2095    0.018 598411311431841
       -------                 -------
 tot    TBD   ms                TBD   ms
 
@@ -22,6 +23,7 @@ Stats:
 
       -------Part 1--------   -------Part 2--------
 Day       Time  Rank  Score       Time  Rank  Score
+ 13   01:16:45  7549      0   02:27:40  3806      0
  12   00:09:08   645      0   00:16:03   373      0
  11   00:55:39  4799      0   01:20:27  4040      0
  10   00:08:17  1496      0   00:51:01  2766      0
diff --git a/20/py/d13.py b/20/py/d13.py
new file mode 100644
index 0000000..fde95e9
--- /dev/null
+++ b/20/py/d13.py
@@ -0,0 +1,38 @@
+#!/usr/bin/env python3
+import aoc20
+import sys
+
+
+def pt1(_in):
+    me = int(_in[0])
+    busses = [int(s) for s in _in[1].split(",") if s != "x"]
+    time = me
+    while True:
+        for bus in busses:
+            if time % bus == 0:
+                return (time - me) * bus
+        time += 1
+
+
+def mul_inv(a, m):
+    return pow(a, -1, mod=m)
+
+
+def pt2(_in):
+    busses = {}
+    for i, s in enumerate(_in[1].strip().split(",")):
+        if s != "x":
+            busses[i] = int(s)
+    N = 1
+    for dep, bus in busses.items():
+        N *= bus
+    x = 0
+    for dep, bus in busses.items():
+        x += -dep * (N // bus) * mul_inv(N // bus, bus)
+    return x % N
+
+
+if __name__ == "__main__":
+    input = aoc20.read_input(sys.argv[1:], 13)
+    print(pt1(input))
+    print(pt2(input))