"""Derive integer division and search from contracts. Python 3.10+, no packages."""
from __future__ import annotations


def divide(a: int, b: int) -> tuple[int, int]:
    """Pre: a>=0, b>0, both integers. Post: a=q*b+r and 0<=r<b."""
    if not isinstance(a, int) or not isinstance(b, int) or a < 0 or b <= 0:
        raise ValueError("a must be a nonnegative integer and b a positive integer")
    q, r = 0, a
    # Invariant: a == q*b + r and r >= 0. Bound: r.
    while r >= b:
        q, r = q + 1, r - b
    return q, r


def first_index(values: list, target) -> int:
    """Pre: finite list. Post: first matching index, or len(values) if absent."""
    i = 0
    # Invariant: target not in values[:i], 0<=i<=len(values). Bound: len(values)-i.
    while i < len(values) and values[i] != target:
        i += 1
    return i


def demo():
    """Show a contract and its boundary cases."""
    print("divide(17,5):", divide(17, 5))
    print("divide(0,5):", divide(0, 5))
    print("first_index([4,8,8],8):", first_index([4, 8, 8], 8))
    print("first_index([4,8,8],7):", first_index([4, 8, 8], 7))


def self_test():
    """Check division against divmod and search against a simple reference."""
    count = 0
    # Invariant: previous pairs agree with divmod. Bound: remaining 640 pairs.
    for a in range(80):
        for b in range(1, 9):
            check(divide(a, b), divmod(a, b))
            count += 1
    for values in ([], [1], [1, 2, 1], [3, 3, 3]):
        for target in range(5):
            expected = values.index(target) if target in values else len(values)
            check(first_index(values, target), expected)
            count += 1
    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()