From 7d09a0e556b3a957d16f6b44908371ee9d4b6f76 Mon Sep 17 00:00:00 2001
From: Cody Hiar <cody@hiar.ca>
Date: Fri, 26 Mar 2021 12:55:39 -0600
Subject: day 13

---
 day13/day13.py | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 day13/input    |  2 ++
 2 files changed, 74 insertions(+)
 create mode 100644 day13/day13.py
 create mode 100644 day13/input

diff --git a/day13/day13.py b/day13/day13.py
new file mode 100644
index 0000000..de80cb7
--- /dev/null
+++ b/day13/day13.py
@@ -0,0 +1,72 @@
+"""Day 13."""
+import re
+
+with open("input") as f:
+    data = f.read().rstrip().split("\n")
+
+leave = int(data[0])
+buses_orig = data[1].split(",")
+buses = list(map(int, filter(lambda elem: elem != "x", buses_orig)))
+
+lowest_time = None
+lowest_id = None
+
+for bus in buses:
+    itr = 0
+    while itr < leave:
+        itr += bus
+    diff = itr - leave
+    if lowest_time is None:
+        lowest_time = diff
+        lowest_id = bus
+    else:
+        if diff < lowest_time:
+            lowest_time = diff
+            lowest_id = bus
+
+res = lowest_time * lowest_id
+print(res)
+assert res == 1915
+
+
+# Part 2
+
+# My brute force, takes too long for big input
+
+# step = max(buses)
+# step_idx = buses_orig.index(str(step))
+# print(step, step_idx)
+
+# pos = step
+# while True:
+#     print(pos)
+#     all_good = True
+#     for idx, el in enumerate(buses_orig):
+#         if el == 'x':
+#             continue
+#         temp = pos + idx - step_idx
+#         if temp % int(el) != 0:
+#             all_good = False
+#             break
+#     if all_good:
+#         print(pos - step_idx)
+#         break
+#     pos += step
+
+
+# Peter norvig's genius way
+
+
+def wait(id, t):
+    return 0 if t % id == 0 else id - t % id
+
+time = 0
+step = 1
+schedule = {t: int(id) for t, id in enumerate(buses_orig) if id != 'x'}
+for t in schedule:
+    while wait(schedule[t], time + t):
+        time += step
+    step *= schedule[t]
+print(time)
+
+assert time == 294354277694107
diff --git a/day13/input b/day13/input
new file mode 100644
index 0000000..e614056
--- /dev/null
+++ b/day13/input
@@ -0,0 +1,2 @@
+1000391
+19,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,383,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29,x,457,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,17
-- 
cgit v1.2.3