-
Notifications
You must be signed in to change notification settings - Fork 0
/
day19.py
174 lines (143 loc) · 5.75 KB
/
day19.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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
# vi: set shiftwidth=4 tabstop=4 expandtab:
import datetime
import os
import re
import itertools
import collections
top_dir = os.path.dirname(os.path.abspath(__file__)) + "/../../"
year_dir = os.path.dirname(os.path.abspath(__file__))
scanner_re = r"^--- scanner (\d+) ---$"
def get_info_from_lines(lines):
scanner = None
info = []
scanner_info = []
for l in lines:
if scanner is None:
m = re.match(scanner_re, l)
scanner = int(m.group(1))
assert scanner == len(info)
elif l == "":
info.append(tuple(scanner_info))
scanner = None
scanner_info = []
else:
pos = tuple(int(v) for v in l.split(","))
scanner_info.append(pos)
assert scanner_info
info.append(tuple(scanner_info))
return info
def get_info_from_file(file_path=top_dir + "resources/year2021_day19_input.txt"):
with open(file_path) as f:
return get_info_from_lines([l.strip() for l in f])
def gap(p1, p2):
# Compute some tuple representing the gap between 2 points
# That value does not depend on the position/orientation of the observer
return tuple(sorted(abs(c1 - c2) for c1, c2 in zip(p1, p2)))
def raw_gap(p1, p2):
return tuple((c1 - c2) for c1, c2 in zip(p1, p2))
def manhattan(p1, p2):
return sum(abs(c1 - c2) for c1, c2 in zip(p1, p2))
def get_gaps(info):
# Mapping gaps to list of (scanner number, beacon1, beacon2)
gaps = dict()
for i, scanner_info in enumerate(info):
for (b1, p1), (b2, p2) in itertools.combinations(enumerate(scanner_info), 2):
gaps.setdefault(gap(p1, p2), []).append((i, b1, b2))
return gaps
def get_overlaps(gaps, nb_common):
# If scanners have n overlapping points, we expect n*(n-1)/2
# common pairs of points seen from the 2 scanners
nb_overlaps = nb_common * (nb_common - 1) // 2
# Count similar gaps for each pair of scanners
overlaps = collections.Counter()
for points in gaps.values():
for p1, p2 in itertools.combinations(points, 2):
i, _, _ = p1
j, _, _ = p2
k = tuple(sorted([i, j]))
overlaps[k] += 1
graph = dict()
for (s1, s2), count in overlaps.items():
if count >= nb_overlaps:
graph.setdefault(s1, []).append(s2)
graph.setdefault(s2, []).append(s1)
return graph
def get_rotations():
for s_x, s_y, s_z in itertools.product([-1, 1], repeat=3):
yield lambda x, y, z: (s_x * x, s_y * y, s_z * z)
yield lambda x, y, z: (s_x * x, s_z * z, s_y * y)
yield lambda x, y, z: (s_y * y, s_x * x, s_z * z)
yield lambda x, y, z: (s_y * y, s_z * z, s_x * x)
yield lambda x, y, z: (s_z * z, s_y * y, s_x * x)
yield lambda x, y, z: (s_z * z, s_x * x, s_y * y)
def convert_scanner_info(reference_points, scanner_info, nb_common):
# If scanners have n overlapping points, we expect n*(n-1) similar gaps
nb_overlaps = nb_common * (nb_common - 1)
ref_raw_gaps = set(
raw_gap(p1, p2) for p1, p2 in itertools.permutations(reference_points, 2)
)
for rot in get_rotations():
info = [rot(*point) for point in scanner_info]
raw_gaps = set(raw_gap(p1, p2) for p1, p2 in itertools.permutations(info, 2))
nb_match = len(raw_gaps.intersection(ref_raw_gaps))
if nb_match >= nb_overlaps:
deltas = collections.Counter(
raw_gap(p1, p2) for p1, p2 in itertools.product(reference_points, info)
)
delta, count = deltas.most_common(1)[0]
if count >= nb_common:
dx, dy, dz = delta
info = [(x + dx, y + dy, z + dz) for x, y, z in info]
assert len(set(info).intersection(set(reference_points))) >= nb_common
return info, delta
assert False
def convert_points(info, nb_common):
gaps = get_gaps(info)
overlaps = get_overlaps(gaps, nb_common)
scanners = set(range(len(info)))
assert scanners == set(overlaps.keys())
# Assume scanner 0 is the reference and convert everything into it
# Map index to tuple (list of points, position of scanner)
converted = {0: (info[0], (0, 0, 0))}
change = True
while change:
change = False
for scan in scanners:
for neigh in overlaps[scan]:
if scan not in converted and neigh in converted:
converted[scan] = convert_scanner_info(
converted[neigh][0], info[scan], nb_common
)
change = True
assert all(s in converted for s in scanners)
all_points = set()
for (points, scanner) in converted.values():
all_points.update(points)
all_scanners = [scanner for points, scanner in converted.values()]
return all_points, all_scanners
def get_max_distance(points):
return max(manhattan(p1, p2) for p1, p2 in itertools.combinations(points, 2))
def run_tests():
nb_common = 12
info = get_info_from_file(year_dir + "/day19_example_input.txt")
gaps = get_gaps(info)
overlaps = get_overlaps(gaps, nb_common)
assert 1 in overlaps[0]
assert 0 in overlaps[1]
assert 1 in overlaps[4]
assert 4 in overlaps[1]
converted_points, converted_scanners = convert_points(info, nb_common)
assert len(converted_points) == 79
assert get_max_distance(converted_scanners) == 3621
def get_solutions():
nb_common = 12
info = get_info_from_file()
converted_points, converted_scanners = convert_points(info, nb_common)
print(len(converted_points) == 454)
print(get_max_distance(converted_scanners) == 10813)
if __name__ == "__main__":
begin = datetime.datetime.now()
run_tests()
get_solutions()
end = datetime.datetime.now()
print(end - begin)