"""Millennium Lab round 4, P vs NP hunt: the full fragment with defeaters.

Reads NeuruhAI/lead-recipe-os read-only (vendored clone at
../vendor/lead-recipe-os, HEAD 7363dcb1, fetched 2026-11-20) and runs the
real registry loader and the real evaluator. No ledger writes, no
deploys, no receipt scripts.

Part 1: phase transition in the FULL fragment (defeaters included).
Round 1 measured random ALL recipes of r required plain leaves against
timelines where each chosen signal is PRESENT independently with
probability p, and the SATISFIED fraction tracked p^r. Here the same
method is run with defeater clauses in the composition pool, in four
clause mixes (plain only, defeater only, 50/50 mixed, 25 percent
defeater), plus a second experiment where non-present signals are
evidentially ABSENT half the time so that NOT(plain) and ABSENT-op
clauses become live. A third experiment measures existence directly:
random evidence subsets over all 317 signals at density p, and the
question is whether any SATISFIED composed recipe exists at all
(decided by an interleaved per-signal greedy scan with early exit).

Part 2 support: the greedy proof sketch for DF-COMP lives in
data/p_vs_np_greedy_proof_r4.md; its theorem and evidence are
summarized in the JSON output of this script.

Run: cd ~/workspace/millennium-lab && \
  ~/workspace/sovereign-runtime/.venv/bin/python compute/p_vs_np_r4.py
Writes data/p_vs_np_r4.json next to this file's parent data dir.
"""
import json
import random
import sys
import time
from datetime import date
from pathlib import Path

HERE = Path(__file__).resolve().parent
LAB = HERE.parent
VENDOR = LAB / "vendor" / "lead-recipe-os"
sys.path.insert(0, str(VENDOR))
sys.path.insert(0, str(HERE))

from lead_recipe_os.registry.contracts import (  # noqa: E402
    ABSENT, ALL, NOT, leaf,
)
from lead_recipe_os.registry.store import load_default  # noqa: E402
from lead_recipe_os.signals.graph import evaluate_logic  # noqa: E402
from lead_recipe_os.signals.model import (  # noqa: E402
    SignalInstance, SignalTimeline, absent, observed,
)
from p_vs_np_r2 import candidate_nodes  # noqa: E402  (round 2 pool builder)

AS_OF = date(2026, 11, 20)
SUBJECT = "parcel:test:001"
P_GRID = [0.0, 0.1, 0.25, 0.5, 0.75, 0.9, 1.0]
R_GRID = [1, 2, 3, 5, 8]
TRIALS = 200


def tl(instances):
    return SignalTimeline(SUBJECT, instances)


def present(sid, **kw):
    return observed(sid, SUBJECT, **kw)


def ev_absent(sid, **kw):
    return absent(sid, SUBJECT, **kw)


def conflicted(sid):
    return SignalInstance(signal_id=sid, subject=SUBJECT, kind="FACT",
                          state="CONFLICTED", source_id="fixture",
                          confidence="HIGH", basis="VERIFIED")


# ---------------------------------------------------------------------------
# clause forms
# ---------------------------------------------------------------------------

def plain_leaf(sid):
    return leaf(sid, state="PRESENT")


def defeater_node(sid):
    return NOT(leaf(sid, state="PRESENT", defeater=True))


def not_plain_node(sid):
    return NOT(leaf(sid, state="PRESENT"))


def absent_op_node(sid):
    return ABSENT(sid)


def build_recipe(clause_kinds, sids):
    """ALL over one node per (kind, signal) pair."""
    nodes = []
    for kind, sid in zip(clause_kinds, sids):
        if kind == "plain":
            nodes.append(plain_leaf(sid))
        elif kind == "defeater":
            nodes.append(defeater_node(sid))
        elif kind == "not_plain":
            nodes.append(not_plain_node(sid))
        elif kind == "absent_op":
            nodes.append(absent_op_node(sid))
        else:
            raise ValueError(kind)
    return ALL(*nodes)


def eval_tree(tree, timeline):
    return evaluate_logic(tree, timeline, AS_OF).outcome


# ---------------------------------------------------------------------------
# experiment A: random composed recipes, round 1 method, full fragment
# ---------------------------------------------------------------------------

