Saturday, September 14, 2013

Customizing the Topcoder greed plugin

Yesterday I wrote a quick howto about setting up the topcoder greed plugin. But that post doesn't really do much to show why I switched to it. What Greed does well is, it is very customizable. So customizable that you change the tester code. You can change not only the output format but also even add new test behaviors.

Configuration file

Greed's configuration is all file-dependent. It is not for everyone, I think some people prefer GUIs, but files are very convenient once you get used to them.

You can start a Greed configuration file by just adding a text file called greed.conf to the workspace folder. Whenever you modify this file while Greed is open, you should click the [Reload Configuration] button in the plugin window.

The first basic thing you would like to decide is where and how to place the code files. By default it saves them in a subfolder called "Contest Name", and the filenames are the same as the problem name. While I appreciate the concept of saving code in sub-folders named after the contest, I think I prefer having all my code in the same workspace folder. For starters, all my build scripts are there and it would be difficult to change my system to consider sub-folders :). Anyway, let us do it.

Greed's wiki has a page explaining all of this. So what I do is add this to my (currently empty) greed.conf:

greed {
  templates {
    pathPattern = ""
  }
}
Or this works too:
greed.templates.pathPattern = ""

Basically, my making the pathPattern an empty string, I make it save code files in the workspace root. This works ok in Linux, perhaps other OS need ".". Normally this setting is "${Contest.Name}". Greed has a cool configuration and templates system that has replacement variables like that one. This means the folder name will be replaced with the contest name.

Template

The code template is an important part of your topcoder life. What library modules do you want to include? Any macros (boo!)? What is the code style you prefer for your class? Default comments, etc. In the last post we saw that the code it generates for c++ looks liek this:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
 
using namespace std;
 
class FoxAndChess {
    public:
    string ableToMove(string begin, string target) {
        return "";
    }
};

I have other tastes. I prefer to include only <bits/stdc++.h>, it is a magical header that includes the whole standard library. This is very convenient because of precompiled headers. If you know how to configure a g++ setup, you can use precompiled headers and bits/stdc++ to make compilation time smaller. I also prefer to use struct instead of class in c++, that way I don't have to type public: . The braces format is also all wrong :).

So, we need to change the template. According to the configuration wiki page, the default template file for c++ is said to be res:/Template.cpp, ok... the res:/ folder is inside the package, the jar and that is where we can find Template.cpp:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;

class ${ClassName} {
    public:
    ${Method.ReturnType} ${Method.Name}(${Method.Params}) {
        return ${Method.ReturnType;ZeroValue};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}

So that's what a Greed template looks like. It is easy to see how to make the modifications I was planning:

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

struct ${ClassName}
{
    ${Method.ReturnType} ${Method.Name}(${Method.Params})
    {
        return ${Method.ReturnType;ZeroValue};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}

Now we just need to make Greed use this template. I will save it as template.cpp in the workspace folder. The configuration field for the c++ code template is : greed.templates.cpp.tmplFile, so I will just add:

greed.templates.cpp.tmplFile = "template.cpp"

Go to a practice room and open a problem. Maybe the source file already exists and greed by default doesn't override files that already exist, so click [Regenerate Code]. You probably need to [Reload configuration] first. Now open the new file and verify the template changes.

Advanced template tweaks

So from now it is all very mundane. All plugins that generate code for TopCoder probably have some sort of template for your own code and can be configured in similar ways.

The cool thing about Greed is that it has a very flexible templates system. Namely it uses a library called jmte. You can not only add text bits that are replaceable by special values, like how ${ClassName} is replaced with the TopCoder-defined class name. You can also use conditional statements and ${foreach ...} in the templates. The template language is actually a whole language you need to learn, but it can be very useful, if you are like me and need all the flexibility you can use.

This tends to be more useful for the Tester template, but still, let us try to take some advantage of the power we have here. You know what's annoying? To copy the arguments the function receives so that they become class members. What if we wanted a template that did that automatically?, so the code for the problem would look like this:

#include <bits/stdc++.h>
using namespace std;
 
struct FoxAndChess
{
    string begin;
    string target;
    
