Testing algorithms: edge cases and stress tests

An algorithm can pass every example in a problem statement and still be wrong: the examples show what the problem means, not where solutions break. This lesson gives you two habits that find the breaks before a judge or a user does. First, a checklist of edge cases that you run every solution through. Second, a stress test: thousands of small random inputs, each solved by your fast solution and by a slow one that is obviously right, until the two disagree. You will also shrink a failing input until removing any one of its elements makes the failure go away, which usually leaves a case small enough for the bug to explain itself.

Write down what the answer should be

A test needs an expected answer, so decide first what the function returns in the awkward cases. Take “the second-largest value of a list”. Is the second-largest of [9, 9, 7] 9 or 7? What does [6, 6, 6] give, or an empty list? The examples below settle it: the second-largest distinct value, and None when there are fewer than two distinct values. Writing that sentence down is half the work of testing; the other half is checking it.

An edge-case checklist

Most bugs hide in the same few places. Before trusting a solution, run it on one input of each kind that applies:

• Lists and arrays: empty; one element; two elements; all values equal; already sorted; sorted in reverse; duplicates, especially of the largest or smallest value; negative numbers and zero; the largest and smallest values the problem allows (in Java, C++ and Go a sum of large values can overflow a fixed-size integer; Python’s integers grow instead); the largest n, to check the running time.
• Strings: the empty string; one character; every character the same; a palindrome; spaces, upper and lower case; characters outside ASCII, such as é or an emoji, if the problem allows them.
• Graphs: a single vertex; no edges at all; several disconnected parts; a self-loop and repeated edges; a cycle; a long path, which makes recursive searches go very deep; a complete graph, the densest case.
• Numbers: 0, 1 and negative values; the limits of the type; for decimals, values such as 0.1 + 0.2, which are not exact in binary floating point.

Here is a first attempt at second_largest, run on one case from each line of the list checklist that applies:

def second_largest(values):
    """The second-largest distinct value, or None with fewer than two distinct values: a first attempt."""
    return sorted(values)[-2]


# (input, expected): one case for each line of an edge-case checklist.
CASES = [
    ([4, 9, 7], 7),  # an ordinary case
    ([1, 2, 3, 4], 3),  # already sorted
    ([4, 3, 2, 1], 3),  # reverse sorted
    ([-8, -3, -5], -5),  # only negative numbers
    ([0, 0, 5], 0),  # zeros
    ([9, 9, 7], 7),  # the largest value twice
    ([6, 6, 6], None),  # all equal: no second value
    ([42], None),  # one element
    ([], None),  # empty
]

for values, expected in CASES:
    try:
        got = second_largest(values)
    except Exception as error:
        got = f"{type(error).__name__}: {error}"
    verdict = "ok  " if got == expected else "FAIL"
    print(f"{verdict} {str(values):<15} expected {expected!r}, got {got!r}")

ok   [4, 9, 7]       expected 7, got 7
ok   [1, 2, 3, 4]    expected 3, got 3
ok   [4, 3, 2, 1]    expected 3, got 3
ok   [-8, -3, -5]    expected -5, got -5
ok   [0, 0, 5]       expected 0, got 0
FAIL [9, 9, 7]       expected 7, got 9
FAIL [6, 6, 6]       expected None, got 6
FAIL [42]            expected None, got 'IndexError: list index out of range'
FAIL []              expected None, got 'IndexError: list index out of range'

Five ordinary-looking cases pass and four fail: the duplicate largest value, the all-equal list, one element and the empty list. Sorting and taking the second-to-last element ignores duplicates and assumes at least two elements. The fixed version walks the list once and keeps the two largest distinct values seen so far:

def second_largest(values):
    """The second-largest distinct value, or None with fewer than two distinct values: one pass, two variables."""
    largest = second = None
    for value in values:
        if largest is None or value > largest:
            largest, second = value, largest
        elif value != largest and (second is None or value > second):
            second = value
    return second


CASES = [
    ([4, 9, 7], 7),
    ([1, 2, 3, 4], 3),
    ([4, 3, 2, 1], 3),
    ([-8, -3, -5], -5),
    ([0, 0, 5], 0),
    ([9, 9, 7], 7),
    ([6, 6, 6], None),
    ([42], None),
    ([], None),
]

