Report: 2013 Prolog Programming Contest

This is a slightly enhanced version of the Prolog Programming Contest speech during the ICLP 2013 banquet, on the boat.

It is good to be back at ICLP: I have not been able to attend for the past 4 years. The drawback of skipping so many ICLPs is that I recognize few people. I obviously do not recognize the younger attendants because they are new, and the older guys have forgotten to put more recent pictures on their websites and have become unrecognizable.

It is also good to be back in Istanbul after 41 years: I was here with my friend Paul in 1972. Our fantastic, adventurous trip through Turkey started in Istanbul. But on the first day here, we lost half of our money during a black market money exchange in the streets, so the next three weeks, we had to save money on food: the price of the busses was fixed of course. It meant surviving basically on bread, water melon and diarrhea. I lost 10 kg, and I was secretly hoping that during this ICLP in Turkey, I could lose as much again, but with the abundance of
food, during the breaks at the conference, and here on the banquet boat, it is not going to happen. I must admit: until now, I did not realize that one could eat well in Turkey.

Back to the contest …

First my thanks to the people who helped making this 20th Prolog Programming Contest a success: Esra Erdem and Joohyung Lee for making a room available, Evelina Lamma and Terrance Swift for a superb slot in the program, Gopal Gupta for sponsoring the contest financially through his company Interoperate, and Phuong-Lan Nguyen for cooking up the questions together with me, as she has done so many times in the past. Gopal’s company payed for the chocolates, and just so there is no misunderstanding to those who think the contest is about Prolog: it is all about Belgian chocolates, pralines to be more precise.

The contest takes two hours, and every team consists of 3 persons. The traditional exception to that rule, since many years now: the Paul Tarau team consists of only one person. This year there was another exception: Peter Ludemann was also a single person team, because some people who promised they would participate did not. I am wondering, maybe Hans Ditmarsch, the expert on lying, can help me out here: a non-kept promise, when does it turn into a lie ?

The teams try to solve 5 problems: under time stress, that’s a lot. There were 8 teams this year, not an all time high, but quite ok. Together they produced 629 lines of Prolog code.

As soon as the problems are handed out, the participants – respectable professors, researchers, postdocs … – turn into undergraduates: they can hardly read the problem statement, and they lose the most basic of all skills: counting. Indeed, one participant questioned me on the example query: “the result is wrong, look here, you wrote it is 48, but it is 4 times 8, and that’s 54, no ?”. I gently told him I thought that “4*8 equals 48”. He looked at me in disbelief “ok, if you say so …”

A team gets Belgian chocolates when they submit their first solution; it doesn’t even have to be correct, and after all these years organising this contest, I am convinced: the participants are in the contest mainly for the chocolates, because hardly ever is the first solution correct. Teams can resubmit solutions for the same problem as often as they want.

Now the results: every team solved at least one problem; no team solved three; four teams had a correct program that did not scale. Indeed, in the invited talk of Torsten Schaub, we learned that it is easy to write a correct program in ASP, but to make it scale is difficult: Prolog is very similar. Still, while ASP people can then try to fiddle with all the toggles of the grounder/solver and hope that somehow by random chance their program will work on large input, Prolog programmers must rely on their brains. Two teams used assert in their solution, even though Michael Kifer gave us all a warning about how bad assert is (in modeling Transaction Logic) during his talk for the most influential 20-year paper award. And also despite the fact that the rules of the contest explicitly forbid to use any yuckie features of Prolog: some contestants asked whether that included findall/3 …

In third place ended a young team consisting of David Vaz, Przemek Wałęga, and Sitor Kortik: they deserve a special mentioning because they submitted solutions for three problems, and they failed on only one testcase for the third, so they were close to winning.thirdteam

In second place ended the team with Edison Mira, Johannes-Klaus Fichte and Jan Wielemaker. They solved two problems and needed 177 minutes for that, while the winning team solved the same two problems in 130 minutes.

So, the winners are Martin Gebser, Claudia Schulz and Stefan Ellmauthaler. They did something remarkable that never happened during a contest: they did not need to resubmit a solution, because it was twice correct from the first time ! They could have finished more problems, but during the contest, I could see they were unexperienced and used a bad strategy … they actually cooperated as a team.

Congratulations to the winners: you did well ! I am sorry the t-shirts are a bit big for some of you. After I came back from the conference, I have made (and send) their certificate. I could not print the winners’ certificate beforehand this time, as Peter Stuckey was not at the conference.

Two more things: the book about the first 10 editions of this contest is still available, hardcopy from me, free download from my website; and the 21th Prolog Programming Contest will take place in July 2014 at the occasion of the Vienna Summer of Logic: we are ready … are you ?

See you next year,

Bart Demoen