test_bubble_sort.py

#!/usr/bin/env python3
"""Automated tests for the bubble sort Turing Machine.

Uses generate_yaml.py to create a TM for each input, then runs it through
the emulator and checks that the output is correctly sorted.
"""

import itertools
import sys
import time

from generate_yaml import generate_yaml
from emulator import preprocess_yaml, TuringMachine

import yaml


def run_tm(input_str, step_limit=100_000):
    """Run the bubble sort TM on the given input string.

    Returns (tape_contents, steps, final_state, halted).
    """
    yaml_text = generate_yaml(input_str)
    yaml_text = preprocess_yaml(yaml_text)
    config = yaml.safe_load(yaml_text)
    tm = TuringMachine(config)

    halted = False
    while True:
        if tm.halted():
            halted = True
            break
        if tm.steps >= step_limit:
            break
        tm.step()

    return tm.tape_contents(), tm.steps, tm.state, halted


def check_sorted(tape_str, input_str):
    """Verify that tape_str is the sorted version of input_str."""
    expected = "".join(sorted(input_str))
    return tape_str == expected


# ---------------------------------------------------------------------------
# Test cases
# ---------------------------------------------------------------------------

def test_primary_input():
    """The primary test case from the spec: 327154 -> 123457."""
    tape, steps, state, halted = run_tm("327154")
    assert halted, "Machine did not halt"
    assert state == "done", f"Expected state 'done', got '{state}'"
    assert tape == "123457", f"Expected '123457', got '{tape}'"
    assert steps == 63, f"Expected 63 steps, got {steps}"
    return f"327154 -> {tape} in {steps} steps"


def test_already_sorted():
    """Already-sorted input should complete in one clean pass."""
    tape, steps, state, halted = run_tm("123457")
    assert halted and state == "done"
    assert tape == "123457"
    # One clean pass: read each pair, then halt. Should be very few steps.
    assert steps < 20, f"Already sorted took too many steps: {steps}"
    return f"123457 -> {tape} in {steps} steps"


def test_reverse_sorted():
    """Worst case for bubble sort: fully reversed input."""
    tape, steps, state, halted = run_tm("754321")
    assert halted and state == "done"
    assert tape == "123457", f"Expected '123457', got '{tape}'"
    return f"754321 -> {tape} in {steps} steps"


def test_single_element():
    """A single digit should halt immediately."""
    for d in "1234567":
        tape, steps, state, halted = run_tm(d)
        assert halted and state == "done"
        assert tape == d
    return "All single digits OK"


def test_two_elements():
    """All pairs of two digits."""
    failures = []
    for a in range(1, 8):
        for b in range(1, 8):
            inp = f"{a}{b}"
            tape, steps, state, halted = run_tm(inp)
            expected = "".join(sorted(inp))
            if not halted or state != "done" or tape != expected:
                failures.append(f"{inp}: got '{tape}' state={state} halted={halted}")
    assert not failures, f"Failures: {failures}"
    return f"All 49 two-digit pairs OK"


def test_three_element_permutations():
    """All permutations of 3 distinct digits (pick a representative set)."""
    failures = []
    count = 0
    for combo in itertools.combinations(range(1, 8), 3):
        for perm in itertools.permutations(combo):
            inp = "".join(str(d) for d in perm)
            tape, steps, state, halted = run_tm(inp)
            expected = "".join(sorted(inp))
            if not halted or state != "done" or tape != expected:
                failures.append(f"{inp}: got '{tape}'")
            count += 1
    assert not failures, f"Failures: {failures}"
    return f"All {count} three-element permutations OK"


def test_duplicates():
    """Inputs with duplicate values."""
    cases = ["3313", "1111", "7171", "2222222", "5151515", "3322", "1177"]
    failures = []
    for inp in cases:
        tape, steps, state, halted = run_tm(inp)
        expected = "".join(sorted(inp))
        if not halted or state != "done" or tape != expected:
            failures.append(f"{inp}: expected '{expected}', got '{tape}'")
    assert not failures, f"Failures: {failures}"
    return f"All {len(cases)} duplicate-value cases OK"


def test_four_element_permutations():
    """A selection of 4-element permutations."""
    failures = []
    count = 0
    # Test all permutations of {1,2,3,4} and {4,5,6,7}
    for combo in [(1, 2, 3, 4), (4, 5, 6, 7), (1, 3, 5, 7), (2, 4, 6, 7)]:
        for perm in itertools.permutations(combo):
            inp = "".join(str(d) for d in perm)
            tape, steps, state, halted = run_tm(inp)
            expected = "".join(sorted(inp))
            if not halted or state != "done" or tape != expected:
                failures.append(f"{inp}: got '{tape}'")
            count += 1
    assert not failures, f"Failures: {failures}"
    return f"All {count} four-element permutations OK"


def test_full_seven():
    """All 7 digits in various orders."""
    cases = [
        "1234567",  # sorted
        "7654321",  # reversed
        "4261537",  # random
        "1357246",  # interleaved
        "7135246",  # another random
    ]
    failures = []
    for inp in cases:
        tape, steps, state, halted = run_tm(inp)
        expected = "1234567"
        if not halted or state != "done" or tape != expected:
            failures.append(f"{inp}: expected '{expected}', got '{tape}' (steps={steps})")
    assert not failures, f"Failures: {failures}"
    return f"All {len(cases)} seven-digit cases OK"


def test_step_counts_monotonic():
    """Verify that harder inputs take more steps (sanity check)."""
    # sorted < random < reversed  (for the same set of elements)
    _, s_sorted, _, _ = run_tm("123456")
    _, s_random, _, _ = run_tm("315264")
    _, s_reversed, _, _ = run_tm("654321")
    assert s_sorted < s_random, f"sorted({s_sorted}) >= random({s_random})"
    assert s_random <= s_reversed, f"random({s_random}) > reversed({s_reversed})"
    return f"Step counts: sorted={s_sorted} < random={s_random} <= reversed={s_reversed}"


# ---------------------------------------------------------------------------
# Runner
# ---------------------------------------------------------------------------

ALL_TESTS = [
    test_primary_input,
    test_already_sorted,
    test_reverse_sorted,
    test_single_element,
    test_two_elements,
    test_three_element_permutations,
    test_duplicates,
    test_four_element_permutations,
    test_full_seven,
    test_step_counts_monotonic,
]


def main():
    passed = 0
    failed = 0
    t0 = time.time()

    for test_fn in ALL_TESTS:
        name = test_fn.__name__
        try:
            result = test_fn()
            print(f"  PASS  {name}: {result}")
            passed += 1
        except AssertionError as e:
            print(f"  FAIL  {name}: {e}")
            failed += 1
        except Exception as e:
            print(f"  ERROR {name}: {type(e).__name__}: {e}")
            failed += 1

    elapsed = time.time() - t0
    print(f"\n{passed} passed, {failed} failed in {elapsed:.2f}s")
    sys.exit(0 if failed == 0 else 1)


if __name__ == "__main__":
    main()