failures = [(values, expected) for values, expected in CASES if second_largest(values) != expected]
print(f"{len(CASES) - len(failures)} of {len(CASES)} edge cases pass")
for values, expected in failures:
    print(f"FAIL {values}: expected {expected!r}, got {second_largest(values)!r}")

9 of 9 edge cases pass

A table of cases like this is easy to keep. In a project, put the same table into a test framework: Python’s unittest has subTest, which reports every failing case separately with its values instead of stopping at the first one.

Stress testing against a brute force

A checklist only covers the cases you thought of. A stress test covers the ones you did not:

1. Write a brute force: the simplest correct solution you can think of, however slow. It is the oracle that decides who is right, so it must be easy to trust; reusing the fast solution’s idea would reuse its bugs.
2. Write a generator of small random inputs. Small matters: short lists with small values hit equal values, negative values and boundaries far more often than long ones, and a failing case of five numbers is easy to read.
3. Seed the generator, so that the same inputs come out in the same order on every run and a failure can be repeated while you debug.
4. Loop: generate an input, run both solutions, compare, and stop at the first difference.

The next program stress-tests a fast solution of the maximum-subarray problem (the largest sum of a slice of consecutive values), which a later lesson of this track develops properly. The fast version has a bug planted in it, and the stress test has not been told where:

import random


def max_subarray_brute(values):
    """The largest sum of a non-empty slice, by trying every slice: slow, but too simple to get wrong."""
    best = values[0]
    for start in range(len(values)):
        total = 0
        for end in range(start, len(values)):
            total += values[end]
            best = max(best, total)
    return best


def max_subarray_fast(values):
    """The same in one pass (Kadane's algorithm), with a planted bug."""
    best = current = values[0]
    for value in values[1:-1]:
        current = max(value, current + value)
        best = max(best, current)
    return best


def random_case(rng):
    """A small list: short lists with small numbers hit the special cases often."""
    return [rng.randint(-5, 5) for _ in range(rng.randint(1, 8))]


def disagree(values):
    return max_subarray_fast(values) != max_subarray_brute(values)


def shrink(values):
    """Remove one element at a time, keeping each removal after which the two still disagree."""
    smaller = True
    while smaller:
        smaller = False
        for i in range(len(values)):
            candidate = values[:i] + values[i + 1 :]
            if candidate and disagree(candidate):
                values, smaller = candidate, True
                break
    return values


SEED = 9  # a fixed seed: the same cases, in the same order, on every run
rng = random.Random(SEED)
for case in range(1, 201):
    values = random_case(rng)
    if disagree(values):
        print(f"seed {SEED}, case {case} fails: {values}")
        print(f"  brute force {max_subarray_brute(values)}, fast {max_subarray_fast(values)}")
        smallest = shrink(values)
        print(f"shrunk to {smallest}")
        print(f"  brute force {max_subarray_brute(smallest)}, fast {max_subarray_fast(smallest)}")
        break
else:
    print("200 random cases, no difference")

seed 9, case 3 fails: [1, -3, -3, -2, -5, -4, -3, 3]
  brute force 3, fast 1
shrunk to [-3, 3]
  brute force 3, fast -3

random.Random(SEED) creates a generator of its own from the seed 9, so the third case is the same failing list on every run, and the program prints the seed with it, ready to repeat. The fast version’s loop runs over values[1:-1], which leaves out the last element, so it never considers a slice that ends with the last element.

JavaScript cannot do the same with Math.random(): the browser or engine chooses its seed, and a program cannot set it. So the JavaScript version brings its own generator, a few lines of xorshift, from George Marsaglia’s paper on xorshift generators. It is fast and repeatable, which is all a test needs, but it is no good for anything secret, just like Math.random() and Python’s random module (use crypto.getRandomValues() or Python’s secrets module for that):

// Math.random() cannot be seeded, so a failure it finds cannot be repeated. This small generator can: xorshift32,
// with the shifts 13, 17 and 5 from George Marsaglia's paper "Xorshift RNGs". Same seed, same numbers, every run.
function makeRandom(seed) {
  let x = seed >>> 0 || 1;
  return () => {
    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;
    return x >>> 0;
  };
}
const between = (next, low, high) => low + (next() % (high - low + 1));

