Computational thinking & correctness

1 · Loop invariants

Here's a bug you've almost certainly written. You have an off-by-one somewhere in a loop — the answer is right on the examples you tried but wrong on the edge (the empty list, the single element, the last item). You add a print, stare, tweak a +1, run it again, and eventually it "works" — but you couldn't say why, and you're quietly nervous it'll break again. That nervousness is the tell: you were testing the loop, not reasoning about it. A loop invariant is how you replace the nervousness with proof.

The everyday analogy is a running total on a bank statement. After every transaction the balance shown must equal "starting balance plus every transaction so far." That sentence is an invariant: it's true before the first line, and each new line preserves it. If at any row the printed balance doesn't match that rule, you know instantly that this row is where the error crept in — you don't re-audit the whole statement. An invariant gives your loop the same property: a single sentence that pins down exactly what "correct so far" means at every step.

Why this matters more than it looks: a loop is a tiny promise repeated many times, and the thing that makes it hard to trust is that the state changes on every pass. The invariant is the part that doesn't change — the fixed truth that survives every iteration. Once you can name it, correctness becomes a two-line argument: the invariant holds when the loop stops, and combined with why the loop stopped (the exit condition), it forces the answer to be right. That's the exact reasoning graders, interviewers, and your future self reviewing a PR are looking for.

The common mistake is writing an invariant that's true but useless — something like "i is between 0 and n," which is real but tells you nothing about the answer you're building. A good invariant connects your accumulator (the thing you're computing) to the portion of the input you've processed. "The running max equals the max of the slice seen so far" is useful because at the end, "the slice seen so far" becomes "the whole input" and the invariant collapses into the postcondition. If you can't turn your invariant into the answer just by plugging in the exit condition, it's the wrong invariant.

A loop invariant is a statement that is true just before the loop starts and remains true after every iteration. Combined with the loop's exit condition, an invariant lets you prove the loop produces the right answer — the same reasoning graders and interviewers ask for. The trick is to write the invariant as a checkable assertion so a wrong one fails loudly.

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

9

The invariant here is best == max(xs[:i]): true before the loop (best = xs[0], i = 1), and preserved by the body (each step extends the considered prefix by one and keeps the running max). At exit i == len(xs), so the invariant becomes exactly the postcondition best == max(xs) — a proof, not a hope.

2 · Pre/postconditions & assertions

A story engineers keep re-living. Someone guards an admin-only endpoint with assert user.is_admin. Every test passes, code review nods it through, it ships. Weeks later, non-admins are quietly getting in. Nobody changed the check — but production runs Python with the -O flag, and -O deletes every assert from the bytecode. The guard didn't fail; it stopped existing. That single misunderstanding — treating assert as a security gate — has caused real breaches, and it's why this section exists.

Think of a contract the way you'd think of a job description handshake. A function says: "Give me inputs that meet these conditions (the precondition), and I promise you an output meeting those conditions (the postcondition)." Both sides have obligations. If the caller breaks the deal by handing you a negative number where you required non-negative, that's their bug — and you want to hear about it immediately, at the doorway, not three functions deeper where the symptom is unrecognizable. An assertion is the tripwire that catches a broken contract right at the boundary and points a finger at the exact line.

So why does this earn a whole section instead of "just add some checks"? Because the value of assert is that it does two jobs at once — it documents your assumption in a way that can't rot (unlike a comment, it's executable) and it checks that assumption every run during development. A well-placed assert turns a vague "this should be sorted by now" into a statement that either holds or crashes loudly with a stack trace. Silent wrong answers are the most expensive bugs in existence; assertions convert them into cheap, obvious, immediate failures.

The mistake to name and avoid: reaching for assert to validate untrusted input — form data, API payloads, user IDs, permission checks. Those must run always, in every deployment, and -O silently strips them. The rule of thumb is a clean split: use if not ...: raise ... for anything that guards data or access coming from outside your code, and reserve assert for internal invariants you believe are always true and only want to catch during development. "Would it be a security or data-integrity hole if this check vanished?" If yes, it can't be an assert.

A precondition is what a function requires of its inputs; a postcondition is what it guarantees about its output. assert both documents and checks them, turning silent wrong behavior into a loud failure at the exact spot. One caveat that trips people in production: assertions are removed when Python runs with -O, so never use them for input validation that must always run — use explicit checks/exceptions there, and use assertions for internal invariants.

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)

1.414214
caught: precondition: x must be non-negative

3 · The iterator & iterable protocol

