"""Board cat-ldpc: local classical phase-flip codes on a grid (SPEC_v3 s.4). Maximize k d / n.

Artifact {"n": n, "H": [[i, ...], ...], "xy": [[x, y], ...], "order": [v, ...]}. The code is ker H over GF(2): its
codewords are the phase-flip patterns that every check (row of H) sees an even number of times.
Validity: 1 <= n <= n_max; H has at most rows_factor_max * n distinct rows, each a strictly increasing list of 2..4
data indices (linear dependencies allowed); every data index lies in at most column_degree_max rows; xy gives n
distinct integer points of the open grid_width x grid_height grid, and every row fits in a 3 x 3 box
(max x - min x <= local_span and max y - min y <= local_span); order is a permutation of the n data indices whose
frontier (the largest number of rows r with first(r) <= i <= last(r), first/last = extreme positions of r's indices
in order) is at most frontier_max; k = n - rank H >= 1; and the exact minimum distance d >= d_min.
Score: efficiency k d / n as an exact fraction (max), then n (min), then the maximum column degree (min).

Exact method for d (no sampling, no search certificate from the submitter): a dynamic program over the submitted
order. After the first i variables, a state is the parity vector of the rows that are open at position i (one slot
bit per open row; at most frontier_max of them), for partial assignments with at least one 1; its value is the least
weight of such a partial assignment. The partial assignments that are all zero form the single state 0 of cost 0,
so they are kept implicitly (the spec's "nonzero flag"). Variable i branches on 0 (state unchanged) or 1 (state XOR
the slot mask of its rows, cost + 1, and from the all-zero prefix: state = mask, cost 1). A row that closes at
position i must have even parity, so states with its bit set are discarded, and its slot is reused later. Merging
equal states by minimum cost is exact because what follows depends only on the open parities. At the end every row
is closed, and the value of the empty parity vector is d. The table has 2^w entries (w = actual frontier, at most
frontier_max: 20 on the ranked instances after review amendment C2), so the program costs n 2^w integer updates
(0.5 s CPU at n = 256, w = 20). For the witness it stores one bit per state and step, "did the value 1 give the
minimum" (n 2^w / 8 bytes, 32 MiB at the cap), rebuilds a minimum-weight codeword backwards and checks it directly
(H x = 0, |x| = d) before anything is reported; any mismatch is an internal error (status error), never an accept.
"""
import os
import time
from fractions import Fraction

import numpy as np

from common import Reject, exact_keys, want_int, want_list, is_int, load_instance, rank, short

class Budget(Exception):
    pass


