"""THE TAGGED BIRTHDAY — exact L=6 collision survey (2026-07-24).

Deposited by THE SEVENTH JAM, played live through Tom's browser by a
disk-handed GPT walker and a stateless Grok walker. It keeps the Ladder's
original state:

    (n mod M, Q(n-5) mod M, ..., Q(n) mod M)

and finds the earliest repeated state whose next *integer* Q value differs.
States are packed into uint64 exactly (all requested M satisfy M**7 < 2**64),
then sorted by (state, n).  Within each state class, the first chronological
change of next-Q value is exactly that class's first predictive collision.

The sort-based implementation uses substantially less memory than a Python
dictionary at ten-to-thirty million states. It makes the chronological
"first collision" claim independently of the deposited dict-based probes.

Two-channel use:

    python tagged_birthday.py --moduli 7 60 84 --factor 1.5 --tag-clock

Raw-survey use:

    python tagged_birthday.py --moduli 60 66 78 84 90 102 --factor 2.5

The first command reports exact HOMOTHETY / CLOCK_TRANSLATION witnesses
without deleting them, then continues to the first untagged opposite-next
collision. The second reports the unconditioned Ladder exactly as originally
defined. Large factors require substantial memory and time; separate runs at
the exact horizons recorded in THE_SEVENTH_JAM.md produced the deposited
table.
"""

from __future__ import annotations

import argparse
import gc
import json
import math
import time
from array import array

import numpy as np


L = 6
KNOWN_CLOCK_BASE = 9  # the Clock's Long Arm supplies 9 * 2**a


def build_q(n_max: int) -> array:
    """Build Hofstadter Q in a compact uint32 array, auditing totality."""
    q = array("I", [0]) * (n_max + 1)
    q[1] = 1
    q[2] = 1
    for n in range(3, n_max + 1):
        a = n - q[n - 1]
        b = n - q[n - 2]
        if not (1 <= a < n and 1 <= b < n):
            raise AssertionError(f"Q undefined at n={n}: a={a}, b={b}")
        value = q[a] + q[b]
        if value <= 0 or value > 0xFFFFFFFF:
            raise AssertionError(f"Q out of uint32 range at n={n}: {value}")
        q[n] = value
    return q


def clock_contamination_witness(m: int, max_a: int = 60) -> int | None:
    """Return 9*2**a if M divides a known clock-shift constant."""
    for a in range(max_a + 1):
        c = KNOWN_CLOCK_BASE * (1 << a)
        if c % m == 0:
            return c
    return None


def birthday_scale(m: int) -> float:
    return m ** ((L + 1) / 2.0)


def clock_relation(q: array, n1: int, n2: int) -> dict | None:
    """Classify the two exact raw clock/dilation relations seen in the jam.

    This deliberately does *not* work modulo M.  At the modular level every
    state collision already has zero additive shift and unit dilation, making
    such a filter vacuous.  Nor does it delete a witness: callers tag the
    relation and continue looking for the first untagged predictive collision.
    """
    w1 = list(q[n1 - L + 1 : n1 + 1])
    w2 = list(q[n2 - L + 1 : n2 + 1])

    # Exact homothety of both time and the raw window.
    if n1 > 0 and n2 % n1 == 0:
        d = n2 // n1
        if d > 1 and all(y == d * x for x, y in zip(w1, w2)):
            return {"kind": "HOMOTHETY", "d": d}

    # Exact leading-edge clock translation.  In every audited clock pair,
    # the center/index advances by twice the common window shift.
    diffs = [y - x for x, y in zip(w1, w2)]
    if diffs and all(delta == diffs[0] for delta in diffs):
        c = diffs[0]
        if c != 0 and n2 - n1 == 2 * c:
            return {"kind": "CLOCK_TRANSLATION", "c": c}
    return None