/** The largest sum of a non-empty slice, by trying every slice: slow, but too simple to get wrong. */
function maxSubarrayBrute(values) {
  let best = values[0];
  for (let start = 0; start < values.length; start++) {
    let total = 0;
    for (let end = start; end < values.length; end++) {
      total += values[end];
      best = Math.max(best, total);
    }
  }
  return best;
}

/** The same in one pass (Kadane's algorithm), with a planted bug. */
function maxSubarrayFast(values) {
  let best = values[0];
  let current = values[0];
  for (const value of values.slice(1, -1)) {
    current = Math.max(value, current + value);
    best = Math.max(best, current);
  }
  return best;
}

const disagree = (values) => maxSubarrayFast(values) !== maxSubarrayBrute(values);

/** Remove one element at a time, keeping each removal after which the two still disagree. */
function shrink(values) {
  let smaller = true;
  while (smaller) {
    smaller = false;
    for (let i = 0; i < values.length; i++) {
      const candidate = [...values.slice(0, i), ...values.slice(i + 1)];
      if (candidate.length && disagree(candidate)) {
        values = candidate;
        smaller = true;
        break;
      }
    }
  }
  return values;
}

const show = (values) => `[${values.join(', ')}]`;
const SEED = 37; // a fixed seed: the same cases, in the same order, on every run
const next = makeRandom(SEED);
let found = false;
for (let c = 1; c <= 200 && !found; c++) {
  const values = Array.from({ length: between(next, 1, 8) }, () => between(next, -5, 5));
  if (disagree(values)) {
    found = true;
    console.log(`seed ${SEED}, case ${c} fails: ${show(values)}`);
    console.log(`  brute force ${maxSubarrayBrute(values)}, fast ${maxSubarrayFast(values)}`);
    const smallest = shrink(values);
    console.log(`shrunk to ${show(smallest)}`);
    console.log(`  brute force ${maxSubarrayBrute(smallest)}, fast ${maxSubarrayFast(smallest)}`);
  }
}
if (!found) console.log('200 random cases, no difference');

seed 37, case 1 fails: [-2, 0, 1, -1, -1, -2, -4, 2]
  brute force 2, fast 1
shrunk to [-4, 2]
  brute force 2, fast -4

Shrink the failing case before you debug

The first failing input is random, so it is usually longer than it needs to be. Both programs shrink it before printing: they try removing each element in turn and keep any removal after which the two solutions still disagree, until no single removal keeps the bug alive. Eight numbers became two, [-3, 3] in Python and [-4, 2] in JavaScript, and two numbers are enough to see that the last element is the problem.

Testing tools do the same at a larger scale. Go has fuzzing built into go test: it changes inputs automatically, guided by which code they reach, and when it finds a failure it minimises the input and saves it under testdata/fuzz as a test that runs from then on. For Python, the Hypothesis library chooses the inputs for you from a description of the values a test should work for.

Testing the tests

The same thinking can check the tests themselves. Start from a solution you trust: it passes all its tests, while an unfinished version, such as an exercise’s starter code, fails at least one. Then make copies of the solution, each with one operator flipped, a < turned into >= say, and run the tests on every copy. At least one test should fail for each copy. A copy that passes every test is a warning: either the flip changes nothing the task asks for, or it is a broken solution that the tests cannot tell from a correct one, and then the tests need another case. This idea is called mutation testing, and it is a good way to test your own test suites.

Key takeaways

• Decide what the answer is in every awkward case before testing, then run each solution through a checklist: empty, one element, all equal, sorted, reversed, duplicates, negatives and zero, extreme values; for graphs, disconnected parts, self-loops, cycles and long paths.
• A stress test compares the fast solution with a slow, obviously correct brute force on many small random inputs and stops at the first difference.
• Seed the generator so a failure repeats: random.Random(seed) in Python, a small generator such as xorshift in JavaScript, because Math.random() cannot be seeded. Keep failing inputs as tests.
• Shrink a failing input by removing elements while it still fails; a two-element case usually points straight at the bug.