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.
International Functional Programming Contest 2007
-
- 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
Link
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Argh. Danke für den Link. Der sollte natürlich auch schon im ersten Beitrag auftauchen. Ich werd' alt und vergesslich.
Um das Thema nochmal nach oben zu bringen: Heute um 12 Uhr mitteleuropäischer Zeit geht's los.
-
- User
- Beiträge: 419
- Registriert: Sonntag 3. September 2006, 15:11
- Wohnort: in den weiten von NRW
- Kontaktdaten:
Das ist aber einfach...
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. 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.
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. 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.
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.
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
- 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.
Meine Fre***, klingt das kompliziert. Na ja, ich bin derzeit eh mit dem Bundeswettbewerb Informatik beschäftigt (wohl eher meine Kragenweite ).
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.
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ß!