spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

In diesem Forum werden in unregelmäßigen Abständen Programmier-Contests stattfinden.

Die Aufgaben
Die Aufgaben sind eher allgemeiner Natur, also nicht unbedingt spielespezifisch, relativ einfach und jeweils innerhalb kurzer Zeit lösbar. Die Aufgabe besteht darin, eine Funktion in C++ mit vorgegebener Signatur (Rückgabetyp und Parametertypen) zu implementieren, die eine gewisses Problem löst.

Frist und Abgabe
Jeder Contest hat eine feste Deadline. Wenn der Contest beispielsweise am 09.03. endet, dann werden Einreichungen bis um 23:59:59 dieses Tages akzeptiert. Man darf mehrmals abgeben. Es wird immer die letzte Abgabe zur Bewertung herangezogen. Mehrere Varianten abzugeben ist im Allgemeinen nicht zulässig, es muss sich für eine davon entschieden werden.
Die Abgabe erfolgt per E-Mail an contest@spieleprogrammierer.de. Dazu reicht die .cpp-Datei, die lediglich die zu implementierte Funktion enthält (ohne das Gerüst), mehr ist nicht nötig. Die Datei sollte irgendwo als Kommentar oder im Namespace den Namen enthalten, unter dem du am Wettbewerb teilnehmen willst.

Auswertung
Nach Ablauf der Abgabefrist werden die Lösungen bewertet. Dazu gibt es gegebenenfalls Statistiken und eine genaue Erläuterung des Testverfahrens. Die Lösungen und das Testprogramm werden ebenfalls veröffentlicht. Wer nicht möchte, dass seine Lösung veröffentlicht wird, der sollte dies rechtzeitig bekannt geben.

Bewertungskriterien
Die Korrektheit bzw. Gültigkeit der berechneten Lösungen ist sehr wichtig! Zu jeder Aufgabe gibt es eine Referenzlösung oder zumindest eine Funktion, mit der Ihr Euer Ergebnis (oberflächlich) auf Korrektheit testen könnt (bei der Auswertung finden dann die härteren Tests statt), und ein Programmgerüst, das die Lösung mit Testdaten füttert.
Der Code muss sich mit GCC 4.6.x kompilieren lassen. Windows-Benutzer bekommen mit CodeLite eine kostenlose IDE mit einem Windows-Port des GCC. Vorkompilierte Installer gibt es hier. Dort die neueste Version anklicken und anschließend den Installer für das jeweilige Betriebssystem herunterladen. Unter Windows bitte die Datei mit "mingw" im Namen herunterladen, z.B. "codelite-4.0.5589-mingw4.6.1.exe".
Davon abgesehen werden die Lösungen, je nach Aufgabe, anhand einer der folgenden Kriterien bewertet:

Wettbewerbsmodus "Geschwindigkeit":
Hier werden alle eingereichten Lösungen auf mindestens zwei Rechnern mit vorher nicht bekannten Daten getestet. Die Ergebnisse werden gewichtet und zusammengezählt. Die schnellste Lösung gewinnt.

Wettbewerbsmodus "Kürze des Codes":
Gezählt wird hier die Anzahl der Token, die benötigt wurden (es bringt also nichts, kurze Variablennamen zu verwenden oder Leerzeichen wegzulassen). Da die Token nach dem Präprozessor-Schritt gezählt werden, bringen auch Makros nichts. Die Lösung, die mit den wenigsten Token auskommt und korrekt ist, gewinnt. Die Korrektheit wird ebenfalls mit GCC 3.4.2 getestet.
Im Allgemeinen ist bei "Kürze des Codes" das Verwenden der Standardbibliothek verboten.
Code, der undefiniertes Verhalten erzeugt, sollte vermieden werden. Da in C++ ziemlich viele Dinge undefiniert sind, muss hier im Einzelfall entschieden werden.
Weiterhin sind Inline-Assembler, das Verpacken von ausführbarem Code (Maschinencode in irgendeiner Form) in einem String und Ähnliches bei diesem Wettbewerbstyp verboten. Auch das Programmieren einer VM und das Verpacken des eigentlichen Codes in einem String (den die VM dann ausführt), ist nicht erlaubt.
Was ist überhaupt ein Token? Folgender Code-Schnipsel besteht zum Beispiel aus 24 Token:


Einen simplen Token-Counter für Windows gibt es hier zum Runterladen. Bitte die Anleitung lesen!

Wettbewerbsmodus "Spezial":
Bei manchen Aufgaben kann man die Lösungen nicht als falsch oder korrekt bezeichnen, zum Beispiel wenn die optimale Lösung viel zu teuer wäre (Traveling Salesman), oder wenn der Zufall ins Spiel kommt und lediglich eine Schätzung durchgeführt werden kann. In diesem Fall wird das genaue Bewertungskriterium zusammen mit der Aufgabenstellung angegeben.

Was ist erlaubt, was ist verboten?
- Es ist verboten, sich Dinge in statischen oder globalen Variablen für den jeweils nächsten Durchlauf des Algorithmus zu merken, um ihn zu beschleunigen (das gilt auch für Speicherreservierungen o.Ä.).
- Es ist verboten, übermäßig große Mengen von Speicher auf dem Stack anzulegen (das Programm muss ohne Änderung der Stack-Größe funktionieren).
- Zugriff auf Ein- oder Ausgabedaten außerhalb des gültigen Bereichs ist verboten (zum Beispiel ist es nicht erlaubt, über das Ende eines Strings hinaus zu lesen oder zu schreiben).
- Alle Nicht-Standard-Libraries sind verboten (Boost, WinAPI, DirectX o.Ä.).
- Fremder Code (z.B. Zufallsgeneratoren) darf benutzt werden, wenn er als solcher kenntlich gemacht wird. Es sind aber keine zusätzlichen Dateien erlaubt. Der ganze Code sollte nach Möglichkeit in der zu implementierenden Funktion liegen (lokale struct/class). Wenn es nicht anders geht, dann auch außerhalb, aber nicht in separaten Dateien.
- Welche Optimierungsmöglichkeiten (Inline-Assembler, Intrinsics, Multi-Threading) erlaubt/verboten sind, wird je nach Contest bekanntgegeben.

Wer kann mitmachen?
Jeder! Man sollte aber C++ beherrschen, denn wenn Lösungen in verschiedenen Sprachen zugelassen wären, würde es mit der Bewertung und einem fairen Vergleich sehr schwierig.

Was gibt es zu gewinnen?
Zu gewinnen gibt es (normalerweise) nichts. Aber Ihr werdet schon sehen, wie viel Spaß es machen kann, aus einem kleinen Stück Code das Letzte an Geschwindigkeit oder Kürze herauszuholen, was möglich ist.