"""Board andcount: bilinear rank of GF(2^m) multiplication (catalog W1-1 board c).

Artifact {"m": m, "U": [r bit strings of length m], "V": [r bit strings of length m], "W": [m bit strings of length r]}.
Valid iff for all i, j, l: sum_k U[k][i] V[k][j] W[l][k] = T_ijl (mod 2), T = multiplication tensor of the frozen modulus.
Score r (min), tie-break naive XOR count (min).
"""
from common import Reject, exact_keys, want_int, want_list, bitstring, popcount, load_instance
import gf2m


def verify(inst, art):
    I = load_instance("andcount", inst)
    m = I["m"]
    exact_keys(art, ["m", "U", "V", "W"])
    want_int(art["m"], m, m, "m")
    U = want_list(art["U"], "U", max_len=m * m, min_len=1)
    r = len(U)
    V = want_list(art["V"], "V", max_len=r, min_len=r)
    W = want_list(art["W"], "W", max_len=m, min_len=m)
    U = [bitstring(s, m, f"U[{k}]") for k, s in enumerate(U)]
    V = [bitstring(s, m, f"V[{k}]") for k, s in enumerate(V)]
    W = [bitstring(s, r, f"W[{l}]") for l, s in enumerate(W)]

    T = gf2m.tensor(m)
    if sorted(map(list, T)) != sorted(I["T"]):
        raise RuntimeError("instance file disagrees with the recomputed tensor")
    # Wk[k] = bitset over l of W[l][k]
    Wk = [0] * r
    for l in range(m):
        for k in range(r):
            if W[l] >> k & 1:
                Wk[k] |= 1 << l
    bad = 0
    first = None
    for i in range(m):
        for j in range(m):
            acc = 0
            for k in range(r):
                if (U[k] >> i & 1) and (V[k] >> j & 1):
                    acc ^= Wk[k]
            want = sum(1 << l for l in range(m) if (i, j, l) in T)
            if acc != want:
                bad += 1
                if first is None:
                    first = (i, j, acc ^ want)
    if bad:
        i, j, diff = first
        raise Reject(f"not a multiplication algorithm: {bad} of {m * m} products x^{i}*x^{j} are wrong "
                     f"(first: i={i}, j={j}, wrong output bits {[l for l in range(m) if diff >> l & 1]})")
    xor = sum(popcount(x) - 1 for x in U + V + W if x)
    return {"status": "accepted", "score": {"r": r, "xor": xor},
            "detail": {"m": m, "r": r, "xor": xor, "check": f"all {m * m * m} tensor entries match"}}