Don't worry, your regularly scheduled useless information programming will resume soon.↵
↵
Anyway, here is [`gtest`, my attempt at writing a script to help with stresstesting](https://github.com/greatericontop/gtest).↵
↵
Note that I still personally think stresstesting is slightly overrated. It is not a silver bullet, especially when some questions are unstresstestable, like some constructive problems, [problems where the solution space grows way faster than even exponentially if you're trying to brute](https://codeforces.me/contest/1747/problem/D), other cases where your brute forcer has to make some core observation that could potentially be wrong, or if your brute forcer is bugged too and misses the same edge case your fast solution does (Cirno and Number with digit 0 be like). I also think it takes a lot of time so you decide whether you want to write everything up or not. With that being said though, it should be very helpful for debugging WA2s, hopefully.↵
↵
The format is↵
↵
~~~~~↵
gtest -s <path to solution 1> -t <path to solution 2> -g <path to generator> [-c <path to checker>] [-T <trials>]↵
~~~~~↵
↵
It supports:↵
↵
- Custom checker (the default just compares the tokens in the two outputted solutions). Also, the `-t` argument is optional, since for some constructive problems maybe you just want to code your solution and a checker that confirms your solution is correct.↵
- Solutions, checkers, and generators can be written in Python or C++ (I didn't add support for any other languages sorry lol)↵
↵
Example:↵
↵
↵
↵
### Solutions↵
↵
Literally just drop your current solution (`.cpp` will be compiled automatically; `.py` will be run with python automatically; executables will be run by themselves) in. And code your brute force solution the same way since they'll be reading the same input.↵
↵
In the example, we have two solutions for two sum on the same input format (n on one line, target on the next, then the array).↵
↵
### Using checkers↵
↵
The two solutions' standard outputs are redirected to `1.out` and `2.out` so go ahead and open those files and see. You should return exit code 0 to give AC and exit code nonzero to give WA. For an example, see `token_checker()` in `gtest.py`.↵
↵
### Using generators↵
↵
For C++ generators, just write your test data to stdout, it will be redirected. Seed your RNG as appropriate.↵
↵
For Python generators, the script will load the module (using importlib) and extract every function you write that starts with `gen_`. So you can write multiple generators, like `gen_small()`, `gen_medium()`, `gen_maximum()` and it will run all of them. Again, just write to stdout (such as with `print`), it will be redirected.↵
↵
### Installation↵
↵
Go here https://github.com/greatericontop/gtest, clone the repo, and run `make install`. Alternatively just copy the python script `gtest.py` and put it somewhere. It has no dependencies other than python STL.↵
↵
I didn't see a lot of good stresstesting tools publicly available. Hopefully this is useful!↵
↵
### Example usage↵
↵
Here is what I did while debugging a WA25 (actual hell) on [1808C](https://codeforces.me/problemset/problem/1808/C). (Read the problem first so the code makes more sense)↵
↵
First I write a super stupid brute forcer:↵
↵
~~~~~↵
t = int(input())↵
for tt in range(t):↵
left, right = map(int, input().split())↵
best_luckiness = 1000↵
which_num = None↵
for i in range(left, right + 1):↵
s = [c for c in str(i)]↵
s.sort()↵
luckiness = int(s[-1]) - int(s[0])↵
if luckiness < best_luckiness:↵
best_luckiness = luckiness↵
which_num = i↵
print(which_num)↵
~~~~~↵
↵
And a few generators:↵
↵
~~~~~↵
def gen_borderline_interval():↵
left = randint(10**18 - 500, 10**18)↵
right = left + randint(1, 500)↵
right = min(right, MAX)↵
print(1)↵
print(left, right)↵
↵
def gen_tiny_interval():↵
left = randint(1, 10)↵
right = left + randint(0, 10)↵
right = min(right, MAX)↵
print(1)↵
print(left, right)↵
~~~~~↵
↵
This problem requires a custom checker since the answers generated by the two solutions may not actually be the same:↵
↵
~~~~~↵
# Checker should read the input and both solution outputs manually↵
with open('gen.in', 'r') as f:↵
f.readline()↵
left, right = map(int, f.readline().split())↵
with open('1.out', 'r') as f:↵
ans1 = int(f.readline().strip()) # In this case I hardcoded it to only check 1 case, which is fine, you don't need it to be beautiful↵
with open('2.out', 'r') as f:↵
ans2 = int(f.readline().strip())↵
↵
s1 = [int(c) for c in str(ans1)]↵
s2 = [int(c) for c in str(ans2)]↵
l1 = max(s1) - min(s1)↵
l2 = max(s2) - min(s2)↵
assert left <= ans1 <= right # A tripped assert will exit non-zero and thus be interpreted as WA↵
assert left <= ans2 <= right↵
if l1 != l2:↵
print('WA luckinesses are different')↵
exit(10)↵
~~~~~↵
↵
A few hundred runs later, I find out that I'm kind of stupid:↵
↵
~~~~~↵
$ gtest -s 1808C -t 1808C.py -g 1808C_gen.py -T 2000 -f -c 1808C_checker.py↵
gen_borderline_interval 175/2000Traceback (most recent call last):↵
File ..., in <module>↵
assert left <= ans1 <= right↵
AssertionError↵
↵
↵
-----Wrong answer on test gen_borderline_interval:176-----↵
Input (gen.in):↵
1↵
1000000000000000000 1000000000000000000↵
↵
Output from solution 1 (1.out):↵
1↵
↵
Output from solution 2 (2.out):↵
1000000000000000000↵
~~~~~↵
↵
Took me about 8 minutes to write the brute, generator, and checker, so not too bad in terms of time in my opinion.↵
↵
Anyway, here is [`gtest`, my attempt at writing a script to help with stresstesting](https://github.com/greatericontop/gtest).↵
↵
Note that I still personally think stresstesting is slightly overrated. It is not a silver bullet, especially when some questions are unstresstestable, like some constructive problems, [problems where the solution space grows way faster than even exponentially if you're trying to brute](https://codeforces.me/contest/1747/problem/D), other cases where your brute forcer has to make some core observation that could potentially be wrong, or if your brute forcer is bugged too and misses the same edge case your fast solution does (Cirno and Number with digit 0 be like). I also think it takes a lot of time so you decide whether you want to write everything up or not. With that being said though, it should be very helpful for debugging WA2s, hopefully.↵
↵
The format is↵
↵
~~~~~↵
gtest -s <path to solution 1> -t <path to solution 2> -g <path to generator> [-c <path to checker>] [-T <trials>]↵
~~~~~↵
↵
It supports:↵
↵
- Custom checker (the default just compares the tokens in the two outputted solutions). Also, the `-t` argument is optional, since for some constructive problems maybe you just want to code your solution and a checker that confirms your solution is correct.↵
- Solutions, checkers, and generators can be written in Python or C++ (I didn't add support for any other languages sorry lol)↵
↵
Example:↵
↵
↵
↵
### Solutions↵
↵
Literally just drop your current solution (`.cpp` will be compiled automatically; `.py` will be run with python automatically; executables will be run by themselves) in. And code your brute force solution the same way since they'll be reading the same input.↵
↵
In the example, we have two solutions for two sum on the same input format (n on one line, target on the next, then the array).↵
↵
### Using checkers↵
↵
The two solutions' standard outputs are redirected to `1.out` and `2.out` so go ahead and open those files and see. You should return exit code 0 to give AC and exit code nonzero to give WA. For an example, see `token_checker()` in `gtest.py`.↵
↵
### Using generators↵
↵
For C++ generators, just write your test data to stdout, it will be redirected. Seed your RNG as appropriate.↵
↵
For Python generators, the script will load the module (using importlib) and extract every function you write that starts with `gen_`. So you can write multiple generators, like `gen_small()`, `gen_medium()`, `gen_maximum()` and it will run all of them. Again, just write to stdout (such as with `print`), it will be redirected.↵
↵
### Installation↵
↵
Go here https://github.com/greatericontop/gtest, clone the repo, and run `make install`. Alternatively just copy the python script `gtest.py` and put it somewhere. It has no dependencies other than python STL.↵
↵
I didn't see a lot of good stresstesting tools publicly available. Hopefully this is useful!↵
↵
### Example usage↵
↵
Here is what I did while debugging a WA25 (actual hell) on [1808C](https://codeforces.me/problemset/problem/1808/C). (Read the problem first so the code makes more sense)↵
↵
First I write a super stupid brute forcer:↵
↵
~~~~~↵
t = int(input())↵
for tt in range(t):↵
left, right = map(int, input().split())↵
best_luckiness = 1000↵
which_num = None↵
for i in range(left, right + 1):↵
s = [c for c in str(i)]↵
s.sort()↵
luckiness = int(s[-1]) - int(s[0])↵
if luckiness < best_luckiness:↵
best_luckiness = luckiness↵
which_num = i↵
print(which_num)↵
~~~~~↵
↵
And a few generators:↵
↵
~~~~~↵
def gen_borderline_interval():↵
left = randint(10**18 - 500, 10**18)↵
right = left + randint(1, 500)↵
right = min(right, MAX)↵
print(1)↵
print(left, right)↵
↵
def gen_tiny_interval():↵
left = randint(1, 10)↵
right = left + randint(0, 10)↵
right = min(right, MAX)↵
print(1)↵
print(left, right)↵
~~~~~↵
↵
This problem requires a custom checker since the answers generated by the two solutions may not actually be the same:↵
↵
~~~~~↵
# Checker should read the input and both solution outputs manually↵
with open('gen.in', 'r') as f:↵
f.readline()↵
left, right = map(int, f.readline().split())↵
with open('1.out', 'r') as f:↵
ans1 = int(f.readline().strip()) # In this case I hardcoded it to only check 1 case, which is fine, you don't need it to be beautiful↵
with open('2.out', 'r') as f:↵
ans2 = int(f.readline().strip())↵
↵
s1 = [int(c) for c in str(ans1)]↵
s2 = [int(c) for c in str(ans2)]↵
l1 = max(s1) - min(s1)↵
l2 = max(s2) - min(s2)↵
assert left <= ans1 <= right # A tripped assert will exit non-zero and thus be interpreted as WA↵
assert left <= ans2 <= right↵
if l1 != l2:↵
print('WA luckinesses are different')↵
exit(10)↵
~~~~~↵
↵
A few hundred runs later, I find out that I'm kind of stupid:↵
↵
~~~~~↵
$ gtest -s 1808C -t 1808C.py -g 1808C_gen.py -T 2000 -f -c 1808C_checker.py↵
gen_borderline_interval 175/2000Traceback (most recent call last):↵
File ..., in <module>↵
assert left <= ans1 <= right↵
AssertionError↵
↵
↵
-----Wrong answer on test gen_borderline_interval:176-----↵
Input (gen.in):↵
1↵
1000000000000000000 1000000000000000000↵
↵
Output from solution 1 (1.out):↵
1↵
↵
Output from solution 2 (2.out):↵
1000000000000000000↵
~~~~~↵
↵
Took me about 8 minutes to write the brute, generator, and checker, so not too bad in terms of time in my opinion.↵
