Saturday, September 21, 2013

Did I just spent all my saturday customizing my Tester?

A word of caution about the Greed plugin. It might enable certain obsessive aspects of your personality.

I was not entirely happy with my previous solution to the Tester problem. So I began customizing even more.

The more I used the previous version of my tester, the more annoyed I was at the select case syntax of c++. It is awful. The need for break really kills me. Also, the whole thing with marking the last test cases with 'm' was messy.

I decided the optimal solution would be to abuse initializer lists and tuples and make the part of the code that saves test cases something like this:

typedef tuple< tuple<int,int,string,string>, int > test;

vector<test> testCases = {
     {  { 2, 2, "ABC", "ADC" }, {2} },
     {  { 2, 2, "ABC", "ABD" }, {0} },
     {  { 3, 4, "ABCDDE", "ACCBDE" }, {1899302} },
     {  { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, {120390576} },
    // Your custom  goes here:
    // {  { , , , },  {} },
};

This would be the test case section for the StringPath problem. This has many advantages over the previous thing. It is less verbose. Adding a test case is just creating a new line. In case a single line is confusing we can add some formatting. It is also exactly the way input is represented in TC's system tests.

In order to use tuples like this, I would have to heavily modify the template, including the part that does the testing. I would need to extract parts of the tuple through indexes. But Greed doesn't have a field that gives an index to a parameter in the function. So in fact I had to update the source code. The fork that has this feature is at github.

Some time after adding the feature to Greed, I learned some very sad news. My initial idea of doing that with tuples and initializer lists did not work. Tuples don't support initializer lists like that. Initializer lists are also supposed to be used for things that have the same type... Back to square one.

The constructor idea

Although tuples don't allow that usage of initializer lists, they do have constructors, and constructors do support a {} syntax. So the following is possible:

vector<test> testCases = {
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 2, 2, "ABC", "ADC" }, 2 },
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 2, 2, "ABC", "ABD" }, 0 },
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 3, 4, "ABCDDE", "ACCBDE" }, 1899302 },
     tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, 120390576 },
     // Your custom  goes here:
     //tuple< tuple<int,int,string,string>, int > { tuple<int,int,string,string> { , , ,  },  },
};

But that is awful, you might say, well, not so much if we use typedefs:

typedef tuple<int,int,string,string> input;
typedef tuple<int> output;
typedef tuple< input, output > test;

vector<test> testCases = {
     test { input { 2, 2, "ABC", "ADC" }, output{2} },
     test { input { 2, 2, "ABC", "ABD" }, output{0} },
     test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
     test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
    // Your custom  goes here:
    //test {  input { , , , }, output {} },
};

That... actually seems cool, doesn't it? I think it is the closest I can get to the system test syntax in c++. In python though we can use tuples directly.

Unknown output

A new issue was that this doesn't allow you to mark a test as not having a known required output. Sometimes you add custom tests just to test for timeout or to learn the solution and you have no idea what the correct solution actually is. Then I thought, well if you are going to use constructor syntax... we might as well just create a struct...

typedef tuple<int,int,string,string> input;
struct output
{
    int value; //the value
    bool u;    //false if the output is known, else we ignore the value.
};
output unknown{ 0, true };
typedef tuple< input, output > test;

vector<test> testCases = {
     test { input { 2, 2, "ABC", "ADC" }, output{2} },
     test { input { 2, 2, "ABC", "ABD" }, output{0} },
     test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
     test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
     
     // A test with an unknown value:
     test { input { 5, 4, "ZZZZZZZZ", "ZAAAABXZ" }, unknown },
     
     // Your custom  goes here:
     //test {  input { , , , }, output {} },
};

Initializing simple classes with the {} syntax tends to be a life saver. output{6} creates an output object that has value 6 and u = false. The unknown variable contains an output object that has u = true. So that the tester (the part that does the grading) can know the output doesn't exist.

Compact layout

Everybody seems to like compact layout for the output of the tester. So I wanted to give it a try. Because of colors, I can actually make the smallest output ever. It looks like this:

Certainly smaller than it was before:

However, I am undecided, so I made this an optional thing. Determined by the value of a boolean constant. I can actually change the constant whenever I want. So maybe I have the compact layout until I really need debugging power in which I enable the full-info layout.

