1  from lib import *
 2  
 3  input = read_input(2021, 19)
 4  
 5  ROT1 = [
 6      np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]]),
 7      np.array([[-1, 0, 0], [0, -1, 0], [0, 0, 1]]),
 8      np.array([[0, 1, 0], [-1, 0, 0], [0, 0, 1]]),
 9      np.array([[0, -1, 0], [1, 0, 0], [0, 0, 1]]),
10      np.array([[0, 0, 1], [0, -1, 0], [1, 0, 0]]),
11      np.array([[0, 0, -1], [0, 1, 0], [1, 0, 0]]),
12  ]
13  
14  
15  ROT2 = [
16      np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]]),
17      np.array([[1, 0, 0], [0, 0, -1], [0, 1, 0]]),
18      np.array([[1, 0, 0], [0, -1, 0], [0, 0, -1]]),
19      np.array([[1, 0, 0], [0, 0, 1], [0, -1, 0]]),
20  ]
21  
22  
23  def rotations():
24      for a in ROT1:
25          for b in ROT2:
26              yield lambda x: b @ (a @ x)
27  
28  
29  def match_scanner(beacons, scanner_positions, scanner):
30      for rot in rotations():
31          counter = Counter()
32  
33          for rel in map(rot, scanner[0]):
34              for abs_ in map(np.array, beacons):
35                  k = abs_ - rel
36  
37                  counter[kt := tuple(k)] += 1
38  
39                  if counter[kt] >= 12:
40                      beacons.update([tuple(rot(x) + k) for x in scanner[0]])
41  
42                      scanner_positions.append(k)
43  
44                      return
45  
46  
47  remaining = []
48  for block in input.split("\n\n"):
49      positions = [np.array(tuple(map(int, line.split(",")))) for line in block.splitlines()[1:]]
50      distances = {int((x := a - b).dot(x)) for a in positions for b in positions}
51      remaining.append((positions, distances))
52  
53  first = remaining.pop(0)
54  beacons = {*map(tuple, first[0])}
55  distances = first[1].copy()
56  scanners = []
57  while remaining:
58      i = max(range(len(remaining)), key=lambda j: len(remaining[j][1] & distances))
59      s = remaining.pop(i)
60  
61      match_scanner(beacons, scanners, s)
62  
63      distances.update(s[1])
64  
65  
66  print(len(beacons))
67  print(max(sum(np.abs(a - b)) for a in scanners for b in scanners))