Build a stress tester: brute force vs optimal

A stress tester is a small program that checks a fast solution against a brute force on thousands of small random inputs. It stops at the first input where the two answers differ, shrinks that input for as long as it still fails, and prints what is left as a test you can keep. You write it once, in about 90 lines of Python; for every later problem you add only a generator of random cases, the brute force and the fast solution. The lessons on brute force to optimal and on edge cases ran a stress test as a loop inside one program. This lesson builds the reusable tool, runs it on an original problem, where it finds two bugs in a short O(n) solution, and measures which generators and which shrinking moves make it work.

What you write, and what the harness does

For each problem you write three functions:

• gen(rng) makes one small random case, using only the random.Random object it is given. Taking every random number from that object is what makes a trial repeatable.
• brute(case) solves the case in the plainest way you can think of, however slow: every block, every pair, every order. It is the judge, so it should share no idea with the fast solution, or it will share that solution’s bugs.
• fast(case) is the solution under test.

The harness does the rest, the same way for every problem:

1. One seed per trial. Trial t of a run with seed s uses random.Random(s * 1_000_000 + t). When trial 6 fails, gen(random.Random(1000006)) rebuilds its case without replaying trials 1 to 5.
2. Separate copies. Each solution gets its own copy.deepcopy of the case. A solution that sorts its input, or overwrites it with running totals, would otherwise change what the other solution sees, and the case in the report would no longer be the one that failed.
3. A crash is an answer. An exception becomes a Crash value that equals only the same crash, so an IndexError on an edge case is reported with its input instead of ending the run.
4. Shrinking. The failing case is replaced by a simpler one that still fails, again and again, until none of three moves keeps the failure: drop one item, move one value nearer to 0 (to 0, to half, or by one step), or move two values one step nearer to 0 at once. An optional valid(case) keeps the shrinker inside the problem’s limits, so that a real failure is not shrunk into an input the problem rules out, such as an empty list.
5. A report you can act on. The harness prints the seed, every step of the shrinking, both answers and an assert line ready to paste into your tests.

"""A stress tester written once and reused for every problem.

For each problem you write gen(rng), which makes one small random case with a seeded random.Random; brute(case),
which solves it slowly but plainly; and fast(case), the solution under test. stress() runs both until their
answers differ, shrinks the failing case and prints it as a regression test.
"""
import copy
import random
from dataclasses import dataclass


@dataclass(frozen=True)
class Crash:
    """The 'answer' of a solution that raised an exception: equal only to the same crash."""

    error: str

    def __repr__(self):
        return f"raised {self.error}"


def answer(solve, case):
    """solve's answer on its own copy of case, so a solution that changes its input cannot mislead the other one."""
    try:
        return solve(copy.deepcopy(case))
    except Exception as error:  # a crash is an answer too, and never the right one
        return Crash(type(error).__name__)


def step(value):
    """One step nearer to 0."""
    return value - 1 if value > 0 else value + 1


def drop_one(case):
    """Simpler cases with one item fewer."""
    for i in range(len(case)):
        yield case[:i] + case[i + 1 :]


def nearer_one(case):
    """Simpler cases with one value nearer to 0: 0 itself first, then half the value, then one step."""
    for i, value in enumerate(case):
        half = abs(value) // 2 * (1 if value > 0 else -1)
        for nearer in dict.fromkeys((0, half, step(value))):
            if abs(nearer) < abs(value):
                yield case[:i] + [nearer] + case[i + 1 :]


def nearer_two(case):
    """Simpler cases with two values one step nearer to 0 at once, which keeps the total's parity."""
    for i in range(len(case)):
        for j in range(i + 1, len(case)):
            if case[i] and case[j]:
                both = case.copy()
                both[i], both[j] = step(case[i]), step(case[j])
                yield both


