Hello Codeforces community.
Tl;dr: The script is specifically for Linux and can be used to stress test C++
solutions. It can be easily modified to work with python or java and other operating systems.
First let me tell you what stress testing is if you don't know, Stress testing is technique using which we can run our solution (which we think might fail/is failing) on a number of random test cases and match it's output with the output of a solution which is a brute force solution or accepted solution of someone else.
If you don't know why and when to use stress testing you can use this detailed article on Stress Testing by ADJA.
I want to share my script for stress testing your solution.
Requirements:
1) A solution which we want to test.
2) A brute force solution which gives correct solution.
3) A generator for generating test cases according to the problem.
About script:
code#!/bin/bash
i=1
# You can change the version of C++ or add the compiler flags you wish
g++ -std=c++17 gen.cpp -o generator
g++ -std=c++17 solution.cpp -o original
g++ -std=c++17 brute.cpp -o brute
max_tests=10 # change it accordingly
diff_found=0
# to color the output text in different colours
green=$(tput setaf 71);
red=$(tput setaf 1);
blue=$(tput setaf 32);
orange=$(tput setaf 178);
bold=$(tput bold);
reset=$(tput sgr0);
while [ $i -le $max_tests ]
do
# Generate test_case and save it in input1.txt
./generator > input1.txt
# run original solution, take input from above generated test case i.e. from input1.txt
# and save it in original_output.txt
./original < input1.txt > original_output.txt
# run brute force solution, take input from above generated test case i.e. from input1.txt
# and save it in brute_output.txt
./brute < input1.txt > brute_output.txt
# check if files original_output and brute_output
# differs(we are ignoring spaces and then comparing files)
if diff --tabsize=1 -F --label --side-by-side --ignore-space-change original_output.txt brute_output.txt >
dont_show_on_terminal.txt; then
echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${green}Accepted$$${reset}"
else
echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${red}Wrong Answer$$${reset}"
diff_found=1
break
fi
i=$((i+1))
done
if [ $diff_found -eq 1 ]
then
echo "$$${blue}Input: $$${reset}"
cat input1.txt
echo ""
echo "$$${blue}Output: $$${reset}"
cat original_output.txt
echo ""
echo ""
echo "$$${blue}Expected: $$${reset}"
cat brute_output.txt
echo ""
fi
rm input1.txt
rm generator
rm original
rm brute
rm original_output.txt
rm brute_output.txt
rm dont_show_on_terminal.txt
Go through the code once, i have added comments and you will understand most of the part. To understand the script all we need is just basics of the language bash
. So we have three .cpp
files:
1) gen.cpp // our cpp solution for generating test cases
2) solution.cpp // our orignial solution
3) brute.cpp // our solution which uses brute force and guaranteed to give correct output
About test case generator:
For generating test cases you can either use "testlib.h" here (i personally don't use it because it takes 6-7 seconds on average to compile in my pc(idk there might be ways to reduce it) and also i need to remember the methods to generate things.) or write your own since most of the time you just need arrays, strings, trees or simple graphs or simple some integers.
I use the below code for generating test cases most of the times(file gen.cpp):
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define accuracy chrono::steady_clock::now().time_since_epoch().count()
#define rep(i,a,n) for (int i = a; i <= n; ++i)
const int N = 1e6 + 4;
int32_t permutation[N];
mt19937 rng(accuracy);
int rand(int l, int r){
uniform_int_distribution<int> ludo(l, r); return ludo(rng);
}
const int inf = 1LL << 31;
using pii = pair<int,int>;
namespace generator {
string gen_string(int len = 0, bool upperCase = false, int l = 1, int r = 26) {
assert(len >= 0 && len <= 5e6);
string str(len, (upperCase ? 'A' : 'a'));
for (char &ch: str) {
ch += rand(l, r) - 1;
}
return str;
}
vector<int> gen_array(int len = 0, int minRange = 0, int maxRange = inf){
assert(len >= 0 and len <= 5e6);
vector<int> a(len);
for (int &x: a) x = rand(minRange, maxRange);
return a;
}
vector<pair<int, int>> gen_tree(int n = 0){
assert(n >= 0);
vector<pii> res(n ? n - 1 : 0);
// if you like to have bamboo like tree or star like tree uncomment below 8 lines
/*if (rng() % 5 == 0) { // bamboo like tree
for (int i = 1; i < n; ++i) res[i-1] = {i, i + 1};
return res;
}
if (rng() % 7 == 0) { // star tree
for (int i = 2; i <= n; ++i) res[i-2] = {1, i};
return res;
}*/
iota(permutation, permutation + 1 + n, 0);
shuffle(permutation + 1, permutation + 1 + n, rng);
for(int i = 2; i <= n; ++i){
int u = i, v = rand(1 , i-1);
u = permutation[u], v = permutation[v];
res[i-2] = minmax(u, v); // u < v, just for convenience while debugging
}
shuffle(res.begin() , res.end() , rng);
return res;
}
vector<pair<int, int>> simple_graph(int n = 0, int m = 0) {
assert(n > 0 && m >= n);
int max_edges = n * (n - 1) / 2;
assert(m <= max_edges);
vector<pii> res = gen_tree(n);
set<pii> edge(res.begin(), res.end());
for (int i = n; i <= m; ++i) {
while (true) {
int u = rand(1, n), v = rand(1, n);
if (u == v) continue;
auto it = edge.insert(minmax(u, v));
if (it.second) break;
}
}
res.assign(edge.begin(), edge.end());
return res;
}
}
using namespace generator;
template<typename T = int>
ostream& operator<< (ostream &other, const vector<T> &v) {
for (const T &x: v) other << x << ' ';
other << '\n';
return other;
}
ostream& operator<< (ostream &other, const vector<pair<int,int>> &v) {
for (const auto &x: v) other << x.first << ' ' << x.second << '\n';
return other;
}
// comment the just below line if test cases required
#define SINGLE_TEST
const int max_tests = 10;
// complete this function according to the requirements
void generate_test() {
int n = rand(1, 40);
cout << n << '\n';
cout << gen_array(n, 1, 20);
}
signed main() {
srand(accuracy);
int t = 1;
#ifndef SINGLE_TEST
t = rand(1, max_tests), cout << t << '\n';
#endif
while (t--) {
generate_test();
}
}
You can above code too and modify it according to your needs. Just go through the code once and everything is self explanatory(i have added some comments too). Usage of above gen.cpp code:
1) to generate an array calling:
gen_array(10, -5, 10);
it will return an array(vector more specifically) with length 10 and elements in the range [-5, 10].
2) to generate a tree calling:
gen_tree(10):
will return a tree with 10 nodes.
3) to generate a simple graph calling:
gen_simple_graph(10, 12);
will return a simple connected graph with 10 nodes and 12 edges.
You can add things as you need them or use testlib which is the best if you know how to use it.
Usage:
Download this repository manually or by using git clone on terminal.
Copy your original solution which you expect might fail in the file solution.cpp
.
Copy your brute force solution which is expected to give correct output in the file brute.cpp
.
Change the gen.cpp
file so as to generate test cases according to the question.
Now open your terminal in the directory where file s.sh
resides and run command:
$ bash s.sh
or
$ ./s.sh
If it shows permission denied then give it execute permission using:
$ sudo chmod +x s.sh
.
In file s.sh
you can change the value of variable max_tests
as you wish on how many random test you want to run the solution.
Verdict: the verdict of running file s.sh
on every test case is either Accepted
if your solution's output matches the brute solution output or Wrong Answer
and will show the input on which the solution failed, the output of your solution and expected output according to the brute force solution on terminal and the script will be terminated.
If you wish to terminate the script at any moment you wish use the command ctrl + c
in terminal.
quick demo: ()
Any suggestions or corrections are welcomed.
Apologies for my poor english.