My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import fileinput
2from itertools import combinations
3
4from utils import parse_nums
5
6
7def find_intersection(x1, y1, x2, y2, x3, y3, x4, y4):
8 # https://stackoverflow.com/a/51127674
9 px = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4)) / ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
10 py = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4)) / ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
11 return [px, py]
12
13# Parse problem input.
14HAILSTONES = [tuple(parse_nums(line)) for line in fileinput.input()]
15
16MIN = 200000000000000
17MAX = 400000000000000
18
19part_1 = 0
20
21for a, b in combinations(HAILSTONES, 2):
22 ax, ay, _, avx, avy, _ = a
23 bx, by, _, bvx, bvy, _ = b
24
25 a_slope = avy / avx
26 a_b = ay - (a_slope * ax)
27
28 a_start = a_slope * MIN + a_b
29 a_end = a_slope * MAX + a_b
30
31 b_slope = bvy / bvx
32 b_b = by - (b_slope * bx)
33
34 b_start = b_slope * MIN + b_b
35 b_end = b_slope * MAX + b_b
36
37 try:
38 px, py = find_intersection(MIN, a_start, MAX, a_end, MIN, b_start, MAX, b_end)
39 except:
40 # Parallel lines.
41 continue
42
43 # Intersection in A's past
44 if avx > 0 and px < ax:
45 continue
46 elif avx < 0 and px > ax:
47 continue
48
49 # Intersection in B's past
50 if bvx > 0 and px < bx:
51 continue
52 elif bvx < 0 and px > bx:
53 continue
54
55 # Good intersection in zone.
56 if MIN <= px <= MAX and MIN <= py <= MAX:
57 part_1 += 1
58
59print("Part 1:", part_1)
60
61# Solve Part 2.
62try:
63 from z3 import Real, Solver
64except:
65 print("Part 2 requires z3 to be installed (`pip install z3-solver`)")
66 import sys
67 sys.exit()
68
69mx = Real('mx')
70my = Real('my')
71mz = Real('mz')
72mxv = Real('mxv')
73myv = Real('myv')
74mzv = Real('mzv')
75c = [Real('c' + str(n)) for n in range(len(HAILSTONES))]
76
77s = Solver()
78
79for i, (px, py, pz, vx, vy, vz) in enumerate(HAILSTONES):
80 s.add(c[i] >= 0)
81 s.add(mx + c[i] * mxv == px + c[i] * vx)
82 s.add(my + c[i] * myv == py + c[i] * vy)
83 s.add(mz + c[i] * mzv == pz + c[i] * vz)
84
85s.check()
86m = s.model()
87print("Part 2:", m[mx].as_long() + m[my].as_long() + m[mz].as_long())