def shrink(case, fails, valid, moves=(drop_one, nearer_one, nearer_two)):
    """Move to the first simpler case that still fails, again and again; return every case on the way."""
    path = [case]
    while True:
        for smaller in (simpler for move in moves for simpler in move(path[-1])):
            if valid(smaller) and fails(smaller):
                path.append(smaller)
                break
        else:
            return path


def stress(brute, fast, gen, trials=2000, seed=1, valid=lambda case: True):
    """Compare fast with brute on random cases; print and return the first failing case, shrunk, or None."""

    def fails(case):
        return answer(fast, case) != answer(brute, case)

    for trial in range(1, trials + 1):
        trial_seed = seed * 1_000_000 + trial  # one seed per trial: gen(random.Random(trial_seed)) replays it
        case = gen(random.Random(trial_seed))
        if fails(case):
            path = shrink(case, fails, valid)
            small, want = path[-1], answer(brute, path[-1])
            print(f"trial {trial} (seed {trial_seed}): {case}")
            for simpler in path[1:]:
                print(f"  still fails: {simpler}")
            print(f"{fast.__name__} gives {answer(fast, small)!r}, {brute.__name__} gives {want!r}")
            print(f"regression test: assert {fast.__name__}({small}) == {want!r}")
            return small
    print(f"{trials:,} trials, no difference")
    return None

A problem to test: the longest equal-sum split

For example, [4, 2, -1, 3, 0] gives 4: the block [2, -1, 3, 0] and the rest [4] both total 4. [5, 5] gives 1, [1, 2] gives 0 because an odd total cannot be halved, and [7] gives 0 because a single item cannot be shared.

The brute force tries every block and compares its total with the total of the rest: O(n²), and short enough to check line by line. The fast version starts from a fact about fair cuts: both sides total half of the whole list, so a block is fair exactly when its own total is half, the list’s total divided by 2. Let prefix[i] be the running total of the items up to and including item i. The block that ends at item i and starts right after position j then totals prefix[i] - prefix[j], so at each item the fast version looks up the earliest position whose running total was prefix[i] - half. A dictionary, first, remembers where each running total appeared first, and the earliest start gives the longest block: one pass over the list, O(n) time on average.

"""The longest equal-sum split: a block of consecutive items against the rest of the list."""


def split_brute(points):
    """Every block, with its total against the total of the rest: O(n^2), and plain enough to trust."""
    n, total, best = len(points), sum(points), 0
    for start in range(n):
        block = 0
        for end in range(start, n):
            block += points[end]
            length = end - start + 1
            if length < n and block == total - block:  # the rest keeps at least one item
                best = max(best, length)
    return best


def split_v1(points):
    """O(n): the block after position j up to position i is fair when prefix[i] - prefix[j] is half the total."""
    total = sum(points)
    if total % 2:  # an odd total has no half
        return 0
    half, first, prefix, best = total // 2, {}, 0, 0
    for i, p in enumerate(points):
        prefix += p
        j = first.get(prefix - half)  # where the earliest running total that leaves `half` for the block ended
        if j is not None:
            best = max(best, i - j)
        first.setdefault(prefix, i)
    return best


if __name__ == "__main__":
    examples = [([4, 2, -1, 3, 0], 4), ([5, 5], 1), ([1, 2], 0), ([7], 0)]
    for solve in (split_brute, split_v1):
        answers = [solve(points) for points, _ in examples]
        verdict = "all as expected" if answers == [want for _, want in examples] else "WRONG"
        print(f"{solve.__name__:<11} {answers}  {verdict}")

split_brute [4, 1, 0, 0]  all as expected
split_v1    [4, 1, 0, 0]  all as expected

Both functions give the expected answers on the four examples. That is as much as the examples of a problem statement can show.

Run the harness: two bugs, one at a time

stress_split.py gives the harness a generator of 1 to 8 values from −3 to 3 and runs it on split_v1, then on the two corrections it leads to:

"""Stress-test three versions of the equal-sum split against the brute force."""
from fixes import split_fast, split_v2
from harness import stress
from split import split_brute, split_v1


