#!/usr/bin/env python3
"""Exact, small cross-entropy experiments; Python standard library only.

Robot probabilities: https://www.youtube.com/watch?v=GlYgs6v2YfU&t=200s
Symbol order is U, D, L, R. This is synthetic data, not an LLM benchmark.
The decoder shares the static probability table, symbol count and bit length.
These metadata and the model's storage are excluded from payload sizes.
"""

from collections import Counter
from fractions import Fraction
import hashlib
import json
import math
import platform
import random


SYMBOLS = "UDLR"
SEED = 20261114
GRID = 40


def cumulative(weights):
    total = sum(weights)
    return [Fraction(sum(weights[:i]), total) for i in range(len(weights) + 1)]


def encode(message, cdf):
    """Refine an exact rational interval, then emit a contained binary cell."""
    low, high = Fraction(0), Fraction(1)
    for symbol in message:
        width = high - low
        i = SYMBOLS.index(symbol)
        low, high = low + width * cdf[i], low + width * cdf[i + 1]

    width = high - low
    nbits = max(0, width.denominator.bit_length() - width.numerator.bit_length())
    while True:
        scale = 1 << nbits
        cell = (low.numerator * scale + low.denominator - 1) // low.denominator
        if Fraction(cell + 1, scale) <= high:
            break
        nbits += 1

    assert low <= Fraction(cell, scale) < Fraction(cell + 1, scale) <= high
    padding = (-nbits) % 8
    payload = (cell << padding).to_bytes((nbits + 7) // 8, "big")
    return payload, nbits


def decode(payload, nbits, count, cdf):
    """Decode using only the payload and agreed metadata, not the message."""
    padding = len(payload) * 8 - nbits
    cell = int.from_bytes(payload, "big") >> padding
    point = Fraction(2 * cell + 1, 2 * (1 << nbits))
    low, high = Fraction(0), Fraction(1)
    output = []
    for _ in range(count):
        width = high - low
        for i, symbol in enumerate(SYMBOLS):
            left, right = low + width * cdf[i], low + width * cdf[i + 1]
            if left <= point < right:
                output.append(symbol)
                low, high = left, right
                break
        else:
            raise AssertionError("Point fell outside the coding intervals")
    return "".join(output)


def cross_entropy(p, q):
    if any(pi > 0 and qi == 0 for pi, qi in zip(p, q)):
        return math.inf
    return -sum(pi * math.log2(qi) for pi, qi in zip(p, q) if pi > 0)


def brier(p, q):
    # Average, over outcomes y, the sum of all four squared prediction errors.
    return sum(py * sum((qi - int(i == y)) ** 2 for i, qi in enumerate(q))
               for y, py in enumerate(p))


def grid_minima(p):
    scores = {
        "cross_entropy_bits": lambda q: cross_entropy(p, q),
        "linear_1_minus_q": lambda q: 1 - sum(pi * qi for pi, qi in zip(p, q)),
        "brier_sum_over_classes": lambda q: brier(p, q),
    }
    best = {name: {"loss": math.inf, "q": None, "ties": 0} for name in scores}
    tested = 0
    for a in range(GRID + 1):
        for b in range(GRID - a + 1):
            for c in range(GRID - a - b + 1):
                q = [a / GRID, b / GRID, c / GRID, (GRID - a - b - c) / GRID]
                tested += 1
                for name, score in scores.items():
                    loss = score(q)
                    if loss < best[name]["loss"] - 1e-12:
                        best[name] = {"loss": loss, "q": q, "ties": 1}
                    elif math.isfinite(loss) and abs(loss - best[name]["loss"]) < 1e-12:
                        best[name]["ties"] += 1
    assert best["cross_entropy_bits"]["q"] == p
    assert best["brier_sum_over_classes"]["q"] == p
    assert best["linear_1_minus_q"]["q"] == [0, 0, 0, 1]
    return {"step": 1 / GRID, "tested": tested, "minima": best}


def main():
    message = list("UDLLRRRR" * 64)
    random.Random(SEED).shuffle(message)
    message = "".join(message)
    counts = Counter(message)
    p = [counts[s] / len(message) for s in SYMBOLS]
    entropy = cross_entropy(p, p)
    models = {
        "matched": [1, 1, 2, 4],
        "old_code": [4, 2, 1, 1],
        "uniform": [1, 1, 1, 1],
        "squared": [1, 1, 4, 16],
    }
    rows = []
    for name, weights in models.items():
        q = [w / sum(weights) for w in weights]
        ce = cross_entropy(p, q)
        nll_bits = -sum(math.log2(q[SYMBOLS.index(s)]) for s in message)
        payload, nbits = encode(message, cumulative(weights))
        restored = decode(payload, nbits, len(message), cumulative(weights))
        assert restored == message
        assert math.isclose(nll_bits, len(message) * ce, abs_tol=1e-8)
        assert -1e-8 <= nbits - nll_bits < 2 + 1e-8
        kl = sum(pi * math.log2(pi / qi) for pi, qi in zip(p, q))
        assert math.isclose(ce - entropy, kl, abs_tol=1e-10)
        rows.append({
            "model": name, "q": q, "cross_entropy_bits": ce,
            "nll_bits": nll_bits, "coded_bits": nbits,
            "payload_bytes": len(payload), "roundtrip_ok": restored == message,
            "top1_fraction": counts[SYMBOLS[max(range(4), key=weights.__getitem__)]] / len(message),
            "kl_bits": kl, "payload_hex": payload.hex(),
        })

    example_payload, example_bits = encode("DU", cumulative(models["old_code"]))
    example_restored = decode(example_payload, example_bits, 2, cumulative(models["old_code"]))
    assert example_bits == 3 and example_payload.hex() == "80" and example_restored == "DU"

    print(json.dumps({
        "python": platform.python_version(), "seed": SEED,
        "symbol_order": SYMBOLS, "symbols": len(message),
        "counts": {s: counts[s] for s in SYMBOLS},
        "message_sha256": hashlib.sha256(message.encode("ascii")).hexdigest(),
        "empirical_entropy_bits": entropy, "coding": rows,
        "walkthrough": {"message": "DU", "model": "old_code",
                        "coded_bits": example_bits, "payload_hex": example_payload.hex(),
                        "restored": example_restored},
        "loss_grid": grid_minima(p),
    }, indent=2, allow_nan=False))


if __name__ == "__main__":
    main()