def parse(art, I):
    """Validate the artifact against instance I. Returns (n, rows as index tuples, xy, order, degrees)."""
    exact_keys(art, ["n", "H", "xy", "order"])
    n = want_int(art["n"], 1, I["n_max"], f"n (instance {I['instance']} allows 1 <= n <= {I['n_max']})")
    W, Hh, span = I["grid_width"], I["grid_height"], I["local_span"]
    wmax, degmax = I["row_weight_max"], I["column_degree_max"]

    xy = want_list(art["xy"], "xy", max_len=n, min_len=n)
    pts, seen = [], {}
    for v, p in enumerate(xy):
        if not isinstance(p, list) or len(p) != 2 or not all(is_int(c) for c in p):
            raise Reject(f"xy[{v}] must be a pair [x, y] of integers, got {short(p)}")
        x, y = p
        if not (0 <= x < W and 0 <= y < Hh):
            raise Reject(f"xy[{v}] = {short(p)} lies outside the {W} x {Hh} grid (0 <= x < {W}, 0 <= y < {Hh})")
        if (x, y) in seen:
            raise Reject(f"xy[{v}] = {short(p)} repeats the position of data index {seen[(x, y)]}")
        seen[(x, y)] = v
        pts.append((x, y))

    Hl = want_list(art["H"], "H", max_len=I["rows_factor_max"] * n)
    rows, have = [], {}
    deg = [0] * n
    for i, r in enumerate(Hl):
        if not isinstance(r, list) or not 2 <= len(r) <= wmax:
            raise Reject(f"H[{i}] must be a list of 2 to {wmax} data indices, got {short(r)}")
        prev = -1
        for q in r:
            if not is_int(q) or not 0 <= q < n:
                raise Reject(f"H[{i}] contains {short(q)}, not a data index in [0, {n})")
            if q <= prev:
                raise Reject(f"H[{i}] = {short(r)} must be strictly increasing (no repeated index)")
            prev = q
        t = tuple(r)
        if t in have:
            raise Reject(f"H[{i}] repeats H[{have[t]}]")
        have[t] = i
        xs = [pts[q][0] for q in t]
        ys = [pts[q][1] for q in t]
        if max(xs) - min(xs) > span or max(ys) - min(ys) > span:
            raise Reject(f"H[{i}] = {short(r)} is not local: its positions {short([list(pts[q]) for q in t])} span "
                         f"{max(xs) - min(xs)} in x and {max(ys) - min(ys)} in y (each must be <= {span})")
        for q in t:
            deg[q] += 1
            if deg[q] > degmax:
                raise Reject(f"data index {q} lies in more than {degmax} rows (H[{i}] is its row number {deg[q]})")
        rows.append(t)

    order = want_list(art["order"], "order", max_len=n, min_len=n)
    pos = [-1] * n
    for i, v in enumerate(order):
        if not is_int(v) or not 0 <= v < n:
            raise Reject(f"order[{i}] = {short(v)} is not a data index in [0, {n})")
        if pos[v] >= 0:
            raise Reject(f"order is not a permutation: data index {v} appears at positions {pos[v]} and {i}")
        pos[v] = i
    return n, rows, pts, order, pos, deg


def frontier(n, rows, pos):
    """Per row (first, last) positions; the frontier profile; its maximum and where it is reached."""
    fl = [(min(pos[q] for q in r), max(pos[q] for q in r)) for r in rows]
    delta = [0] * (n + 1)
    for a, b in fl:
        delta[a] += 1
        delta[b + 1] -= 1
    prof, c = [], 0
    for i in range(n):
        c += delta[i]
        prof.append(c)
    w = max(prof) if prof else 0
    return fl, prof, w, (prof.index(w) if prof else 0)