You've written for x in something a thousand times without asking what makes it work. Most of the time you don't need to — until the day you loop over a file, a database cursor, or a streaming API response and it behaves in a way a list never would: it can only be walked once, or it hangs forever, or a "copy" of it turns up empty. Those aren't bugs in the loop; they're the iterator protocol showing through. Understanding it is what lets you process a 50 GB file on a laptop, or stream tokens from an LLM one at a time instead of waiting for the whole response.

Here's the analogy that makes it click. An iterable is like a book on a shelf — it can be read, but it isn't itself keeping your place. An iterator is the bookmark: it points at exactly one spot and knows how to advance to the next. When you say for x in book, Python quietly asks the book for a fresh bookmark (iter()), then keeps asking the bookmark "what's next?" (next()) until the bookmark says "we're done" (StopIteration). A list is a book you can hand out many bookmarks for; a file object is stranger — it is its own single bookmark, which is exactly why you can only read it once.

Why separate the two ideas at all? Because it buys you laziness — the ability to produce values on demand instead of building them all up front. A list of a million doubled numbers costs a million slots of memory the instant you create it; an iterator that yields them costs one value at a time and never holds the whole thing. That's not a micro-optimization — it's the difference between a pipeline that streams and one that runs out of RAM. The protocol is the machinery that makes "process it as it arrives" possible.

The classic mistake is confusing the iterable with the iterator — assuming you can restart or reuse something you've already consumed. You loop over a generator to find a total, then loop again to print the items, and the second loop does nothing because the bookmark is already at the end. The fix is knowing which you hold: if you need to walk the data twice, materialize it into a list (a reusable iterable), or build a fresh iterator each time. A hand-written iterator's __iter__ returning self is the code-level signature of "I am my own bookmark, and once I'm spent, I'm spent."

Iteration is a protocol, not magic. An iterable defines __iter__, which returns an iterator; an iterator defines __next__ (return the next item, raise StopIteration when done) and an __iter__ that returns itself. A for loop is sugar for “call iter(), then next() until StopIteration.” A generator is the easy way to get one: yield makes the compiler write the whole protocol for you, including the lazy, resumable state.

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")

class iterator: [3, 2, 1]
generator     : [3, 2, 1]
10 20
exhausted

4 · The real cost of your Python

The most common performance bug isn't slow code — it's the wrong container. Picture a task queue that works beautifully in testing: tasks.append(job) to add, tasks.pop(0) to grab the next one. Ship it, let the queue reach a few hundred thousand entries, and throughput quietly collapses — not because any single line got slower, but because pop(0) on a list secretly shifts every remaining element down one slot, and doing that inside a loop turns a linear job into a quadratic one. Nobody wrote a slow algorithm; someone picked a list where a deque belonged. This section is about seeing that before it pages you at 2 a.m.

The analogy is the difference between a filing cabinet and a conveyor belt. A Python list is a filing cabinet: grabbing folder number 5,000 is instant (you know exactly which drawer), but removing the front folder means physically sliding every folder behind it forward to close the gap. A deque is a conveyor belt with an operator at each end: adding or removing from either end is instant, but there's no cheap way to reach into the middle. A set or dict is a coat-check: you don't scan every coat to find yours, you hand over a ticket (the key) and get an answer in one step no matter how many coats are hung.

Why this deserves its own section, above any clever micro-optimization: the container you choose fixes the Big-O of every operation you'll ever do on it, and Big-O is what decides whether your code survives when the input grows 1000×. Swapping x in some_list (which walks the whole list) for x in some_set (one hop to a bucket) can turn a function that's fine on 100 items and hopeless on 100,000 into one that doesn't care about the size at all. You rarely need to write a faster algorithm; you need to reach for the structure whose costs already match your access pattern.

The mistake to watch for is trusting how code reads instead of what it costs. x in things looks identical whether things is a list or a set — same three words — but one is O(n) and the other O(1) on average. Likewise lst.insert(0, x) reads as innocently as lst.append(x), yet one shifts the entire list and the other doesn't. Train your eye to ask, for every collection operation: "which end am I touching, and am I searching by position or by value?" The answer, plus the table below, tells you the real price — and the fix is almost always a one-line change of container, not a rewrite.

Two lines that look equally innocent can differ by orders of magnitude at scale. Choosing the right built-in data structure is usually a bigger win than any micro-optimization. The table gives the amortized Big-O of common operations; the practical headline is: list.pop(0)/insert(0, x) are O(n) (everything shifts), collections.deque gives O(1) at both ends, and membership testing is O(n) in a list but O(1) in a set/dict.

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

x in list : 61.11 ms/1000
x in set  : 0.05 ms/1000
list.pop(0)     is O(n): shifts every element
deque.popleft() is O(1): 0

5 · The __eq__ / __hash__ contract

