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
|
import sys, re, itertools
# 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)])
def manhattan(a):
return abs(a[0] - a[2]) + abs(a[1] - a[3])
def partOne(y):
r = RangeSet()
for l in data:
m = manhattan(l)
w = m - abs(l[1] - y)
if w < 0: continue
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)
def vis(size):
s = ''
for y in range(size):
for x in range(size):
c = ' '
for l in data:
m = abs(l[0] - l[2]) + abs(l[1] - l[3])
if abs(l[0] - x) + abs(l[1] - y) <= m:
c = '#'
break
if (x, y) in [(a[0], a[1]) for a in data]:
c = 'S'
if (x, y) in [(a[2], a[3]) for a in data]:
c = 'B'
s += c
s += '\n'
return s
def partTwo():
for y in range(4000000):
if y % 4000 == 0: print(y / 40000)
r = RangeSet()
for l in data:
m = manhattan(l)
w = m - abs(l[1] - y)
if w < 0: continue
r.add(l[0] - w, l[0] + w)
l = len(r.rs)
if l == 0: break
if l != 1:
print(r.rs, y)
x = r.rs[0][1] + 1
return 4000000 * x + y
#print(partOne(2000000))
print(partTwo())
|
