"""Verify the bilateral-projection certificate for the literal rounded chiral cube STEP wireframe.

Usage: python verify-chiral-cube-wireframe.py PATH_TO_STEP
Uses exact integer/rational comparisons and requires only the Python standard library.
"""

from fractions import Fraction
from itertools import combinations
from math import sqrt
from pathlib import Path
import re
import sys

SCALE = 10**12
DELTA = Fraction(1, 10**10)
EPSILON = 2 * DELTA


def add(a, b):
    return tuple(x + y for x, y in zip(a, b))


def subtract(a, b):
    return tuple(x - y for x, y in zip(a, b))


def multiply(a, value):
    return tuple(x * value for x in a)


def dot(a, b):
    return sum(x * y for x, y in zip(a, b))


def cross(a, b):
    x, y, z = a
    p, q, r = b
    return (y * r - z * q, z * p - x * r, x * q - y * p)


def norm_squared(a):
    return dot(a, a)


def references(args):
    return tuple(map(int, re.findall(r"#(\d+)", args)))


def read_centers(file):
    source = file.read_text(encoding="latin-1")
    assert re.search(r"SI_UNIT\s*\(\s*\.MILLI\.\s*,\s*\.METRE\.", source)
    entities = {
        int(number): (kind, args)
        for number, kind, args in re.findall(r"#(\d+)\s*=\s*([A-Z][A-Z0-9_]*)\s*\((.*?)\)\s*;", source, re.S)
    }

    def coords(identifier, kind):
        actual, args = entities[identifier]
        assert actual == kind
        return tuple(Fraction(x.strip()) for x in re.search(r"\(([^()]*)\)\s*$", args)[1].split(","))

    groups = {}
    lines = arcs = 0
    for kind, args in entities.values():
        if kind != "EDGE_CURVE":
            continue
        start, end, geometry = references(args)
        curve, params = entities[geometry]
        if curve == "LINE":
            lines += 1
            continue
        assert curve == "CIRCLE"
        assert coords(references(entities[start][1])[0], "CARTESIAN_POINT") != coords(
            references(entities[end][1])[0], "CARTESIAN_POINT"
        )
        placement, = references(params)
        assert entities[placement][0] == "AXIS2_PLACEMENT_3D"
        origin, normal, _ = references(entities[placement][1])
        point = coords(origin, "CARTESIAN_POINT")
        center = tuple(round(SCALE * coordinate) for coordinate in point)
        assert norm_squared(subtract(point, tuple(Fraction(t, SCALE) for t in center))) < DELTA**2
        groups.setdefault(center, []).append(coords(normal, "DIRECTION"))
        arcs += 1
    assert (lines, arcs, len(groups)) == (24, 27, 8)
    for normals in groups.values():
        assert any(abs(dot(a, cross(b, c))) > Fraction(1, 10) for a, b, c in combinations(normals, 3))
    return list(groups)


def involutions(indices):
    if not indices:
        yield ()
        return
    first, *rest = indices
    for tail in involutions(rest):
        yield ((first, first),) + tail
    for index, partner in enumerate(rest):
        for tail in involutions(rest[:index] + rest[index + 1:]):
            yield ((first, partner),) + tail


def residual_lower_bound(rows, multiplier):
    """Squared lower bound on the largest absolute dot product with a unit vector.

    G = M^T M and lambda_min(G) >= 4 det(G) / trace(G)^2.
    Dividing by the row count gives a bound on the squared max row error.
    The multiplier accounts for using doubled midpoints.
    """
    if len(rows) < 3:
        return 0, 1
    aa = ab = ac = bb = bc = cc = 0
    for x, y, z in rows:
        aa += x*x
        ab += x*y
        ac += x*z
        bb += y*y
        bc += y*z
        cc += z*z
    determinant = aa*(bb*cc-bc*bc) - ab*(ab*cc-ac*bc) + ac*(ab*bc-ac*bb)
    trace = aa + bb + cc
    if determinant == 0:
        return 0, 1
    return 4 * determinant, len(rows) * (trace * multiplier * SCALE)**2


def larger(a, b):
    return a[0] * b[1] > b[0] * a[1]