def run_experiment_a(signals, rng):
    """Four clause mixes. Timeline per trial: each chosen signal PRESENT
    with probability p, otherwise absent from the timeline (unresolved).
    Predicted per-clause SAT probability q: plain p, defeater 1-p,
    mixed50 0.5, mixed25 0.25 + 0.5p. Predicted match fraction q^r."""
    mixes = {
        "plain": {"plain": 1.0},
        "defeater": {"defeater": 1.0},
        "mixed50": {"plain": 0.5, "defeater": 0.5},
        "mixed25": {"plain": 0.75, "defeater": 0.25},
    }

    def q_pred(mix, p):
        return sum(w * (p if k == "plain" else (1.0 - p))
                   for k, w in mixes[mix].items())

    def draw_kind(mix):
        roll = rng.random()
        acc = 0.0
        for kind, w in mixes[mix].items():
            acc += w
            if roll < acc:
                return kind
        return list(mixes[mix])[-1]

    cells = {}
    for mix in mixes:
        cells[mix] = {}
        for p in P_GRID:
            cells[mix][str(p)] = {}
            for r in R_GRID:
                sat = 0
                for _ in range(TRIALS):
                    sids = rng.sample(signals, r)
                    kinds = [draw_kind(mix) for _ in range(r)]
                    insts = [present(s) for s in sids if rng.random() < p]
                    if eval_tree(build_recipe(kinds, sids), tl(insts)) == "SATISFIED":
                        sat += 1
                pred = q_pred(mix, p) ** r
                meas = sat / TRIALS
                cells[mix][str(p)][str(r)] = {
                    "measured": round(meas, 3),
                    "predicted": round(pred, 4),
                    "diff": round(meas - pred, 3),
                    "satisfied_trials": sat,
                    "trials": TRIALS,
                }
        print(f"experiment A mix {mix} done", flush=True)
    return {"mixes": {m: dict(v) for m, v in mixes.items()},
            "p_grid": P_GRID, "r_grid": R_GRID, "trials_per_cell": TRIALS,
            "cells": cells,
            "timeline": "each chosen signal PRESENT independently with "
            "probability p, otherwise absent from the timeline (unresolved)",
            "predictions": {
                "plain": "p^r",
                "defeater": "(1-p)^r",
                "mixed50": "0.5^r, independent of p",
                "mixed25": "(0.25 + 0.5p)^r",
            }}


# ---------------------------------------------------------------------------
# experiment A2: evidential absence makes NOT(plain) and ABSENT live
# ---------------------------------------------------------------------------

def run_experiment_a2(signals, rng):
    """Timeline per trial: each chosen signal PRESENT with probability p,
    evidentially ABSENT with probability 0.5*(1-p), unresolved otherwise.
    Clause types are uniform per cell (not mixed). Predicted per-clause
    SAT probability: plain p, not_plain 0.5*(1-p), absent_op 0.5*(1-p),
    defeater 1-p. Predicted match fraction q^r."""
    types = ["plain", "not_plain", "absent_op", "defeater"]

    def q_pred(kind, p):
        if kind == "plain":
            return p
        if kind in ("not_plain", "absent_op"):
            return 0.5 * (1.0 - p)
        return 1.0 - p

    cells = {}
    for kind in types:
        cells[kind] = {}
        for p in P_GRID:
            cells[kind][str(p)] = {}
            for r in (1, 3):
                sat = 0
                for _ in range(TRIALS):
                    sids = rng.sample(signals, r)
                    insts = []
                    for s in sids:
                        roll = rng.random()
                        if roll < p:
                            insts.append(present(s))
                        elif roll < p + 0.5 * (1.0 - p):
                            insts.append(ev_absent(s))
                    if eval_tree(build_recipe([kind] * r, sids),
                                 tl(insts)) == "SATISFIED":
                        sat += 1
                pred = q_pred(kind, p) ** r
                meas = sat / TRIALS
                cells[kind][str(p)][str(r)] = {
                    "measured": round(meas, 3),
                    "predicted": round(pred, 4),
                    "diff": round(meas - pred, 3),
                    "satisfied_trials": sat,
                    "trials": TRIALS,
                }
        print(f"experiment A2 type {kind} done", flush=True)
    return {"clause_types": types, "p_grid": P_GRID, "r_grid": [1, 3],
            "trials_per_cell": TRIALS, "cells": cells,
            "timeline": "each chosen signal PRESENT with probability p, "
            "evidentially ABSENT with probability 0.5*(1-p), unresolved "
            "otherwise",
            "predictions": {
                "plain": "p^r",
                "not_plain": "(0.5*(1-p))^r",
                "absent_op": "(0.5*(1-p))^r",
                "defeater": "(1-p)^r",
            }}


