ICFP Programming Contest

Moderator: Aktive Fachschaft

Forumsregeln
Auch ohne Registrierung können Beiträge in diesem Unterforum geschrieben werden.
Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

ICFP Programming Contest

Beitrag von Tillmann »

Der diesjährige ICFP Programmierwettbewerb findet von Freitag, dem 20. Juli, 12:00 bis Montag, den 23. Juli, 12:00 statt. Teilnehmen darf jeder, Teams dürfen beliebig groß sein, die Konkurrenz ist üblicherweise groß und die Aufgabenstellung interessant. Zu gewinnen gibts eine Einladung zur International Conference on Functional Programming Anfang Oktober in Freiburg sowie "unlimited bragging rights".

Mehr Infos gibt es auf der Website und im Blog des Organisators. Dort stammt auch das Bild vom Interstellar Garbage Collector her:
  • Bild
Eine Google-Suche liefert auch Websiten von Teilnehmern früherer Wettbewerbe, wenn man sich einen Eindruck davon verschaffen will, wie der IFCP-Contest funktioniert.

Ich möchte gerne dieses Jahr am ICFP Contest teilnehmen. Vielleicht kriegen wir ein Team zusammen, es sind ja noch drei Wochen bis zum Contest! Wer mitmachen möchte oder zumindest interessiert ist, kann sich ja hier oder per Mail an rendel@rbg... melden. Studenten, wissenschaftliche Mitarbeiter und Professoren aller Fachbereiche sind gleichermaßen willkommen, solange sie etwas vom Programmieren verstehen.


Vielleicht noch kurz zu mir: Ich studiere Informatik, interessiere mich für alles, was mit Programmiersprachen zusammenhängt (formale Semantik, Optimierung, Sprachdesign, Compilerbau, ...) und programmiere am liebsten in Haskell, mag aber auch andere Sprachen (Lisp, Prolog, ...). Wenn's sein muß, kann ich mich auch in herkömmlicheren Sprachen ausdrücken (Java, C, ...)

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

Da sich auf meinen Beitrag hier niemand gemeldet hat, habe ich mich einem internationalen Team angeschlossen. Der Contest war sehr interessant, lustig, lehrreich und anstrengend. Ich fürchte bloß, nach 72 Stunden Programmieren mit nur 7 Stunden Schlaf insgesamt war meine Performance bei der Klausur "Einführung in die Künstliche Intelligenz" heute nicht mehr so gut.

Es ging beim ICFP Contest um die Entwicklung einer Virtuellen Machine für eine ziemlich abgedrehte Sprache, die auf PatternMatching über und Modifikation des gesamten Maschinenprogrammes als einziger nativer Operation basiert. Ein bißchen so, als würde man ausschließlich mit s/pattern/template Pattern à la Perl programmieren, die auch noch automatisch gegen den aktuellen Programmtext gematcht werden. Als zweiter Befehl wird der erste Befehl des resultierenden Programmes nach der Ausführung des ersten Befehls ausgeführt, und so weiter.

Als Ausgabeformat verwendet diese Sprache wiederum eine selbstdefinierte, abgedrehte Vektorgraphiksprache, die Elemente aus TurtleGraphik (move, left, right, mark, line to mark) aber auch Bitmap-Operationen (Clipping, Alpha-Blending) kombiniert.

Die Aufgabenstellung war, zu einem gegebenen Programm ein Prefix zu schreiben, so daß das kombinierte Programmm ein bestimmtes Bild produziert.

Dazu mußte man natürlich erstmal eine solche virtuelle Maschine & Graphik Engine implementieren, dann das gegebene Programm (acht MB Maschinencode, der sich in jedem Zyklus selbst neu schreibt) analysieren, um es dann durch geschickte Anpassung durch vorgeschaltete pattern matches so zu verändern, daß es das gewünschte Bitmap erzeugt.

Leider haben wir die ersten zwei Tage nur an der virtuellen Maschine gearbeitet, bevor wir überhaupt anfangen konnten, mit dem gegebenen Programm zu experimentieren. Dann sind wir zunächst schnell vorangekommen, haben mehrere versteckte Nachrichten gefunden und ein paar kleinere versteckte Rätsel gelöst. Die Nachrichten umfassten Hinweise zur Laufzeitorganisation des gegebenen Programmes (Position des Datensegments, Aufrufkonvention, ...). Am Sonntag abend 12 Stunden vor Ende des Contests haben wir dann etwas halbherzig mit dem reverse engineering des gegebenen Programmes angefangen, sind aber nicht weit gekommen. Wäre wir am Anfang mit der VM schneller vorangekommen, wäre vielleicht noch Motivation für die "eigentliche" Aufgabe geblieben, so waren wir's zufrieden.

Wir waren zu dritt, haben 1200 Zeilen Haskell geschrieben und sind schließlich auf Platz 80 von 869 gekommen. Nach den Gerüchten um weitere versteckte Nachrichten etc. haben wir längst nicht alles gefunden, was es in dem gegebenen Programm aus ca. 8 Millionen Maschinenworten à 2bit zu finden gab.

Die Hintergrundgeschichte und die genaue Aufgabenstellung gibt es auf http://www.icfpcontest.org/.

Antworten

Zurück zu „Veranstaltungen“