Computational thinking & correctness

invariant.py# A loop INVARIANT is a condition true before the loop and preserved by every
# iteration. Together with the exit condition it proves the result.
def find_max(xs):
    assert len(xs) > 0, "precondition: xs is non-empty"
    best = xs[0]
    for i in range(1, len(xs)):
        # INVARIANT (holds at the top of each iteration):
        #   best == max(xs[:i])
        assert best == max(xs[:i])          # checkable statement of the invariant
        if xs[i] > best:
            best = xs[i]
    # At exit i == len(xs), so the invariant gives: best == max(xs[:len(xs)])
    assert best == max(xs), "postcondition"
    return best

print(find_max([3, 1, 4, 1, 5, 9, 2, 6]))   # 9

contracts.py# Preconditions guard the inputs; postconditions guarantee the output. Assertions
# document AND check both. (Note: assertions are stripped under `python -O`.)
import math

def newton_sqrt(x, iters=50):
    assert x >= 0, "precondition: x must be non-negative"
    if x == 0:
        return 0.0
    guess = x
    for _ in range(iters):
        guess = (guess + x / guess) / 2      # Newton-Raphson step
    assert math.isclose(guess * guess, x, rel_tol=1e-9), "postcondition failed"
    return guess

print(round(newton_sqrt(2), 6))              # 1.414214
try:
    newton_sqrt(-1)
except AssertionError as e:
    print("caught:", e)

iterator.py# The protocol: an ITERABLE has __iter__ (returns an iterator); an ITERATOR has
# __next__ (returns items, raises StopIteration to stop) and __iter__ (returns self).

class Countdown:                      # a hand-written iterator
    def __init__(self, start): self.n = start
    def __iter__(self): return self   # an iterator is its own iterable
    def __next__(self):
        if self.n <= 0:
            raise StopIteration       # signals "no more items"
        self.n -= 1
        return self.n + 1

print("class iterator:", list(Countdown(3)))    # [3, 2, 1]

def countdown(start):                 # a GENERATOR: the compiler writes the
    while start > 0:                   # __iter__/__next__/StopIteration for you
        yield start
        start -= 1

print("generator     :", list(countdown(3)))    # [3, 2, 1]

# for-loops speak this protocol: iter(obj) then repeated next() until StopIteration
it = iter([10, 20])
print(next(it), next(it))             # 10 20
try:
    next(it)
except StopIteration:
    print("exhausted")

cost.pyfrom collections import deque
import time

def bench(fn, n=1000):
    t = time.perf_counter()
    for _ in range(n):
        fn()
    return (time.perf_counter() - t) * 1000   # ms per 1000 calls

L = list(range(10_000))
S = set(range(10_000))
print("x in list :", round(bench(lambda: 9999 in L), 2), "ms/1000")   # slow, O(n)
print("x in set  :", round(bench(lambda: 9999 in S), 2), "ms/1000")   # fast, O(1)

# list vs deque at the front:
lst = list(range(100_000))
dq = deque(range(100_000))
print("list.pop(0)     is O(n): shifts every element")
print("deque.popleft() is O(1):", dq.popleft())                       # 0

eq_hash.py# The contract: if a == b then hash(a) == hash(b). Break it and dicts/sets break.

# BUG 1: define __eq__ but forget __hash__ -> Python makes the type UNHASHABLE.
class BadPoint:
    def __init__(self, x, y): self.x, self.y = x, y
    def __eq__(self, o): return (self.x, self.y) == (o.x, o.y)
try:
    {BadPoint(1, 2)}                  # can't put it in a set
except TypeError as e:
    print("unhashable:", type(e).__name__)

# BUG 2: equal objects with DIFFERENT hashes -> duplicates leak into a set.
class SneakyPoint:
    _n = 0
    def __init__(self, x, y): self.x, self.y = x, y
    def __eq__(self, o): return (self.x, self.y) == (o.x, o.y)
    def __hash__(self):
        SneakyPoint._n += 1
        return SneakyPoint._n         # inconsistent hash: violates the contract
s = {SneakyPoint(1, 2), SneakyPoint(1, 2)}
print("leaked duplicates:", len(s))  # 2  -> equal points, but both stored!

# CORRECT: hash the SAME fields you compare.
class Point:
    def __init__(self, x, y): self.x, self.y = x, y
    def __eq__(self, o): return isinstance(o, Point) and (self.x, self.y) == (o.x, o.y)
    def __hash__(self): return hash((self.x, self.y))
print("correct dedup   :", len({Point(1, 2), Point(1, 2)}))   # 1

floats.py# Floats are binary IEEE-754: most decimals (0.1, 0.2) can't be represented exactly.
import math
from decimal import Decimal

print("0.1 + 0.2      :", 0.1 + 0.2)                 # 0.30000000000000004
print("== 0.3         :", 0.1 + 0.2 == 0.3)          # False
print("math.isclose   :", math.isclose(0.1 + 0.2, 0.3))          # True
print("Decimal money  :", Decimal("0.1") + Decimal("0.2"))       # 0.3 (exact)

# Rounding is not always "round half up" — Python uses banker's rounding.
print("round(2.5)     :", round(2.5))                # 2  (round half to even)
print("round(3.5)     :", round(3.5))                # 4

properties.py# Property-based thinking: assert what must hold for ALL inputs, not examples.
import random

def my_sort(xs):
    return sorted(xs)

def is_permutation(a, b):
    return sorted(a) == sorted(b)          # same multiset of elements

# Properties of a correct sort, checked on many random inputs:
for _ in range(1000):
    xs = [random.randint(-50, 50) for _ in range(random.randint(0, 20))]
    out = my_sort(xs)
    assert all(out[i] <= out[i + 1] for i in range(len(out) - 1)), "ordered"
    assert is_permutation(xs, out), "same elements"
    assert len(out) == len(xs), "same length"

print("all sort properties held over 1000 random inputs")