#!/usr/bin/env python3
"""Exact relative-rank validation for the Second-Best Gate.

Assumptions: n distinct candidates arrive in uniformly random order; the first
eight remain recallable; evaluation stops at the first later candidate better
than the second-best scout; the best candidate seen by then is selected.  If
no later candidate clears the gate, the best scout is selected.
"""

from __future__ import annotations

from fractions import Fraction
from math import comb
import json


SCOUTS = 8
POOL_SIZES = (9, 10, 12, 16, 18, 20, 24, 32, 50, 100, 250, 1000)


def exact_metrics(n: int) -> dict[str, float | int]:
    if n < SCOUTS + 1:
        raise ValueError(f"n must be at least {SCOUTS + 1}")

    denominator = comb(n, SCOUTS)
    expected_rank = Fraction(0)
    probability_best = Fraction(0)
    expected_seen = Fraction(0)
    probability_mass = Fraction(0)

    # a and b are the smallest (best) and second-smallest absolute ranks in
    # the scout sample.  Its other six ranks must all be worse than b.
    for b in range(2, n - (SCOUTS - 2) + 1):
        pair_mass = Fraction(comb(n - b, SCOUTS - 2), denominator)
        for a in range(1, b):
            probability_mass += pair_mass
            if b == 2:  # necessarily a == 1; no later rank can clear the gate
                conditional_rank = Fraction(1)
                conditional_best = Fraction(1)
                conditional_seen = Fraction(n)
            else:
                gate_crossers = b - 2
                # The first gate-crosser is uniform over ranks 1..b-1 except a.
                conditional_rank = Fraction(
                    a * (a - 1) // 2 + a * (b - a - 1), gate_crossers
                )
                conditional_best = Fraction(1) if a == 1 else Fraction(1, gate_crossers)
                # Expected minimum position of q marked items in n-8 slots.
                conditional_seen = SCOUTS + Fraction(n - SCOUTS + 1, gate_crossers + 1)

            expected_rank += pair_mass * conditional_rank
            probability_best += pair_mass * conditional_best
            expected_seen += pair_mass * conditional_seen

    assert probability_mass == 1
    percentile = 1 - (expected_rank - 1) / (n - 1)
    return {
        "pool_size": n,
        "scout_count": SCOUTS,
        "expected_absolute_rank": float(expected_rank),
        "expected_rank_percentile": float(percentile),
        "probability_literal_best": float(probability_best),
        "expected_candidates_seen": float(expected_seen),
    }


def build_evidence() -> dict[str, object]:
    rows = [exact_metrics(n) for n in POOL_SIZES]
    return {
        "schema": "second-best-gate-evidence-v1",
        "method": "exact enumeration of the two leading scout ranks",
        "assumptions": [
            "distinct ranks",
            "uniformly random arrival order",
            "eight sampled candidates remain recallable",
            "best-so-far is selected at the first later candidate above the second-best scout",
            "best scout is selected if no candidate crosses the gate",
        ],
        "rows": rows,
    }


if __name__ == "__main__":
    print(json.dumps(build_evidence(), indent=2))