#!/usr/bin/env python3
"""Independent exhaustive certificate for regular-abelian (16,5,3) covers.

For each of the five abelian groups of order 16, enumerate all 5-set and
3-set translation orbits. Exhaust all four-orbit choices. As every 5-set
orbit has size 16, failure of four orbits plus an exhibited five-orbit
cover proves an exact invariant minimum of 80 blocks.
"""
from itertools import combinations,product
from pathlib import Path
import hashlib,json,math,time
import numpy as np
from numba import njit
TYPES=[(16,),(8,2),(4,4),(4,2,2),(2,2,2,2)];V=16;K=5;T=3
@njit
def max_four(masks):
 n=len(masks);best=-1;best_tuple=(-1,-1,-1,-1);ties=0;tested=0
 for i in range(n-3):
  mi=masks[i]
  for j in range(i+1,n-2):
   mij=mi|masks[j]
   for k in range(j+1,n-1):
    mijk=mij|masks[k]
    for l in range(k+1,n):
     tested+=1;z=mijk|masks[l];pc=0;y=z
     while y:
      y&=y-np.uint64(1);pc+=1
     if pc>best:best=pc;best_tuple=(i,j,k,l);ties=1
     elif pc==best:ties+=1
 return best,best_tuple,ties,tested

def analyse(rad,witness):
 elems=list(product(*[range(r) for r in rad]));idx={g:i for i,g in enumerate(elems)}
 def add(a,b):return tuple((x+y)%r for x,y,r in zip(a,b,rad))
 perms=[[idx[add(x,g)] for x in elems] for g in elems]
 def orbit(block):return sorted({tuple(sorted(p[x] for x in block)) for p in perms})
 def canon(block):return min(orbit(block))
 triples=list(combinations(range(V),T));tkeys=sorted({canon(q) for q in triples});ti={q:i for i,q in enumerate(tkeys)};bases=sorted({canon(b) for b in combinations(range(V),K)})
 masks=np.array([sum(1<<ti[canon(q)] for q in {z for b in orbit(base) for z in combinations(b,T)}) for base in bases],dtype=np.uint64)
 started=time.time();best,arg,ties,tested=max_four(masks);elapsed=time.time()-started
 wbases=[tuple(b) for b in witness['selected_base_blocks']];expanded=sorted({b for base in wbases for b in orbit(base)});counts={q:0 for q in triples}
 for b in expanded:
  for q in combinations(b,T):counts[q]+=1
 text='\n'.join(' '.join(map(str,b)) for b in expanded)+'\n'
 assert len(bases)==273 and len(tkeys)==35 and set(len(orbit(b)) for b in bases)=={16}
 assert tested==math.comb(273,4) and best<len(tkeys)
 assert len(expanded)==80 and min(counts.values())>=1
 return {'group_invariant_factors':list(rad),'block_orbits':len(bases),'triple_orbits':len(tkeys),'all_block_orbit_sizes':sorted(set(len(orbit(b)) for b in bases)),'four_orbit_combinations_tested':int(tested),'maximum_triple_orbits_covered_by_four':int(best),'number_of_maximizing_four_tuples':int(ties),'one_maximizing_four_tuple':[list(bases[i]) for i in arg],'no_four_orbit_cover':best<len(tkeys),'witness_base_blocks':[list(b) for b in wbases],'witness_block_count':len(expanded),'witness_uncovered_triples':sum(c==0 for c in counts.values()),'witness_coverage_histogram':{str(x):list(counts.values()).count(x) for x in sorted(set(counts.values()))},'witness_sha256':hashlib.sha256(text.encode()).hexdigest(),'enumeration_seconds':elapsed}

WITNESSES={
 (16,):[[0,1,2,13,14],[0,1,6,11,14],[0,1,7,9,13],[0,1,8,10,12],[0,2,5,9,11]],
 (8,2):[[0,1,2,13,15],[0,1,4,9,10],[0,1,6,8,14],[0,2,4,8,15],[0,2,9,12,15]],
 (4,4):[[0,1,2,14,15],[0,1,5,14,15],[0,1,7,8,12],[0,1,8,10,14],[0,1,9,11,14]],
 (4,2,2):[[0,1,2,14,15],[0,1,8,11,12],[0,2,4,13,14],[0,2,5,10,14],[0,2,5,11,13]],
 (2,2,2,2):[[0,1,2,14,15],[0,1,4,11,12],[0,1,6,9,12],[0,2,4,7,9],[0,2,4,9,10]],
}
results=[]
for rad in TYPES:
 r=analyse(rad,{'selected_base_blocks':WITNESSES[rad]});results.append(r);print(json.dumps(r),flush=True)
out={'claim':'For every abelian group G of order 16 acting regularly on itself, the minimum size of a G-translation-invariant (16,5,3) covering is 80.','method':'Exhaust all C(273,4) choices of four 5-set orbits; validate a five-orbit witness for each group.','combination_formula':str(math.comb(273,4)),'results':results}
Path('c1653-abelian-exhaustive-certificate.json').write_text(json.dumps(out,indent=2),encoding='utf-8')