Skip to main content

Properties catch what examples miss

Level 5: Level 5: Judging Code You Did Not Writemedium24 minproperty testinginvariantstest designverification

When you run out of examples, assert a property that must hold for every input and search for the smallest input that violates it.

The limit of examples

An example test says "this input gives that output". It is precise, it is easy to read, and it covers exactly one point in an infinite space. You can write twenty of them and still miss the case that matters, because you chose all twenty and you chose them from the same mental model that wrote the code.

A property is a claim that holds for every valid input. You do not have to guess which input breaks it. You write the claim once and let a loop go looking.

Four kinds cover most of what you will need.

Round trip

Encoding then decoding must give back what you started with.

for n in range(1, 200):
    original = "a" * n
    assert decode(encode(original)) == original

Invariant

Something must be true of the output no matter what went in. Splitting a bill preserves the total. Sorting preserves the multiset of elements. A discount never produces a negative price.

parts = split_evenly(total, count)
assert sum(parts) == total                  # nothing was created or lost
assert max(parts) - min(parts) <= 1         # the split is actually even

Idempotence

Applying it twice is the same as applying it once. True of normalizing, trimming, deduplicating, and most "clean this up" functions, and very often false in the implementation.

assert normalize(normalize(text)) == normalize(text)

Agreement with something obviously correct

A slow, dull, clearly-right implementation is a specification you can execute. The fast one must agree with it on every input.

Check yourself
Run-length encoding turns 'aaab' into 'a3b1', and the decoder walks the code two characters at a time reading a letter then a count. What is the smallest run of one repeated letter that breaks the round trip?

Searching for the smallest violation

Once you have a property, finding a counterexample is a loop. Start small and stop at the first failure, because the smallest failing input is the easiest one to reason about.

def first_round_trip_failure(limit):
    for n in range(1, limit + 1):
        original = "a" * n
        try:
            if decode(encode(original)) != original:
                return n
        except Exception:
            return n            # a crash is a violation too
    return -1

The try matters. A property can be violated by a wrong answer or by an exception, and a search that only handles the first stops at the second. This is one of the few places where catching Exception broadly is right: inside a probe you genuinely do want every failure mode to count as a failure, and the exception is being converted into a verdict rather than discarded.

Check yourself

You are reviewing split_evenly(total, parts), which should return as many whole numbers as parts asks for, summing to total, differing by at most 1. Sort each assertion by whether it is a property worth checking or a restatement of the implementation.

sum(result) == total
result[0] == total // parts + total % parts
max(result) - min(result) <= 1
len(result) == parts
all(x == result[0] for x in result[1:])

Where properties come from

You do not invent them. You read the contract and translate each promise into something executable.

The contract saysThe property is
"splits the total between them"sum(parts) == total
"evenly"max(parts) - min(parts) <= 1
"returns a sorted copy"sorted(result) == result and sorted(original) == result
"removes duplicates"len(set(result)) == len(result)
"never charges more than the cap"result <= cap
"cleans up the input"clean(clean(x)) == clean(x)

If a promise in the contract has no executable form, that is worth noticing on its own: it usually means the requirement is not yet specific enough to build against, and asking the question is a more valuable review comment than any test.

Check yourself
A generated sort_by_priority passes all six of your example tests. You have time for one more check. Which is worth the most?

Interview nuance: in a pairing interview, "what property should always hold here?" is a question you can ask about any function on the screen, and it moves the conversation from typing to specification instantly. For a sort it is "the output is a permutation of the input". For a cache it is "a hit returns exactly what was written". Interviewers notice, because most candidates only ever discuss examples.

Check yourself
Your property loop over inputs 1 through 500 reports the first violation at 10. What do you do next?
Worked example (Python)
def encode(text):
    if not text:
        return ""
    out = []
    current = text[0]
    count = 1
    for ch in text[1:]:
        if ch == current:
            count += 1
        else:
            out.append(current + str(count))
            current = ch
            count = 1
    out.append(current + str(count))
    return "".join(out)


print(encode("a" * 9))    # a9,  two characters
print(encode("a" * 10))   # a10, three characters and the pair-wise decoder breaks

Apply

Your turn

The task this lesson builds to.

Write a function first_round_trip_failure(limit) that returns the smallest run length n between 1 and limit for which decode(encode("a" * n)) does not give back "a" * n, or -1 when every length in that range round-trips correctly.

The property: for any text, decode(encode(text)) must equal text. Both functions are in the starter and neither should be changed.

A violation can be a wrong answer or an exception, so your search has to survive both. Keep first_round_trip_failure as the last function in the file.

3 hints and 4 automated checks are waiting in the workspace.

Practice

Make it stick

A second problem on the same idea, so it survives past today.

Your product splits a group order between the people at the table, and an assistant wrote the split_evenly function in the starter. The bill always adds up, so accounting is happy, but customers on large tables have started complaining that one person is charged noticeably more than everyone else.

Write a function first_uneven_total(parts, start) that returns the smallest total between start and start + 100 inclusive for which split_evenly violates one of its two properties, or -1 if none of those totals do.

The two properties: the returned numbers must sum to total, and the largest must exceed the smallest by at most 1. Check both. Keep first_uneven_total as the last function in the file.

3 hints and 4 automated checks are waiting in the workspace.