1  from lib import *
 2  
 3  input = read_input(2022, 15)
 4  
 5  lines = [tuple(ints(line)) for line in input.splitlines()]
 6  
 7  
 8  ty = 2000000
 9  out = set()
10  beacons = set()
11  for sx, sy, bx, by in lines:
12      d = abs(sx - bx) + abs(sy - by)
13      a = sx - (d - abs(sy - ty))
14      b = sx + (d - abs(sy - ty))
15      out.update(range(a, b + 1))
16      if by == ty:
17          beacons.add(bx)
18  print(len(out - beacons))
19  
20  
21  sensors = []
22  minx = 1e1337
23  miny = 1e1337
24  maxx = -1e1337
25  maxy = -1e1337
26  for sx, sy, bx, by in lines:
27      d = abs(sx - bx) + abs(sy - by)
28      sensors.append((sx, sy, d))
29  
30      minx = min(sx, minx)
31      miny = min(sy, miny)
32      maxx = max(sx, maxx)
33      maxy = max(sy, maxy)
34  
35  for sx, sy, d in sensors:
36      for x, y in itertools.chain(
37          iter_line(sx, sy - d - 1, sx + d + 1, sy),
38          iter_line(sx + d + 1, sy, sx, sy + d + 1),
39          iter_line(sx, sy + d + 1, sx - d - 1, sy),
40          iter_line(sx - d - 1, sy, sx, sy - d - 1),
41      ):
42          if minx <= x <= maxx and miny <= y <= maxy and all(abs(x - a) + abs(y - b) > d for a, b, d in sensors):
43              print(x * 4000000 + y)
44              break