Stress testing against a brute force

You have written a fast solution to a problem. It passes the sample inputs. But does it work on all test cases, especially the large ones? If you cannot submit to a real judge, a strong local check is to run your fast solution against thousands of random small inputs and compare the output to a correct brute-force solution. Mismatches show you where your logic breaks down.

The idea

A brute-force solution is one that tries all possibilities or uses a slow but obviously correct method. For a problem asking for the maximum sum of a contiguous subarray, a brute-force approach is to check every possible subarray and track the maximum. This is slow for large inputs, but small inputs run instantly and the logic is transparent.

Your fast solution uses a clever technique to solve the same problem in less time. For the subarray problem, you might use Kadane's algorithm or prefix sums. This is faster, but the code is more complex. The chance of a subtle bug is higher.

Stress testing pairs these two solutions. You generate hundreds or thousands of random inputs, run both solutions on each one, and check whether both produce the same output. If they do, your fast solution passed another test. If they do not, you have found a case where your logic broke. Because you generated the input, you can read it and understand why.

Building a stress tester

The script below generates random inputs, runs both a brute-force and a fast solution, and reports mismatches. The idea is specific to one problem, but the pattern is reusable for any problem where you have two candidate solutions.

1import random2
3
4def brute_force_max_sum(arr):5    """Find the maximum sum of any contiguous subarray (brute force)."""6    max_sum = arr[0]7    for i in range(len(arr)):8        current_sum = 09        for j in range(i, len(arr)):10            current_sum += arr[j]11            max_sum = max(max_sum, current_sum)12    return max_sum13
14
15def fast_max_sum(arr):16    """Find the maximum sum of any contiguous subarray (Kadane's algorithm)."""17    max_sum = arr[0]18    current_sum = arr[0]19    for i in range(1, len(arr)):20        current_sum = max(arr[i], current_sum + arr[i])21        max_sum = max(max_sum, current_sum)22    return max_sum23
24
25# Set seed for reproducible random inputs26random.seed(42)27
28mismatches = 029for test_num in range(1000):30    n = random.randint(2, 20)31    arr = [random.randint(-100, 100) for _ in range(n)]32
33    brute = brute_force_max_sum(arr)34    fast = fast_max_sum(arr)35
36    if brute != fast:37        mismatches += 138        print(f"Test {test_num}: MISMATCH")39        print(f"  Input: {arr}")40        print(f"  Brute force: {brute}")41        print(f"  Fast solution: {fast}")42        print()43
44if mismatches == 0:45    print("All 1000 tests passed!")46else:47    print(f"{mismatches} test(s) failed out of 1000.")

The script generates inputs with small values of N (say, 2 to 20), because brute-force is slow. On inputs this small, brute-force runs instantly. The fast solution should also be fast. You generate 1000 random inputs and run both solutions on each one. Mismatches mean the fast solution has a bug. If all 1000 pass, your confidence in the fast solution grows.

Using the output

When the script finds a mismatch, it prints the input, the brute-force output, and the fast output. Use this to understand where your fast solution went wrong. Read the input carefully. Trace through your fast solution by hand on that input. Often the issue is an off-by-one error, a wrong comparison operator, or a forgotten edge case.

Once you fix the bug, regenerate random inputs and rerun the stress test. If the mismatch was in the logic (not the input generation), your fix should make it disappear. Rerun the test multiple times to build confidence.

Seeding the random generator with a fixed value, as the script does, means you get the same inputs every time you run it. This makes the test reproducible. If you remove the seed, you get different inputs each run, which is also useful for deeper testing. But a fixed seed is good for debugging, because you can rerun the stress test, verify that your fix works on the same inputs that broke it before, and move on.

When to use this

Stress testing works best when you have two candidate solutions: one you are confident is correct but slow, and one you have just written and want to verify. You do not need to submit the brute-force solution anywhere. It is only a reference. You keep the brute-force solution in your testing file, never in your contest submission.

Use stress testing when your fast solution passes the sample input but you are unsure about edge cases or larger inputs. The time you spend writing a brute-force and running this test is often less than the time it would take to debug a wrong submission at the judge.

One constraint: stress testing is only useful if your brute-force solution is actually correct. If both solutions have the same bug, the test will miss it. But in practice, brute-force logic is much simpler and easier to verify by eye than fast logic. The tradeoff is worth it.

A second example: counting inversions

Another problem: count how many pairs (i, j) where i < j and arr[i] > arr[j] (inversions in an array). The brute-force loops through all pairs and counts. The fast solution uses merge sort to count inversions in O(N log N) time.

Both solutions take the same array as input. The brute-force counts every inversion directly. The fast solution counts them during the merge step. You generate 1000 random arrays of size 2 to 20, run both, and compare counts. If a random array [3, 1, 2] produces different counts, the test prints it immediately. You then trace through your merge sort to see where it miscounts. Often the bug is in how you count during the merge, not in the merge itself.

This example is harder to verify by eye than the subarray problem, so stress testing is especially valuable. Without it, you might submit a merge-sort solution that looks correct and get a Wrong Answer at the judge.

Common mistakes in stress testing

One mistake is writing the brute-force wrong. If both your brute-force and fast solution share the same bug, the test misses it. Always double-check the brute-force logic on paper first. Brute-force should be obviously correct, even if inefficient. Walk through it by hand on a small example.

Another mistake is not seeding the random generator. Without a fixed seed, you get different inputs each run. This is useful for thorough testing later, but during debugging it makes finding the bug harder. If one run finds a mismatch, you cannot easily rerun that exact case to verify your fix. Use a seed during development. Once your fast program passes every test from a fixed seed, remove the seed and run many more times to check for other bugs.

A third mistake is changing both solutions at once. If you debug the brute-force and the fast solution simultaneously, you may accidentally break both. Fix the brute-force first, verify it on paper, then fix the fast solution using the brute-force as reference.

Recap

Write a slow but obviously correct brute-force solution and a fast solution to the same problem. Generate hundreds of small random inputs, run both solutions on each, and compare their outputs. A mismatch points to exactly which input breaks your fast solution. Use this to find and fix bugs before the contest. Seed the random generator so you can reproduce failing inputs and verify your fix.