Actually, after a while of using the compact layout, it seems to me that information is more important than the coolness. I remember so many times in which my solution always returns a number that is exactly the intended result plus 1. It is useful to see the intended result and the actual result. It is also useful to see the parameters. Also, the compact layout loses its charm when you start putting tons of debugging messages in your solution.

Clean code

An issue with a full-featured template is that it is generating tons and tons of code. But you are supposed to use the file to code a solution. The code creates visual bloat that is a distraction.

The vector that initializes test cases was at the top, but it still required many things to be declared before it. Things that are distractful. Optimally, the test cases should be as above as possible. Just bellow the solution code. But how?

How do you use the input tuple or the output struct before declaring them? Turns out the only way I found was to use a template...

#include <bits/stdc++.h>
using namespace std;

struct StringPath
{
    int countBoards(int n, int m, string A, string B)
    {
        return 0;
    }
};

// CUT begin
//------------------------------------------------------------------------------
const double CASE_TIME_OUT = 2.0;
const bool   COMPACT_MODE  = false;

template<class test, class input, class output>
vector<test> getTestCases() {

    return {
        test { input { 2, 2, "ABC", "ADC" }, output{2} },
        test { input { 2, 2, "ABC", "ABD" }, output{0} },
        test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
        test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
        // Your custom test goes here:
        //test { input { , , ,  }, output {} },
    };
// output{} = unknown result.
}
bool disabledTest(int x)
{
    return x < 0;
}

// Dragons be below this line:

That is how the file generated for StringPath looks like, just before the part that has a lot of code. Very messy code. Possibly without line breaks so it doesn't take space.

This brought me a new problem. The unknown variable was no longer usable that easily. I eventually settled to making the output struct have explicit constructors: (value) constructs the output with a value . Constructor with no arguments: () creates an unknown output. So if we want a known value we use output{2}, and if we do not know the value, we use output{} with nothing between the braces.

That fix added yet more code to a bunch of code that was already quite bloated.

A meta-tester!

BEEHOLD! Most of the operations the tester performs were the same everywhere (for all problems). Most of the functions were the same everywhere . A good start would be to move all the library and configuration functions like a function called pretty that prints any function argument or return with added "" if there is a string somewhere. Or the thing that compares floating point variables using TopCoder rules. If we put all these library functions into an external file that is shared by all solutions to all problems that are generated by my greed template. This saves a few space.

The real deal is though, to make an abstraction for the tester. Most of what the tester does is the same for all problems: Run each of the n tests. Decorate the output, call solution for each test, show solution results. Only few things vary, the actual types and number of the arguments. The solution class and method. The return type. The problem class name, the time when you opened the problem and the vector of tests.

The vector of tests is already a vector of pairs of tuples and an output struct. What if we made a template main function for the tester that took the test cases vector, the types of the method and everything else and just did the repetitive things?

The first speed bump was that input was represented by a tuple. Processing tuples requires variadic templates and it would have been very messy to, for example, print the arguments, or call the problem class with individual arguments.

This was the moment where I figure out. Maybe OOP is the solution. I really, really, hate OOP. But I was already using an output object. An input object was not that much different. And it would be very useful. The input object stores the parameters of a single test case, but it also has a method to perform the actual test, return the result and measure the execution time. Another useful method is the one to print the argument list.

And the files generated for a single TopCoder problem now look like this:

#include <bits/stdc++.h>
using namespace std;

struct StringPath
{
    int countBoards(int n, int m, string A, string B)
    {
        return 0;
    }
};

// CUT begin
//------------------------------------------------------------------------------
const double CASE_TIME_OUT = 2.0;
const bool   COMPACT_MODE  = false;

template<class test, class input, class output>
vector<test> getTestCases() {

    return {
        test { input { 2, 2, "ABC", "ADC" }, output{2} },
        test { input { 2, 2, "ABC", "ABD" }, output{0} },
        test { input { 3, 4, "ABCDDE", "ACCBDE" }, output{1899302} },
        test { input { 8, 8, "ZZZZZZZZZZZZZZZ", "ZABCDEFGHIJKLMZ" }, output{120390576} },
        // Your custom test goes here:
        //test { input { , , ,  }, output {} },
    };
// output{} = unknown result.
}
bool disabledTest(int x)
{
    return x < 0;
}

