Automated Stress Testing: Main vs. Naive Solutions

The Logic of Automated Stress Testing

At its heart, stress testing is a simple, repetitive loop. Automating it requires us to program a computer to perform the manual steps you might otherwise take. The process looks like this:

1. Generate: Run your test case generator to produce a single, random test case.
2. Execute: Feed this same test case as input to both your main, optimized solution and your simple, naive solution.
3. Compare: Check if the outputs from both solutions are identical.
4. Decide:
   • If the outputs match, the test passed. Discard the test case and loop back to step 1.
   • If the outputs differ, you've found a bug! Stop the loop, and present the failing input, your solution's incorrect output, and the expected correct output for debugging.

This loop can be run hundreds or thousands of times in just a few seconds, far exceeding what's possible with manual testing. To implement this, we'll use a shell script, the native language for automating tasks and stringing programs together on Linux-based systems like the ones Codeforces uses.

The Essential Tool: The Bash Script

The most common way to automate this process in the competitive programming world is with a Bash script. Bash is a command-line interpreter that can execute commands, redirect input and output, and has basic programming constructs like loops and conditionals.

Let's imagine you have your three compiled C++ programs in your directory:

• main: Your optimized solution.
• naive: Your brute-force solution.
• generator: Your test case generator.

A straightforward Bash script to implement our testing loop would look like this. You could save this in a file named stress.sh:

#!/bin/bash

# A simple stress-testing script

# Compile the programs first (optional, can be done manually)
g++ main.cpp -o main
g++ naive.cpp -o naive
g++ generator.cpp -o generator

# Loop indefinitely (or for a fixed number of times)
for i in {1..1000}; do
    echo "Running test case #$i"
    
    # Generate test case
    ./generator > input.txt
    
    # Run both solutions
    ./main < input.txt > main_output.txt
    ./naive < input.txt > naive_output.txt
    
    # Compare the outputs. The `diff` command is key here.
    # The `-w` flag tells it to ignore differences in whitespace.
    if diff -w main_output.txt naive_output.txt > /dev/null; then
        # If diff returns 0, files are the same.
        echo "OK"
    else
        # If diff returns non-zero, files are different.
        echo "Wrong Answer!"
        echo "Failing input:"
        cat input.txt
        echo "Your output:"
        cat main_output.txt
        echo "Expected output:"
        cat naive_output.txt
        # A mismatch was found, so we exit the loop.
        break
    fi
done

This script automates the entire process using two fundamental shell features:

• I/O Redirection: The > symbol redirects a program's standard output to a file. The < symbol redirects a file's content to a program's standard input.
• The diff Command: This utility compares two files line by line. Crucially, it returns an exit code of 0 if the files are identical and a non-zero code if they differ. The if statement in the script checks this exit code to determine if the test passed.

Using a Professional-Grade Script

While the script above is perfectly functional, the community has developed more advanced and user-friendly versions. The following Codeforces blog post provides a powerful, ready-to-use script that adds features like colored output and command-line arguments.

The script in the blog post is a fantastic template to adopt for your own use. After you download it and place your main.cpp, brute.cpp (the naive solution), and tc_generator.cpp files in the same directory, you can run it, and it will handle the compilation and testing loop for you. When it finds a bug, it will stop and print the results clearly, just like in this example:

This is the result of a successful stress test. After three accepted cases, the script found a test case where the main solution's output differed from the expected output and printed all the necessary information for debugging.

Seeing it in Action

Watching someone walk through the process can be very helpful. The following video provides a practical demonstration of setting up a similar automated testing environment, this time using a Python script. The principles are exactly the same, regardless of the scripting language.

This video reinforces that the core components—a generator, a correct solution, a solution to test, and a script to manage them—are universal.

Conclusion

Congratulations! You have now completed the first module and have built a complete, professional toolkit for approaching competitive programming problems. You know how to analyze complexity, manage your time based on constraints, and most importantly, how to rigorously and automatically test your solutions. Stress testing is not just a debugging technique; it's a way to build confidence in your code, allowing you to submit your solution knowing it has been vetted against thousands of random cases.

Key Takeaways:

• The automated stress testing loop consists of four steps: Generate, Execute, Compare, Decide.
• Bash scripting is the standard way to automate this process in a Linux environment.
• I/O redirection (<, >) and the diff command are the core shell tools for linking your programs together.
• You can start with a simple script and graduate to more feature-rich community-provided templates.
• The goal is to stop on the first failing test case and get the exact input that breaks your code.

This concludes our module on fundamentals. You now possess the strategic framework to tackle problems effectively. In our next lesson, we will pivot from strategy and tools to learning our first specific algorithmic technique: Prefix Sums. This simple but powerful idea is a cornerstone of solving many array-based problems efficiently, and it will be the first of many such techniques you'll add to your problem-solving arsenal.