Dynamic Languages Shootout
Als Stefan Keller mir das erste Mal das Inserat des Dynamic Languages Shootout im Java-Spektrum gezeigt hatte, fühlte ich mich eigentlich nicht besonders davon angesprochen. Zum einen mag ich den Begriff “Dynamic Languages” nicht besonders (darüber vielleicht ein anderes Mal..) und ein Shootout, naja, war mir irgendwie alles zu reisserisch. Die Aufgabenstellung habe ich dann doch durchgelesen, und dachte mir, das ist ja eigentlich ganz einfach: Es geht grob darum, ein Programm zu erstellen, welches 5 Runden Scrabble spielt. Das Wörterbuch ist vorgegeben, pro Zug bekommt man 7 neue Buchstaben. Und schon hatte ich angefangen, mir zu überlegen, wie ich es umsetzen würde, und so nahm alles seinen Lauf…
Mein erster Ansatz bestand darin, mit dem vorhandenen Buchstaben alle möglichen Kombinationen zu bilden und diese dann im Wörterbuch nachzuschlagen. Das Problem, mit 7 Buchstaben gibt es 13699 Möglichkeiten, bei 9 Buchstaben sind es schon 986409, und mit 10 sinds 9864100 (eine elegante Formel hab ich leider nicht parat.. ). Mit etwas Pech sind es in der 5. Runde sogar 5 * 7 – (4 * 2) = 27 Buchstaben.
Ok, nächster Versuch: Performanter ist es, jedes Wort im Wörterbuch durchzugehen und zu prüfen, ob man es mit den vorhandenen Buchstaben bilden kann. Das gibt zwar auch noch einen Haufen zu tun, aber immerhin ist die Zunahme linear. Als nächstes werden die Wörter nach ihrer Wertigkeit sortiert und danach einfach versucht, auf dem Spielfeld korrekt zu platzieren.
Nachdem ich nun schon zwei Abende investiert hatte, wollte ich eigentlich auch am Wettbewerb teilnehmen, allerdings fehlte mir noch eine gute Idee für die Kür. Das Inserat hat Stefan im Java-Spektrum entdeckt, was mich denn auch auf die Idee brachte: Das ganze mit JRuby zu machen und ein Swing-GUI zu implementieren, natürlich alles in Ruby. Um das ganze noch etwas cooler zu machen, habe ich alles in ein Jar verpackt und das Ganze lässt sich per Java Webstart starten. Wie gesagt, ohne eine Zeile Java-Code.
Aussehen tut es folgendermassen:
und ausprobieren kann man es von hier aus. Eine der Anforderungen war auch, dass das ganze Dokumentiert wird, also habe ich auch mal etwas rdoc geschrieben.
Ach ja, es hat dann doch für den 2. Platz gereicht. Und gegen Smalltalk zu verlieren macht mir überhaupt nichts aus. 
13 comments on “Dynamic Languages Shootout”
Leave a comment
You must be connected to write a comment.
Gratulation!
Bemerkenswert auch der Grössenvergleich der Lösungen, deine 22KB stehen 40MB (der 1. Platz) gegenüber ^^
Gratuliere
.
Erweitern könnte man die Lösung noch mit einem Sprachmodell, womit sämtliche Konjugationen und Deklinationen der Wörter auch noch dabei wären, oder ist das nicht gültig bei Scrabble?
Wie viele Wörter man mit 7 Buchstaben bilden kann, hängt davon ab wie viele Buchstaben gleich sind. Wenn alle verschieden sind, ist die Formel doch einfach 7!, was 5040 gibt. Oder vergess ich da was? Bei 2 gleichen ists 7! / 2!, bei zwei mal drei gleichen ists 7! / (3! * 3!) und so weiter.
Cool! Gratulation zur Loesung
Habe nicht zwei Abende Zeit um zu ueberlegen darum frage ich einfach mal
Kann man hier auch einen trie-tree (oder wie diese Dinger heissen) verwenden?
Wenn das Dictionary sehr gross ist, und der Trie explodiert, muesste man ihn Zusammenstauchen ( “two trie” oder so)
Kann mir jemand mit mehr Ahnug sagen ob das funktionieren wuerde? Waere es tendenziell schneller als pro Wort die Kombinationen durchzugehen? Oder uebersehe ich ein fundamentales Problem in der Aufgabe?
Gratuliere!
Echt cool dass du alles mit Ruby machen konntest
Und nach welchen Kriterien wurde bewertet? oder habe ich das jetzt überlesen?
Danke euch allen
Robin: Ja da hast du schon recht, aber es könnten ja auch nur 6 Buchstaben sein.. Und ja, die ganzen Flexionen wären auch erlaubt gewesen, aber dann hätte ich noch herausfinden müssen, wie die mit em Openoffice-Dictionary gebildet werden.
Steve: Schau dir mal die Lösung des Siegers an, der hat mit Tries gearbeitet. Ich wollte die Lösung so einfach wie möglich halten, die Performance war mir nicht so wichtig, solange das Ganze akzeptabel schnell lief. Auch der Algorithmus wäre noch einfach zu verbessern gewesen, aber das hätte den Code wieder aufgebläht..
Rico: Ich habe keine Ahnung… ich weiss nur, dass meine Lösung von Michael Stal bewertet wurde.
Voll cool, aber was fdj wohl für ein Wort ist?
Ist halt etwas doof, dass Abkürzungen auch drin sind im Wörterbuch..
Gratulation!
War an der OOP an der Siegerehrung dabei:) Du ja leider nicht. Hatte das Gefühl, der Gewinner hat sein Programm recht vermarktet. Seine Lösung mit den Trees, die er an der OOP vorgestellt hat, fand ich noch elegant, aber dafür ist Deine Lösung extrem einfach und klein, genau dach dem KISS-Prinzip…
An der OOP gab es ja einen rechten Hype auf Smalltalk mit Seaside und Ruby. Erinnerst Du Dich überhaupt noch an Deine C++ Zeit in der Lehre? *g* z.B. an den “Dateilistengenerator aufgrund einer Confspec”
Ein Nachfolger Deiner LAP wurde übrigens auch in Ruby programmiert, aber C++ ist hier immer noch Alltag.
Übrigens arbeitet Michael Stal auch für Siemens, nur ist der halt ein anderes Kaliber als ich
Sali Rolf!
Wenn ich gewusst hätte, dass du auch da bist, hätte ich vielleicht eher überredet werden können..
Ja die Siegerlösung sieht schon recht nett aus, aber das wäre mir zu aufwändig gewesen, bzw. das hätte ich nicht einfach mal am Abend angefangen. Und mal was mit JRuby zu machen war auch interessant, Java Webstart mit Ruby werde ich wohl auch noch etwas weiter verfolgen.
Mich würden die weiteren Teilnehmer noch interessieren, nicht nur die ersten drei.. ich hoffe doch, dass mehr mitgemacht haben
Natürlich erinnere ich mich noch an meine Siemens Zeit! Aber meinen Code von damals möchte ich wohl lieber nicht sehen…
Schade habe ich damals Ruby noch nicht gekannt.. hätte sich für die Aufgabe wohl auch viel besser geeignet als C++.
Mein jetztiger Chef war auch mal bei Siemens und hat mit Michael Stal zusammen an POSA1 geschrieben. Die Welt ist einfach klein..
Also es waren mindestens 10 Teilnehmer, denn die ersten 10 wurden auch namentlich erwähnt. Aufwand und Ertrag war bei dir also super. Vielleicht hätte ich auch mitmachen sollen:)
Ja, irgendwie waren alle mal bei Siemens! (Oder hald vieleicht Alcatel
Rolf: Dann muss ich mir also das nächste Java-Spektrum besorgen, da wird bestimmt noch was drinstehen.
Leo: Stimmt, wenn man die Lebensläufe unserer Profs anschaut schon..