aoc-2021/19.py

from util import get_input
from itertools import product

input = []

for line in get_input("19.input"):
    if line == "":
        continue
    elif line.startswith("---"):
        input.append([])
    else:
        input[-1].append(tuple([int(i) for i in line.split(",")]))

def sub(a, b):
    return (a[0] - b[0], a[1] - b[1], a[2] - b[2])

def add(a, b):
    return (a[0] + b[0], a[1] + b[1], a[2] + b[2])

def rotate(a, rot):
    if rot == 0:
        return (a[0], a[1], a[2])
    elif rot == 1:
        return (a[0], -a[2], a[1])
    elif rot == 2:
        return (a[0], -a[1], -a[2])
    else:
        return (a[0], a[2], -a[1])

def orient(a, o):
    (dir, neg, rot) = o
    if dir == 0:
        x = neg * a[0]
        if neg == 1:
            y = a[1]
            z = a[2]
        else:
            y = a[2]
            z = a[1]
    elif dir == 1:
        x = neg * a[1]
        if neg == 1:
            y = a[2]
            z = a[0]
        else:
            y = a[0]
            z = a[2]
    else:
        x = neg * a[2]
        if neg == 1:
            y = a[0]
            z = a[1]
        else:
            y = a[1]
            z = a[0]

    return rotate((x, y, z), rot)

def dist(a):
    return abs(a[0]) + abs(a[1]) + abs(a[2])

def dist2(a):
    return a[0] ** 2 + a[1] ** 2 + a[2] ** 2

def try_match(existing, new):
    for ebase in list(existing)[:-11]:
        edists = set([dist2(sub(ebase, e)) for e in existing])
        for nbase in new[:-11]:
            ndists = set([dist2(sub(nbase, n)) for n in new])
            matching = edists.intersection(ndists)
            if len(matching) >= 12:
                for o in product([0, 1, 2], [-1, 1], [0, 1, 2, 3]):
                    relative = sub(ebase, orient(nbase, o))
                    maxx = len(new)
                    found = 0
                    for i, n in enumerate(new):
                        if (found + (maxx - i)) < 12:
                            break
                        if add(orient(n, o), relative) in existing:
                            found += 1
                    if found >= 12:
                        return relative, o
                print("Found dist match, but no orient")
    return None

known = {0: (0, 0, 0)}
tried = set()
existing = {0: set(input[0])}
while len(input) > len(known):
    before = len(known)
    for j in list(known.keys()):
        if j in tried:
            continue
        for i, probe in enumerate(input):
            if i in known.keys():
                continue
            rel = try_match(existing[j], probe)
            if rel:
                rel, o = rel
                existing[i] = set([add(orient(n, o), rel) for n in probe])
                known[i] = rel
        tried.add(j)
    if before == len(known):
        print("No solution")
        break
    print("Progress: ", len(known), "/", len(input))

tot = set()
for v in existing.values():
    tot = tot.union(v)
print("Part 1:", len(tot))

print("Part 2:", max(dist(sub(a, b)) for [a, b] in product(list(known.values()), repeat=2)))