#!/usr/bin/env python3
"""T^GPT v0.8.2 hostile non-T semantic coverage baseline.

<=20 candidates: exact enumeration under token budget.
>20 candidates: deterministic multi-start greedy + 1-swap local search.
"""
from __future__ import annotations
import argparse, json
from pathlib import Path
from typing import Dict, List, Tuple

EPS = 1e-12


def validate(data: dict):
    budget = int(data["token_budget"])
    if budget <= 0:
        raise ValueError("token_budget must be >0")
    clusters = data["clusters"]; candidates = data["candidates"]
    ids = [str(x["id"]) for x in clusters]
    if len(ids) != len(set(ids)) or not ids:
        raise ValueError("cluster ids must be unique/nonempty")
    weights = {str(x["id"]): float(x.get("weight", 1.0)) for x in clusters}
    if any(v < 0 for v in weights.values()) or sum(weights.values()) <= 0:
        raise ValueError("weights must be nonnegative with positive total")
    cids, out = [], []
    for raw in candidates:
        cid = str(raw["id"]); cids.append(cid); cost = int(raw["token_cost"])
        if cost <= 0:
            raise ValueError(f"{cid}: token_cost must be >0")
        covers = {}
        for k, v in raw.get("covers", {}).items():
            k = str(k)
            if k not in weights:
                raise ValueError(f"{cid}: unknown cluster {k}")
            fv = float(v)
            if not 0 <= fv <= 1:
                raise ValueError(f"{cid}/{k}: coverage must be in [0,1]")
            covers[k] = fv
        out.append({**raw, "id": cid, "token_cost": cost, "covers": covers})
    if len(cids) != len(set(cids)):
        raise ValueError("candidate ids must be unique")
    return budget, weights, out


def objective(selected: List[dict], weights: Dict[str, float]) -> Tuple[float, Dict[str, float]]:
    best = {c: 0.0 for c in weights}
    for item in selected:
        for c, s in item["covers"].items():
            best[c] = max(best[c], s)
    return sum(weights[c] * best[c] for c in weights), best


def greedy(candidates, weights, budget, mode):
    sel, spent = [], 0; remaining = {x["id"]: x for x in candidates}; cur, _ = objective(sel, weights)
    while True:
        feas = [x for x in remaining.values() if spent + x["token_cost"] <= budget]
        if not feas:
            break
        scored = []
        for x in feas:
            nv, _ = objective(sel + [x], weights); gain = nv - cur
            score = gain / x["token_cost"] if mode == "density" else gain
            scored.append((score, gain, -x["token_cost"], x["id"], x, nv))
        scored.sort(key=lambda t: (-t[0], -t[1], -t[2], t[3]))
        _, gain, _, _, x, nv = scored[0]
        if gain <= EPS:
            break
        sel.append(x); spent += x["token_cost"]; remaining.pop(x["id"]); cur = nv
    return sel


def one_swap(sel, candidates, weights, budget):
    chosen = {x["id"] for x in sel}; cur, _ = objective(sel, weights); spent = sum(x["token_cost"] for x in sel)
    improved = True
    while improved:
        improved = False; best = None; outside = [x for x in candidates if x["id"] not in chosen]
        for out in sorted(sel, key=lambda x: x["id"]):
            base = [x for x in sel if x["id"] != out["id"]]; basecost = spent - out["token_cost"]
            for inn in sorted(outside, key=lambda x: x["id"]):
                if basecost + inn["token_cost"] > budget:
                    continue
                nv, _ = objective(base + [inn], weights)
                if nv > cur + EPS and (best is None or nv > best[0] + EPS or (abs(nv - best[0]) <= EPS and (out["id"], inn["id"]) < (best[1]["id"], best[2]["id"]))):
                    best = (nv, out, inn, base)
        if best:
            cur, _, inn, base = best; sel = base + [inn]; chosen = {x["id"] for x in sel}; spent = sum(x["token_cost"] for x in sel); improved = True
    return sel


def exact(candidates, weights, budget):
    best_val, best_ids, best_sel = -1.0, None, []; n = len(candidates)
    def rec(i, sel, spent):
        nonlocal best_val, best_ids, best_sel
        if spent > budget:
            return
        if i == n:
            val, _ = objective(sel, weights); ids = tuple(sorted(x["id"] for x in sel))
            if val > best_val + EPS or (abs(val - best_val) <= EPS and (best_ids is None or ids < best_ids)):
                best_val, best_ids, best_sel = val, ids, list(sel)
            return
        rec(i + 1, sel, spent)
        x = candidates[i]
        if spent + x["token_cost"] <= budget:
            rec(i + 1, sel + [x], spent + x["token_cost"])
    rec(0, [], 0)
    return best_sel


def solve(data: dict) -> dict:
    budget, weights, candidates = validate(data)
    if len(candidates) <= 20:
        sel = exact(candidates, weights, budget); algo = "exact_enumeration_n_le_20"
    else:
        candidates = sorted(candidates, key=lambda x: x["id"])
        starts = [greedy(candidates, weights, budget, "density"), greedy(candidates, weights, budget, "gain")]
        starts += [[x] for x in candidates if x["token_cost"] <= budget]
        refined = [one_swap(s, candidates, weights, budget) for s in starts]
        scored = []
        for s in refined:
            val, _ = objective(s, weights); ids = tuple(sorted(x["id"] for x in s)); scored.append((val, ids, s))
        scored.sort(key=lambda t: (-t[0], t[1])); sel = scored[0][2]; algo = "multistart_greedy_plus_1swap"
    val, cov = objective(sel, weights); total = sum(weights.values()); spent = sum(x["token_cost"] for x in sel)
    return {"schema":"T_GPT_COVERAGE_BASELINE_RESULT_V0_8_2","algorithm":algo,"token_budget":budget,"tokens_spent":spent,"selected_ids":sorted(x["id"] for x in sel),"objective_weighted":val,"objective_normalized":val/total,"cluster_coverage":cov,"note":"Hostile non-T baseline. Exact for <=20 candidates; deterministic heuristic otherwise."}


def main():
    ap = argparse.ArgumentParser(); ap.add_argument("input", type=Path); ap.add_argument("-o", "--output", type=Path)
    a = ap.parse_args(); out = solve(json.loads(a.input.read_text(encoding="utf-8"))); payload = json.dumps(out, ensure_ascii=False, indent=2) + "\n"
    a.output.write_text(payload, encoding="utf-8") if a.output else print(payload, end="")


if __name__ == "__main__":
    main()