//------------------------------------------------------------------------------
// Tester code:
    #include "../tester.cpp"
    struct input
    {
        int n; int m; string A; string B;
        
        int run(double & elapsed) {
            StringPath* instance = new StringPath();
            time_t s = clock();
            int r = instance->countBoards( this->n,this->m,this->A,this->B );
            elapsed = (double)(clock() - s) / CLOCKS_PER_SEC;
            delete instance;
            return r;
        }
    
        void print() { 
            cout << "[" << Tester::pretty(n) << ","<< Tester::pretty(m) << ","<< Tester::pretty(A) << ","<< Tester::pretty(B)  << "]";
        }
    };
    struct output {
        int value; bool u=false;
        
        output(int value) { this->value = value; }
        output() { u = true; }
    };
    
    int main() {
        Tester::runTests(
            getTestCases<pair<input,output>,input, output>(), disabledTest, 
            "StringPath", 900, 1379806426,
            CASE_TIME_OUT, COMPACT_MODE
        );
        return 0;
    }
// CUT end

Note how the part that says Tester code just contains the input / output structs and a main method that calls a runTests function that happens to be a template function. It takes basically everything as arguments, including the test cases, the problem score, the function that determines if a test case is disabled, the configuration constants...

This ../tester.cpp file is the same for all topcoder problems and it works nicely. The tester code in the problem file is very short and nice and takes 33 lines. The actual code in tester.cpp is 168 lines long.

The other benefit is that I can modify the tester.cpp without worrying about Greed't template systax. I can add new features to the tester like multi threading or running in a single thread.

I do wish I could get rid of the input and output structs...

This post is just intended to show once more the power of Greed. Here is the template that generates the files for any TC problem:

const double CASE_TIME_OUT = 2.0;
const bool   COMPACT_MODE  = false;

template<class test, class input, class output>
vector<test> getTestCases() {

    return {
${<foreach Examples e}
        test { input { ${foreach e.Input in , }${if in.Param.Type.Array}{${foreach in.ValueList v ,}${v}${end}}${else}${in.Value}${end}${end} }, output{${if Method.ReturnType.Array}{ ${foreach e.Output.ValueList v ,}${v}${end}}${else}${e.Output}${end}} },
${<end}
        // Your custom test goes here:
        //test { input { ${foreach Method.Params p , }${if p.Type.Array}{}${end}${end} }, output {} },
    };
// output{} = unknown result.
}
bool disabledTest(int x)
{
    return x < 0;
}

//------------------------------------------------------------------------------
// Tester code:
    #include "../tester.cpp"
    struct input
    {
        ${foreach Method.Params p  }${p.Type} ${p.Name};${end}
        
        ${Method.ReturnType} run(double & elapsed) {
            ${ClassName}* instance = new ${ClassName}();
            time_t s = clock();
            ${Method.ReturnType} r = instance->${Method.Name}( ${foreach Method.Params p ,}this->${p.Name}${end} );
            elapsed = (double)(clock() - s) / CLOCKS_PER_SEC;
            delete instance;
            return r;
        }
    
        void print() { 
            cout << "[" ${<foreach Method.Params p << ","}<< Tester::pretty(${p.Name}) ${<end} << "]";
        }
    };
    struct output {
        ${Method.ReturnType} value; bool u=false;
        
        output(${Method.ReturnType} value) { this->value = value; }
        output() { u = true; }
    };
    
    int main() {
        Tester::runTests(
            getTestCases<pair<input,output>,input, output>(), disabledTest, 
            "${Problem.Name}", ${Problem.Score}, ${CreateTime},
            CASE_TIME_OUT, COMPACT_MODE
        );
        return 0;
    }

3 comments :

vexorian said...

Maybe I could turn the input struct into a variadic template. hmn...

PRAVEEN DHINWA said...

I just want to say thank you for posting things on your blog. I really love your blog. Thank you very much for the blog :)

Washington Sump Pump Repair said...

Hello mate great bllog