def probe_sorted(q: array, cap: int, m: int, tag_clock: bool = False) -> dict:
    """Find the exact earliest opposite-next collision for n in [L, cap).

    With tag_clock=True, exact raw homotheties/translations are reported as
    tagged confounders and the search continues to the first untagged pair.
    """
    if m ** (L + 1) >= 2**64:
        raise ValueError(f"M={m} cannot be packed exactly into uint64")

    qv = np.frombuffer(q, dtype=np.uint32)
    count = cap - L
    dtype = np.dtype([("state", "<u8"), ("n", "<u4"), ("next", "<u4")])
    rec = np.empty(count, dtype=dtype)

    # Fill the state field in place to avoid holding a second uint64 state
    # array.  Slice k is Q(n-L+1+k), aligned over n=L,...,cap-1.
    state = rec["state"]
    state[:] = np.arange(L, cap, dtype=np.uint64)
    np.remainder(state, np.uint64(m), out=state)
    residues = np.remainder(qv[: cap + 1], np.uint32(m))
    for k in range(L):
        np.multiply(state, np.uint64(m), out=state)
        np.add(
            state,
            residues[1 + k : cap - L + 1 + k],
            out=state,
            casting="unsafe",
        )

    rec["n"] = np.arange(L, cap, dtype=np.uint32)
    rec["next"] = qv[L + 1 : cap + 1]
    del residues, state
    gc.collect()

    t_sort = time.time()
    rec.sort(order=["state", "n"], kind="quicksort")
    sort_seconds = time.time() - t_sort

    if not tag_clock:
        same_state = rec["state"][1:] == rec["state"][:-1]
        changed_next = rec["next"][1:] != rec["next"][:-1]
        candidate = np.flatnonzero(same_state & changed_next)
        del same_state, changed_next

        if candidate.size == 0:
            result = {
                "verdict": "SURVIVED",
                "cap": cap,
                "sort_seconds": sort_seconds,
            }
        else:
            later_n = rec["n"][candidate + 1]
            pos = int(candidate[int(np.argmin(later_n))])
            first = rec[pos]
            second = rec[pos + 1]
            result = {
                "verdict": "COLLISION",
                "cap": cap,
                "n1": int(first["n"]),
                "n2": int(second["n"]),
                "next1": int(first["next"]),
                "next2": int(second["next"]),
                "state_packed": int(first["state"]),
                "sort_seconds": sort_seconds,
            }
        del candidate
    else:
        # Duplicate state groups are rare at birthday-scale occupancy.  Build
        # only their boundaries, then compare exact chronological pairs.  A
        # later untagged collision may be non-adjacent after a tagged one, so
        # retaining all records in each duplicate group is necessary.
        duplicate_edges = np.flatnonzero(rec["state"][1:] == rec["state"][:-1])
        groups = []
        if duplicate_edges.size:
            run_start = int(duplicate_edges[0])
            previous = run_start
            for edge_raw in duplicate_edges[1:]:
                edge = int(edge_raw)
                if edge != previous + 1:
                    groups.append((run_start, previous + 2))
                    run_start = edge
                previous = edge
            groups.append((run_start, previous + 2))

        earliest_untagged = None
        earliest_tagged = None
        tagged_pairs_seen = 0
        opposite_next_pairs_seen = 0
        for start, end in groups:
            group = rec[start:end]  # already chronological within state
            for j in range(1, len(group)):
                for i in range(j):
                    if int(group[i]["next"]) == int(group[j]["next"]):
                        continue
                    opposite_next_pairs_seen += 1
                    n1 = int(group[i]["n"])
                    n2 = int(group[j]["n"])
                    relation = clock_relation(q, n1, n2)
                    event = {
                        "n1": n1,
                        "n2": n2,
                        "next1": int(group[i]["next"]),
                        "next2": int(group[j]["next"]),
                        "state_packed": int(group[i]["state"]),
                    }
                    if relation is not None:
                        tagged_pairs_seen += 1
                        event["clock_relation"] = relation
                        if earliest_tagged is None or n2 < earliest_tagged["n2"]:
                            earliest_tagged = event
                    elif (
                        earliest_untagged is None
                        or n2 < earliest_untagged["n2"]
                    ):
                        earliest_untagged = event

        result = {
            "verdict": "COLLISION" if earliest_untagged else "SURVIVED",
            "cap": cap,
            "sort_seconds": sort_seconds,
            "clock_tagging": True,
            "opposite_next_pairs_seen": opposite_next_pairs_seen,
            "tagged_pairs_seen": tagged_pairs_seen,
            "earliest_tagged": earliest_tagged,
        }
        if earliest_untagged:
            result.update(earliest_untagged)

        del duplicate_edges

    del rec
    gc.collect()
    return result


