Programmierwettbewerb

Hallo!

Ich möchte einen Programmierwettbewerb im "kleinen Kreis" ausrichten, und suche dafür kurze, aber anspruchsvolle Aufgaben, und eine automatische Evaluationssoftware. Die Aufgaben sollen ein Zeitlimit von ca. 20 Minuten haben und Ergebnis- oder Geschwindigkeitsorientiert sein. D.h. entweder lädt man nur das Ergebnis seiner Berechnung hoch, wobei die Berechnung mit beliebigen Mitteln gefunden werden kann, oder man lädt Quelltext hoch, der automatisch ausgeführt und auf Korrektheit und Geschwindigkeit getestet wird. Im ersten Fall gewinnt die erste richtige Antwort, im zweiten das schnellste korrekte Programm, das innerhalb des Zeitlimits hochgeladen wurde.

Habt ihr euch schonmal damit beschäftigt? Das Internet schlägt DOMjudge als Software vor -- habt ihr Alternativen?

Jester

Wir benutzen häufig den DOMJudge. Allerdings legt der ein etwas anderes Bewertungsscheme zugrunde. Unterstützt werden nur Aufgaben wo der Quelltext eingesendet werden muß, und dieser wird dann ausgeführt. Die Ausführungszeit fällt nur insofern ins Gewicht, als dass es ein Timelimit gibt, nachdem das Programm abgeschossen wird -- und die Lösung damit nicht gezählt wird.

Die Punktevergabe ist dann wie folgt: 1 Punkt für jede korrekt gelöste Aufgabe. Haben mehrere Leute gleich viele Aufgaben gelöst, so wird die genaue Platzierung ermittelt, indem bei allen gelösten Aufgaben die Zeit von Contest-Beginn bis zum Einsendezeitpunkt der korrekten Lösung in Minuten aufsummiert wird. Hier gilt dann: weniger ist besser. Fehleinsendungen von Aufgaben, die anschließend noch korrekt gelöst werden, schlagen dabei mit 10 Strafminuten zu Buche, damit man lieber nachdenkt als trial&error macht.

Gregor

Suchst Du auch Aufgaben?

Wenn ja: Wir hatten damals auf javacore einen kleinen halbregelmaessigen Wettbewerb. Eine recht einfache Aufgabe damals, die vielleicht noch ungefaehr in dem Zeitlimit zu loesen ist, war, den kuerzesten Weg durch eine "Huegellandschaft" finden. Die Huegellandschaft wurde praktisch im Vorfeld generiert und als zweidimensionales Array bereitgestellt, wobei die Kosten zwischen zwei benachbarten Elementen vermutlich irgendwie proportional zur Differenz ihrer Hoehen bzw. Arrayelementinhalten waren. ...und der Abstand (Diagonal oder nicht) hat auch irgendwie mit reingespielt. Also etwas wie SQRT(Abstand^{2+Hoehendifferenz}2) oder so

Im Prinzip programmiert man dann mal nen A* Algorithmus runter, um das zu loesen. Damals war das eine Aufgabe, die im Vergleich zu unseren anderen Ideen recht gut angenommen wurde, da das etwas ist, zu dem viele Leute noch einen Zugang haben und es vom Programmieraufwand auch nicht sooo viel ist. Es gab bei den Einsendungen damals allerdings grosse Unterschiede bei den Laufzeiten und auch bei der Korrektheit.

Ich bin mir allerdings nicht sicher, ob das auch schon in 20 Minuten zu realisieren ist. Vielleicht sind 60 Minuten realistischer. Irgendwie sind die beiden Ziele "anspruchsvoll" und "in 20 Minuten realisierbar" etwas stark widerspruechlich.

Gregor schrieb:

Suchst Du auch Aufgaben?

Ja! Ich wollte erst gar nicht fragen, weil hier meistens nicht-technische Fragen nicht so gerne beantwortet werden.

