AoC, Day 8

import itertools
import math
import time

def timer(func, *args, **kwargs):
    def wrapper(*args, **kwargs):
        a = time.time()
        result = func(*args, **kwargs)
        b = time.time()
        print(func.__name__, (b - a))
        return result

    return wrapper

def acquire_data(filename):
    return open(filename).read().splitlines()

def calc_distance(x1, y1, z1, x2, y2, z2):
    # While the actual formula calls for math.sqrt(), pow() is faster, and we don't really need the exact result.
    return pow((x2 - x1)**2 + (y2 - y1)**2 + (z2 - z1)**2, 2)

@timer
def process_v1(data, max_attempts=1000, slice_len=3):
    data = [eval(junction) for junction in data]
    max_circuit_length = len(data)
    distances, banned_junctions = {}, {}

    for junction_pair in itertools.product(data, repeat=2):
        # Banning a junction means that it is no longer a valid option for junction_pair[1], which is useful.
        # For instance, if the very first junction_pair[0] we encounter is (0, 0, 0), then two things happen.
        # 1. We are about to encounter (0, 0, 0) paired with (0, 0, 0), which is not a valid pair. It will be immediately discarded.
        # 2. Later on, once junction_pair[0] is (0, 0, 0) no longer, we'll be encountering (0, 0, 0) as junction_pair[1]. Yet, every
        # such pair has already been processed: (x, y, z), (0, 0, 0) and (0, 0, 0), (x, y, z) are one and the same for our purposes.
        banned_junctions[junction_pair[0]] = None
        if junction_pair[1] in banned_junctions:
            continue

        x1, y1, z1 = junction_pair[0]
        x2, y2, z2 = junction_pair[1]

        # This is risky, because we can't be certain that all distances are unique, but it'll do, luckily.
        distances[calc_distance(x1, y1, z1, x2, y2, z2)] = (junction_pair[0], junction_pair[1])

    circuitry = []
    iterations = 0
    last_connection = None

    for d in sorted(distances.items()):
        _, junctions = d
        iterations += 1

        if iterations > max_attempts > 0:
            break

        newest_junction = None

        for circuit in circuitry:
            if junctions[0] in circuit and junctions[1] in circuit:
                break
            elif junctions[0] in circuit:
                newest_junction = junctions[1]
            elif junctions[1] in circuit:
                newest_junction = junctions[0]

            if newest_junction:
                circuit.add(newest_junction)
                break

        if not newest_junction:
            # Reconstructing the list in this fashion beats appending in terms of performance (with the further actions in mind).
            circuitry = [set([junctions[0], junctions[1]])] + circuitry

        # And now we have to check whether there are any pairs of circuits which have common elements, meaning they must be condensed into a single circuit.
        diff = bool(newest_junction)
        if diff:
            # We know that a newly added junction is present in at least one circuit. No escaping that.
            diff = len([c for c in circuitry if newest_junction in c])
            # But we need it to be present in at least two circuits, otherwise we should just carry on.
            diff = bool(diff > 1)

        circuitry = sorted(circuitry, key=len)

        # If a new circuit has just been added, then it's not a part of any other circuits.
        # Otherwise one of them would have been modified, raising the newest_junction flag.
        # Thus, the following loop is pointless, and the value of diff will let us skip it.
        while diff:
            b = time.time()
            unified_circuit = None
            diff = len(circuitry)

            for i, main_circuit in enumerate(circuitry):
                for j in range(i+1, len(circuitry)):
                    if main_circuit.intersection(circuitry[j]):
                        unified_circuit = (main_circuit.union(circuitry[j]))
                        circuitry[i] = circuitry[j] = None
                        circuitry.append(unified_circuit)
                        break

                if unified_circuit:
                    circuitry = [c for c in circuitry if c]
                    break

            diff -= len(circuitry)

        if not last_connection and max([len(c) for c in circuitry]) == max_circuit_length:
            last_connection = d[1]

        if len(circuitry) == 1 and len(circuitry[0]) == max_circuit_length:
            break

    circuitry_sizes = sorted([len(c) for c in circuitry], reverse=True)

    if last_connection:
        last_connection = last_connection[0][0] * last_connection[1][0]

    return math.prod(circuitry_sizes[:slice_len]), last_connection

@timer
def process_v2(data):
    return process_v1(data, max_attempts=0)

@timer
def main(func):
    data = acquire_data("008 - Input.txt")
    return func(data)

print(main(process_v1))
print(main(process_v2))