#!/usr/bin/env python3
"""Independent audit for FPRD-SH-T15--T18.

This implementation does not import the original research checkers.  It uses
bit-mask clique enumeration, direct homogeneous-state evaluation, and direct
product-state multiplicity counts to test the two reviewed theorem families.
"""

from __future__ import annotations

from itertools import combinations, product
from math import prod
import json
from pathlib import Path


Signature = tuple[int, int]  # (letter, nonempty support bit mask)


def compatible(left: Signature, right: Signature) -> bool:
    return left[0] == right[0] or (left[1] & right[1]) == 0


def is_clique(vertices: tuple[Signature, ...], chosen: int) -> bool:
    indices = [i for i in range(len(vertices)) if chosen & (1 << i)]
    return all(compatible(vertices[i], vertices[j]) for i, j in combinations(indices, 2))


def clique_number(vertices: tuple[Signature, ...]) -> int:
    return max(
        (chosen.bit_count() for chosen in range(1 << len(vertices)) if is_clique(vertices, chosen)),
        default=0,
    )


def incoming_at_label_state(vertices: tuple[Signature, ...], labels: tuple[int, ...]) -> int:
    """Count signatures entering a homogeneous state.

    Coordinate label 0 is unused; letter j is encoded as j+1.  A signature
    enters exactly when every coordinate in its support carries its letter.
    The state is required to have no labelled coordinate outside the union of
    entering supports, which is the reachability condition for the starred
    realization.
    """
    entering = [
        support
        for letter, support in vertices
        if all(labels[i] == letter + 1 for i in range(len(labels)) if support & (1 << i))
    ]
    covered = 0
    for support in entering:
        covered |= support
    used = sum((1 << i) for i, label in enumerate(labels) if label)
    return len(entering) if covered == used else 0


def audit_compatibility() -> dict:
    policy_count = 0
    incidence_count = 0
    failures: list[dict] = []
    for arity in (1, 2, 3):
        signatures = tuple(
            (letter, support)
            for letter in (0, 1)
            for support in range(1, 1 << arity)
        )
        for policy_mask in range(1 << len(signatures)):
            vertices = tuple(
                signature
                for i, signature in enumerate(signatures)
                if policy_mask & (1 << i)
            )
            graph_max = clique_number(vertices)
            state_max = max(
                incoming_at_label_state(vertices, labels)
                for labels in product((0, 1, 2), repeat=arity)
            )
            policy_count += 1
            incidence_count += len(vertices)
            if graph_max != state_max:
                failures.append(
                    {
                        "arity": arity,
                        "policy_mask": policy_mask,
                        "graph_max": graph_max,
                        "state_max": state_max,
                    }
                )
    return {
        "policies": policy_count,
        "signature_incidences": incidence_count,
        "failures": failures,
    }


def matching_number(triples: tuple[tuple[int, int, int], ...]) -> int:
    best = 0
    for chosen_mask in range(1 << len(triples)):
        chosen = [triples[i] for i in range(len(triples)) if chosen_mask & (1 << i)]
        if all(
            all(left[d] != right[d] for d in range(3))
            for left, right in combinations(chosen, 2)
        ):
            best = max(best, len(chosen))
    return best


def audit_three_dimensional_matching() -> dict:
    universe = tuple(product(range(2), repeat=3))
    failures: list[dict] = []
    for instance_mask in range(1 << len(universe)):
        instance = tuple(
            triple for i, triple in enumerate(universe) if instance_mask & (1 << i)
        )
        vertices = tuple(
            (
                i,
                (1 << x) | (1 << (2 + y)) | (1 << (4 + z)),
            )
            for i, (x, y, z) in enumerate(instance)
        )
        expected = matching_number(instance)
        observed = clique_number(vertices)
        if expected != observed:
            failures.append(
                {"instance_mask": instance_mask, "matching": expected, "clique": observed}
            )
    return {"instances": 1 << len(universe), "failures": failures}


def target_overhead(targets: tuple[int, ...], universe_size: int) -> tuple[int, int, int]:
    union = 0
    for target in targets:
        union |= target
    collision = sum(target.bit_count() for target in targets) - union.bit_count()
    direct = sum(
        max(0, sum(bool(target & (1 << point)) for target in targets) - 1)
        for point in range(universe_size)
    )
    pairs = sum((left & right).bit_count() for left, right in combinations(targets, 2))
    return collision, direct, pairs


