Stress Tester For Competitive Programming

Firstly don’t get intimidated 🤯 by the name stress tester. This is just a so called fancy term for a utility tool that I’ve built to accompany me during competitive programming 😉.

Many a times we have faced difficulties in competitive programming especially when we feel that our logic is unbeatable and it turns out that our code fails miserable at some strong test case.

But it’s not always the case that we have a backup where our brute force solution comes to rescue. Yes, the brute force solution is correct, Then what’s the problem ? 🤔. You’ve guessed it right it’s not fast. Strictly speaking in terms of competitive programming it is not optimal and in some challenges our code may pass the time limits for some small sub tasks too.

We could leverage the fact that our brute force solution is correct and test our optimal solution against it. I came up with this idea that if we take a test case and feed it into the brute force and optimal solution and check where our solution fails. But where am i about to get so many Test cases ? 😣😣. That’s where randomization comes into play.

Instead of dumping the code at you I’ll be taking you through the strategy and plan i had while building this tool.

Strategy:

• Generate random test cases.
• After generating them i should be able to feed them to my programs.
• So get equipped with the executable’s of the brute and optimal solutions.
• Then ill need to get their outputs into some files and then check the difference.

And another hurdle is that we need to do the above task may be a thousand number of times.

The Choice of Tech:

• I could have implemented this using python with the help of several modules like subprocess (to run terminal commands), difflib (to check difference), random (to generate random test cases) and file I/O operations but that could be hectic because this involves a lot of terminal operations and we may face problems.
• That’s the reason i chose a perfect combo between bash and python

• The reason for choosing bash is the ease with which a bash script could perform most of the above things and for generating test cases I’ll be using python.

Directory Structure :

• brute.cpp and optimal.cpp containing the respective code.
• testcase.py file which generates test cases
• brute_out.txt and optimal_out.txt which will be created during runtime containing the respective outputs.
• difference_file.txt where we can look at the point of difference.

Part-1 (Generating the test files)

For this I’ve picked a question from codechef (https://www.codechef.com/OCT20B/problems/REPLESX)

At the first place, understand that one test file is the exact input format values. To elaborate on, One test file (not the same as a test case) of this question contains all above in the image

This is a test file: (Please look at the input format above)

We will be generating n such test files. The python code to generate such a test file depends on the input format. Look at the python code below for generating a test file suitable for this input format.

But for easiness I’ve designed some classes for easier generation of test cases to facilitate some common operations say, generating an array of n integers and other functionalities too. Have a look at it too.

testcase.py

Part-2 (The Master Bash Script)

1. generate executable files of brute force and optimal programs.
2. take number of test files to run the program against as command line args
3. for each test file generated, map the outputs and test the difference

The Code Explains it all 😉

mapper.sh

Description of some essential parts of the bash script.

Important: We are breaking the loop when we see a difference and look at the test case where our program fails open the testcase.txt file because our tool reported a difference when we were executing on the testcase.txt file

The diff command:

• diff <file_1> <file_2> : returns the difference between 2 files
• using -Z flag with diff omits the trailing spaces and newlines

Getting the result of a bash command inside a bash script:

• $(command) : gives us the output of that command so we are taking advantage of the fact and checking if there’s any difference because if the diff command returns nothing then it implies that the files are same.

Input output redirection:

• command > “filename” will redirect the command’s output to “filename” .
• command < “filename” will feed the contents of filename as input to command.

Using the tool:

1. Copy your code to the brute.cpp and optimal.cpp files.
2. Modify the testcase.py file to suit the input format.
3. Switch to the terminal and navigate to the directory where the project is.
4. Run the mapper.sh and file by passing a command line argument(number of test files) and see the magic 😯.
5. Look at the difference_file.txt for seeing the difference produced.

• It took me some time to get used to using this tool. But when it helped me get some AC’s the adrenaline rush was amazing.
• And that’s not it we could also use to test our expected solution which passes all our custom test cases against the correct solution.

• you can look that i ran it for 20 test files but the difference was spotted at the first test file itself.

• And after checking the difference file found out some corner cases where my program was outputting 1 every time .
• After modifying the optimal.cpp file and handling the corner cases I’ve ran the code again.
• This time i made sure that i cover every test case and i ran the tool for 100 test files. You can look at the execution process in the linked video below.
• Believe, Me without this tool I would not have got AC in this question. I felt it worth sharing.

Github Link :https://github.com/kaushik-rishi/Stress-Testing-CP