The First 10 Prolog Programming Contests

Prolog is an excellent programming contest language: Prolog is close enough to the ultimate specification language (logic), so that the distance between problem and solution is not too big. This means that, even if you don’t have a clue about a good algorithm, you might still end up with a nice program that computes a useful result (at least for small problem sizes). Prolog is also a real programming language, which means you can express your favorite nifty optimal solution strategy in it.

Programming is enormously fun. Fun was indeed our main motivation for starting the series of Prolog Programming Contests in 1994. Ask anybody who ever participated in a Prolog Programming Contest: they loved it! There is a thrill in trying to solve five problems in two hours, crammed in a small room filled with ten or more sweaty teams doing the same. And there is a great satisfaction, unmatched by any other daytime scheduled conference event, when the attempt is even partially successful.

This book shows solutions to problems that were in the first 10 Prolog Programming Contests. The solutions in this book were not constructed by participants during the contest, since the contest rules always prevented that. However, many of our solutions could have been constructed during the contest under extreme time pressure, and so you will find many solutions using the generate and test strategy, together with a higher than usual deployment of member/2, append/3, findall/3 and even reverse/2. On the other hand, we have avoided dynamic predicates (except in the solution of two problems), and we have often preferred the Prolog if-then-else and once/1 predicate over the use of the !. We have also avoided comments in the programs.

Mind you: this book does not attempt to teach you how to program in Prolog. For that, you will need to read one of the excellent books on Prolog, or go through one of the on-line Prolog tutorials. You can find them in the comp.lang.prolog FAQ . Keep in mind that reading the books is not enough: you must do lots of exercises!

So we assume that you have already some basic Prolog programming skills. Then, how should you use this book? We suggest that you do not try to digest all questions and answers at once. Read one problem statement, skip the hints, and solve the problem, preferably with the clock ticking at your side. Oh well, if you really want, you can read the hints anyway. When you are finished programming, look at our solution, and compare it with yours. You might be inclined to make a judgment like ‘My solution is better than yours’, or the other way around. Don’t just stop there: learn from the differences.

In case you are particularly proud of your solution, or you think your program is better than ours for some reason, please send it to us. We intend to make the book available electronically very soon, and your solution might find its place there – with proper credits to you of course. As an alternative, consider sending an elaborated version of your program to the Logic Programming Pearls section of the Journal of Theory and Practice of Logic Programming.

We have made sure that all the solutions in this book run as is in SWI-Prolog. This means that together with the lists library and a small contest library (see Page 145), you always have a working program. Most solutions also run in Ciao, SICStus Prolog, and YAP. When they don’t, the reason is usually a small difference in the lists library or a missing common predicate.

Some of the problems lend themselves better to being solved in a different LP language, such as CLP, CHR, XSB, ASP, . . . Have a go at it and spread the word!

This book is meant to be sold out quickly, so only a small number of copies were printed. Soon you will be able to download the book for free. The web version of the book will contain all our programs in a form that you can directly consult, a set of test cases, and, hopefully with your help, new solutions in Prolog and other logic languages. You can find this material and further contact information at http://www.cs.kuleuven.be/~dtai/ppcbook/.

Finally, before you dive into the problems, consider this quote from an honest participant after the first contest: ‘I did my best to write a completely declarative program, but I now realize this was absolutely unnecessary’. We hope you enjoy the book!