def audit_target_sets() -> dict:
    failures: list[dict] = []
    subsets = range(16)
    checked = 0
    for targets in product(subsets, repeat=4):
        collision, direct, pairs = target_overhead(targets, 4)
        max_multiplicity = max(
            sum(bool(target & (1 << point)) for target in targets)
            for point in range(4)
        )
        if collision != direct or direct > pairs or ((direct == pairs) != (max_multiplicity <= 2)):
            failures.append(
                {
                    "targets": targets,
                    "collision": collision,
                    "direct": direct,
                    "pairs": pairs,
                    "max_multiplicity": max_multiplicity,
                }
            )
        checked += 1
    return {"families": checked, "failures": failures}


def closed_overhead(sizes: tuple[int, ...]) -> int:
    total = prod(sizes)
    return sum((size - 1) * (total // size) for size in sizes) - (total - 1)


def direct_product_overhead(sizes: tuple[int, ...]) -> int:
    return sum(
        max(0, sum(value != 0 for value in state) - 1)
        for state in product(*(range(size) for size in sizes))
    )


def audit_disjoint_blocks() -> dict:
    failures: list[dict] = []
    vectors = 0
    states = 0
    strict_gap_vectors = 0
    equality_vectors = 0
    for arity in range(1, 6):
        for sizes in product(range(1, 6), repeat=arity):
            exact = closed_overhead(sizes)
            direct = direct_product_overhead(sizes)
            total = prod(sizes)
            clique_bound = (arity - 1) * (total - 1)
            gap = sum(total // size for size in sizes) - arity
            expected_strict = arity >= 2 and any(size > 1 for size in sizes)
            if exact != direct or clique_bound - exact != gap or ((gap > 0) != expected_strict):
                failures.append(
                    {
                        "sizes": sizes,
                        "exact": exact,
                        "direct": direct,
                        "clique_bound": clique_bound,
                        "gap": gap,
                        "expected_strict": expected_strict,
                    }
                )
            vectors += 1
            states += total - 1
            strict_gap_vectors += int(gap > 0)
            equality_vectors += int(gap == 0)
    return {
        "size_vectors": vectors,
        "noninitial_product_states": states,
        "strict_gap_vectors": strict_gap_vectors,
        "bound_equality_vectors": equality_vectors,
        "failures": failures,
    }


def hostile_controls() -> dict:
    same_letter = ((0, 0b001), (0, 0b011), (0, 0b110))
    different_overlap = ((0, 0b011), (1, 0b110))
    triple_targets = (0b1, 0b1, 0b1)
    triple_collision, triple_direct, triple_pairs = target_overhead(triple_targets, 1)
    return {
        "same_letter_overlapping_clique": clique_number(same_letter) == 3,
        "different_letters_overlapping_nonedge": clique_number(different_overlap) == 1,
        "triple_collision_pair_bound_strict": (triple_collision, triple_direct, triple_pairs)
        == (2, 2, 3),
        "single_active_block_attains_clique_bound": all(
            closed_overhead((size,)) == 0 for size in range(1, 8)
        ),
        "binary_2_by_2_overhead": closed_overhead((2, 2)) == 1,
        "ternary_2_by_2_by_2_overhead": closed_overhead((2, 2, 2)) == 5,
    }


def main() -> None:
    compatibility = audit_compatibility()
    matching = audit_three_dimensional_matching()
    target_sets = audit_target_sets()
    blocks = audit_disjoint_blocks()
    controls = hostile_controls()
    failures = (
        compatibility["failures"]
        + matching["failures"]
        + target_sets["failures"]
        + blocks["failures"]
    )
    result = {
        "status": "pass" if not failures and all(controls.values()) else "fail",
        "compatibility": compatibility,
        "three_dimensional_matching": matching,
        "target_sets": target_sets,
        "disjoint_blocks": blocks,
        "hostile_controls": controls,
        "failure_count": len(failures),
    }
    output = Path(__file__).with_name("independent-output.json")
    output.write_text(json.dumps(result, indent=2, sort_keys=True) + "\n")
    print(json.dumps(result, indent=2, sort_keys=True))


if __name__ == "__main__":
    main()