# coverage_check_unionfind.py
# Author: David Niedbala Giraudin, ORCID 0009-0009-1526-1178
# Technical assistance: Claude (Anthropic)
#
# Coverage check of the cubes, second method (no canonical forms): union-find.  A pattern of G_1 is (M, miss): M a matching on the five
# positions 0..4 (inner edges of G_1), miss a map from matched positions to an empty cross slot in
# {3,...,8} (absent = no empty slot); unmatched positions have their own slot empty.  The group
# acting is S_5 (positions) x W, W = the 48 permutations of {3,...,8} preserving {3,4},{5,6},{7,8}.
# Orbits are computed by union-find using generators of S_5 and of W only.  Checked for the
# cubes of Program A (cubesA.json, also: Case labels, m-order and canonical inner edges) and for
# the representatives of Program B (reps39.json).  Pure Python, no arguments, a few seconds.
import itertools, json, os
os.chdir(os.path.dirname(os.path.abspath(__file__)))
POS = range(5)
def all_matchings():
    edges = list(itertools.combinations(POS, 2))
    out = [frozenset()]
    out += [frozenset([e]) for e in edges]
    out += [frozenset([e, f]) for e, f in itertools.combinations(edges, 2) if not set(e) & set(f)]
    return out
def patterns():
    for M in all_matchings():
        matched = sorted(p for e in M for p in e)
        for ch in itertools.product([None, 3, 4, 5, 6, 7, 8], repeat=len(matched)):
            yield (M, frozenset((p, c) for p, c in zip(matched, ch) if c is not None))
PAT = list(patterns())
index = {p: i for i, p in enumerate(PAT)}
parent = list(range(len(PAT)))
def find(i):
    while parent[i] != i:
        parent[i] = parent[parent[i]]; i = parent[i]
    return i
def union(i, j):
    a, b = find(i), find(j)
    if a != b: parent[a] = b
def act_pos(pi, pat):
    M, miss = pat
    return (frozenset(tuple(sorted((pi[a], pi[b]))) for a, b in M), frozenset((pi[p], c) for p, c in miss))
def act_lab(w, pat):
    M, miss = pat
    return (M, frozenset((p, w[c]) for p, c in miss))
gens_pos = [(1, 0, 2, 3, 4), (1, 2, 3, 4, 0)]                     # S_5
gens_lab = [{3: 4, 4: 3, 5: 5, 6: 6, 7: 7, 8: 8},                 # swap inside a pair
            {3: 5, 4: 6, 5: 3, 6: 4, 7: 7, 8: 8},                 # exchange pairs 1,2
            {3: 5, 4: 6, 5: 7, 6: 8, 7: 3, 8: 4}]                 # cycle the pairs
for i, p in enumerate(PAT):
    for g in gens_pos: union(i, index[act_pos(g, p)])
    for g in gens_lab: union(i, index[act_lab(g, p)])
orbits = {}
for i in range(len(PAT)): orbits.setdefault(find(i), []).append(i)
def is_case1(pat):
    M, miss = pat
    matched = {p for e in M for p in e}
    return any(p not in dict(miss) for p in matched)
n1 = sum(1 for o in orbits.values() if is_case1(PAT[o[0]]))
print('patterns', len(PAT), 'orbits', len(orbits), 'case I orbits', n1, 'case II orbits', len(orbits) - n1, flush=True)
# case labels must be orbit invariants
assert all(len({is_case1(PAT[i]) for i in o}) == 1 for o in orbits.values())
def m_order_ok(miss):
    m = {w: 5 - sum(1 for c in miss.values() if c == w) for w in range(3, 9)}
    return m[3] >= m[4] and m[5] >= m[6] and m[7] >= m[8] and m[3] >= m[5] >= m[7]
def check(fname, program_a):
    data = json.load(open(fname))
    hit = {}
    for k, c in enumerate(data):
        M = frozenset(tuple(sorted(e)) for e in c['own'])
        miss = frozenset((int(a), b) for a, b in c['miss'].items())
        pat = (M, miss)
        assert pat in index, ('not a valid pattern', fname, k)
        if program_a:
            assert (c['case'] == 'I') == is_case1(pat), ('wrong case label', k)
            assert [tuple(e) for e in c['own']] in ([], [(0, 1)], [(0, 1), (2, 3)]), ('inner edges not canonical', k)
            assert m_order_ok({int(a): b for a, b in c['miss'].items()}), ('m-order violated', k)
        hit.setdefault(find(index[pat]), []).append(k)
    twice = sum(1 for v in hit.values() if len(v) > 1)
    print('%s: %d cubes, orbits hit %d, hit twice %d, missed %d' % (fname, len(data), len(hit), twice, len(orbits) - len(hit)), flush=True)
    return len(hit) == len(orbits) == len(data)
ok1 = check('cubesA.json', True)
ok2 = check('reps39.json', False)
print('RESULT:', 'every orbit is covered exactly once by both lists' if ok1 and ok2 else 'FAILED', flush=True)