def separated_case(centers):
    pairs = [(a, b) for a in range(len(centers)) for b in range(a, len(centers)) if a != b]
    differences = {ij: subtract(centers[ij[0]], centers[ij[1]]) for ij in pairs}
    midpoints = {(i, j): add(a, b) for i, a in enumerate(centers) for j, b in enumerate(centers) if i <= j}
    worst = None
    count = 0
    for orbits in involutions(tuple(range(len(centers)))):
        vertical = residual_lower_bound([differences[ij] for ij in orbits if ij[0] != ij[1]], 1)
        base = midpoints[orbits[0]]
        horizontal = residual_lower_bound([subtract(midpoints[ij], base) for ij in orbits[1:]], 2)
        bound = vertical if larger(vertical, horizontal) else horizontal
        assert larger(bound, (EPSILON.numerator**2, EPSILON.denominator**2))
        if worst is None or larger(worst, bound):
            worst = bound
        count += 1
    assert count == 764
    return count, sqrt(worst[0] / worst[1])


def near_collision_case(centers):
    # The nominal centers are in a 20 mm ball, more than 7 mm apart,
    # and have diameter below 37 mm. Rotating to the nearby pair direction
    # and clustering near-coincident points gives mirror error < 1e-8 mm.
    eta = Fraction(1, 10**8)
    diameter = 37
    signature_margin = 4 * diameter * eta
    area_margin = 2 * diameter * eta
    size = len(centers)
    total = tuple(map(sum, zip(*centers)))
    for point in centers:
        assert norm_squared(subtract(multiply(point, size), total)) < (20 * size * SCALE)**2
    differences = [subtract(p, q) for p, q in combinations(centers, 2)]
    assert all(norm_squared(direction) > (7*SCALE)**2 for direction in differences)
    assert all(norm_squared(direction) < (diameter*SCALE)**2 for direction in differences)
    assert EPSILON + 4 * 20 * (2 * EPSILON) / 7 + 2*DELTA < eta

    minimum_fixed = size
    for direction in differences:
        squared = norm_squared(direction)
        denominator = SCALE * squared
        denominator_squared = denominator**2
        projected = []
        for point in centers:
            q = subtract(multiply(point, squared), multiply(direction, dot(point, direction)))
            if all(norm_squared(subtract(q, p)) * DELTA.denominator**2 > denominator_squared for p in projected):
                projected.append(q)
        distances = [[norm_squared(subtract(p, q)) for q in projected] for p in projected]
        # A matching with error eta must be a permutation.
        assert all(distances[i][j] * eta.denominator**2 > 4 * denominator_squared for i, j in combinations(range(len(projected)), 2))
        signatures = [sorted(row) for row in distances]
        # Matched points' sorted squared-distance signatures may differ by at most
        # 4 times the diameter times eta.
        fixed = [
            projected[i] for i, signature in enumerate(signatures)
            if all(i == j or max(abs(a-b) for a, b in zip(signature, other)) * signature_margin.denominator > signature_margin.numerator * denominator_squared
                   for j, other in enumerate(signatures))
        ]
        minimum_fixed = min(minimum_fixed, len(fixed))
        # Three fixed points must fit in a strip of width eta. Then their doubled
        # triangle area is at most twice the diameter times eta.
        assert any(
            norm_squared(cross(subtract(b, a), subtract(c, a))) * area_margin.denominator**2 > area_margin.numerator**2 * denominator_squared**2
            for a, b, c in combinations(fixed, 3)
        )
    assert len(differences) == 28
    return len(differences), minimum_fixed


def main():
    if len(sys.argv) != 2:
        raise SystemExit(__doc__)
    centers = read_centers(Path(sys.argv[1]))
    print("Read 24 line edges and 27 arcs at 8 centers. All 8 centers have three independent normals.")
    count, residual = separated_case(centers)
    print(f"Excluded all {count:,} pairings for separated centers. Certified equation error: at least {residual:.12g} mm.")
    axes, fixed = near_collision_case(centers)
    print(f"Excluded all {axes} pair directions and their nearby views. Each reference view has at least {fixed} forced fixed centers.")
    print("Certificate passed. The complete STEP wireframe has no exact bilateral orthographic projection.")


if __name__ == "__main__":
    main()
