International Functional Programming Contest 2007

Alles, was nicht direkt mit Python-Problemen zu tun hat. Dies ist auch der perfekte Platz für Jobangebote.
Antworten
BlackJack

Und schon wieder ein Programmierwettbewerb. :-)

Bei dem gibt's sogar was zu gewinnen.

Der Wettbewerb findet an einem Wochenende im Juli statt und man hat Zeit von Freitag dem 20.07. 12 Uhr mittags bis zum Montag, ebenfalls 12 Uhr Mittags. Man kann als Team antreten, was wahrscheinlich auch heisst, dass die Aufgabe für einen alleine nicht so einfach ist. Ich hatte es 2005 mal versucht und kam mit der Zeit leider nicht hin. Damals war ein Server vorgegeben, für den man Computer-Spieler ─ Räuber und Polizisten ─ schreiben sollte, die so etwas ähnliches wie das Brettspiel "Scotland Yard" veranstalteten.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Ja, den kenne ich noch von den letzten Jahren :) Das tolle an dem ist, dass dort mehr Underdog-Sprachen vertreten sind, was die Sache auch noch etwas interessanter macht.

Link
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

Argh. Danke für den Link. Der sollte natürlich auch schon im ersten Beitrag auftauchen. Ich werd' alt und vergesslich. :-)
BlackJack

Um das Thema nochmal nach oben zu bringen: Heute um 12 Uhr mitteleuropäischer Zeit geht's los.
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Das ist aber einfach... :roll:
BlackJack

Tja, ich hab' mich dran versucht, bin aber nicht so weit gekommen.

Kurz die Aufgabe umrissen: Es gibt eine Alien DNA mit den Basen I, C, F und P. Diese DNA kann man "ausführen". Dabei wird immer ein Muster (pattern) und eine Vorlage (template) vom Anfang der DNA dekodiert und das auf den Rest angewendet. So ähnlich wie reguläre Ausdrücke. Vom Muster bekommt man einen "Match" mit Gruppen und in der Vorlage können Referenzen auf "gematchte" Gruppen vorkommen. Nach der Ersetzung wird das Ergebnis vor die restliche DNA gehängt und das ganze geht von vorn los. Solange bis keine DNA mehr vorhanden ist.

Beim Dekodieren von Mustern und Vorlagen gibt's auch Regeln bei denen Teile der DNA in RNA überführt wird. Diese RNA wird in einem weiteren Schritt als Folge von Anweisungen für eine Art "Turtle"-Grafik benutzt.

Das Bild soll man durch voranstellen eines eigenen DNA-Stücks so ändern, dass ein vorgegebenes Zielbild heraus kommt.

Die Programmstücke zum "Ausführen" der DNA und Malen eines Bildes aus RNA sind in der Aufgabenstellung recht ausführlich in Pseudocode angegeben. Trotzdem nicht ganz einfach umzusetzen, weil die Fehlersuche bei den grossen Datenmengen ─ lange Ketten aus den vier Basen ─ nicht so leicht ist. Ich hatte einen Fehler, den ich erst am Sonntag gefunden hatte, nachdem die Veranstalter so gnädig waren ein paar Eckdaten der ersten 10 Iterationen des Suchen und Ersetzen-Teils zu verraten.

Als es dann lief, lief es laaaangsam. Ich habe eine recht naive Implementierung der DNA und die Laufzeit wird vom "Vorhängen" der Ersetzung vor die Rest-DNA dominiert. Da werden dann immer lustig grosse Zeichenketten im Speicher angelegt, umherkopiert und wieder freigegeben. Mehr als ca. 20 Iterationen pro Sekunde gibt mein Rechner nicht her. Die Original-DNA benötigt allerdings ca. 1,8 Millionen Iterationen bevor sie abgearbeitet ist. Das wären 25 Stunden. Argh. :shock: An der Stelle habe ich das Handtuch geworfen.

Wenn ich weiter gemacht hätte, dann mit einer Implementierung einer verketteten Liste von DNA-Segmenten um diese `prepend()`-Operation in O(1) Zeit durchzuführen. Das hätte allerdings bedeutet, entweder die Suchoperation einer Teilsequenz in Python zu programmieren ─ vorher konnte ich einfach `str.index()` benutzen ─ oder auf C auszuweichen. Dann hätte ich noch die "RNA-Turtle" implementieren/debuggen müssen und dann die DNA "reparieren". Das alles in nicht mal mehr einem Tag, erschien nicht schaffbar.

Etwas verwundert hat mich, dass jemand auf der Mailingliste mit Java und einem ähnlich naiven Ansatz, eine noch deutlich langsamere Lösung hat. Es wurde die Vermutung geäussert, dass das daran liegen könnte, dass Java's Zeichenketten Unicode-Zeichenketten sind.

Ich habe auf jeden Fall vor, noch ein bisschen weiter zu basteln. Ohne Zeitdruck.
BlackJack

Es gibt jetzt den abschliessenden, technischen Report von den Veranstaltern unter anderem mit Informationen wie die DNA etc. entstanden/erzeugt worden ist.

Es gibt auch eine Rangliste der Programmiersprachen, die von den Teilnehmern verwendet wurden. Python ist auf Platz 4.

Code: Alles auswählen

#teams Language(s)
    81 C++
    67 C
    66 Haskell
    64 Python
    52 Objective Caml
    48 Java
    35 Perl
    26 Ruby
    22 Lisp
    22 C#
    17 Scheme
     9 Unix shell (sh, bash)
     8 D
     5 PHP
     4 Erlang, Delphi
     3 ML
     2 AWK, Fuun DNA, LOLCODE, Lua, Octave, Pro-
       log, Refal, Scala
     1 2D, Basic, Blub, Brainfuck, CWEB, Cobol, Dylan,
       Emacs Lisp, Excel, FP, F#, Grep, Hub, MUMPS,
       Nemerle, PL/I, Pascal, R, Sed, Silcc, Smalltalk,
       Unlambda

        Table 2. Languages used by teams
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Leider war Python noch nie bei den Gewinnern dabei, außer beim letztjährigen Team, das "C++, Haskell, Python, Bash, 2D and a private Google language" benutzt hat.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Imperator
User
Beiträge: 275
Registriert: Montag 20. August 2007, 14:43
Kontaktdaten:

Meine Fre***, klingt das kompliziert. Na ja, ich bin derzeit eh mit dem Bundeswettbewerb Informatik beschäftigt (wohl eher meine Kragenweite :wink: ).
Benutzeravatar
C4S3
User
Beiträge: 292
Registriert: Donnerstag 21. September 2006, 10:07
Wohnort: Oberösterreich

Etwas OT, aber:
lustige Resonanz: erst vor 2 Tagen habe ich mir einen alten PodCast vom CCC angehört in dem es um diese Contest ging und die Gastsprecher haben mit Dylan programmiert. Python wurde da natürlich auch erwähnt.
Gruß!
Antworten