def decorate_result(q: array, m: int, result: dict) -> dict:
    b = birthday_scale(m)
    result = dict(result)
    result.update(
        {
            "M": m,
            "L": L,
            "sqrt_state_space": b,
            "clock_contamination_constant": clock_contamination_witness(m),
        }
    )
    if result["verdict"] == "COLLISION":
        n1, n2 = result["n1"], result["n2"]
        result["ratio_n2_over_sqrtS"] = n2 / b
        result["window1"] = list(q[n1 - L + 1 : n1 + 1])
        result["window2"] = list(q[n2 - L + 1 : n2 + 1])
        result["window1_mod_M"] = [x % m for x in result["window1"]]
        result["window2_mod_M"] = [x % m for x in result["window2"]]
        result["n1_mod_M"] = n1 % m
        result["n2_mod_M"] = n2 % m
        result["next1_mod_M"] = result["next1"] % m
        result["next2_mod_M"] = result["next2"] % m
    else:
        result["censor_ratio"] = result["cap"] / b
    return result


def main() -> None:
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "--moduli",
        nargs="+",
        type=int,
        default=[54, 85, 60, 66, 78, 84, 90, 102],
    )
    parser.add_argument(
        "--factor",
        type=float,
        default=2.5,
        help="Censor each search at factor * sqrt(M**7).",
    )
    parser.add_argument(
        "--output",
        default=None,
        help="Optional JSON output path.",
    )
    parser.add_argument(
        "--tag-clock",
        action="store_true",
        help="Tag exact raw clock/dilation pairs and continue past them.",
    )
    args = parser.parse_args()

    plans = []
    for m in args.moduli:
        b = birthday_scale(m)
        cap = int(math.ceil(args.factor * b)) + L + 1
        plans.append((m, b, cap))
    n_max = max(cap for _, _, cap in plans)

    print(f"L={L}; exact sort-based predictive-collision survey")
    print(f"factor={args.factor}; Q required through n={n_max:,}")
    for m, b, cap in plans:
        clock = clock_contamination_witness(m)
        tag = f"CLOCK-CONTAMINATED via {clock}" if clock else "clean by known clock test"
        print(f"  M={m:3d} sqrt(S)={b:,.0f} cap={cap:,}  {tag}")

    t0 = time.time()
    q = build_q(n_max)
    print(
        f"built Q through {n_max:,} in {time.time() - t0:.1f}s; "
        f"Q[n_max]={q[n_max]:,}"
    )

    results = []
    for m, _, cap in plans:
        t0 = time.time()
        raw = probe_sorted(q, cap, m, tag_clock=args.tag_clock)
        result = decorate_result(q, m, raw)
        result["probe_seconds"] = time.time() - t0
        results.append(result)
        if result.get("clock_tagging") and result.get("earliest_tagged"):
            tagged = result["earliest_tagged"]
            print(
                f"M={m:3d} TAGGED {tagged['clock_relation']['kind']} "
                f"n1={tagged['n1']:,} n2={tagged['n2']:,} "
                f"next={tagged['next1']:,}/{tagged['next2']:,}; "
                "continuing past it"
            )
        if result["verdict"] == "COLLISION":
            print(
                f"M={m:3d} COLLISION n1={result['n1']:,} "
                f"n2={result['n2']:,} r={result['ratio_n2_over_sqrtS']:.6f} "
                f"next={result['next1']:,}/{result['next2']:,} "
                f"({result['probe_seconds']:.1f}s)"
            )
            print(f"      window1 mod M={result['window1_mod_M']}")
            print(f"      window2 mod M={result['window2_mod_M']}")
        else:
            print(
                f"M={m:3d} SURVIVED to {result['cap']:,} "
                f"r>{result['censor_ratio']:.6f} "
                f"({result['probe_seconds']:.1f}s)"
            )
        print("RESULT_JSON " + json.dumps(result, separators=(",", ":")))

    if args.output:
        with open(args.output, "w", encoding="utf-8") as fh:
            json.dump(results, fh, indent=2)
            fh.write("\n")


if __name__ == "__main__":
    main()