Ich bin mir allerdings nicht sicher, ob das auch schon in 20 Minuten zu realisieren ist. Vielleicht sind 60 Minuten realistischer. Irgendwie sind die beiden Ziele "anspruchsvoll" und "in 20 Minuten realisierbar" etwas stark widerspruechlich.

Ja, "anspruchsvoll" ist relativ zur Zeit zu sehen. Ich wollte das ganze in kleinem Kreis mit bekannten Teilnehmern machen. Das "anspruchvoll" bezog sich zum Teil darauf, dass man in einer Klasse von Aufgaben nicht einen bekannten Algorithmus möglichst schnell runterschreibt (oder kopiert), sondern eher eine mathematische Aufgabe mit Computerhilfe möglichst effizient und schnell löst. (ähnlich zu Project Euler) Bei deiner Navigationsaufgabe würden z.B. die Landschaftsdaten der Aufgabe beiliegen, und wenn man es schneller lösen kann indem man die richtige Bibliothek einbindet, oder es per Hand ausrechnet, dann ist es eben so. 20 Minuten ist wohl auch wirklich etwas wenig für komplexere Aufgaben, aber ich dachte auch an sowas wie "finde alle Zahlen zwischen A und B, die die Bedingungen X und Y erfüllen", und dann A, B, X, Y so wählen, dass es nicht naiv bruteforcebar ist.

Wenn ihr Ideen für interessantere Aufgaben dieser Art habt, nur her damit.

Bei einer anderen Klasse von Aufgaben kommt es nur aufs schnelle Code-Produzieren an, d.h. extrem einfache Aufgabe mit knappem Zeitlimit. Wobei ich mir hier noch überlegen muss, was die richtige Komplexität ist -- sowas wie "schreibe ein Programm das über stdin Zahlen einliest und deren Summe ausgibt", und dann 7 Minuten Zeit.

Dass man bei DOMJudge nur Code hochladen kann ist eigentlich kein Hindernis.

Was waren denn die anderen Ideen? (Auch, wenn sie mehr Zeit in Anspruch nehmen)

SeppJ

Wie wäre es mit:
Vorgabe:
- Eine Menge Scrabblebuchstabem
- Eine große Liste erlaubter Wörter (suchst du irgendein offenes Wörterbuch)
- Der bekannte Scrabblespielplan

Aufgabe:
Ausgehend vom mittleren Feld, erstelle eine gültige Anordnung, die möglichst viele Gesamtpunkte erzielt.
(Dabei ist nicht zu beachten, ob die Anordnung so in einem realistischen Spiel hätte zustande kommen können. Also zum Beispiel keine Beschränkung auf 7 Buchstaben pro Zug. Nur die Punkte der Gesamtanordnung zählen)

Siegbedingung:
Die meisten Punkte erzielen.

Erwartete Lösung:
Keine Ahnung, daher stelle ich die Aufgabe ja. Irgendwie will man fette Wörter auf die 3x Punktefelder legen, aber man muss auch irgendwie dahin und mit den Buchstaben auskommen und auf dem Weg noch möglichst viel mitnehmen. Vermutlich wird ein Mensch einen Computer in 20 Minuten schlagen können. In 60 Minuten wird vielleicht schon der Computer gewinnen, wenn ein guter Programmierer davor sitzt.

Allgemein:
20 Minuten finde ich echt knapp, da muss man schon ganz schön gut sein, um mit einem Computer einen Menschen bei einem "kreativen" Problem schlagen zu können. Ich könnte in 20 Minuten bloß primitive Brute-Forcer schreiben, aber nicht mir tolle Algorithmen ausdenken und auch noch umsetzen. Und das auch nur für einfache mathematische Probleme, bei meiner Scrabbleaufgabe würde ich vermutlich schon für die Regeln und Datenstrukturen mehr als 20 Minuten brauchen (daher auch die Schätzung oben mit 60 Minuten, bevor der Computer gewinnt).