"""Board tcount: T count of the GF(2^m) multiplication phase in the CNOT+T (phase polynomial) model, no ancillas
(catalog W1-1 board a). An accepted artifact is an explicit circuit, so r is an upper bound on the ancilla-free
Clifford+T count; it is not claimed that circuits with internal Hadamards cannot do better.

Target: D_m|a,b,c> = (-1)^{sum T_ijl a_i b_j c_l}|a,b,c>, n = 3m qubits ordered a_0..a_{m-1}, b_0.., c_0..
Artifact {"n": n, "columns": [r bit strings of length n]}: column y_j is the parity carrying the j-th T gate.
Valid iff the full symmetric signature tensor S(A)[x,y,z] = sum_j A[x,j] A[y,j] A[z,j] mod 2 equals S*
for ALL index triples, repeated indices included (S* = 1 exactly on permutations of (a_i, b_j, c_l) with T_ijl = 1).
That is the condition for the CNOT+T circuit to equal D_m up to a Clifford diagonal (S, CZ, Z), see the board page.
Duplicate columns are allowed (two T gates on one parity make an S gate): they only raise r.
Score r (min).
"""
import numpy as np
from common import Reject, exact_keys, want_int, want_list, load_instance
import gf2m


def verify(inst, art):
    I = load_instance("tcount", inst)
    m = I["m"]
    n = 3 * m
    exact_keys(art, ["n", "columns"])
    want_int(art["n"], n, n, "n")
    cols = want_list(art["columns"], "columns", max_len=8 * m * m, min_len=1)
    r = len(cols)
    A = np.zeros((n, r), dtype=np.float64)
    for j, s in enumerate(cols):
        if not isinstance(s, str) or len(s) != n or s.strip("01") != "":
            raise Reject(f"columns[{j}] must be a string of exactly {n} characters '0'/'1'")
        if "1" not in s:
            raise Reject(f"columns[{j}] is the zero parity (a T gate on it is only a global phase)")
        A[:, j] = [1.0 if ch == "1" else 0.0 for ch in s]

    T = gf2m.tensor(m)
    if sorted(map(list, T)) != sorted(I["T"]):
        raise RuntimeError("instance file disagrees with the recomputed tensor")
    target = np.zeros((n, n, n), dtype=np.int64)
    for (i, j, l) in T:
        a, b, c = i, m + j, 2 * m + l
        for x, y, z in ((a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)):
            target[x, y, z] = 1

    # S[x] = (A * A[x]) @ A.T, exact in float64 since every entry is an integer <= r < 2^53.
    S = np.empty((n, n, n), dtype=np.int64)
    for x in range(n):
        S[x] = np.rint((A * A[x]) @ A.T).astype(np.int64) & 1
    diff = np.argwhere(S != target)
    if len(diff):
        names = [f"a{i}" for i in range(m)] + [f"b{i}" for i in range(m)] + [f"c{i}" for i in range(m)]
        ex = [tuple(names[t] for t in d) for d in diff[:5]]
        raise Reject(f"signature tensor mismatch at {len(diff)} of {n ** 3} entries, e.g. {ex}")
    return {"status": "accepted", "score": {"r": r},
            "detail": {"m": m, "n": n, "r": r, "check": f"all {n ** 3} signature-tensor entries match"}}