Stress testing: brute force against a fast solution
25 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Samples pass, the judge says wrong answer, and you cannot see why. A stress test finds the input for you. You write a slow, obvious solution, a random input maker, and a loop that compares the two.
Two solutions, one input
Stress testing is running a fast solution and a simple brute force on thousands of small random inputs, and stopping at the first input where their answers differ.
A fast solution can be wrong in ways examples never show. A brute force is slow but simple, so it is easy to trust. Run both on many small random inputs and compare the answers.
Example 1 · Brute force against Kadane's algorithm
import random
def brute(nums): best = nums[0] for i in range(len(nums)): total = 0 for j in range(i, len(nums)): total += nums[j] best = max(best, total) return best
def fast(nums): best = cur = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return best
rng = random.Random(5)for _ in range(2000): nums = [rng.randint(-4, 4) for _ in range(rng.randint(1, 7))] assert brute(nums) == fast(nums), numsprint("2000 inputs agree")2000 inputs agree
What this code does
- brute tries every start and end, so it is easy to trust; fast makes one pass.
- Both start from the first item, so all-negative inputs are handled.
Example 2 · Two solutions, one input
import random
def brute(nums): return max(sum(nums[i:j]) for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))
def fast(nums): best = cur = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return best
random.seed(1)for _ in range(1000): nums = [random.randint(-5, 5) for _ in range(random.randint(1, 8))] assert brute(nums) == fast(nums), numsprint("1000 inputs agree")1000 inputs agree
What this code does
- The loop makes a small random list, asks both functions and stops at the first difference, printing the list that caused it.
- Running it prints
1000 inputs agree.
A seeded generator of small inputs
Small inputs are better than large ones. A bug that shows on a list of four items is easy to trace. Use a small range of values so that duplicates, zeros and negatives appear often.
import random
def make_input(rng): n = rng.randint(1, 6) return [rng.randint(-3, 3) for _ in range(n)]
rng = random.Random(42)print(make_input(rng))print(make_input(rng))Example 3 · Stress test finds a bug
import random
def brute(nums): best = nums[0] for i in range(len(nums)): total = 0 for j in range(i, len(nums)): total += nums[j] best = max(best, total) return best
def fast(nums): best = cur = 0 for x in nums: cur = max(x, cur + x) best = max(best, cur) return best
rng = random.Random(5)for round_no in range(1, 2001): nums = [rng.randint(-4, 4) for _ in range(rng.randint(1, 7))] b, f = brute(nums), fast(nums) if b != f: print("round", round_no, nums, "brute", b, "fast", f) breakround 6 [-1, -2] brute -1 fast 0
What this code does
- This fast version starts its best value at 0, which is wrong when every item is negative.
- The first mismatch shows an input where every item is below zero.
A random.Random(seed) object keeps its own sequence, so the same seed always replays the same inputs. Print the seed when a test fails.
When the answers differ
A mismatch is a gift: it comes with an input that breaks your code. Print it, shrink it by removing items while the answers still differ, then trace that tiny input by hand.
def shrink(nums, differs): changed = True while changed: changed = False for i in range(len(nums)): smaller = nums[:i] + nums[i + 1:] if smaller and differs(smaller): nums = smaller changed = True break return numsExample 4 · Shrink the failing input
def brute(nums): best = nums[0] for i in range(len(nums)): total = 0 for j in range(i, len(nums)): total += nums[j] best = max(best, total) return best
def fast(nums): best = cur = 0 for x in nums: cur = max(x, cur + x) best = max(best, cur) return best
def differs(nums): return brute(nums) != fast(nums)
nums = [-2, -3, -1, -4, -6]assert differs(nums)changed = Truewhile changed: changed = False for i in range(len(nums)): smaller = nums[:i] + nums[i + 1:] if smaller and differs(smaller): nums, changed = smaller, True breakprint(nums)[-6]
What this code does
- The loop deletes one item at a time while the two answers still differ.
- A single negative number is the smallest input that exposes the bug.
Example 5 · Pair sum: brute force against a set
import random
def brute(nums, target): return any(nums[i] + nums[j] == target for i in range(len(nums)) for j in range(i + 1, len(nums)))
def fast(nums, target): seen = set() for x in nums: if target - x in seen: return True seen.add(x) return False
rng = random.Random(9)for _ in range(3000): nums = [rng.randint(-5, 5) for _ in range(rng.randint(0, 6))] target = rng.randint(-8, 8) assert brute(nums, target) == fast(nums, target), (nums, target)print("3000 cases agree")3000 cases agree
What this code does
- The generator makes the list and the target together and allows an empty list.
- Both functions answer yes or no, so the comparison is a plain equality.
The function keeps deleting one item at a time while the two solutions still disagree. What remains is a minimal failing input.
When many answers are valid
Some problems accept more than one answer, such as any index of the largest value. Then comparing equal outputs fails even for a correct program. Write a small checker that tests whether an answer is valid.
def valid_max_index(nums, i): return 0 <= i < len(nums) and nums[i] == max(nums)
print(valid_max_index([4, 9, 9], 1))print(valid_max_index([4, 9, 9], 2))print(valid_max_index([4, 9, 9], 0))Example 6 · A checker for many valid answers
import random
def find_max_index(nums): best = 0 for i in range(1, len(nums)): if nums[i] >= nums[best]: best = i return best
def valid(nums, i): return 0 <= i < len(nums) and nums[i] == max(nums)
rng = random.Random(2)for _ in range(1000): nums = [rng.randint(0, 3) for _ in range(rng.randint(1, 6))] assert valid(nums, find_max_index(nums)), numsprint("all answers valid")all answers valid
What this code does
- The function returns the last index of the largest value, while another correct one may return the first.
- Checking validity avoids false alarms from a different but correct answer.
Both index 1 and index 2 are valid answers. The checker accepts any of them and rejects the rest.
Next step
Check your understanding
12 quick questions