"""AUDIT TRAP found while running collision_ladder_birthday_test.py
(2026-07-23): the (L=6, M=72) "collision" at n=382 was real (hand-
verified against an independent tuple rebuild -- packed-int encoding
cannot itself produce a false collision, base-M digit packing is a
bijection) but its window was (48,48,48,48,48,48): a Q PLATEAU, a
run of six equal values. Any two plateaus sharing a value and landing
on compatible n mod M residues collide INSTANTLY, regardless of L or
M -- a completely different, much cheaper mechanism than the generic
"random hash" birthday story the whole ladder has been built on. The
M=54 baseline and M=85 stretch-rung collisions were checked by hand
and are genuinely non-constant windows (see conversation record) --
but nobody had checked this before, across any prior rung on this
ladder, in any jam.

This instrument re-runs the descriptor family with plateau-degenerate
states EXCLUDED (any window with all L values equal is skipped, never
entered into the collision dictionary), isolating the question the
ladder actually meant to ask: does a GENUINE, non-degenerate window
collision occur near the birthday scale, or later? It also reports
how many states encountered along the way were plateau-degenerate --
a direct measurement of how much of the ladder's prior evidence may
have been silently contaminated.
"""
import time


def build_q(n_max: int):
    Q = [0] * (n_max + 1)
    Q[1] = 1
    if n_max >= 2:
        Q[2] = 1
    for n in range(3, n_max + 1):
        a = n - Q[n - 1]
        b = n - Q[n - 2]
        assert 1 <= a < n and 1 <= b < n, "Q UNDEFINED at n=%d" % n
        Q[n] = Q[a] + Q[b]
        assert Q[n] > 0, "Q NONPOSITIVE at n=%d" % n
    return Q


def probe_filtered(Q, n_max: int, L: int, M: int):
    """Packed-int state, identical to collision_ladder_birthday_test's
    probe_packed, EXCEPT states whose L-window is constant (a plateau)
    are counted but never stored -- they cannot register a collision
    against anything, degenerate or not."""
    seen = {}
    plateau_visits = 0
    for n in range(L, n_max):
        window = [Q[i] for i in range(n - L + 1, n + 1)]
        if len(set(window)) == 1:
            plateau_visits += 1
            continue
        state = n % M
        for w in window:
            state = state * M + (w % M)
        nxt = Q[n + 1]
        prior = seen.get(state)
        if prior is not None:
            prev_n, prev_nxt = prior
            if prev_nxt != nxt:
                return ("COLLISION", n, prev_n, prev_nxt, nxt, plateau_visits)
        else:
            seen[state] = (n, nxt)
    return ("SURVIVED", n_max, None, None, None, plateau_visits)


def birthday(M: int, L: int) -> float:
    return M ** ((L + 1) / 2.0)


RUNGS = [(54, 3), (72, 4), (85, 3)]
L = 6


def main():
    plans = []
    for M, mult in RUNGS:
        b = birthday(M, L)
        n_needed = int(b * mult) + L + 10
        plans.append((M, mult, b, n_needed))
    n_max = max(p[3] for p in plans)

    print("Plateau-filtered rerun of the ladder's stretch test. L=%d." % L)
    for M, mult, b, n_needed in plans:
        print("  M=%-3d  birthday=%.0f  target=%dx -> need n>=%d"
              % (M, b, mult, n_needed))

    print("\nbuilding Q(1..%d) ..." % n_max)
    t0 = time.time()
    Q = build_q(n_max)
    print("  built in %.1fs" % (time.time() - t0))

    print("\n  M |  L | birthday |   n_max run | verdict   | ratio  | plateau"
          " visits skipped | time")
    for M, mult, b, n_needed in plans:
        t0 = time.time()
        verdict, n, pn, pnxt, nxt, pv = probe_filtered(Q, n_needed, L, M)
        dt = time.time() - t0
        frac = pv / (n_needed - L)
        if verdict == "COLLISION":
            print("  %-3d| %2d | %8.0f | %10d  | COLLISION | %.3fx | %9d (%.4f%%)      | %.1fs"
                  % (M, L, b, n_needed, n / b, pv, frac * 100, dt))
            print("        genuine witness: (n1=%d,next=%d) vs (n2=%d,next=%d)"
                  % (pn, pnxt, n, nxt))
            w1 = [Q[i] for i in range(pn - L + 1, pn + 1)]
            w2 = [Q[i] for i in range(n - L + 1, n + 1)]
            print("        window(n1)=%s  window(n2)=%s  (both non-constant, verified)"
                  % (w1, w2))
        else:
            print("  %-3d| %2d | %8.0f | %10d  | SURVIVED  | %.2fx  | %9d (%.4f%%)      | %.1fs"
                  % (M, L, b, n_needed, n_needed / b, pv, frac * 100, dt))

    print("\nHonest reading: plateau visits are excluded entirely from the")
    print("collision dictionary in this run -- they can neither register nor")
    print("break a collision here. Any COLLISION reported above is therefore a")
    print("genuine non-degenerate one-step-Markov failure of the descriptor,")
    print("not a byproduct of Q resting on a constant run.")


if __name__ == "__main__":
    main()