    string ableToMove(string begin, string target) {
        this->begin = begin;
        this->target = target;
        return "";
    }
};

Believe it or not, it is possible to make a Greed template that automatically does this for us. The first thing we need is to add the member variables to the struct. For each argument in the method, create a member variable with the same type and name.

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

struct ${ClassName}
{
${<foreach Method.Params p}
    ${p.Type} ${p.Name}; 
${<end}
    ${Method.ReturnType} ${Method.Name}(${Method.Params})
    {
${<foreach Method.Params p}
        this->${p.Name} = ${p.Name}; 
${<end}
        return ${Method.ReturnType;ZeroValue};
    }
};

${CutBegin}
${<TestCode}
${CutEnd}

The important part to understand is this one:

${<foreach Method.Params p}
    ${p.Type} ${p.Name}; 
${<end}

That is how the foreach template command works like. Method.Params contains the list of method parameters, p is the variable that will represent a single parameter. p.Type is the type, p.Name the name. We declare each variable and finish with a ;. Note that some commands begin with ${< and some with just ${. The ${< is an custom extension to jmte included in Greed that just says (Please ignore the line breaks surrounding this command). It is useful because without it, all the contents of the ${foreach } macro , including the line breaks, would be repeated for each parameter.

There is a conditional statement, it doesn't have things like a = operator for strings or binary operators, it is mainly used to call predefined boolean variables. It does have a ! operator and optional ${else}.

Customizing the Tester

The template language is great because it is also used in the Tester code and not just the template code. You can customize the tester template in the same way as the source template.

In a previous post, I mentioned all the trouble I went through to customize the tester in KawigiEdit to have cool things like colors. In greed, I wanted just about the same thing. I also don't really like not being able to read the input of a test case in the output text. I learned that it is very useful to be able to notice what the differences are between passing example cases and the ones you are not having correct. There are many other things that KawigiEdit does and the default tester in Greed didn't, like telling you if a test case is timing out. Allowing you to disable test cases, or allowing test cases that do not have a known return value. Also changed the format of the test case code so that it is easier to edit and so that it is the first part of the code, away from the messy tester code. The result looks like this:

I also modified the python tester template to have the same features. I am quite sure that TopCoder has other languages and that Greed supports them too, but I currently cannot remember their names.

My c++ tester template:

${-- /*
    Vexorian's c++ tester template for greed. Version 0.1
    - Colors using ANSI C codes.
    - Allow custom test cases with unknown result.
    - Allow "disabling" custom test cases by modifying the list of tests to run.
    - Timeout for individual cases, modify CASE_TIME_OUT below to customize
    (c) Victor Hugo Soliz Kuncar, ZLIB/LibPNG license 
*/ }  
using namespace std;${-- /*Maybe template/your final code doesn't include using namespace std*/ --}
char do_test(${foreach Method.Params p}${p.Type},${end}${Method.ReturnType},int,bool);
//------------------------------------------------------------------------------
${<if RecordRuntime}
const double CASE_TIME_OUT = 2.0;
${<end}

char run_testcase(int __no) {
${<foreach Method.Params p}
 ${if p.Type.Array}vector<${p.Type.Primitive}>${else}${p.Type.Primitive}${end} ${p.Name};
${<end}
 ${if Method.ReturnType.Array}vector<${Method.ReturnType.Primitive}>${else}${Method.ReturnType.Primitive}${end} __expected = ${Method.ReturnType;ZeroValue};
 bool __unknownAnswer = false;
    
 switch (__no) {
${<foreach Examples e}
  case ${e.Num}: {
${<foreach e.Input in}
${<if !in.Param.Type.Array}
    ${in.Param.Name} = ${in};
${<else}
    ${in.Param.Name} = { ${foreach in.ValueList v ,}${v}${end} };
${<end}
${<end}

${<if !e.Output.Param.Type.Array}
    __expected = ${e.Output};
${<else}
    __expected = {${foreach e.Output.ValueList v ,} ${v}${end} };
${<end}
    break;
  }
${<end}
  /*case ${NumOfExamples}: { 
    // Your custom testcase goes here (don't forget to add to num/runTests below)
${<foreach Method.Params p}
    ${p.Name} = ;
${<end}
     
    __unknownAnswer = true; 
    break;
  }*/

  default: return 'm';
 }
 return do_test(${foreach Method.Params p , }${p.Name}${end}, __expected, __no, __unknownAnswer);
}

// Tests total:
int      numTests  = ${NumOfExamples};
// Tests to run when there are no arguments:
set<int> runTests = { ${foreach Examples e , }${e.Num}${end} };

//------------------------------------------------------------------------------
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <ctime>
${-- /*Maybe template/final code doesn't #include those files*/ --}
template <typename T> string pretty_print(T t) { stringstream s; typeid(T) == typeid(string) ? s << "\\"" << t << "\\"" : s << t; return s.str(); }
${<if HasArray}
// Vector print
template <typename T> ostream &operator << (ostream &out, vector<T> arr) {
    out << "{";
    for (int i = 0; i < arr.size(); ++i) out << (i == 0 ? "" : ",") << pretty_print(arr[i]);
    out << "}";
    return out;
}
${<end}

${<if Method.ReturnType.RealNumber}
#include<cmath>
bool double_equal (const double &expected, const double &received) { return abs(expected - received) < 1e-9 || abs(received) > abs(expected) * (1.0 - 1e-9) && abs(received) < abs(expected) * (1.0 + 1e-9); }

${<if Method.ReturnType.Array}
bool double_vector_equal (const vector<double> &expected, const vector<double> &received) {
    if (expected.size() != received.size()) return false;
    int n = expected.size();
    for (int i = 0; i < n; ++i)
        if (!double_equal(expected[i], received[i])) return false;
    return true;
}
${<end}
${<end}

string colorString(string s, int q)
{
    if (q == 0) {
        //neutral
        return s;
    } else if (q < -1) {
        //bad (score)
        return "\\033[1;41m"+s+"\\033[0m";
    } else if (q < 0) {
        //bad (single result)
        return "\\033[1;31m"+s+"\\033[0m";
    } else {
        //good
        return "\\033[1;32m"+s+"\\033[0m";
    }
}

string colorTestResult(char r)
{
    string s = string(1, r);
    switch(r) {
        case '+' :
            return colorString(s, 1);
        case '?':
            return colorString(s, 0);
        default :
            return colorString(s, -1);
    }
    return "";
}

char do_test(${Method.Params}, ${Method.ReturnType} __expected, int __caseNo, bool __unknownAnswer) {
 cout << "\\033[1;36mTest " << __caseNo << "\\033[0m: [" ${<foreach Method.Params p << ","}<< ${if p.Type.Array}${p.Name}${else}pretty_print(${p.Name})${end} ${<end} << "]" << endl;


${<if RecordRuntime}
    time_t __startClock = clock();
${<end}
    ${ClassName} *__instance = new ${ClassName}();
    ${Method.ReturnType} __result = __instance->${Method.Name}(${foreach Method.Params par , }${par.Name}${end});
${<if RecordRuntime}
    double __elapsed = (double)(clock() - __startClock) / CLOCKS_PER_SEC;
    cout << "Time: "<<__elapsed<<" seconds." << endl;
${<end}
    delete __instance;

    bool __correct = __unknownAnswer || ${<if Method.ReturnType.RealNumber}
${<if Method.ReturnType.Array}${--
    --}double_vector_equal(__expected, __result);
${<else}${--
    --}double_equal(__expected, __result);
${<end}
${<else}${--
    --}(__result == __expected);
${<end}

    if (! __correct) {
        cout << "Desired answer:" << endl;
        cout << "\\t" << ${if Method.ReturnType.Array} __expected ${else} pretty_print(__expected) ${end} << endl;
    }
    cout << "Your answer:" << endl;
 cout << "\\t" << ${if Method.ReturnType.Array} __result ${else} pretty_print(__result) ${end} << endl; 

    char __res = '-';
    if (! __correct) {
        __res = 'X';
${<if RecordRuntime}
    } else if (__elapsed > CASE_TIME_OUT ) {
        __res = 'T';
${<end}
    } else if (__unknownAnswer) {
        __res = '?';
    } else {
        __res = '+';
    }
    cout << " "<<colorTestResult(__res)<<endl;
    
    cout << "\\033[0;2m===============================================================\\033[0m" << endl;
    return __res;
}

int main(int argc, char *argv[]) {
    string result;
    if (argc > 1) {
        runTests.clear();
        for (int i = 1; i < argc; ++i) {
            runTests.insert(atoi(argv[i])); 
        }
    }
    int j = 0;
    for (int i: runTests) {
        while (j < i) {
            result += 'd';
            j++;
        }
        result += run_testcase(i);
        j = i + 1;
    }
    result += string( std::max(0, numTests - j), 'd' );
    cout << "${Problem.Name}: ";
    bool good = true;
    for (char ch: result) {
        good &= ( ch == '?' || ch == '+' );
        cout << colorTestResult(ch);
    }

${<if RecordScore}
    int T = time(NULL) - ${CreateTime};
    double PT = T / 60.0, TT = 75.0, SS = ${Problem.Score} * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT));
    string SSS = std::to_string((int)SS) + "." + std::to_string((int)(SS*100) % 100);
    cout << " (" << colorString(SSS, good? 1 : -2) <<")." << endl;
${<else}
    cout << endl;
${<end}
    return 0;
}

My python tester template:

${--
#    Vexorian's python tester template for greed. Version 0.1
#    - Colors using ANSI C codes.
#    - Allow custom test cases with unknown result.
#    - Allow "disabling" custom test cases by modifying the list of tests to run.
#    - Timeout for individual cases, modify CASE_TIME_OUT below to customize
#    (c) Victor Hugo Soliz Kuncar, ZLIB/LibPNG license 
}  
#-------------------------------------------------------------------------------
${<if RecordRuntime}
CASE_TIME_OUT = 2.00
${<end}

def run_testcase(__no):
${<foreach Examples e}
 if __no == ${e.Num}:
${<foreach e.Input in}
${<if !in.Param.Type.Array}
     ${in.Param.Name} = ${in}
${<else}
     ${in.Param.Name} = (${foreach in.ValueList v} ${v},${end})
${<end}
${<end}

${<if !e.Output.Param.Type.Array}
     __expected = ${e.Output}
${<else}
     __expected = (${foreach e.Output.ValueList v} ${v},${end})
${<end}

${<end}
 # Your custom testcase goes here (don't forget to update num/runTests below)
 #if __no == ${NumOfExamples}:
${<foreach Method.Params p}
 #    ${p.Name} = 
${<end}
 #
 #    __expected = None
 #
 #...
 
 # run the code
 return do_test(${foreach Method.Params p , }${p.Name}${end}, __expected, __no)

#Tests total:
numTests = ${NumOfExamples}
#Tests to run when there are no arguments:
runTests = [ ${foreach Examples e , }${e.Num}${end} ];

#-------------------------------------------------------------------------------

import sys
import time
import string

def colorCode(q):
    return [ "\\033[1;41m%s\\033[0m", "\\033[1;31m%s\\033[0m", "%s", "\\033[1;32m%s\\033[0m" ][q+2]  

def colorTestResult(r):
    q = {'+': 1, '?':0 }
    return colorCode( q[r] if r in q else -1 ) % r

def prettyStr(x):
    if type(x) == str:
        return '"%s"' % x
    elif type(x) == tuple:
        return '(%s)' % string.join( (prettyStr(y) for y in x), ',' )
    else:
        return str(x)

def tc_equal(expected, received):
    try:
        _t = type(expected)
        received = _t(received)
        if _t == list or _t == tuple:
            if len(expected) != len(received): return False
            return all(tc_equal(e, r) for (e, r) in zip(expected, received))
        elif _t == float:
            eps = 1e-9
            if abs(expected - received) < eps: return True
            if abs(received) > abs(expected) * (1.0 - eps) and abs(received) < abs(expected) * (1.0 + eps): return True
        else:
            return expected == received
    except:
        return False

def do_test(${Method.Params}, __expected, __caseNo):
    sys.stdout.write("\\033[1;36mTest " + str(__caseNo) + "\\033[0m: ["+${foreach Method.Params p +","+}prettyStr(${p.Name})${end}+"]\\n")


${<if RecordRuntime}
    startTime = time.time()
${<end}
    instance = ${ClassName}()
    exception = None
    try:
        __result = instance.${Method.Name}(${foreach Method.Params par , }${par.Name}${end});
    except:
        import traceback
        exception = traceback.format_exc()
${<if RecordRuntime}
    elapsed = time.time() - startTime   # in sec
${<end}

    if exception is not None:
        sys.stdout.write("RUNTIME ERROR: \\n")
        sys.stdout.write(exception + "\\n")
        correct = False
    else:
        correct = __expected is None or tc_equal(__expected, __result)
        if not correct:
            sys.stdout.write("Desired answer:\\n")
            sys.stdout.write("\\t%s\\n" % prettyStr(__expected) )
        sys.stdout.write("Your answer:\\n")
        sys.stdout.write("\\t%s\\n" % prettyStr(__result) )
    
    res = '?'
    if not correct:
        res = 'X'
${<if RecordRuntime}
    elif elapsed > CASE_TIME_OUT:
        res = 'T'
${<end}
    elif __expected is not None:
        res = '+'
    sys.stdout.write(" %s\\n" % colorTestResult(res) )
    sys.stdout.write("\\033[0;2m%s\\033[0m\\n" % ('='*63))
    return res


def run_tests():
    global numTests, runTests
    result = ""
    if len(sys.argv) > 1:
        runTests = [ int(arg) for arg in sys.argv[1:] ]
    j = 0
    for i in set(runTests):
        while (j < i):
            result += 'd'
            j += 1
        result += run_testcase(i)
        j = i + 1
    result += 'd' * max(0, numTests - j)
    line = "${Problem.Name}: %s" % string.join( (colorTestResult(ch) for ch in result), '')
${<if RecordScore}
    T = time.time() - ${CreateTime}
    PT, TT = (T / 60.0, 75.0)
    points = ${Problem.Score} * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT))
    points = "%.2f" % points
    q = 1
    if any( ch != '+' and ch != '?' for ch in result ):
        q = -2
    points = colorCode(q) %  points