def min_weight(n, rows, order, fl, w, deadline):
    """Exact minimum weight of a nonzero x with H x = 0, by the frontier dynamic program over `order`.
    Returns (d, x) with x a sorted list of indices of a minimum-weight codeword, or (None, None) if ker H = {0}."""
    S = n + 1                                   # sentinel: no partial assignment reaches the state
    B = max(w, 1)                               # slot bits; one unused slot when no row is ever open (1-D table)
    shape = (2,) * B
    starts = [[] for _ in range(n)]
    ends = [[] for _ in range(n)]
    for j, (a, b) in enumerate(fl):
        starts[a].append(j)
        ends[b].append(j)
    rows_of = [[] for _ in range(n)]
    for j, r in enumerate(rows):
        for q in r:
            rows_of[q].append(j)

    cost = np.full(1 << B, S, dtype=np.int16)   # nonzero partial assignments; index = parity bits of the slots
    took1 = np.empty((n, max((1 << B) // 8, 1)), dtype=np.uint8)   # per step: did the value 1 give the minimum?
    masks = [0] * n
    free = list(range(B - 1, -1, -1))           # stack, lowest free slot on top
    slot = {}
    for i in range(n):
        if time.process_time() > deadline:
            raise Budget
        for j in starts[i]:
            slot[j] = free.pop()
        sl = [slot[j] for j in rows_of[order[i]]]
        m = 0
        for s in sl:
            m |= 1 << s
        masks[i] = m
        # flipping axis B-1-s of the C-ordered (2,)*B view maps index t to t XOR (1 << s)
        cand = np.flip(cost.reshape(shape), axis=tuple(B - 1 - s for s in sl)).reshape(-1) + np.int16(1)
        if cand[m] > 1:
            cand[m] = 1                         # the first 1 of the assignment, after an all-zero prefix
        better = cand < cost
        np.copyto(cost, cand, where=better)
        took1[i] = np.packbits(better)
        for j in ends[i]:
            s = slot.pop(j)
            idx = [slice(None)] * B
            idx[B - 1 - s] = 1
            cost.reshape(shape)[tuple(idx)] = S  # the closing row must have even parity
            free.append(s)
            free.sort(reverse=True)
    if slot:
        raise RuntimeError("frontier bookkeeping mismatch: a row was never closed")
    d = int(cost[0])
    if d >= S:
        return None, None
    # rebuild one minimum-weight codeword backwards from the stored choices
    x, t, c = [], 0, d
    for i in range(n - 1, -1, -1):
        if not took1[i][t >> 3] >> (7 - (t & 7)) & 1:
            continue                            # x_v = 0, same state and cost one step earlier
        x.append(order[i])
        if c == 1:                              # the first 1: every earlier variable is 0
            if t != masks[i]:
                raise RuntimeError(f"witness reconstruction failed at position {i}")
            t, c = 0, 0
            break
        t ^= masks[i]
        c -= 1
    if c != 0 or t != 0:
        raise RuntimeError("witness reconstruction did not reach the empty assignment")
    return d, sorted(x)


def verify(inst, art, time_budget=None):
    return check(load_instance("catldpc", inst), art, time_budget)


def check(I, art, time_budget=None):
    """verify() on an instance given as a loaded dict (tests pass small ad hoc instances this way)."""
    t0 = time.process_time()
    budget = time_budget if time_budget is not None else float(os.environ.get("QARENA_CPU", I["cpu_seconds"])) - 20
    deadline = t0 + budget
    n, rows, pts, order, pos, deg = parse(art, I)
    maxdeg = max(deg)
    fl, prof, w, at = frontier(n, rows, pos)
    if w > I["frontier_max"]:
        raise Reject(f"frontier {w} > frontier_max = {I['frontier_max']}: {w} rows are open at order position {at} "
                     f"(data index {order[at]}); reorder the data or use fewer long-range rows in the order")
    bits = [sum(1 << q for q in r) for r in rows]
    rk = rank(bits)
    k = n - rk
    if k < 1:
        raise Reject(f"k = n - rank H = {n} - {rk} = 0: the code has no nonzero codeword")
    try:
        d, x = min_weight(n, rows, order, fl, w, deadline)
    except Budget:
        return {"status": "error", "detail": {"reason": "distance computation did not finish within the time limit "
                                                        "(not ranked)", "n": n, "k": k, "frontier": w}}
    xs = set(x or ())
    if d is None or len(xs) != d or any(sum(q in xs for q in r) % 2 for r in rows):
        raise RuntimeError("minimum-weight codeword failed its direct check")
    if d < I["d_min"]:
        raise Reject(f"distance d = {d} is below the floor d_min = {I['d_min']}: the nonzero codeword with ones at "
                     f"data indices {short(x, 400)} satisfies every row")
    eff = Fraction(k * d, n)
    sc = {"num": format(eff.numerator, "x"), "den": format(eff.denominator, "x")}
    return {"status": "accepted",
            "score": {"efficiency": sc, "n": n, "maxdeg": maxdeg, "k": k, "d": d},
            "detail": {"n": n, "k": k, "d": d, "rank_H": rk, "rows": len(rows), "max_column_degree": maxdeg,
                       "max_row_weight": max((len(r) for r in rows), default=0), "frontier": w,
                       "frontier_max": I["frontier_max"], "dp_states": 1 << max(w, 1),
                       "efficiency_decimal": f"{float(eff):.6f}",
                       "min_weight_codeword": x,
                       "check": f"exact minimum distance {d} by a frontier dynamic program over all 2^{k} - 1 nonzero "
                                f"codewords; the codeword shown has weight {d} and satisfies every row",
                       "verify_cpu_seconds": round(time.process_time() - t0, 3)}}