Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

upobir's blog

By upobir, 5 years ago, In English

Sometimes when you are getting WA on a problem, possibly due to missing some corner case or a bug in your code, all you really need are the perfect test cases. Of course you don't know the perfect test cases, so you have to resort to something else. And that something else is checking your code on a bunch of randomly generated testcases. I recently learnt about it and so, am writing this so other noobs like me can get a little help.

First of all, this isn't an unique idea. I myself learnt about it from Errichto's youtube video. You should check it out if you haven't seen it before. So the idea is simple, you will write two new c++ programs, one to generate random test cases. And another to get solution for those test cases, but unlike your actual solution code, this will definitely give the correct answer (perhaps not efficiently/ via brute force). You run the test generator a bunch of times and save the tests in a fine input.in. After each generation, you also solve the problem for the test case in output.out (your original solution) and output2.out (your brute force solution). And then you compare the solutions with a script code of your OS.

The test generation part is easy for a lot of problems, you need to just randomly generate a bunch of data. Sometimes these need to follow a strict restriction but that depends on the problem. For random numbers I use

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
long long random(long long a, long long b){
    return a + rng() % (b - a + 1);
}

Anyways, about the script part, which is the main goal of this blog. For linux script you can just see errichto's video. For windows sctipt, put all three codes TestGenerator.cpp, solution.cpp, brute.cpp in one folder, compile them, and write the following code in checker.bat file.

@echo off
for /l %%x in (1, 1, 100) do (
    TestGenerator > input.in
    solution < input.in > output.out 
    brute < input.in > output2.out
    fc output.out output2.out > diagnostics || exit /b
    echo %%x
)
echo all tests passed

The code basically runs a loop 100 times. Each time it calls TestGenerator.exe and puts the randomly generated output in input.in (the > command redirects stdout to input.in). Then solution.exe and brute.exe are run by redirecting stdin to input.in. The output are put in output.out and output2.out respectively. fc is the command for comparing files, if the files have difference then "exit /b" command stops the batch file. Otherwise if there is no difference, the test case number x will be printed showing you the progress. The advantage of the exit command is that after exiting, you will find the corner test case in input.in and you can debug your code. So all you gotta do is just open cmd in the folder of the files and write checker.bat and run.

I myself don't know that much windows scripting, I learned about it from yeputons's comment in this post. Anyways hope this helps. Forgive any mistakes please.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I don't recommend using system clock for seed. If you loose an input file you created, you won't be able to retrieve it. It's better to take seed from arguments: int main(int argc, char* argv[]).