Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 63 ยท Real-World Projects

Project: A Stress-Testing Framework

Turn the stress-testing loop into a reusable framework: seeded generators, a brute force, a checker for many valid answers, crash detection and an automatic input minimizer.

In stress testing with a brute force you wrote the loop by hand: generate, solve twice, compare, stop at the first mismatch. That works, but you rewrote it for every problem and the shrinking code was tied to one input type. In this project you build the loop once, as a small framework you can paste into any practice session. It has four pluggable parts, a failure report, and a minimizer that works on any kind of input.

The design goal is that a new problem needs only four small functions: the fast solution, the brute force (or a checker), a generator and a list of "smaller version" ideas. Everything else, such as seeding, catching crashes, minimizing and reporting, lives in the framework. We build it in three stages, test it on a real bug, and then extend it to problems with many valid answers.

flowchart TD
  G["gen(rng)"] --> X["input x"]
  X --> F["fast(x)"]
  F -->|"exception"| CR["crash"]
  F -->|"output"| J{"Judge"}
  J -->|"brute force:<br/>fast(x) == brute(x)"| OK1["ok / wrong"]
  J -->|"checker(x, out)"| OK2["ok / invalid"]
  CR --> M["minimize(x)"]
  OK1 --> M
  OK2 --> M
  M --> REP["Report: test number,<br/>original, minimal, result"]

Every input ends as ok, wrong, invalid or crash; any failure goes to the minimizer.

The framework

The core is a function stress with these parameters:

  • fast is the solution under test. It takes a parsed input and returns an answer.
  • brute returns the reference answer for the same input. It is not needed when you pass a checker.
  • gen takes a random.Random object and returns one input.
  • shrink_candidates takes a failing input and yields smaller inputs worth trying.
  • checker (optional) takes the input and the output and says whether the output is valid.
  • tests and seed control how many inputs are tried and which random streams are used.

Two decisions make the framework pleasant to use. First, every test gets its own generator, seeded from seed and the test number, so "test 8 failed" is enough to reproduce a failure without rerunning tests 1 to 7. Second, an exception in the fast solution is a failing result, not a crash of the harness, which matters because runtime errors are one of the verdicts from verdicts and debugging.

The minimizer is a loop: ask shrink_candidates for smaller variants of the current input, adopt the first one that still fails, and repeat until none does. This is the greedy shrinking from the earlier lesson, now independent of the input's type.

Python The framework, tested on a buggy maximum subarray

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The buggy version fails at test 28, and the minimizer reduces the failing list [-1, -4] to [-1]. The fixed version survives 2,000 tests and the call returns None, the framework's way of saying "no counterexample found". Notice that non_empty filters the shrinks: a minimizer that produced an empty list would "find" a failure that the problem forbids. A shrinker must keep inputs valid.

Crashes are failures too

If fast raises an exception, outcome returns ("crash", message), and the same minimizer shrinks the input that triggers it. The next TryIt feeds the framework a solution that reads one position too far, which only happens for lists of three or more elements.

Python Minimizing an input that makes the solution crash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result is a list of three zeros: the shortest list for which the bug triggers, and with every value reduced to the simplest number. That tells you immediately that the bug depends on the length, not on the values.

Problems with many valid answers

Brute-force comparison needs a single right answer. For "print any valid answer", pass a checker instead. The checker takes the input and the solution's output and returns True if the output is acceptable, and it must be written independently from the solution.

Take "find positions i < j with a[i] + a[j] == target, or (-1, -1) if none". Our buggy solution stores each value before looking up its partner, so with the input [4] and target 8 it pairs the element with itself.

Python Checker-based stress test with a minimal counterexample

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The minimal case is a single-element list and a target equal to twice the element. Different valid answers on larger inputs never trigger a false alarm, because the checker looks at the property rather than at one expected output.

A checker can be wrong too. If the checker is too lenient (it accepts (0, 0)), real bugs pass; if it is too strict, it rejects correct answers. Test the checker on a few hand-made right and wrong outputs first, as the judge project does with its two_sum_checker.

Improving the framework

Once the basics work, these extensions are worth the few lines they cost:

  1. Better generators. Mix sizes: usually tiny, sometimes the maximum allowed by the brute force, and occasionally special shapes such as sorted, constant or alternating lists. The table in the earlier lesson lists useful shapes.
  2. Type-aware shrinkers. For a graph, shrink by deleting a vertex and its edges. For a string, delete a character or replace a letter with a. For a tree, replace a vertex's parent with its grandparent. Always keep the input valid.
  3. A time guard. Pair the framework with the line budget from the local judge project so a hang becomes a reported failure instead of a frozen page.
  4. Statistics. Count how often generated inputs hit interesting cases (ties, n = 1, all-equal values). If a case never appears, your generator is not testing it.
  5. Multiple seeds. Report the seed with every failure so you can re-run exactly that experiment in a different session.

Even a perfect framework only helps with correctness. The speed of the solution is a separate question answered by estimating time and memory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does each test get its own random generator seeded from the test number?

    With a per-test seed, 'test 28 failed' is a complete bug report: you can regenerate that exact input directly.
  2. 2. What must a shrinker never do?

    An invalid input (such as an empty list when n >= 1) may fail for a reason that has nothing to do with the real bug, so the minimizer would report a false counterexample.
  3. 3. When is a checker needed instead of a brute force comparison?

    If several outputs are right, equality with the brute force's answer would flag correct solutions as wrong. A checker validates the property instead.
  4. 4. In the framework, what does it mean when stress returns None?

    None means all generated tests passed. That is strong evidence but not a proof, since only those inputs were tried.
  5. 5. The minimizer reduced a crashing list to [0, 0, 0]. What does this tell you?

    Once values are simplified to zero and one element removed no longer fails, only the length of three or more matters.

Summary

  • A reusable stress framework needs four pieces: fast solution, reference (brute force or checker), seeded generator and a shrinker.
  • Seed every test separately and report the test number so any failure is reproducible.
  • Treat exceptions as failures and minimize them like wrong answers.
  • Shrinkers must keep inputs valid: delete elements, move values toward zero, and respect the problem's constraints.
  • Use a checker for problems with many valid answers, and test the checker itself.
  • A passing stress test is evidence of correctness on small inputs, not a proof, and says nothing about speed.

Next: Project: An Elo-Style Rating Calculator