-
Notifications
You must be signed in to change notification settings - Fork 0
/
part1.py
84 lines (57 loc) · 2.72 KB
/
part1.py
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
78
79
80
81
82
83
84
from itertools import compress, permutations
from collections import defaultdict
from math import copysign
Vector = tuple[int, int, int]
def vector_rotations(vector: Vector) -> tuple[Vector]:
variations = set()
for x, y, z in permutations(vector):
for flip_x in (-1, 1):
for flip_y in (-1, 1):
for flip_z in (-1, 1):
variations.add((flip_x * x, flip_y * y, flip_z * z))
return tuple(variations)
def apply_rotation(scanner: tuple[Vector], rotation: Vector) -> tuple[Vector]:
result = []
for reading in scanner:
result.append([])
for i in range(len(reading)):
result[-1].append(reading[abs(rotation[i]) - 1] * int(copysign(1, rotation[i])))
return result
def add_vectors(vector1: Vector, vector2: Vector) -> Vector:
return tuple(x + y for x, y in zip(vector1, vector2))
def sub_vectors(vector1: Vector, vector2: Vector) -> Vector:
return tuple(x - y for x, y in zip(vector1, vector2))
ALL_VECTOR_ROTATIONS = vector_rotations((1, 2, 3))
with open("input.txt") as file:
scanner_readings = []
for line in file:
if line.startswith("---"):
scanner_readings.append([])
elif line.strip():
scanner_readings[-1].append(tuple(map(int, line.split(','))))
total_scanners = len(scanner_readings)
scanner_processed = [False] * total_scanners
scanner_processed[0] = True
scanner_positions = [None] * total_scanners
scanner_positions[0] = (0, 0, 0)
while not all(scanner_processed):
for ref_index in compress(range(total_scanners), scanner_processed):
ref_scanner = scanner_readings[ref_index]
for test_index in compress(range(total_scanners), (not processed for processed in scanner_processed)):
test_scanner = scanner_readings[test_index]
for rotation in ALL_VECTOR_ROTATIONS:
test_rotation = apply_rotation(test_scanner, rotation)
offsets = defaultdict(int)
for ref_reading in ref_scanner:
for test_reading in test_rotation:
offsets[sub_vectors(test_reading, ref_reading)] += 1
most_common_offset = max(offsets, key=offsets.get)
if offsets[most_common_offset] >= 12:
scanner_positions[test_index] = add_vectors(most_common_offset, scanner_positions[ref_index])
scanner_processed[test_index] = True
scanner_readings[test_index] = test_rotation
break
for scanner, shift in zip(scanner_readings, scanner_positions):
for i, reading in enumerate(scanner):
scanner[i] = sub_vectors(reading, shift)
print(len(set(map(tuple, sum(scanner_readings, [])))))