blob: de80cb77870eacbaa277d090b8a1eb9f0a63511b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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
|
