Coding Challenges Framework

• Download source - 12.8 MB

Introduction

There are many code challenge sites on the net currently. They're a great way to learn to code, to keep up to snuff if you are already a coder and even to win rewards in the form of jobs or money. They range from simplistic to incredibly challenging and are becoming more and more popular. I love taking up these challenges but starting up a separate project for each one was a hassle. Keeping track of them and knowing what their status was was problematic and writing all the boilerplate code that goes along with them was tedious - especially if you wanted nice features in there like timing their performance, editing the input and trying again and referring back to their web page. Also, different languages had different requirements and different contests handled their I/O differently. I decided to make my life easier by writing a framework which provides these niceties and keeps all my code tidily together.

Background

There were three basic premises that I really wanted to adhere to in this process:

First I wanted to ensure that there be one self contained file per challenge. I've seen many projects which were designed to be expanded but required changes in several places spread across several files in order to make such an expansion and I wanted no part of that. It's error prone, tedious and usually redundant. In order to solve a new challenge in this current framework you simply add a single source file for that challenge. That source file should implement the IChallenge interface which only requires three functions - one to return the sample data for the challenge, one to return the expected output for that sample data and, of course, one to solve the challenge. The class that implements the IChallenge interface should be decorated with information on the contest involved, the name of the challenge within that contest and optionally, a URL pointing to the challenge's site. That's all that's required to solve a challenge

Second, I wanted multiple languages to be represented. The different contests have different requirements as far as which language can be used on them. Unmanaged C++ is almost always an option so I definitely wanted that. C# is my personal language of choice so I wanted that also. F# is something I've really enjoyed programming in and seemed like an easy thing to add so I wanted to put that in as well. As of right now, those are the three language choices. Unmanaged C++ was a special challenge since the attributes which I use for decoration in C# and F# aren't available. I ended up using some special C++ macros to allow for this. Also, special care had to be taken with the I/O in unmanaged C++.

Third, I wanted the challenge files to be at least optionally directly available for submissions to the challenge sites. That is, I wanted to be able to structure the files so that end end result would be acceptable in its entirety as a submission for that challenge. I did achieve this with various amounts of jury rigging. The C++ files were pretty easy due to macro magic. The F# files were also pretty easy with the help of a defined constant CHALLENGE_RUNNER which is defined for both C# and F# files. The C# files were a little tougher but with the right "template" they will work fine also as a submission.

While the files can be formatted so as to work in submissions and it really isn't hard to do so, it may not always be desirable. The challenge site may not accept the language you wish to solve the challenge in - for instance one of the largest, UVa, only will allow the unmanaged C++ code out of the three languages the framework currently supports. Another problem is that you may wish to use libraries that aren't available on the challenge site. Most sites don't allow arbitrary libraries to be included so in these cases the code can't be submitted. Some sites (i.e., Project Euler) don't even take submissions. If you can type in the answer you've solved the challenge. In these cases the code can be made a little simpler to handle by leaving out the boilerplate for the submissions process. Also if you don't like the boilerplate, you can just write without it and and then cut and paste the solution onto the challenge site.

Using the code

This is a framework for solving programming challenges and as such, doesn't really do much until you start writing code for it to solve those challenges. As mentioned above, solving a new challenge consists of adding a single source file which implements the IChallenge interface.

public interface IChallenge
{
    void Solve();
    string RetrieveSampleInput();
    string RetrieveSampleOutput();
}

The class implementing IChallenge should be decorated with information about the challenge. In general, there are three pieces of information that must be included with a challenge.

First is the contest. The challenge solutions will appear in a treeview in the framework and the nodes of that treeview will be whatever is written in for the contest in these decorations. It can be anything but any solutions with the same contest name will be collapsed under that name in the treeview.

The second is the specific challenge name. Again, this can be anything but it will be what is listed when the contest node is expanded for this challenge.

Finally, and optionally, a URL can be given which points to the page for the challenge. When the challenge is selected in the treeview a button for the webpage will be enabled which will take you to that webpage.

