Programmierwettbewerbe bei Infinite Search Space

Prinzip

Ein Wettbewerb besteht aus einer Reihe von sehr ähnlichen Problemen (die sich zum Beispiel nur durch einen gegebenen ganzzahligen Wert unterscheiden). Für jede Teilaufgabe kann man eine Lösung eingeben (und auch jederzeit eine bessere nachreichen). Der Wettbewerb ist so konstruiert, dass sich die Lösung relativ einfach überprüfen und bewerten lässt. Für jede Teilaufgabe bekommt derjenige, der die beste Lösung gefunden hat, einen Punkt und diejenigen, die eine weniger gute Lösung haben, entsprechend Teilpunkte. Man kann jederzeit seinen eigenen Punktestand für die Teilaufgaben einsehen, außerdem wird noch die Gesamtpunktzahl ermittelt und danach ein Ranking aller Teilnehmer erstellt, das man ebenfalls einsehen kann.

Im Gegensatz zu den „Al Zimmermann’s Programming Contests“ gibt es bei diesem Wettbewerb (bisher) allerdings nicht viel zu gewinnen.

Der aktuelle Wettbewerb „Orchard Planting“

Zurzeit befasst sich der Wettbewerb mit einer Variante des „Orchard-planting problem“ (beschrieben unter anderem in der englischen Wikipedia) mit vier Bäumen pro Reihe: Es geht hierbei darum auf einer Ebene (Obstgarten, engl. „Orchard“) n Punkte (Bäume) so unterzubringen, dass es möglichst viele Geraden gibt, auf denen sich genau vier Bäume befinden, aber auf keiner Gerade mehr als vier Bäume liegen.

Auf der Website muss dabei für jedes der 50 Teilprobleme (das heißt für jede Anzahl Bäume n von 11 bis 60) eine Liste mit den (ganzzahligen) Koordinaten der Bäume im Garten abgegeben werden, und die Website ermittelt selbst, ob die Lösung gültig ist und wie viele Geraden mit vier Bäumen es darin gibt. Nach der Anzahl der Geraden mit vier Bäumen bemisst sich dann auch die Punktzahl für das Teilproblem: Wenn für das Teilproblem mit 11 Bäumen die maximal abgegebene Anzahl an Geraden mit vier Bäumen bei sechs liegt, bekommt man beispielsweise einen halben Punkt, wenn man wenn man eine Lösung mit drei Geraden auf denen vier Bäumen liegen eingegeben hat. Wenn man für alle Teilaufgaben die beste Lösung hat, kommt man demzufolge auf die Maximalpunktzahl von 50 Punkten (hat im Moment niemand).

Los geht’s!

Wer also Lust hat, in einer Programmiersprache seiner Wahl ein bisschen mit Teilnehmern aus aller Welt um die Wette zu programmieren oder schon seit längerem auf der Suche nach einer Alternative zum „Al Zimmermann’s Programming Contests“ ist, kann sich die offizielle Aufgabenstellung zum „Orchard Planting“-Wettbewerb anschauen und loslegen.