"""A bounded Turing-machine simulator that increments binary numbers. Python 3.10+."""
from __future__ import annotations


class StepLimit(RuntimeError):
    """The simulation budget ended; this does not establish nontermination."""


INCREMENT = {
    ("scan", "0"): ("scan", "0", 1), ("scan", "1"): ("scan", "1", 1),
    ("scan", "_"): ("carry", "_", -1),
    ("carry", "1"): ("carry", "0", -1),
    ("carry", "0"): ("halt", "1", 0), ("carry", "_"): ("halt", "1", 0),
}


def simulate(bits: str, *, limit=1000) -> tuple[str, list]:
    """Pre: nonempty binary input, positive budget. Post: incremented output or StepLimit."""
    if not bits or set(bits) - {"0", "1"} or limit <= 0:
        raise ValueError("nonempty binary input and a positive step limit required")
    tape = dict(enumerate(bits))
    state, head, steps, trace = "scan", 0, 0, []
    # Invariant: tape/head/state exactly match the machine after 'steps' transitions.
    # Bound: limit-steps. A timeout is deliberately an inconclusive exception.
    while state != "halt":
        if steps >= limit:
            raise StepLimit("budget exhausted; halting status remains unknown")
        symbol = tape.get(head, "_")
        trace.append((steps, state, head, symbol))
        state, written, move = INCREMENT[state, symbol]
        tape[head] = written
        head += move
        steps += 1
    positions = [p for p, symbol in tape.items() if symbol != "_"]
    return "".join(tape.get(p, "_") for p in range(min(positions), max(positions)+1)), trace


def demo():
    result, trace = simulate("111")
    print("111 + 1 =", result)
    print("Trace (step,state,head,read):", trace)
    try:
        simulate("111", limit=2)
    except StepLimit as error:
        print("Short budget:", error)


def self_test():
    count = 0
    # Invariant: earlier inputs have matched ordinary integer increment. Bound: remaining 128.
    for value in range(128):
        bits = format(value, "b")
        result, trace = simulate(bits)
        check(int(result, 2), value + 1)
        check(len(trace) <= 2*len(bits)+2, True)
        count += 2
    try:
        simulate("1", limit=1)
    except StepLimit:
        count += 1
    else:
        raise AssertionError("timeout must be inconclusive, not an accepted result")
    return count

def check(actual, expected):
    """Require an expected result; this check also runs under python -O."""
    if actual != expected:
        raise AssertionError(f"expected {expected!r}, got {actual!r}")


if __name__ == "__main__":
    import argparse
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("--self-test", action="store_true")
    args = parser.parse_args()
    if args.self_test:
        print(f"{self_test()} checks passed")
    else:
        demo()