PR_0202's blog

Stress testing / bug finding in you code without using Bash
By PR_0202, 4 years ago, In English

Many times we are stuck in a problem and don't know the edge case in which the programme fails, specially during long challenges or monthly challenges we think our solution is correct but it gives WA on submition. So, I'm sharing my idea to stress test your code with a bruteforce or an unoptimized solution without using bash.

So, basically what you have to do is first write a brute force solution and put it in the "Solve" function and put the optimized ones in the second one. change the function and return value according to the question also if you want then make the test generating while loop infinite also adjust the array size according to the constraints of your bruteforce solution.

I would recommend you to use Code-blocks or VS Code for this purpose.

Code begins:

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int MOD = 1e9 + 7;

#define show(arr) { for (auto x: arr) cout << x << " "; cout << '\n'; }

	
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int randNo(int lower_limit, int upper_limit){
	
	return lower_limit + rng()%(upper_limit-lower_limit);
}

int solve(int arr[], int n) {
	int ans = 0 ;
	
	//write here your optimed code with low complexity
	
	return ans;
}

int solve2(int arr[], int n) {
	int ans = 0 ;
	
	//write here your brute force solution
	
	return ans;
}

int32_t main() {
	
	int testCases = 1000000;
	while(testCases--){
		
		//generating n
		int n = randNo(1,100);
		
		//To generate a random array
		int a[n];
		for(int i=0;i<n;i++) a[i] = randNo(1,N);
		
		int naive_ans = solve2(a,n);
		int optimised_ans = solve(a,n);
		
		if(naive_ans == optimised_ans) cout << "YES\n";
		else{
			cout << "NO\n";
			cout << n << '\n';
			show(a);
			cout << naive_ans << '\n';
			cout << optimised_ans << '\n';
			break;		
		}
	}
}

Any suggestion/Edits or questions are welcomed.! :) If you are downvoting please comment the reason so that I can improve..

Edit 1: Don't use rand(): a guide to random number generators in C++ Please read this once to generate random numbers efficiently thanks GLAYS .

Edit 2: Updated rand() with mt19937 rng().

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thanks a lot for writing this. I wanted to learn this but most of the sources assumed prerequisite knowledge of bash scripting etc and also I was really lazy.

This is really simple and to the point. Thanks again.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Great work! Stresstesting is very useful and sometimes the only thing you can do to catch bugs or to be 99% sure there aren't any.

You've got the general idea right, and with this template you can just slap your existing solution and some brute force code to begin testing.

However I have some notes :) based on the errors I made myself.

  • First of all, you must use the C++ std::mt19937 library to generate random numbers(take a look at the blog Neal made about it), it is way better, especially in this case where you absolutely need to get different results randomly to ensure your testing is credible. Even with using it I sometimes look at the tests my library is generating and 75% of them look alike in some way, so I can guarantee that using rand() will be a lot worse.
  • Although this template will work just fine for problems having a single integer as output, you'll have to modify it in order to work for every problem. In some problems the output is more complicated(printing a graph, multiple strings, arrays etc..) and the more important thing is that some problems have multiple correct outputs, in that case you'll need a "checker" function(in the place of the solve2() brute force) to check if your "solve()" function outputs correctly.

And finally don't be afraid of bash scripting, you'll only need to learn a small part of it(you'll maybe write 4-5 lines) and it will make the whole process easier and more flexible.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Link to neal's blog plzz :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Thank you so much.. That is really informative.. :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I don't think rand is so bad in this case — at least if you are only doing this to get rid of your WA. No one is hacking you, and in my experience whatever issues rand has with its distribution, they aren't serious enough to do any damage here.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I guess you're right, since everything is done locally there is no fear of hacking. Here are two cases where I think it will be a problem(but not a major one):

      • Since RAND_MAX=32767 (the maximum value rand() can give) is low, you'll have to combine rand() calls and write other functions if you want to get random numbers > 3e4.
      • rand() has smaller cycles, so if your code fails on specific patterns of an input, the stresstest will fail to find it for hundreds of iterations. This will be worse when your input is a whole array and you're using a function that calls rand() multiple times to compute random values > 3e4. This is also based on my testing with it.
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        My RAND_MAX is bigger. Actually I'm wondering whether it is 32767 anywhere but Codeforces :P

        → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Never mind

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Things will get so messy like this, think when you have to print multiple lines or the there are many accepted solutions. I recomend you to check this.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Why are you guys downvoting him. He has written such a wonderful blog. Good job bro!!

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I always use this approach. You still have to write naive solution and generator, why not write it in the same file?

And it is also much more convenient than bash in interactive problems. Example:

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

IMO, this is hands-down the proper way of testing CP implementations. Along with lots of other advantages like speed or interactive problems, I just want to point out some more:

  • You can easily just test the logic-heavy part of your solution instead of the whole solution; e.g., you think your Segment Tree has a bug? Swap it for some naive DS, and keep the rest of the solution intact.
  • You can just as easily swap fuzzy testing with brute-force (on all possible small inputs, for example); this might be harder (but not impossible) when repeatedly calling a ./gen executable.
  • When time pressured, it is A LOT easier to cope with one file and one programming language, as opposed to 2-3 files and 2+ programming languages

However, I want to emphasise that this approach favors a lot the "no-globals" programming style; you don't want to start debugging your solution on a given test case just to realize that your vectors weren't cleaned properly. A lot of people (including me) prefer to write the code to be very aware of this fact, and, consequently, use as few globals as possible (preferably zero). This has other advantages both in debugging and the implementation process overall that I'm not going to emphasize too much, to not divert from the topic.

That way, for example, when I decide to write a stress test for my failing solution, I just straight-up cut-paste my main code (except reading/writing) into a Solve function, and add a Brute counterpart and a Test subroutine. This way, I usually end up finding counterexamples in less than 5 minutes for most of the problems.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can easily just test the logic-heavy part of your solution instead of the whole solution

    That applies to the multi-file version too. It's easier to copy-paste the whole solution to a new file and replace a segment tree with naive computations there.

    When time pressured, it is A LOT easier to cope with one file and one programming language

    I usually copy-paste bash script and generator template. Then it's IMO easier and safer to work with 3 files. If I understand correctly, you need to pass input as arguments to Solve() and Brute(), which might be annoying if the input isn't a single sequence.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I personally have my doubts regarding copy and pasting solutions around the place, especially as you end up having to keep track of two versions (you find bugs and then you potentially have to modify two copies). I stand by DRY :).

      On top of the above argument, when I said ‘test your heavy logic’, I also meant that you have the freedom to test just that part (i.e. create generator just for that specific interface, not for the whole problem).

      Also, a lot of the times it’s inconvenient to create a whole checker program just to compare outputs (for example, in scenarios with multiple solutions). Related to the annoying input passing, I’ve never encountered this problem. But again, I use STL.

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

So what else is new?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also use this Stress Testing Bash Script. As per me, this works the best and is pretty handy, just replace the codes and this runs the script run multiple cases for you.

→ Reply