Testing

Testing is an important step of writing programs of any kind. In algorithm contests, bugs cost time and points, so they must be avoided. There are two strategies you can use in order to avoid bugs: detecting them in an already-written program and writing programs without them.

The most common method to finding bugs in a program is by testing it. The most common way of testing during an algorithm contest is by writing two other separate programs: one that solves the problem in a very simple way (generally a brute-force solution), and one that generates a random test. Then you can repeatedly generate a test, run the two programs on the test, and compare the outputs. If they are different, there is a bug in one of the programs.

Since you don't have to submit these two extra programs, you have a wider choice of tools than those that are allowed for the final solutions. For example in the ACM-ICPC you may only use C, C++, Java, and in the IOI C, C++, Pascal, but all Linux computers have Perl and Python interpreters.

We'll use MaxSquare as an example problem. A possible generator is:

    1 #!/usr/bin/perl -w
    2 use v5.14;
    3 
    4 my $n = 1 + int rand 50;
    5 say $n;
    6 for my $i (1 .. $n) {
    7     for my $j (1 .. $n) {
    8         print 100 - int rand 200, ' ';
    9     }
   10     say '';
   11 }

We'll now need a script to run the tests. Assume that the two programs are written in C++ and named 'prog1.cpp' and 'prog2.cpp', and that the generator is named 'gen'. '

    1 #!/usr/bin/perl -w
    2 use v5.14;
    3 
    4 system 'make prog1 prog2';
    5 for (1 .. 1000) {
    6     system './gen > input';
    7     system './prog1 < input > output1';
    8     system './prog2 < input > output2';
    9     die "The outputs are different!\n" if system 'diff -q output1 output2';
   10 }

If the two programs produce different outputs for a test, the script dies with an error, allowing the user to inspect the input and outputs, find the bug, and fix it.

You can also do this in other languages, such as C++. For example:

Generator:

    1 #include <iostream>
    2 #include <cstdlib>
    3 #include <ctime>
    4 using namespace std;
    5 
    6 int rnd(int a, int b) {
    7     return a + rand() % (b - a);
    8 }
    9 
   10 int main() {
   11     srand(time(NULL));
   12     int n = rnd(1, 100);
   13     cout << n << '\n';
   14     for(int i=0; i<n; ++i) {
   15         for(int j=0; j<n; ++j)
   16             cout << rnd(-100, 100) << ' ';
   17         cout << '\n';
   18     }
   19     return 0;
   20 }

Test runner:

    1 #include <iostream>
    2 #include <cstdlib>
    3 #define TESTS 1000
    4 using namespace std;
    5 
    6 int main() {
    7     system("g++ -o gen gen.cpp");//compile the files, the executable file will be named gen
    8     system("g++ -o brute brute.cpp");
    9     system("g++ -o ok ok.cpp");
   10     for(int i=0; i<TESTS; ++i) {
   11         system("./gen > input");//redirects the stdout of the program gen to the file named input
   12         system("./brute < input > bout");//redirects the file input to stdin and stdout to bout
   13         system("./ok <input > oout");
   14         if(system("diff -q bout oout")) {
   15             cout<<"Outputs differ";
   16             return 0;
   17         }
   18     }
   19     return 0;
   20 }

Testing

Sponsors Gold