A Challengers Handbook

by

Caesum

Programming

Programming challenges tend to divide into two areas - the proper programming type challenges like at Valladolid and the casual programming challenges on most challenge sites. Valladolid is a fantastic set of problems to get into but be aware that problem difficulty can vary considerably and that when you have a WA (wrong answer) on a problem that you may find it difficult to work out why. Having done over 900 of these problems I can say that it is great fun to spend 15-20 minutes doing one but submitting the same problem over and over with repeated WAs can be frustrating. If you are starting off then pick levels with high numbers of submissions and high success rates, and pay attention to the forums and comments that people make there.

So, on to the majority of challenge programming which tends to be fairly simple tasks. Most challenges ask for one of two things, either 1/ computation of something for an answer (how many times does 'ABC' occur in the cube formed from a file of text...) or 2/ webpage 'x' will give you something that you must do something with and return to webpage 'y' in some form and you have x seconds to do it in.

It is always an advantage to know as many languages as possible but if you are a beginner and learning your first language then good luck! I personally think C is good to know although not really a beginners language - it does have the advantage that knowing C there is not much more to learning PHP, and C is ideal for small throwaway programs written in 10 minutes. C is not the best though for challenges under category 2 above. Personally for category 2 programs I tend to do one of two things - 1. Use Borland C++ Builder, RAD environment. Its easy to have a short program that can connect to the web, although strangely enough it is not easy to get at the source code of the returned page and you have to use something like this, or 2. Use a combination of programs including my own web page fetcher and batch files to request page and dump in a file, process it and dump new request to a file and then fetch the result. It sounds complex but its not, its more lateral thinking. I am sure that many people will now say well why do that when you just do blah blah blah in Perl or PHP. The bottom line is that everyone will do something different, a recent poll on one site showed that practically everyone had used a different language to approach a problem. Personally I spew out C code at an amazing rate and thats why I do it the way I do. After 900 Valladolid programs I write C faster than English :)

If a particular challenge site has 10 programming problems all of the form 'connect to web page and get problem, process problem, return problem to another web page' then obviously the approach is to write a skeleton and insert new 'process problem' sections to complete each challenge. Now some people take code reusability to an extreme but personally I only have a few core routines that I reuse (mostly around big number integer programming). Occasionally I will rewrite a program for another purpose but I do write a lot of things from scratch. In the past I have spent more time searching the net for code that I could rewrite than it takes to write something from nothing.

The thing about most challenge site programming levels is that I have often written bigger more complex programs to solve other levels on the same sites, like encryption levels, or cracking particular password schemes. If you take challenges seriously then you really need to be able to program to do anything at all and most programming levels will not be difficult for you - often one small piece of the program will be more of a problem than the real problem itself (how do you make a POST request using language X ?).

Whilst writing this I feel compelled to include a program to do something and rather than take some similar problem to some challenge level (like compute the sum of the squares of numbers from 1 to 10000 - which takes less than 1 minute to complete in Excel and around 20 seconds in Maple which are the two obvious choices for this particular problem) I will study something of more use instead - in this case it will be the web page request program. Some time ago the original Aspect challenge was around and it included an online realtime game where you could attack other players and build your empires. You could make moves every so often and I used the program to be discussed here (although I will clean it up a little for inclusion here) as the basis for a program that played the Aspect challenge automatically :)

Some of you might note that this program is very similar to the SMTPsend program that I wrote, and it is basically the same source rewritten. So you will need a typical HTTP Request and the Source code. Now you can just type something like:

httpget -v www.fbi.gov request.txt

And the program will go off and do its thing. With some thought and some processing of the returned text, etc you could use this in a brute forcer but I dont recommend brute forcing any of the Electrica challenge because I took that into account when writing the challenges and it would take forever to brute force any of them. Also I do not recommend brute forcing other challenges unless it is a specific requirement of the challenge to do so.

The source code should be fairly self explanatory - it is worth noting that the http request and response is a fairly simple conversation along the lines of 'give me this page' and then 'here you go' compared to SMTP which is a little more complicated. It is worth noting that you will sometimes get a pause at the end just before the connection is closed, and you may want to look for the </html> if you intend writing a bot like I did. To complete some challenge levels you will want to perform some function on the returned text and create a new response to send back. To do this you need to append all of the response into one buffer, parse the buffer, formulate your reply, and send the second request back. Simple! You could send request.txt back again, junking the first line in preference to your formulated response.

Incidentally the best way to construct the request.txt in the first place (particularly if the site you are trying on uses cookies) is to grab it from the log window in proxomitron. Turn all the options off and log a request from IE, cut and paste the headers into the text file, and off you go. Proxomitron is discussed on the internet page of this guide :)

If you really want to learn more about programming then I'm sure you have your own language and can find plenty of material on it. So instead I'll give you some alternate resources, why not spend some time reading about algorithms ? Knuth is a great text on this, but can be hard going. I valued it some years ago for its information on multi-precision arithmetic. Introduction to Algorithms is massive and very complete - I often refer to it when doing ACM problems. It's a far easier read than Knuth as well. Herbert Schildts 'programming from the ground up' books really are very detailed - I have the 98 version one, but the 2000 version appears to be the latest.

Update 2012: The C methods above have really become a little outdated and personally I have been using Jeff Heatons Java bot sourcecode as the basis for my programs recently. Java has some advantages in that images can be processed easily along with many other things. I know, however, that many people prefer php, python, etc for challenge programming but if you want to use java then grab the bot code.

Back to Contents