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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
import sys
inf = sys.argv[1] if len(sys.argv) > 1 else "day19data.txt"
ll = [x for x in open(inf).read().strip().split("\n\n")]
ll = [[eval("[" + x + "]") for x in l.split("\n")[1:]] for l in ll]
coord_remaps = [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
coord_negations = [
(1, 1, 1),
(1, 1, -1),
(1, -1, 1),
(1, -1, -1),
(-1, 1, 1),
(-1, 1, -1),
(-1, -1, 1),
(-1, -1, -1),
]
def apply(remap, negat, scan):
ret = []
for item in scan:
ret.append(
[
negat[0] * item[remap[0]],
negat[1] * item[remap[1]],
negat[2] * item[remap[2]],
]
)
return ret
distances_from_scan_0 = [(0, 0, 0)]
def find_alignment(scan_a, scan_b):
in_a = set([tuple(x) for x in scan_a])
for remap in coord_remaps:
for negat in coord_negations:
a = scan_a
b = apply(remap, negat, scan_b)
for a_pos in a:
for b_pos in b:
remap_by = [
b_pos[0] - a_pos[0],
b_pos[1] - a_pos[1],
b_pos[2] - a_pos[2],
]
matches = 0
all_remapped = []
for other_b in b:
remapped_to_a = (
other_b[0] - remap_by[0],
other_b[1] - remap_by[1],
other_b[2] - remap_by[2],
)
if remapped_to_a in in_a:
matches += 1
all_remapped.append(list(remapped_to_a))
if matches >= 12:
print("match", remap_by)
distances_from_scan_0.append(tuple(remap_by))
return (True, all_remapped)
return (False, None)
good = ll[0]
aligned_indices = set()
aligned_indices.add(0)
aligned = {}
aligned[0] = ll[0]
all_aligned = []
all_aligned += [tuple(x) for x in ll[0]]
noalign = set()
while len(aligned_indices) < len(ll):
for i in range(len(ll)):
if i in aligned_indices:
continue
for j in aligned_indices:
print("Checking", i, "against", j)
if (i, j) in noalign:
continue
ok, remap = find_alignment(aligned[j], ll[i])
if ok:
aligned_indices.add(i)
aligned[i] = remap
all_aligned += [tuple(x) for x in remap]
break
noalign.add((i, j))
print(len(set(all_aligned)))
dists = []
for a in distances_from_scan_0:
for b in distances_from_scan_0:
dists.append(sum([abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2])]))
print(max(dists))
|