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
|
import sys, re
# ranges are inclusive from both ends
def range_intersect(a, b):
return a[0] <= b[0] <= a[1] or a[0] <= b[1] <= a[1] or b[0] <= a[0] <= b[1] or b[0] <= a[1] <= b[1]
class RangeSet:
def __init__(self):
self.rs = []
def add(self, a, b):
for i in range(len(self.rs)):
r = self.rs[i]
if range_intersect(r, (a, b)):
a = min(a, r[0])
b = max(b, r[1])
self.rs[i] = None
self.rs = [r for r in self.rs if r]
self.rs.append((a, b))
def size(self):
s = 0
for r in self.rs:
s += r[1] - r[0] + 1
return s
data = []
for line in sys.stdin:
data.append([int(n) for n in re.findall('\d+', line)])
manhattan = [abs(a[0] - a[2]) + abs(a[1] - a[3]) for a in data]
def partOne(y):
r = RangeSet()
for l, m in zip(data, manhattan):
w = m - abs(l[1] - y)
if w < 0: continue
#print(l, w, l[0] - w, l[0] + w)
r.add(l[0] - w, l[0] + w)
beacons = set([(a[2], a[3]) for a in data if a[3] == y])
return r.size() - len(beacons)
print(partOne(2000000))
|