def small_points(rng):
    """1 to 8 items from -3 to 3: with so few values, equal totals and fair splits are common."""
    return [rng.randint(-3, 3) for _ in range(rng.randint(1, 8))]


def valid(points):
    return len(points) >= 1  # the problem promises at least one item


for fast in (split_v1, split_v2, split_fast):
    print(f"--- {fast.__name__}")
    stress(split_brute, fast, small_points, valid=valid)

--- split_v1
trial 6 (seed 1000006): [1, -2, 3, 0, -3, -1]
  still fails: [1, -2, 3, -3, -1]
  still fails: [0, -1, 3, -3, -1]
  still fails: [0, 0, 2, -3, -1]
  still fails: [0, 2, -3, -1]
  still fails: [2, -3, -1]
  still fails: [1, -2, -1]
  still fails: [0, -1, -1]
split_v1 gives 1, split_brute gives 2
regression test: assert split_v1([0, -1, -1]) == 2
--- split_v2
trial 15 (seed 1000015): [-2, -1, 0, 3]
  still fails: [-2, -1, 3]
  still fails: [-1, -1, 2]
  still fails: [0, -1, 1]
  still fails: [-1, 1]
  still fails: [0, 0]
  still fails: [0]
split_v2 gives 1, split_brute gives 0
regression test: assert split_v2([0]) == 0
--- split_fast
2,000 trials, no difference

The first bug. Trial 6 failed on a list of six values, and seven steps later the harness had [0, -1, -1]. The brute force finds the fair block [0, -1], which totals −1 like the rest, [-1]; split_v1 says 1. The block starts at the first item, and that is what split_v1 cannot see: a block that starts at item 0 needs the running total from before the first item, which is 0 at position −1, and first never stored it. The correction is one entry, first = {0: -1}, and it gives split_v2.

The second bug. The harness then failed split_v2 at trial 15 and shrank its case to [0]. A single item cannot be cut fairly, because the rest would be empty, yet split_v2 returns 1. The new entry caused it: when the total is 0, half is 0 too, and at the last item the lookup finds position −1, which makes the whole list the block. The correction uses the rule from the statement. A block that leaves at least one item for the rest must miss the first item or the last one, so split_fast searches points[1:] and points[:-1] separately, with the same loop, and keeps the longer result. It then agreed with the brute force on all 2,000 trials.

"""The two corrections of split_v1 that the stress test leads to."""


def split_v2(points):
    """split_v1 with the empty prefix, whose running total is 0, recorded at position -1."""
    total = sum(points)
    if total % 2:
        return 0
    half, first, prefix, best = total // 2, {0: -1}, 0, 0
    for i, p in enumerate(points):
        prefix += p
        j = first.get(prefix - half)
        if j is not None:
            best = max(best, i - j)
        first.setdefault(prefix, i)
    return best


def longest_block(items, half):
    """The longest block of items whose total is `half`: split_v2's loop, with no rest to protect."""
    first, prefix, best = {0: -1}, 0, 0
    for i, p in enumerate(items):
        prefix += p
        j = first.get(prefix - half)
        if j is not None:
            best = max(best, i - j)
        first.setdefault(prefix, i)
    return best


