-
Notifications
You must be signed in to change notification settings - Fork 3
/
day20.py
80 lines (61 loc) · 2.08 KB
/
day20.py
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
73
74
75
76
77
78
79
80
from collections import defaultdict
import re
with open('./inputs/20.txt') as f:
instructions = f.readlines()
def magnitude(particle_accelerations):
return sum(r**2 for r in particle_accelerations)
pattern = re.compile(r'p=<(-*\d+,-*\d+,-*\d+)>, v=<(-*\d+,-*\d+,-*\d+)>, a=<(-*\d+,-*\d+,-*\d+)>')
particles = []
smallest_acceleration = 98765
closest_particle = None
for i, line in enumerate(instructions):
particle = tuple(tuple(map(int, g.split(','))) for g in re.match(pattern, line).groups())
accel = magnitude(particle[-1])
if accel < smallest_acceleration:
smallest_acceleration = accel
closest_particle = i
particles.append(particle)
print(closest_particle)
def get_differences(x, y):
diff = lambda r_x, r_y: (r_x[0] - r_y[0], r_x[1] - r_y[1], r_x[2] - r_y[2])
p_x, v_x, a_x = x
p_y, v_y, a_y = y
p_diffs = diff(p_x, p_y)
v_diffs = diff(v_x, v_y)
a_diffs = diff(a_x, a_y)
return p_diffs, v_diffs, a_diffs
def check_collision(ppp, vvv, aaa, t):
return all(0.5*a*t*t + (v+0.5*a)*t + p == 0 for p, v, a in zip(ppp, vvv, aaa))
def find_collisions(x, y):
ppp, vvv, aaa = get_differences(x, y)
p, v, a = ppp[0], vvv[0], aaa[0]
b = -v - 0.5 * a
D = b*b - 2 * a * p
if a == 0:
if v != 0:
t = -p/v
if check_collision(ppp, vvv, aaa, t):
return t
elif D == 0:
t = b/a
if check_collision(ppp, vvv, aaa, t):
return t
else:
for t in ((b - D**0.5)/a, (b + D**0.5)/a):
if check_collision(ppp, vvv, aaa, t):
return t
return 0
collisions = defaultdict(set)
for i, p1 in enumerate(particles):
for j, p2 in enumerate(particles[i+1:], i+1):
time = find_collisions(p1, p2)
if time > 0:
collisions[time].add((i, j))
alive = set(range(len(particles)))
for time in sorted(collisions.keys()):
now_colliding = set()
for p1, p2 in collisions[time]:
if p1 in alive and p2 in alive:
now_colliding |= {p1, p2}
alive -= now_colliding
print(len(alive))