# ---------------------------------------------------------------------------
# experiment B: existence vs evidence density over the full vocabulary
# ---------------------------------------------------------------------------

def run_experiment_b(signals, rng):
    """200 random evidence subsets per density p over all 317 signals.
    Existence is decided by an interleaved per-signal greedy scan with
    early exit: for each signal in fixed order, test ALL(plain loose
    leaf) then ALL(NOT(defeater leaf)); the first SATISFIED node is the
    witness. Per-signal complementarity (plain SAT exactly when the
    signal is PRESENT and admissible; defeater SAT exactly when it is
    not) makes existence trivially always YES; the run measures that
    rather than assuming it."""
    rows = {}
    for p in P_GRID:
        exists = 0
        witness_kinds = {}
        nodes_checked_total = 0
        n_present_total = 0
        for _ in range(TRIALS):
            present_set = {s for s in signals if rng.random() < p}
            insts = [present(s) for s in present_set]
            timeline = tl(insts)
            found = None
            checked = 0
            for sid in signals:
                checked += 1
                if eval_tree(ALL(leaf(sid, state="PRESENT",
                                     min_confidence="UNKNOWN",
                                     min_basis="PREDICTED")),
                             timeline) == "SATISFIED":
                    found = "PL_loose"
                    break
                checked += 1
                if eval_tree(ALL(defeater_node(sid)),
                             timeline) == "SATISFIED":
                    found = "NOT_defeater"
                    break
            if found is not None:
                exists += 1
                witness_kinds[found] = witness_kinds.get(found, 0) + 1
            nodes_checked_total += checked
            n_present_total += len(present_set)
        rows[str(p)] = {
            "trials": TRIALS,
            "exists_trials": exists,
            "match_fraction": round(exists / TRIALS, 3),
            "witness_kinds": witness_kinds,
            "mean_nodes_checked": round(nodes_checked_total / TRIALS, 2),
            "mean_signals_present": round(n_present_total / TRIALS, 1),
        }
        print(f"experiment B p={p}: exists {exists}/{TRIALS} "
              f"witnesses {witness_kinds}", flush=True)
    return {"p_grid": P_GRID, "trials_per_cell": TRIALS,
            "method": "interleaved per-signal greedy scan with early exit "
            "(plain loose leaf, then NOT(defeater leaf), per signal in "
            "fixed order); first SATISFIED node is the witness",
            "rows": rows}


def full_pool_counts(timeline, signals, label):
    """Full candidate-pool satisfied counts for one fixed timeline, round
    2 pool plus one NOT(defeater) node per signal, no early exit."""
    pool = candidate_nodes(timeline, signals)
    pool += [("NOT_defeater", defeater_node(s)) for s in signals]
    by_kind = {}
    n_sat = 0
    for kind, node in pool:
        if eval_tree(ALL(node), timeline) == "SATISFIED":
            n_sat += 1
            by_kind[kind] = by_kind.get(kind, 0) + 1
    return {"timeline": label, "n_candidates": len(pool),
            "n_satisfied": n_sat, "by_kind": by_kind}


# ---------------------------------------------------------------------------
# main
# ---------------------------------------------------------------------------