def split_fast(points):
    """A block that leaves at least one item for the rest misses the first item or the last one: try without each."""
    total = sum(points)
    if total % 2:
        return 0
    return max(longest_block(points[1:], total // 2), longest_block(points[:-1], total // 2))

Notice how the shrinking went. In the first run, four of the seven steps moved two values at once, from [1, -2, 3, -3, -1] to [0, -1, 3, -3, -1] for example, and in the second run three of the six did. Why that move matters is measured further down.

Tiny cases are few enough to try them all

Random trials are a sample. For the very smallest sizes you can afford every case: there are 137,256 lists of 1 to 6 values from −3 to 3, and checking all of them against the brute force takes a second or two in CPython.

"""Tiny cases are few enough to try them all: every list of 1 to 6 values from -3 to 3."""
import itertools

from fixes import split_fast
from split import split_brute

checked = 0
for n in range(1, 7):
    for values in itertools.product(range(-3, 4), repeat=n):
        points = list(values)
        assert split_fast(points) == split_brute(points), points
        checked += 1
print(f"split_fast agrees with split_brute on all {checked:,} lists")

split_fast agrees with split_brute on all 137,256 lists

That is still not a proof that split_fast is right, but a bug in it would now need seven or more items, or larger values, to show itself.

Keep the small case as a regression test

The harness prints each shrunk case as an assert. Keep the case itself, not only its seed. The documentation of Python’s random module promises the same sequence across Python versions only for random(); the rest of the module, randint() included, may change. A seed replays a case on the version that found it, while the printed list replays it everywhere. Here are the two cases kept as tests, run against every version:

"""The two shrunk failures, kept as regression tests and run against every version."""
from fixes import split_fast, split_v2
from split import split_v1

REGRESSIONS = [  # (points, the brute force's answer); each found by stress_split.py
    ([0, -1, -1], 2),  # trial 6, seed 1000006: a fair block that starts at the first item
    ([0], 0),  # trial 15, seed 1000015: the whole list is not a block, the rest would be empty
]
for solve in (split_v1, split_v2, split_fast):
    results = ["ok" if solve(points) == want else "FAILS" for points, want in REGRESSIONS]
    print(f"{solve.__name__:<11}", "  ".join(f"{r:<5}" for r in results).rstrip())

split_v1    FAILS  ok
split_v2    ok     FAILS
split_fast  ok     ok

Each test fails the version it was found in and passes the others, so if a later change brings either bug back, its test fails at once. In a project, put these lines with your other tests, where unittest or pytest runs them on every change.

Small values find bugs: measured

The generator you write decides what the harness can find. This program repeats the search for both bugs with 100 different base seeds and four generators, and records when the first failure came:

"""How the generator decides what the harness finds: 100 base seeds, up to 2,000 trials each."""
import random
from statistics import median

from fixes import split_v2
from split import split_brute, split_v1

GENERATORS = {
    "1-8 items, -3 to 3": lambda rng: [rng.randint(-3, 3) for _ in range(rng.randint(1, 8))],
    "1-8 items, 1 to 9": lambda rng: [rng.randint(1, 9) for _ in range(rng.randint(1, 8))],
    "1-8 items, full range": lambda rng: [rng.randint(-10**9, 10**9) for _ in range(rng.randint(1, 8))],
    "1-100 items, -3 to 3": lambda rng: [rng.randint(-3, 3) for _ in range(rng.randint(1, 100))],
}


def first_failure(fast, gen, seed, trials=2000):
    """The first trial where fast and the brute force differ, as stress() numbers its trials, or None."""
    for trial in range(1, trials + 1):
        case = gen(random.Random(seed * 1_000_000 + trial))
        if fast(case) != split_brute(case):  # these functions never change their input, so no copies
            return trial, case
    return None


print(f"{'generator':<22} {'version':<9} {'found':>9} {'median trial':>13} {'median length':>14}")
for name, gen in GENERATORS.items():
    for fast in (split_v1, split_v2):
        hits = [hit for seed in range(1, 101) if (hit := first_failure(fast, gen, seed))]
        trial = f"{median(t for t, _ in hits):g}" if hits else "-"
        length = f"{median(len(case) for _, case in hits):g}" if hits else "-"
        print(f"{name:<22} {fast.__name__:<9} {len(hits):>5} of 100 {trial:>13} {length:>14}")

generator              version       found  median trial  median length
1-8 items, -3 to 3     split_v1    100 of 100             9              6
1-8 items, -3 to 3     split_v2    100 of 100             8              3
1-8 items, 1 to 9      split_v1    100 of 100          32.5              5
1-8 items, 1 to 9      split_v2      0 of 100             -              -
1-8 items, full range  split_v1      0 of 100             -              -
1-8 items, full range  split_v2      0 of 100             -              -
1-100 items, -3 to 3   split_v1    100 of 100             6             45
1-100 items, -3 to 3   split_v2    100 of 100            19             33

• One to eight values from −3 to 3 found both bugs with every seed. The median run found them at trials 9 and 8, on lists of 6 and 3 items.
• Values from 1 to 9 never found the second bug. A list of positive numbers never totals 0, and the second bug needs a total of 0. The first bug was still found, only later (median trial 32.5). A generator has to make every kind of value the limits allow, zeros and negatives included.
• The full range found neither bug in 2,000 trials, for all 100 seeds. With values up to 10⁹, a block and the rest almost never have equal totals, so every version answers 0 and they all agree. Wide values belong in the speed check.
• Lists of up to 100 items also found both bugs quickly (median trials 6 and 19), but the first failing lists had 45 and 33 items in the median: far too long to read before shrinking, and slower for the brute force.

Shrinking: which moves reach the smallest case

The smallest list on which split_v1 fails has three items, and for split_v2 it is [0]; the program finds both by trying every list of up to three values. How often does shrinking get that far? This program shrinks the first failure of each of 100 seeds with three sets of moves:

"""Which shrinking moves reach the smallest failing case? The first failure of 100 base seeds, three move sets."""
import itertools
import random
from statistics import median

from fixes import split_v2
from harness import drop_one, nearer_one, nearer_two, shrink
from split import split_brute, split_v1

MOVE_SETS = {
    "drop one item": (drop_one,),
    "+ one value nearer 0": (drop_one, nearer_one),
    "+ two values at once": (drop_one, nearer_one, nearer_two),
}


def small_points(rng):
    return [rng.randint(-3, 3) for _ in range(rng.randint(1, 8))]


for fast in (split_v1, split_v2):

    def fails(points, fast=fast):
        return fast(points) != split_brute(points)  # neither changes its input, so no copies are needed

    # The smallest failing length, by trying every list of 1 to 3 items from -3 to 3.
    smallest = min(n for n in range(1, 4) for c in itertools.product(range(-3, 4), repeat=n) if fails(list(c)))
    firsts = []
    for seed in range(1, 101):
        trial = 1
        while not fails(case := small_points(random.Random(seed * 1_000_000 + trial))):
            trial += 1
        firsts.append(case)
    print(f"{fast.__name__}: smallest failing list has {smallest} item{'s' * (smallest > 1)}")
    for name, moves in MOVE_SETS.items():
        ends = [shrink(case, fails, lambda p: len(p) >= 1, moves)[-1] for case in firsts]
        reached = sum(len(end) == smallest for end in ends)
        length = median(map(len, ends))
        print(f"  {name:<21} reached it {reached:>3} times of 100; median length after shrinking {length:g}")

split_v1: smallest failing list has 3 items
  drop one item         reached it  32 times of 100; median length after shrinking 5
  + one value nearer 0  reached it  33 times of 100; median length after shrinking 4
  + two values at once  reached it 100 times of 100; median length after shrinking 3
split_v2: smallest failing list has 1 item
  drop one item         reached it  30 times of 100; median length after shrinking 2
  + one value nearer 0  reached it  30 times of 100; median length after shrinking 2
  + two values at once  reached it 100 times of 100; median length after shrinking 1

Dropping items alone reached the smallest case about a third of the time (32 and 30 runs of 100), and moving single values as well hardly helped (33 and 30). Moving two values at once reached it in all 100 runs, for both bugs. The reason is the total, which both bugs depend on: an odd total has no fair cut, and split_v2 goes wrong only when the total is 0. Every single move changes the total, the failure usually disappears with it, and the shrinker stops early at a case such as [2, -2], where no one move keeps the failure. Moving two values one step each changes the total by 0 or by 2, so an even total stays even, and when the two values have opposite signs the total does not change at all.

The general rule: a shrinker stops at a case where no single move keeps the failure, and that case can be far from the smallest. When the result still looks large, ask what the failure depends on, and add a move that keeps it.

Time the fast version at full size

Small cases check answers, not speed. For speed, build the largest input the limits allow and time the fast version on it. The brute force cannot judge at that size, with about 2 × 10¹⁰ blocks to total for 200,000 items, so choose large inputs whose answers you can work out. In a list of zeros every cut is fair, so the longest block leaves a single zero: the answer is n − 1. In a list that alternates 10⁹ and −10⁹, only blocks of even length total 0, so the answer is n − 2. Random values add the hardest case for the dictionary, where every running total is different and first grows to about 200,000 entries.

"""Time split_fast at the largest size the limits allow, on inputs whose answers are known without a brute force."""
import random
import time

from fixes import split_fast

N = 200_000  # the problem's limit
rng = random.Random(1)
largest = [
    ("random values", [rng.randint(-10**9, 10**9) for _ in range(N)], None),
    ("all zeros", [0] * N, N - 1),  # any block that leaves one zero is fair
    ("alternating 10^9, -10^9", [10**9, -(10**9)] * (N // 2), N - 2),  # fair blocks have even length
]
for name, points, expected in largest:
    start = time.perf_counter()
    result = split_fast(points)
    seconds = time.perf_counter() - start
    check = "" if expected is None else f", expected {expected:,}"
    print(f"{name:<24} answer {result:>7,}{check} in {seconds:.2f} s")

random values            answer       0 in 0.92 s
all zeros                answer 199,999, expected 199,999 in 0.26 s
alternating 10^9, -10^9  answer 199,998, expected 199,998 in 0.21 s

In the recorded run each input took less than a second, and both known answers came out right. Measure this way once you have a version that the harness can no longer break: speed is worth having only in a solution that is correct.

When the harness itself is wrong

A harness that never fails proves nothing. These are the usual ways one quietly stops working:

• The judge shares the fast solution’s idea. A brute force built on the same running totals would miss the same blocks. Keep it plain.
• The randomness is not seeded per trial. A module-level random.randint() that nothing seeded, or an unseeded random.Random(), gives a failure that you cannot replay, and one generator seeded once ties every trial to the trials before it.
• The generator cannot make the failing shape. Positive values only, distinct values only, or lists that are always sorted can each hide a whole class of bugs, as the measurements above show for zeros.
• Both solutions get the same list object. Without copies, a solution that changes its input changes the judge’s case as well.
• The shrinker leaves the problem’s limits. If a case must have at least one item, say so in valid, or the shrinker may hand you a failure on an empty list that the problem never allows.
• Several answers are right. Had the problem asked for any longest fair block rather than its length, comparing two blocks would report failures that are not there. Check the fast answer instead: is its block fair, and as long as the brute force’s?
• The answers are floating-point numbers. Compare them with a tolerance, for example with math.isclose, not with ==.

The surest test of a harness is a bug you plant on purpose. If it cannot find an off-by-one that you put there, it will not find yours either, and the exercise below works exactly that way.

The same harness in other languages

The loop is the same everywhere. What differs is the seeded generator, and whether a printed seed rebuilds the same case later:

• Python: random.Random(seed). A seed rebuilds the case on the same Python version; only random() is promised to repeat across versions, so keep the case as well.
• Java: new Random(seed). A seed rebuilds the case on any Java: the documentation of java.util.Random fixes its algorithms “for the sake of absolute portability of Java code”.
• C++: std::mt19937 with std::uniform_int_distribution. The standard fixes the engine, whose 10,000th number from a default-constructed mt19937 must be 4123659995, but the algorithms of the distributions are implementation-defined, so another standard library can build a different case from the same seed.
• JavaScript: a generator of your own, because Math.random() cannot be seeded at all. The xorshift generator of the DSA track’s lesson on testing algorithms is a few lines, and your own code replays exactly.
• Go: rand.New(rand.NewPCG(seed, 0)) from math/rand/v2. Name each trial’s subtest after its seed with t.Run, and go test -run 'TestStress/^seed=1000006$' reruns that one trial.

Go’s built-in fuzzing, go test -fuzz, goes further: it makes the inputs itself, minimises a failing one and writes it under testdata/fuzz, where every later go test runs it as a regression test. In a Python project, the Hypothesis library plays the same part. It shrinks failures and saves them in a local database to replay on the next run, but its documentation recommends against relying on that database for the correctness of your tests, one more reason to keep the shrunk case in the test itself.

Practise: write your own stress()

The exercise asks for a compact version of this harness that returns the shrunk case instead of printing it, with two of the three moves. Its sample tests plant five functions, among them an off-by-one, a bug that needs two equal values to show, a crash and a correct function that sorts the list it is given.

def brute(values):  # pairs i < j with values[i] > values[j]
    return sum(values[i] > values[j] for i in range(len(values)) for j in range(i + 1, len(values)))

def misses_last(values):  # never pairs anything with the last item
    return sum(values[i] > values[j] for i in range(len(values)) for j in range(i + 1, len(values) - 1))

stress(brute, misses_last, lambda rng: [rng.randint(0, 99) for _ in range(rng.randint(0, 6))])  # [1, 0]

import copy
import random


def stress(brute, fast, gen, trials=2000, seed=0):
    """Return the first case where fast and brute differ, shrunk until no simpler case still fails; or None."""
    # Replace this line with your code.
    return None

import sys

from stress import stress

LINE_LIMIT = 3_000_000


def count_brute(values):
    """Pairs i < j with values[i] > values[j], by checking every pair: the judge."""
    return sum(values[i] > values[j] for i in range(len(values)) for j in range(i + 1, len(values)))


def count_misses_last(values):
    """A planted off-by-one: it never pairs anything with the last item."""
    return sum(values[i] > values[j] for i in range(len(values)) for j in range(i + 1, len(values) - 1))


def count_ties(values):
    """A planted mistake that needs two equal values to show: >= instead of >."""
    return sum(values[i] >= values[j] for i in range(len(values)) for j in range(i + 1, len(values)))


def count_sorts_input(values):
    """Right answers, but it sorts the list it was given."""
    result = count_brute(list(values))
    values.sort()
    return result


def count_reads_second(values):
    """Raises IndexError on a list with fewer than two items."""
    first, second = values[0], values[1]  # the planted crash: IndexError on a short list
    return count_brute(values)


def small(rng):
    return [rng.randint(0, 99) for _ in range(rng.randint(0, 6))]


def below_zero(rng):
    return [rng.randint(-99, 0) for _ in range(rng.randint(0, 6))]


def wide(rng):
    """Equal values are rare among 0 to 999, so count_ties fails in only a few trials of every hundred."""
    return [rng.randint(0, 999) for _ in range(rng.randint(0, 6))]


def differs(fast, case):
    try:
        return fast(list(case)) != count_brute(list(case))
    except Exception:
        return True


class NeverStops(BaseException):
    """Not an Exception, so that a harness's own `except Exception` cannot swallow it."""


def limited(run):
    """Call run(), but stop it after LINE_LIMIT executed lines: a shrinker that never ends fails instead of hanging."""
    executed = 0

    def count_lines(frame, event, arg):
        nonlocal executed
        if event == "line":
            executed += 1
            if executed > LINE_LIMIT:
                raise NeverStops
        return count_lines

    sys.settrace(count_lines)
    try:
        return run()
    except NeverStops:
        message = f"stress did not finish within {LINE_LIMIT:,} lines: does every move bring a value nearer to 0?"
        raise AssertionError(message) from None
    finally:
        sys.settrace(None)


def minimal(fast, case):
    """True when no single item can go and no value can move one step nearer 0 while fast still fails."""
    smaller = [case[:i] + case[i + 1 :] for i in range(len(case))]
    nearer = [case[:i] + [v - 1 if v > 0 else v + 1] + case[i + 1 :] for i, v in enumerate(case) if v != 0]
    return not any(differs(fast, c) for c in smaller + nearer)


def test_agreeing_functions():
    """Two functions that always agree: stress returns None"""
    assert stress(count_brute, count_brute, small) is None


def test_finds_the_off_by_one():
    """count_misses_last: stress returns a case on which it really fails"""
    case = stress(count_brute, count_misses_last, small)
    assert case is not None, "stress returned None, but count_misses_last is wrong on many small lists"
    assert differs(count_misses_last, case), f"count_misses_last is right on {case}"


def test_shrunk_to_a_minimal_case():
    """The case for count_misses_last is minimal: no item can go, no value can move nearer 0"""
    case = stress(count_brute, count_misses_last, small)
    assert case is not None, "stress found no failing case"
    assert minimal(count_misses_last, case), f"{case} can still be made smaller or simpler, and it would still fail"


def test_negative_values_move_up():
    """Negative values shrink towards 0 too: count_misses_last on values from -99 to 0"""
    case = limited(lambda: stress(count_brute, count_misses_last, below_zero))
    assert case is not None, "stress found no failing case"
    assert differs(count_misses_last, case), f"count_misses_last is right on {case}"
    assert minimal(count_misses_last, case), f"{case} is not a minimal failing case"


def test_rare_bug_within_2000_trials():
    """count_ties fails only on lists with two equal values: stress still finds it"""
    case = stress(count_brute, count_ties, wide, trials=2000)
    assert case is not None, "no failing case in 2,000 trials: does stress run every trial?"
    assert differs(count_ties, case) and minimal(count_ties, case), f"{case} is not a minimal failing case"


def test_each_function_gets_its_own_copy():
    """A right answer from a function that sorts its input is not a failure"""
    assert stress(count_brute, count_sorts_input, small) is None, (
        "count_sorts_input gives right answers; did count_brute see the list after it was sorted?"
    )


def test_a_crash_is_a_failure():
    """An exception from the fast function counts as a wrong answer"""
    case = stress(count_brute, count_reads_second, small)
    assert case is not None, "count_reads_second raises IndexError on short lists"
    assert len(case) < 2, f"{case} is not the smallest case that makes count_reads_second raise"


def test_same_seed_same_case():
    """The same seed finds the same case again, so a failure can be replayed"""
    first = stress(count_brute, count_ties, wide, seed=7)
    again = stress(count_brute, count_ties, wide, seed=7)
    assert first is not None, "no failing case for count_ties with seed 7"
    assert first == again, f"seed 7 found {first}, then {again}: does every trial seed its own random.Random?"

Interview questions

Fresher · Why do stress tests use tiny random inputs rather than large ones?

Because the bugs they hunt live in coincidences and boundaries: an empty part, a total of 0, two equal values, a block that starts at the first item. A few small values produce those coincidences all the time, while random values up to 10⁹ almost never repeat. Small cases also keep the brute force fast enough to judge thousands of trials a second, and a failing case of three numbers can be traced by hand, while one of fifty cannot. In this lesson’s measurements, one to eight values from −3 to 3 found both bugs with every seed, and the median run found them at trials 9 and 8, while the full range found neither in 2,000 trials. Large inputs still have a job: one timed run at the largest size the limits allow checks the speed.

Key takeaways

• Write the stress tester once. For each problem, add gen, brute and fast, and let it compare them on thousands of small random cases.
• Give every trial its own seed and print it, but keep the shrunk case itself as the regression test: a seed may not rebuild the case on another Python version.
• Run each solution on its own copy of the case, and count a crash as an answer.
• Generate short lists of small values, zeros and negatives included. Here they found both bugs by about the tenth trial in the median run, while values up to 10⁹ found neither in 2,000.
• Shrink with moves that keep what the failure depends on: moving two values at once took the shrinker to the smallest case in 100 runs of 100, against about 30 without it.
• Check speed separately, at the largest size the limits allow, on inputs whose answers you can work out.