Here's a bug that will waste an afternoon of your life if you don't know this rule. You write a tidy little Money or Point class, give it an __eq__ so equal values compare equal, drop a few into a set to deduplicate — and the set keeps the duplicates anyway. Two objects you can prove are equal (the interpreter agrees: a == b is True) both sit in the set side by side. Nothing errors. It just silently does the opposite of what dedup is for. The cause is a contract you didn't know you'd signed the moment you touched __eq__.

The way to feel it: a hash-based container is a library with numbered shelves. When you add a book, the librarian computes a shelf number from the book's hash and files it there; when you later ask "do we have this book?", she recomputes the shelf number and looks only on that one shelf. That's what makes lookups O(1) — she never scans the whole library. But it only works if equal books always produce the same shelf number. If two copies of the same book hash to different shelves, she checks shelf 12, doesn't find it on shelf 40, and cheerfully files a second copy. Equal-but-different-hash means the container never even compares them.

Hence the ironclad rule, and the reason it gets its own section: equal objects must hash equal. Equality and hashing are not two independent features you can tune separately — they're two halves of one promise, and hash-based containers break in bizarre, silent ways when the halves disagree. Python tries to protect you: define __eq__ and it removes the default __hash__, making your type unhashable so a wrong hash can't sneak in. That "helpful" behavior is itself a trap if you don't expect it — your object suddenly can't be a set member or dict key at all, raising TypeError.

The mistake, stated plainly: overriding __eq__ to compare by value while leaving the hash on Python's default (identity-based, one per object) — or worse, computing a hash from fields you didn't include in equality, or from fields that can change after the object is stored. A mutable key whose hash drifts after insertion is the nastiest version: the librarian filed it on shelf 12, someone edited it so it now hashes to shelf 40, and it's effectively lost. The fix is always the same discipline: hash exactly the fields you compare, and prefer making value objects immutable (@dataclass(frozen=True)) so their hash can never move underneath the container.

