The Inaugural Prolog Programming Competition at ILPS'94

Appeared in Volume 8/1, February 1995

Bart Demoen

In conjunction with ILPS'94 in Ithaca, a Prolog Programming Competition was organized, and really took place. In April, I tried the same thing at PAP'94 in London, and it was a disaster because not a single participant showed up. At ILPS'94, there was more enthusiasm - and also much better support from the conference organizers (thank you, Wiktor Marek!) in giving the competition a good time slot, finding a good location (thank you Cornell University and, in particular, Anne Louise Gockel and Orlando Johnson), and promoting the competition.

The idea for a competition was first mentioned to me by Leon Sterling during the PC meeting for ILPS'93, but I am sure that many people must have toyed with a similar idea before. We got inspiration from other programming competitions (thank you, Vivek Khera, for the Internet Programming Contest problem statements). Evan Tick joined the organization later.

The competition was set up as follows: a student lab with 20 X-terminals and SICStus Prolog (thank you, SICS for providing your Prolog!). Participants (in teams of 2 or 3) were locked in the lab for 2.5 hours, during which time they submitted solutions to 6 problems given to them at the beginning. Every solution was evaluated as ok or not-ok according to a run with our test suite. We gave immediate feedback to the teams, so that they could submit new versions. Ranking was made according to the total number of correctly solved problems, with as second criterion the total time needed to submit the solutions, and as third criterion the run time of a particular solution. You might note that this still leaves the possibility for an ex aequo - something I only realized while typing this!.

Twenty people participated, formed into 8 teams. This made us reasonably happy, given that we could accept at most 10 teams, and that several people/teams who intended to participate, finally could not (e.g. the poster session was at the same moment). However, the most oft used excuse for not participating in the contest was "I never program in Prolog" - indeed, most people program mainly in their own language (AKL, Oz, CLP(R), Lambda-Prolog, Gödel, or something even more weird :-)). Alternatively, they only program in the language in which their own language is implemented (invariably C).

The competition was full of amusing incidents, like the team that didn't take the time to read the contest rules and consequentely didn't realize that it had to submit quickly! Or one participant saying, while handing in his solution: "I did my best to write a completely declarative program, but I now realize this was absolutely unnecessary". And the first team to ask for the SICStus manual, was a team with 2 people from SICS! It was also the first team to report that SICStus crashed after reconsulting (sorry about that: SICStus wasn't installed with the proper patch, but it wasn't a big problem). Also noteworthy: teams that used the debugger during the contest, got slowed down considerably. The lesson is: especially under time pressure, write correct programs!

I received many suggestions on how to improve the organization from the participants: give us more time, let us choose our own programming language, rate the solutions according to their beauty and elegance. These are good suggestions, but they make the organizing much more difficult.

Most participants were "frustrated" afterwards because of all the constraints, but this is often what programming in the real world is about: lack of time, unknown environments, buggy software, no manuals (I forgot to bring the SICStus manual :-)). Notwithstanding this frustration, people said that they would participate next time. I take this as an indication of some satisfaction, or is it just the wish for revenge?

The story of the winning team (congratulations, captain Peter Stuckey and Fergus Henderson) is interesting: they came 40 minutes late, opened one shell on their screen, used vi for editing, left it completely after editing, started SICStus in the same window, consulted the file, ran some tests, left SICStus, and restarted the cycle. They didn't bother to have a separate window for the editing, or have an editor coupled to the Prolog system, no reconsult, no ^Z. Simplicity seems to pays off during such a contest. They solved 4 of the 6 problems - and almost had problem 5, which is very good when the average was 2! But I have to add also, that when they failed to find a solution for problem 5 (close to the end of the contest), they submitted (almost) random variations of their initial program in the hope of hitting on a correct solution. The winners each received a copy of the special "Ten Years of Logic Programming" double-volume issue of the Journal of Logic Programming (thank you, Elsevier). What can we say? These bloody Australians did it again: aside from having the fastest Prolog implementation (Mercury), they also have the fastest Prolog programmers!

The problems can be FTP-ed anonymously from:
ftp://ftp.cs.kuleuven.ac.be/pub/private/bimbart/ilps94competition.ps

I might comment on some of these problems at another time, but I want to present one problem here. It is the smallest and easiest problem of the competition, and it was included so that every team would have at least one correct solution:

Generate all triples (X,Y,Z) that satisfy the conditions that all three are different integers between 0 and 9 (both included), and that (10*X+Y)/(10*Y+Z) equals X/Z (with infinite precision)

The output of your program should be to the screen, and be in the form:

	3 5 9
	3 1 6

It was amazing that the fastest team still needed about 30 minutes for this problem and that several teams resubmited their answer more than once before they got it correct! If you can do it in less than half an hour, you are a potential winner of the next Prolog Programming Competition - most probably at ILPS'95 - so participate next time!

Bart Demoen
Email: bimbart@cs.kuleuven.ac.be