summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--day13/day13.py72
-rw-r--r--day13/input2
2 files changed, 74 insertions, 0 deletions
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