My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1
2import sys
3import fileinput
4
5from utils import parse_nums, Point, NE, SE, SW, NW
6
7# How far to the closest beacon?
8manhattan = {}
9sensors = set()
10beacons = set()
11
12min_x = 1e9
13max_x = -1e9
14
15# Parse input
16for line in fileinput.input():
17 sx, sy, bx, by = parse_nums(line)
18 min_x = min(min_x, sx)
19 max_x = max(max_x, sx)
20 s = Point(sx, sy)
21 b = Point(bx, by)
22 sensors.add(s)
23 beacons.add(b)
24 manhattan[s] = s.dist_manhattan(b)
25
26
27# Part 1
28TARGET_Y = 2000000
29part_1 = 0
30
31# Only consider the sensors whose area could possibly overlap with the given row.
32close_sensors = set(s for s in sensors if s.y - manhattan[s] <= TARGET_Y <= s.y + manhattan[s])
33
34# Compute the intervals created by the sensor areas along this row.
35intervals = []
36for s in close_sensors:
37 vertical_delta = abs(s.y - TARGET_Y)
38 half_chord = manhattan[s] - vertical_delta
39 intervals.append((s.x - half_chord, s.x + half_chord))
40
41# Merge the intervals to de-duplicate overlaps.
42intervals.sort()
43merged_intervals = []
44merged = set()
45for i, (a, b) in enumerate(intervals):
46 if i in merged:
47 continue
48
49 end = b
50 for j, (c, d) in enumerate(intervals):
51 if i == j:
52 continue
53 if a <= c <= end:
54 end = max(end, d)
55 merged.add(j)
56
57 merged_intervals.append((a, end))
58
59# Answer is the sum of merged intervals minus any beacons in that row.
60part_1 = sum(b - a + 1 for a, b in merged_intervals)
61part_1 -= sum(1 for b in beacons if b.y == TARGET_Y)
62print("Part 1:", part_1)
63
64
65# Part 2
66MIN_BEACON = 0
67MAX_BEACON = 4000000
68
69def gen_outskirts():
70 """Yields the set of points outside-neighbouring the perimeter of all sensors."""
71 for s in sensors:
72 d = manhattan[s] + 1
73 p = Point(s.x - d, s.y)
74 for move in [NE, SE, SW, NW]:
75 for _ in range(d):
76 p += move
77 if MIN_BEACON <= p.x <= MAX_BEACON and MIN_BEACON <= p.y <= MAX_BEACON:
78 yield p
79
80# Check all outskirt positions for whether it could be the undetected beacon.
81for p in gen_outskirts():
82 for s in sensors:
83 if p.dist_manhattan(s) <= manhattan[s]:
84 break
85 else:
86 tuning_freq = p.x * 4000000 + p.y
87 print("Part 2:", tuning_freq)
88 break
89