summaryrefslogtreecommitdiff
path: root/19_2021.py
blob: a970fc79032061d06661d6f1a40e14281545633d (plain)
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))