Hash-based containers (set, dict) rely on a contract: if two objects are equal, they must have the same hash. Break it and you get real bugs. Define __eq__ without __hash__ and Python makes your type unhashable (can't be a set member or dict key). Provide an inconsistent hash and equal objects land in different buckets, so a set keeps duplicates. The fix is always the same: hash exactly the fields you compare.

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

unhashable: TypeError
leaked duplicates: 2
correct dedup   : 1

6 · Floating-point pitfalls

Type 0.1 + 0.2 into a Python prompt right now. You will not get 0.3 — you'll get 0.30000000000000004, and 0.1 + 0.2 == 0.3 comes back False. Every developer meets this moment and has the same first reaction: "Python is broken." It isn't, and neither is your hardware. The same expression prints the same wrong-looking answer in C, Java, JavaScript, and Go. What's actually happening is one of the most consequential facts in all of computing, and getting it wrong has real teeth: it's how billing systems drift by a cent, how a while balance != 0 loop runs forever, and how "the totals don't reconcile" tickets are born.

The analogy that dissolves the mystery is base-three. Try to write one-third in decimal and you get 0.3333… — it never terminates, so any finite decimal you write down is slightly wrong. Computers store numbers in binary fractions (halves, quarters, eighths…), and in that system the perfectly ordinary decimal 0.1 is exactly as unterminating and unstorable as one-third is for us. So the machine keeps the closest binary value it can fit in 64 bits — a hair off — and when you add two "hairs off" you sometimes get a visible smudge. The number was never really 0.1; it was always the nearest binary neighbour.

Why give it a section instead of a footnote? Because the fix isn't "be careful" — it's a set of habits you apply before the bug happens. Once you accept that a float is an approximation, three rules follow directly: never test two floats with == (compare with a tolerance via math.isclose); never represent money as a float (use decimal.Decimal or integer cents, where base-10 arithmetic is exact); and don't assume rounding works the way school taught you. That last one surprises people: Python's round uses banker's rounding — round half to even — so round(2.5) is 2, not 3. It's not a bug either; it's a deliberate choice that reduces cumulative bias when you round millions of values.

The mistake in one sentence: reaching for float whenever a number "has a decimal point," including for currency and for exact comparisons, because it looks exact when it prints. The moment a value must be exact — dollars and cents, a loop that must hit zero precisely, an equality check that must be trustworthy — a binary float is the wrong tool, and the right one (Decimal, integer cents, or tolerance-based comparison) is a one-import change. Correctness first: pick the representation that matches what "correct" means for your problem.

Floats are IEEE-754 binary fractions, so decimals like 0.1 and 0.2 have no exact representation — their sum is a hair off 0.3, and == says so. Never compare floats with ==; use math.isclose. For money and other exact-decimal needs use decimal.Decimal. And note Python's round uses banker's rounding (round half to even), so round(2.5) == 2.

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

0.1 + 0.2      : 0.30000000000000004
== 0.3         : False
math.isclose   : True
Decimal money  : 0.3
round(2.5)     : 2
round(3.5)     : 4

7 · Property-based thinking

Every bug that reaches production passed all the tests. Sit with that for a second. Your test suite was green; the failure still happened. The reason is almost always the same: example-based tests only check the inputs you thought of, and bugs live in the inputs you didn't — the empty list, the duplicate, the negative number, the string with an emoji in it, the value exactly at the boundary. You can't out-imagine the edge cases by hand; there are too many, and the nasty ones are precisely the ones that never crossed your mind. Property-based thinking is how you stop guessing inputs and start pinning down truths.

The shift is from checking answers to checking rules. An example test says "sort([3,1,2]) should give [1,2,3]" — one input, one blessed output, and you had to compute that output yourself (so if your arithmetic was wrong, the test enshrines the wrong answer). A property says something that must hold for every input: "whatever list I sort, the result is in non-decreasing order, and it's a rearrangement of the original with the same length." You don't state the answer; you state what makes any answer correct — then let the machine throw a thousand random inputs at it and check the rules hold on all of them.

Think of it like inspecting a bridge. Example testing is driving a few specific trucks across and seeing if it holds. Property testing is asserting the structural laws — "no beam exceeds its stress limit under any load in the rated range" — and then simulating thousands of loads. The laws catch the truck you never thought to drive. In code, good properties are often relationships you can check without knowing the answer: a round-trip (decode(encode(x)) == x), an invariant preserved (a shuffled list is a permutation of the original), or agreement with a slow-but-obviously-correct reference implementation.

The mistake beginners make is writing a "property" that's really just the implementation restated — for example, testing your sort by comparing it to sorted() and calling that a property. If your two ways of computing the answer share the same blind spot, they'll agree on the same wrong result. Strong properties describe the shape of a correct answer from the outside (ordered, same elements, same length) rather than recomputing it a second way. Libraries like hypothesis generate the inputs, and — crucially — shrink any failure down to the smallest example that still breaks, handing you a minimal reproduction instead of a 200-element random list. Here we do the generation by hand to show the idea, but the mindset is the payoff: ask "what must be true for all inputs?" long before you ask "what's the answer for this one?"

Example-based tests check a few hand-picked inputs; property-based thinking asks what must hold for every input and checks it against many generated cases. A correct sort, for instance, must output an ordered sequence that is a permutation of the input with the same length — three properties that catch far more bugs than a couple of literal examples. (Libraries like hypothesis automate the generation; here we do it by hand to show the idea.)

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")

all sort properties held over 1000 random inputs

def running_sum(xs):
    total = 0
    for i, x in enumerate(xs):
        total += x
        assert total == sum(xs[:i + 1])   # invariant
    return total

print(running_sum([2, 4, 6]))   # 12

12

class Upto:
    def __init__(self, n): self.i, self.n = 0, n
    def __iter__(self): return self
    def __next__(self):
        if self.i >= self.n: raise StopIteration
        self.i += 1
        return self.i - 1

def upto(n):
    i = 0
    while i < n:
        yield i
        i += 1

print(list(Upto(4)))   # [0, 1, 2, 3]
print(list(upto(4)))   # [0, 1, 2, 3]

[0, 1, 2, 3]
[0, 1, 2, 3]

from collections import deque

lst = list(range(1_000_000))
dq = deque(range(1_000_000))

# list.pop(0): O(n) -- shifts ~1M elements each call
# deque.popleft(): O(1)
print(lst.pop(0))     # 0  (but O(n): avoid in a loop)
print(dq.popleft())   # 0  (O(1): correct for a queue)

0
0

class Coord:
    def __init__(self, x, y): self.x, self.y = x, y
    def __eq__(self, o): return isinstance(o, Coord) and (self.x, self.y) == (o.x, o.y)
    def __hash__(self): return hash((self.x, self.y))

seen = {}
seen[Coord(1, 2)] = 'a'
seen[Coord(1, 2)] = 'b'          # same key -> overwrites
print(len(seen), list(seen.values()))   # 1 ['b']

1 ['b']

import random

def sorted_unique(xs):
    return sorted(set(xs))          # the implementation under test

for _ in range(2000):
    xs = [random.randint(0, 9) for _ in range(random.randint(0, 15))]
    out = sorted_unique(xs)
    assert out == sorted(out), 'sorted'
    assert len(out) == len(set(out)), 'unique'
    assert set(out) == set(xs), 'covers distinct values'
print('all properties held')

all properties held