    line = "%s (%s)" % (line, points)
${<end}
    sys.stdout.write("%s\\n" % line)

if __name__ == '__main__':
    run_tests()

So

As you can see, it only took me a couple of hours distributed in a couple of days, to make the tester template I wanted, with all the features I liked and needed. For KawigiEdit, I needed to edit the source code, and I still didn't have such great results. This is the reason I switched to greed.

I did have a couple of issues in other places. For example, I like to use long instead of long long for 64 bits integers. I was unable to do that using only templates. I had to patch the source code to add a configuration point. Greed is open source and in github, so it wasn't complicated. Hopefully these updates will be incorporated in the official build :).

I wonder, for example, what is the limit now. Maybe I am going to make a tester that uses individual threads for each test cases, so that multicore computers run test cases faster. My Google code jam template already does this, although Google code jam has a more urgent need for that as you need to run code locally for the complete test cases and not just examples. However, I once lost qualification to a TCO tournament round because of 0.2 seconds of difference in submission speed against another coder. Do not underestimate the importance of the time it takes you to test things.

6 comments :

vexorian said...

Forgot to mention my c++ tester template requires c++11.

Vladimir Iofik said...

thanks! great article!

Vladimir Iofik said...

However, this does not seem to work in Greed 2.0.
(You have to set variables like greed.shared.templateDef.source.outputFileName here)

Also I could not find a way to put files into
{root}/499
instead of
{root}/SRM 499

vexorian said...

Yeah, I made this tutorial when Greed 1.6 was the thing.


Greed 2.0 changed many ways. But I am waiting for it to leave beta before making a new tutorial.

Commented on your isse regarding "SRM ".

vetiarvind said...

It would be better if Shivawu would include your changes as part of his plugin. Could you make a request? The tester template you have provided seems a lot better than the default one. That way you would only have to talk about the after-generation-hook portion as well as basic templating.

vexorian said...

This is vexorian, my disqus is acting up.


I think all the relevant changes I did to Greed are now part of Greed 2.0. The colorful tester templates can be enabled.