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
|
from utils import open_day, Point2D, norm_1, inbounds
import re
regex = re.compile(r'^Sensor at x=(-?[0-9]+), y=(-?[0-9]+): closest beacon is at x=(-?[0-9]+), y=(-?[0-9]+)$')
sensors = []
with open_day(15) as f:
for line in f:
m = regex.match(line)
assert(m)
sx, sy, bx, by = map(int, m.group(1, 2, 3, 4))
sensors.append((Point2D(sx, sy), Point2D(bx, by)))
def overlaps_at_y(sensors, y=2000000):
beacons = sum(1 for b in set(b for _, b in sensors) if b.y == y)
sensors = [s for s in ((s[0], norm_1(s[1] - s[0])) for s in sensors) if abs(s[0].y - y) <= s[1]]
ranges = []
for sensor, rang in sensors:
dx = rang - abs(sensor.y - y)
ranges.append((sensor.x - dx, sensor.x + dx))
ranges.sort()
count = 0
cstart, cend = ranges.pop(0)
for start, end in ranges:
if start <= cend:
cend = max(cend, end)
continue
count += cend - cstart + 1
cstart, cend = start, end
return count + cend - cstart + 1 - beacons
print(overlaps_at_y(sensors))
def edgepoints(sensors):
for sp, bp in sensors:
dist = norm_1(bp - sp) + 1
for x in range(sp.x - dist, sp.x + dist + 1):
dy = dist - abs(x - sp.x)
yield Point2D(x, sp.y+dy)
if dy != 0: yield Point2D(x, sp.y-dy)
def dedup(it):
seen = set()
for v in it:
if v in seen: continue
seen.add(v)
yield v
def findbeacon(sensors, max_dim=4000000):
for p in dedup(edgepoints(sensors)):
if not inbounds(p, Point2D(max_dim + 1, max_dim + 1)): continue
for sp, bp in sensors:
dist = norm_1(bp - sp)
if norm_1(p - sp) <= dist: break
else:
return p
def tuning_freq(p):
return p.x * 4000000 + p.y
print(tuning_freq(findbeacon(sensors)))
|
