Comparator and Verifier

"The prerequisite for using a comparator/verifier is that you must have a working brute force solution. Without it, these tools are ineffective."

Application Background

You have a brute force C++ code that produces correct results but is too slow for large datasets. You've also written an optimized non-brute force solution, but you're unsure of its correctness. If the optimized solution is correct, it should produce the same results as the brute force solution when given the same input. This requires a random data generator (mkd.cpp).

Workflow

You should have three C++ files:

• std.cpp (optimized solution)
• bl.cpp (brute force solution)
• mkd.cpp (random data generator)

The process works as follows:

1. mkd generates a dataset A
2. Dataset A is fed to both std.cpp and bl.cpp, producing outputs B and C respectively
3. Compare B and C. If they differ, examine dataset A to identify the case where your optimized solution fails
4. Use this information to improve your std.cpp code

Practical Implementation

Problem: Output all odd numbers from input

bl.cpp (Brute Force Solution)

#include 
using namespace std;

int main(int argc, char** argv) {
    int n = 10;
    int temp = 0;
    while(n--)
    {
        cin >> temp;
        if(temp & 1)
            cout << temp << " ";
    }
    cout << endl;
    return 0;
}

std.cpp (Optimized Solution with Potential Bug)

#include 
using namespace std;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(0));
    int n = 10;
    int temp = 0;
    while(n--)
    {
        cin >> temp;
        if(temp & 1)
            cout << temp << " ";
    }
    if(rand() % 3 == 0)
        cout << "x" << " ";
    // Simulating an occasional error
    cout << endl;
    return 0;
}

mkd.cpp (Data Generator)

#include 
using namespace std;

int main() {
    const int n = 10;
    srand(time(0));
    int a[n] = {0};
    for(int i = 0; i < n; i++)
        a[i] = i;
    random_shuffle(a, a + n); 
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

test.bat (Automation Script)

g++ std.cpp -o std -g
g++ bl.cpp -o bl -g
g++ mkd.cpp -o mkd -g
:loop
mkd.exe > 1.txt
std.exe < 1.txt > 2.txt
bl.exe < 1.txt > 3.txt
fc 2.txt 3.txt
if not errorlevel 1 goto loop
pause
goto loop

The command mkd.exe > 1.txt redirects the output of mkd.exe to 1.txt. The command std.exe < 1.txt > 2.txt uses 1.txt as input for std.exe and redirects its output to 2.txt. Finally, fc 2.txt 3.txt compares the outputs of the two solutions.

When you run test.bat, it will continue executing until it finds a case where the outputs differ. At that point, the script pauses, allowing you to examine 1.txt which contains the input that causes your optimized solution to fail.