/
day13
executable file
·56 lines (49 loc) · 1.77 KB
/
day13
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
#!/usr/bin/python
# Floris Douw
# 2020
#
# AoC 2020 Day 13: Shuttle Search
import sys
import time
import numpy as np
def all_equal(v):
for i in range(1, len(v)):
if v[i] != v[i - 1]:
return False
return True
with open('input/day13.test', 'r') as f:
start1 = time.perf_counter()
estimate = int(f.readline())
ids = [int(n) for n in f.readline().split(',') if n != 'x']
minwait = sys.maxsize
minid = -1
for n in ids:
if (w := n - estimate % n) < minwait:
# if (w := n * (1 + estimate // n) - estimate) < minwait: # Slightly faster?
minwait = w
minid = n
end1 = time.perf_counter()
print(f'Part 1: {minid * minwait}')
with open('input/day13', 'r') as f:
_ = f.readline() # ignore the first line
start2 = time.perf_counter()
periods = []
positions = []
for i, n in enumerate(f.readline().split(',')):
if n != 'x':
periods.append(int(n))
positions.append(-i) # Negate the offset: this way, the resulting sync time will be the correct answer
while not all_equal(positions):
min_idx = np.argmin(positions)
max_idx = np.argmax(positions)
k = np.ceil((positions[max_idx] - positions[min_idx]) / periods[min_idx])
positions[min_idx] += int(k * periods[min_idx])
if positions[min_idx] == positions[max_idx]:
# These 2 buses are now in sync and will only be in sync again with a period of lcm(period_a, period_b)
periods[max_idx] = np.lcm(periods[min_idx], periods[max_idx])
del periods[min_idx]
del positions[min_idx]
end2 = time.perf_counter()
print(f'Part 2: {positions[0]}')
print(f'Time 1: {end1 - start1:1.3}')
print(f'Time 2: {end2 - start2:1.3}')