"""Board tnc: exact cost of a single-amplitude contraction of a Sycamore-grid circuit network (catalog W1-2).

Instance: closed network; every bond has dimension 2 and joins exactly two tensors.
Artifact {"slices": [bond ids], "path": [[i, j], ...]} with an SSA path: inputs are ids 0..T-1, step s contracts two
live ids into the new id T+s; every id is an operand exactly once; one tensor remains.
Cost: sliced bonds are removed from every tensor. Contracting A, B costs 2^|I_A u I_B| scalar multiplications and
leaves I_A xor I_B. Total = 2^|slices| * sum over steps. Peak live elements = max over steps of
(sum of 2^|I| over live tensors before the step + 2^|I_C|), counting the inputs: the per-slice tensor-buffer
peak (the accumulator of finished slices and implementation workspace are not counted).
Score: total multiplications (min), subject to peak <= 2^cap.
"""
import math
from common import Reject, exact_keys, want_list, is_int, load_instance, popcount, short


def verify(inst, art):
    return evaluate(load_instance("tnc", inst), art)


def evaluate(I, art):
    tensors = I["tensors"]
    T = len(tensors)
    B = I["n_bonds"]
    cap = I["cap_log2"]
    # instance integrity: each bond in exactly two tensors
    seen = [0] * B
    for t in tensors:
        for e in t:
            seen[e] += 1
    if any(c != 2 for c in seen):
        raise RuntimeError("instance file is not a closed network")

    exact_keys(art, ["slices", "path"])
    slices = want_list(art["slices"], "slices", max_len=64)
    sl = 0
    for e in slices:
        if not is_int(e) or not 0 <= e < B:
            raise Reject(f"slice {short(e)} is not a bond id in [0, {B})")
        if sl >> e & 1:
            raise Reject(f"bond {e} sliced twice")
        sl |= 1 << e
    path = want_list(art["path"], "path", max_len=T - 1, min_len=T - 1)

    live = {}
    for i, t in enumerate(tensors):
        bs = 0
        for e in t:
            bs |= 1 << e
        live[i] = bs & ~sl
    size = lambda bs: 1 << popcount(bs)
    live_total = sum(size(b) for b in live.values())
    peak = live_total
    cost = 0
    for s, pr in enumerate(path):
        if not (isinstance(pr, list) and len(pr) == 2 and is_int(pr[0]) and is_int(pr[1])):
            raise Reject(f"path[{s}] must be a pair of integers")
        i, j = pr
        if i == j or i not in live or j not in live:
            raise Reject(f"path[{s}] = {short(pr)}: both ids must be distinct and live (not yet contracted, already created)")
        a, b = live.pop(i), live.pop(j)
        c = a ^ b
        cost += 1 << popcount(a | b)
        peak = max(peak, live_total + size(c))
        live_total += size(c) - size(a) - size(b)
        live[T + s] = c
    assert len(live) == 1
    (last,) = live.values()
    if last != 0:
        raise RuntimeError("closed network ended with open bonds")  # impossible for a valid instance
    mults = cost << len(slices)
    if peak > 1 << cap:
        raise Reject(f"peak live elements {peak} (2^{math.log2(peak):.6f}) exceed the cap 2^{cap} = {1 << cap}")
    return {"status": "accepted",
            "score": {"mults": mults, "log10_mults": round(math.log10(mults), 4), "peak_log2": round(math.log2(peak), 4)},
            "detail": {"tensors": T, "slices": len(slices), "steps": len(path), "per_slice_mults": cost,
                       "peak_live_elements": peak, "cap_log2": cap}}