81 lines
2.7 KiB
Python
81 lines
2.7 KiB
Python
import sys; sys.dont_write_bytecode = True;
|
|
from utils import *
|
|
import typing
|
|
|
|
|
|
def do_case(inp: str, sample=False):
|
|
# READ THE PROBLEM FROM TOP TO BOTTOM OK
|
|
def sprint(*a, **k): sample and print(*a, **k)
|
|
lines: typing.List[str] = inp.splitlines()
|
|
paras: typing.List[typing.List[str]] = lmap(str.splitlines, inp.split("\n\n"))
|
|
out = 0
|
|
|
|
scanners = []
|
|
for para in paras:
|
|
points = lmap(ints, para[1:])
|
|
scanners.append(points)
|
|
# print(len(points))
|
|
|
|
# assume scanner 0 is good
|
|
|
|
FACINGS = [x for i in [-1, 1] for x in [[i, 0, 0], [0, i, 0], [0, 0, i]]]
|
|
|
|
def cross(a, b):
|
|
c = [a[1]*b[2] - a[2]*b[1],
|
|
a[2]*b[0] - a[0]*b[2],
|
|
a[0]*b[1] - a[1]*b[0]]
|
|
|
|
return c
|
|
|
|
def common(a, b):
|
|
aset = set(map(tuple, a))
|
|
# return b's points, but now relative to a
|
|
for facing in FACINGS:
|
|
for up in [f for f in FACINGS if all(abs(x) != abs(y) for x, y in zip(f, facing) if x or y)]:
|
|
|
|
# facing's
|
|
right = cross(facing, up)
|
|
|
|
matrix = [facing, up, right]
|
|
new_b = [matvec(matrix, vec) for vec in b]
|
|
|
|
for a_point in a:
|
|
for b_point in new_b:
|
|
# assume they're the same
|
|
# add a-b to all b
|
|
delta = padd(a_point, pneg(b_point))
|
|
new_new_b = [padd(delta, b) for b in new_b]
|
|
if len(aset.intersection(map(tuple, new_new_b))) >= 12:
|
|
return new_new_b
|
|
return None
|
|
|
|
# if sample:
|
|
# print(common(scanners[0], scanners[1]))
|
|
# quit()
|
|
good_scanners = [None] * len(scanners)
|
|
good_scanners[0] = scanners[0]
|
|
done_scanners = [False] * len(scanners)
|
|
while True:
|
|
for i in range(len(scanners)):
|
|
if good_scanners[i] and not done_scanners[i]:
|
|
for j in range(len(scanners)):
|
|
if i != j and good_scanners[j] is None:
|
|
test = common(good_scanners[i], scanners[j])
|
|
# sprint(test)
|
|
if test is not None:
|
|
good_scanners[j] = test
|
|
done_scanners[i] = True
|
|
print(done_scanners, lmap(bool, good_scanners))
|
|
if all(done_scanners):
|
|
break
|
|
|
|
out = set(tuple(point) for points in good_scanners for point in points)
|
|
out = len(out)
|
|
|
|
|
|
if out:
|
|
print("out: ", out)
|
|
return # RETURNED VALUE DOESN'T DO ANYTHING, PRINT THINGS INSTEAD
|
|
|
|
with open('./2021/19.input') as input_file:
|
|
do_case(input_file.read()) |