2nd Annual Prolog Programming Contest

Appeared in Volume 9/2, May 1996

Bart Demoen

The second annual Prolog Programming Contest took place in Portland on Monday, 4th December 1995, at the Portland State University (PSU) during ILPS'95.

Some lobbying during the ILPS'95 welcome reception resulted in 10 registered teams, consisting of 27 people, 20 of whom didn't compete last year. Well-known and respected people, taking the voluntarily risk of not winning this most prestigeous of all Prolog programming contests :).

Every team was special in some respect, but perhaps the most notable was the team consisting of Saumya Debray, Phil Wadler and Peter Van Roy. Phil Wadler took part to "learn something about Prolog" (his words, more or less) and he was unique in submitting a solution using freeze/2 for the "powers" problem.

The winning team of last year - the Australians from Melbourne: Peter Stuckey and Fergus Henderson - competed again, this time slightly handicapped by Thomas Conway :). The Swedish team from Uppsala (last year's runner-up) was also present, now with Jonas Barklund (ill with fever), Johan Bevemyr and Thomas Lindgren, who replaced Per Midler. Aside from these eminent groups, there was a team from Leuven (with two non-Belgians), one from Vancouver (with two non-Canadians), one from Madrid (consisting of three real Spaniards) and several mixed teams. One group with three members managed to represent four continents.

The competition consisted of six problems, each worth a single point. One of the problems had a bonus point, but only Manuel Hermenegildo tried for it. He ran into time problems, maybe because the bonus concerned looping, or was it because he didn't remember exactly how he implemented fair AND-parallelism in &-Prolog?

Every problem was solved by at least one team and every team solved at least one problem. Every team submitted at least two solutions and most teams solved three. In fact, the average score was much higher than last year: 2.9 correct solutions per team, compared to 2.0 previously. This year the problems were just as difficult, but the contest only lasted two hours, not three as last year.

Evan Tick and I organised the contest again this year. As judges, we had a busy time during the contest when alledged solutions were submitted seemingly every second, but together, we coped with the flow of creativity. Also, we got lots of local help from Hannah Linder and John Jendro from PSU; thank you guys!

I "set" the questions myself: a time-consuming but gratifying task. The "numbers" question was adapted from an old ACM programming contest (thank you Vivek Khera). A boring maths assignment given to my son triggered the "cycle" problem. I can't remember where the inspiration came from for the other problems, but I'm certainly not claiming they were invented by me.

The contest was exciting: the first correct solution (to the "triangle" problem) was submitted after only five minutes by the Melbourne team! The Uppsala team submitted its first correct solution after 16 minutes but took the lead after 33 minutes with its second correct solution. Melbourne quickly caught up 3 minutes later, and took the lead with 3 correct solutions after 45 minutes. However, 13 minutes before the competition's end, Uppsala regained the lead with 5 correct solutions while Melbourne still only had 4. It was then clear that if Melbourne managed to submit one more correct solution, they would win because of their speed in the beginning. But would they manage? Yes, they did! Only 2 minutes before the end, Melbourne submitted its fifth solution, which incidentally took us until the next day to find correct.

On average, Melbourne needed 10 minutes less time per problem than Uppsala, and so for the second time, Melbourne won the contest. To both the Melbourne and Uppsala teams: congratulations, you were exceptionally good. I hope you'll compete again next time, and may the best team win. I hope the winners enjoyed their book prizes, generously donated by the MIT Press (thank you MIT).

I received numerous comments and remarks about the contest. A big problem will always be lack of resources, although PSU were really great (as was CSU in Ithaca in 1994). Also, the contest's form and content may change in the future. Perhaps the next one will be a Logic Programming Contest? If you want to co-organize it, let us know.

The questions for both contests can be obtained by anonymous FTP from:
ftp://ftp.cs.kuleuven.ac.be/pub/private/bimbart/
in the files ilps9*competition.ps. Feel free to use them, and it would be nice if you mentioned the annual Prolog programming competition.

See you next time.

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