def main():
    t_start = time.time()
    out = {"repo": {"slug": "NeuruhAI/lead-recipe-os",
                    "head": "7363dcb1efab4dad3e44c7408ba921b193304ff7",
                    "fetched": "2026-11-20",
                    "method": "git clone --depth 1, read-only"},
           "as_of": str(AS_OF),
           "round": 4}
    reg = load_default()
    signals = sorted(reg.signals)
    recipes = list(reg.recipes.values())
    out["registry"] = {
        "recipes": len(recipes),
        "signals": len(signals),
        "ingredients": len(reg.ingredients),
        "sources": len(reg.sources),
        "territories": len(reg.territories),
    }
    from collections import Counter
    defeater_recipes = sum(
        1 for r in recipes
        if any(n.clause is not None and n.clause.defeater
               for n in _walk(r.signal_logic)))
    out["registry"]["recipes_with_defeater_clause"] = defeater_recipes
    print(f"registry: {out['registry']}", flush=True)

    # --- defeater hinge, re-measured this round
    hinge = {}
    for label, defeater in (("defeater", True), ("plain", False)):
        node = NOT(leaf("ownership.government", defeater=defeater))
        hinge[label] = {
            "empty_timeline": eval_tree(node, tl([])),
            "present": eval_tree(node, tl([present("ownership.government")])),
            "evidential_absent": eval_tree(
                node, tl([ev_absent("ownership.government")])),
            "conflicted": eval_tree(
                node, tl([conflicted("ownership.government")])),
        }
    out["defeater_hinge"] = hinge
    print(f"hinge: {hinge}", flush=True)

    rng = random.Random(20261120)
    out["phase_transition_full"] = run_experiment_a(signals, rng)
    out["evidential_absence"] = run_experiment_a2(signals, rng)
    out["existence_vs_density"] = run_experiment_b(signals, rng)

    # --- full-pool satisfied counts on three fixed timelines
    rng_b = random.Random(20261120)
    rand_half = tl([present(s) for s in signals if rng_b.random() < 0.5])
    full = tl([present(s) for s in signals])
    out["existence_vs_density"]["full_pool_counts"] = [
        full_pool_counts(tl([]), signals, "empty"),
        full_pool_counts(full, signals, "full_evidence"),
        full_pool_counts(rand_half, signals, "random_p0.5"),
    ]
    for row in out["existence_vs_density"]["full_pool_counts"]:
        print(f"full pool {row['timeline']}: {row['n_satisfied']} of "
              f"{row['n_candidates']} satisfied, by kind {row['by_kind']}",
              flush=True)

    # --- greedy proof summary (full proof sketch in
    # data/p_vs_np_greedy_proof_r4.md)
    out["greedy_proof_summary"] = {
        "theorem": "DF-COMP-SEARCH, the existence of a composer-valid "
        "defeater-free recipe whose membership evaluates SATISFIED, is "
        "decidable in polynomial time by one pass over a candidate node "
        "pool of at most 2,599 nodes, because ALL is SATISFIED exactly "
        "when every child is SATISFIED, each child evaluates "
        "independently against the timeline, every composer node form is "
        "covered by the pool with dominating parameters, and a witness is "
        "then built with the real composer and validator.",
        "proof_file": "data/p_vs_np_greedy_proof_r4.md",
        "evidence": {
            "brute_force_agreement": "44 of 44 (round 2, 8-signal "
            "vocabulary, ALL trees over subsets of size 1..3)",
            "candidate_pool_max": 2599,
            "greedy_seconds_range": [0.10, 0.58],
            "witnesses_built_and_validated": "round 2 timeline battery: "
            "valid witnesses built on 7 of 9 timelines; the 2 NO rows are "
            "empty (0 satisfied nodes) and empty-with-relations (relational "
            "nodes only, failing evidence feasibility)",
        },
        "scope_limit": "The theorem covers the defeater-free composer "
        "fragment only. It does not extend to arbitrary LogicNode trees "
        "and it does not extend to the full fragment with defeaters, where "
        "round 4 shows existence is trivially always YES instead.",
    }

    out["total_seconds"] = round(time.time() - t_start, 2)
    out["verdict"] = (
        "The p^r phase transition does NOT survive defeaters. Pure "
        "defeater recipes track (1-p)^r, a mirror-image transition that is "
        "easiest to match at low evidence density, and a 50/50 mixed "
        "recipe tracks 0.5^r at every density, so density stops mattering "
        "at all. For existence over the full vocabulary there is no rare "
        "regime: a SATISFIED composed recipe exists on every random "
        "evidence subset at every density, because each signal offers "
        "either a plain witness when PRESENT or a defeater witness when "
        "not. Matching becomes rare only for fixed random recipes with "
        "several plain clauses at low density, or several defeater clauses "
        "at high density. Nothing here separates or collapses P and NP, "
        "and none is claimed."
    )
    dest = LAB / "data" / "p_vs_np_r4.json"
    dest.write_text(json.dumps(out, indent=2))
    print(f"wrote {dest} in {out['total_seconds']}s", flush=True)


def _walk(node):
    if node is None:
        return
    yield node
    for a in node.args:
        yield from _walk(a)


if __name__ == "__main__":
    main()