As an example, the decorations for the sample code in the project is for a CodeChef sample challenge. CodeChef accepts all three supported languages and all the submissions for the sample challenge are viewable in CodeChef so this is the sample I've used. Here is the C# decoration for the sample challenge:

[Challenge("Code Chef", "Test - CS", "http://www.codechef.com/problems/TEST")]

The decoration for F# looks similar:

[<Challenge("Code Chef", "Test - FS", "http://www.codechef.com/problems/TEST")>]

As mentioned previously, C++ doesn't have attributes so a special macro takes on this job for C++ challenges:

prolog("Code Chef", Test, "Test - CPP", "http://www.codechef.com/problems/TEST")

The second argument to the prolog macro is the namespace to place the challenge. Most challenge sites want to have the code written in Main() so that's where the C++ submission code goes. This would, of course, cause collisions if all those functions appeared in the same namespace which necessitates our placing a challenge specific namespace around each instance of Main() - hence the second, namespace, parameter in the C++ challenges.

Note that in each of the challenge names I've chosen to append either CS, FS or CPP depending on the language. This is purely my own convention. Since challenges in all the languages look alike, if I have a single challenge being solved in multiple languages I like to specify that in the challenge name. It could be done differently - I could differentiate automatically in the framework by different colors or maybe as sublevels of the treeview, but this is an easy workaround for the moment.

In C# and F# we implement an interface to solve a new challenge. The IChallenge interface as mentioned before has three members: Solve(), RetrieveSampleInput() and RetrieveSampleOutput(). Solve, for all three languages (well, there is no "Solve()" in C++ - it's place is taken by Main - but the gist is the same) always takes it's input from the Console(stdin for C++) and writes back to the Console (stdout for C++). This matches the protocol that most sites use - UVa and CodeChef among them. For those that don't, adapters may need to be written. This is usually simple and the resulting code can be used as boilerplate for all the challenges in that contest.

Here is some sample code for C# to solve the sample challenge. This is the simplest possible version and so will not work as a direct submission to sites.

using System;

namespace MiscChallenges.Challenges
{
	public static partial class ChallengeClass
	{
		[Challenge("Code Chef", "TestNS - CS", "http://www.codechef.com/problems/TEST")]
		public class ChefTestNS : IChallenge
		{
			public void Solve()
			{
				var input = Console.ReadLine();
				while (input != "42")
				{
					Console.WriteLine(input);
					input = Console.ReadLine();
				}
			}

			public string RetrieveSampleInput()
			{
				return @"
1
2
88
42
99
";
			}

			public string RetrieveSampleOutput()
			{
				return @"
1
2
88
";
			}
		}
	}
}

(The boilerplate for submission worthy code is illustrated in the three sample files which all can be submitted successfully)

Notice that the class which implements IChallenge is a nested class of ChallengeClass which is partially implemented in each challenge source file and is itself in the MiscChallenges.Challenges namespace. You can name the class anything as long as it's unique from all other IChallenge implementations. Conventionally the name should be similar to the challenge name. I've used the "@" style string for the sample input and output to allow me to put the input and output at the left side in exactly the same format they've got to take when passed down. In order to do this I have to put a newline after the starting double quotes of these string. This newline is expected in the framework and is removed before passing in to the challenge code.

The F# code is similar. I've here included the boilerplate so this code can be submitted to CodeChef as is and will pass the test...

module Test
open System

let main() =
    let mutable chk=true
    while chk do
        let x = int(Console.ReadLine())
        match x with
            | 42 -> chk<-false
            | _ -> printfn "%d" x
main()

#if CHALLENGE_RUNNER
open FS_Challenges

[<Challenge("Code Chef", "Test - FS", "http://www.codechef.com/problems/TEST")>]
type TestChallenge() = 
    interface IChallenge with
        member this.Solve() = 
            main()

        member this.RetrieveSampleInput() = @"
1
2
88
42
99
"
        member this.RetrieveSampleOutput() = @"
1
2
88
"
#endif

Finally, the C++ sample code is pretty simple too. Macros make the C++ code a little easier to work both in the framework and in the submission code so I'll show the full submission worthy C++ code here:

