#!/usr/bin/env python3
"""Replay the exact B3 finite-quotient Hurwitz obstruction.

This verifier checks the displayed witness. It does not search for examples or
decide Hurwitz equivalence in B3.
"""

from collections import deque
import json

I = (1, 0, 0, 1)
X = (1, 1, 0, 1)
Y = (1, 0, -1, 1)


def mm(a, b):
    return (
        a[0] * b[0] + a[1] * b[2],
        a[0] * b[1] + a[1] * b[3],
        a[2] * b[0] + a[3] * b[2],
        a[2] * b[1] + a[3] * b[3],
    )


def inverse(a):
    return (a[3], -a[1], -a[2], a[0])


def power(a, n):
    if n < 0:
        return power(inverse(a), -n)
    result = I
    while n:
        if n & 1:
            result = mm(result, a)
        a = mm(a, a)
        n //= 2
    return result


def conjugate(g, a):
    return mm(mm(g, a), inverse(g))


def product(items):
    result = I
    for item in items:
        result = mm(result, item)
    return result


def mod2(a):
    return tuple(entry % 2 for entry in a)


def generated_subgroup(generators):
    generators = [mod2(g) for g in generators]
    seen = {I}
    queue = deque([I])
    while queue:
        current = queue.popleft()
        for generator in generators:
            nxt = mod2(mm(current, generator))
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return seen


def hurwitz(items, index):
    items = list(items)
    a, b = items[index], items[index + 1]
    items[index : index + 2] = [b, mm(mm(inverse(b), a), b)]
    return tuple(items)


def inverse_hurwitz(items, index):
    items = list(items)
    a, b = items[index], items[index + 1]
    items[index : index + 2] = [mm(mm(a, b), inverse(a)), a]
    return tuple(items)


def finite_orbit(items):
    start = tuple(mod2(g) for g in items)
    seen = {start}
    queue = deque([start])
    while queue:
        current = queue.popleft()
        for index in range(len(current) - 1):
            for nxt in (hurwitz(current, index), inverse_hurwitz(current, index)):
                nxt = tuple(mod2(g) for g in nxt)
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
    return seen


def main():
    alpha = conjugate(power(X, 2), Y)
    beta = conjugate(mm(inverse(Y), X), Y)
    a = (alpha, Y, Y)
    b = (X, beta, Y)

    assert product(a) == product(b)
    subgroup_a = generated_subgroup(a)
    subgroup_b = generated_subgroup(b)
    assert (len(subgroup_a), len(subgroup_b)) == (2, 6)

    orbit_a = finite_orbit(a)
    orbit_b = finite_orbit(b)
    assert (len(orbit_a), len(orbit_b)) == (1, 8)
    assert orbit_a.isdisjoint(orbit_b)

    print(json.dumps({
        "result": "pass",
        "common_product_matrix": list(product(a)),
        "permutation_subgroup_orders": {"A": 2, "B": 6},
        "finite_hurwitz_orbit_sizes": {"A": 1, "B": 8},
        "finite_orbits_disjoint": True,
    }, indent=2, sort_keys=True))


if __name__ == "__main__":
    main()