#include <iostream>
#include <queue>
#include <functional>
#include <vector>

prolog("Code Chef", Test, "Test - CPP", "http://www.codechef.com/problems/TEST")

using namespace std;
int main(void) {
	int x;
	cin >> x;
	do
	{
		cout << x << endl;
		cin >> x;
	} while (x != 42);
	return 0;
}
sampleInput
R"(
1
2
88
42
99
)";

sampleOutput
R"(
1
2
88
)";

epilog

Note the four macros: Prolog, SampleInput, SampleOutput and Epilog. Prolog has been discussed and the other three are pretty self evident. As in C#, I'm using the raw string literals feature here so that the sample data looks precisely like it does on the sample page. This isn't necessary, but if you don't use it remember the leading newline which is required and used here for the same reason it's used in the C# and F# files.

That's pretty much all there is to it. There is a separate project for each language and challenges in those respective languages should be placed in the proper projects obviously. I made separate folders in the Programming Challenges folder for each contest. Unnecessary but handy I feel. Folder structure is unimportant as long as all the IChallenge implementations are nested within ChallengeClass. As far as I can see you can't create folders within C++ or F# projects or else I'd do the same there. One thing that perhaps should be noted is that the C++ DLL is copied as a build step using a relative path over to the C# directory which means those two directories have to keep the same relative position or the build step needs to be modified.

The UI is pretty simple but here are some things to point out:

To run a challenge, simply select it in the treeview to the left and click the run button. The sample input will appear in the pain below the output pain when the challenge is selected. It will be passed to the challenge solver and the output from the solver will be placed in the output pane above. If it matches the expected output then it will appear in green. If there is any discrepancy, it will appear in red.

The input can be edited to try new cases if desired. In that case the expected output is ignored and the output will appear in black. If the challenge code throws an exception the message for the exception will be displayed in red on the output. Since you can edit the input and probably didn't write your challenge code to be terribly error resistant, this is pretty easy to happen. Many challenges are very sensitive to their inputs for performance also and can easily take indefinite times to calculate. Each challenge is run on another thread and the Cancel button is enabled while it's running. Pressing the Cancel button summarily kills the thread and puts "Challenge Cancelled" on the output pane in red. There is no allowance for funny operations which means generally avoid anything that can't be killed in the challenges. I know this is considered "dangerous" but challenges generally don't do much other than calculate so don't really require protection. I thought of adding something in to the decorations to say "don't allow cancel in this challenge" but haven't done it yet. If that really was a problem, this should be easy to implement at the expense of slightly more complex decorations.

Finally, a timer is set before the solving and consulted afterwards and the time in ms to solve the challenge is displayed.

Points of Interest

This was an interesting learning experience. I really hadn't tried making a solution with three different languages in three different projects and so there was some challenge in getting that to work correctly. It was also interesting figuring out how to achieve attribute like features from an attribute-less language like C++. I needed to have the information from all the prolog macros available at startup without actually manually creating an array with all that information. The prolog macro does this by assigning functional values to dummy variables. The function in question adds the created ChallengeInfo object to a static global vector so that it's available when the C# assembly calls for it at startup. Some fancy footwork ensures that we don't run into problems because of initialization order. It's been 15 years since I was seriously doing C++ so I'm not at all sure that this is the best way to do it, but it seems to work.

Something I wish I could have easily done is to have circular references between the C# and F# projects. I would have liked to reference and use the C# attribute in F# but that would have kept me from referencing the F# project from the C# one to actually call the solvers. That seemed a bit more important so I just made some essentially redundant attributes in the F# project. Not that big a deal since these two are not required to be identical but it would have been nice to have just one such attribute. I suppose I could make a third project with nothing but the attribute in it and referenced it from both assemblies but that just seems like way overkill.

In the end, the main thing that has made this project interesting has been the ability to easily do lots of challenges in lots of languages, keep track of all of them easily and see the results. Another thing that this framework makes easy is to write solutions in different languages and compare the performance. That's not it's main purpose but it has shown me some things that I would not have guessed otherwise.

History

7/9/2015 - initial submission