9Live Buchstaben Salat-Spiel

[3_of_8]

Eine einfach verkettete, zyklische Liste, die wäre hierfür perfekt geeignet.

[lizardking]

Zitat:

Zitat von leddl

Ich denke aber mal, daß Hagen und glkgereon sich etwas mehr Gedanken gemacht und dann einen etwas performanteren Code entwickelt haben ;)

*g* Spaetestens beim zweiten Beitrag hab ich auch direkt an Hagen gedacht. Ich wette, er hat sogar noch ein paar Tips parat, wie man Anzahl der sinnvollen Permutation noch weiter einschraenken kann.
Wenn man z.B. davon ausgeht, dass es nur um deutsche Worte geht, koennte man z.B. davon ausgehen, dass die Buchstaben "p" und "t" selten hintereinander stehen.
Bei den angesprochenen 9 Stellen, die die Buchstaben "p" und "t" enthalten, koennte die direkte Kombination "pt" 8 mal auftauchen. Die restlichen 7 Buchstaben koennen wieder in 7! Kombinationen auftauchen, also 5040 Kombinationen. Das mal 8, dann haben wir 35280 moegliche Worte.
Also durch EINE einfache Regel direkt ueber 90(!)% der moeglichen Worte ausgeschlossen. Taucht "p" oder "t" doppelt auf, dann geht's noch weiter runter etc. pp.

Aehm. Problematisch wird's bei zusammengesetzten Worten. Da kann natuerlich auch oefter mal ein "pt" auftauchen. Aber ich denke durch solche Sprachspielereien bekommt man schon relativ gute Wortlisten mit guter Trefferquote ;-)

Gruesse,

Lizzy

P.S.: Wenn ich irgendwo Rechenfehler drin hab, bitte melden ;-)

[negaH]

Probiere mal das Attachment.

0.) ZIP entpacken
1.) Project1.exe starten
2.) Button "Dawg laden" klicken
3.) Test.dawg auswählen
4.) in Edit "Kombinatorische Suche" deine Buchstaben eingeben (Groß/Kleinschreibung irrelevant)
5.) in Edit "min. Länge" zb. 5 eingeben
6.) Checkbox "Suche anzeigen" anhacken
7.) Button "Wörter erzeugen" anklicken

Nun zur Theorie:

Die Basis ist eine ganz spezielle Form einer Baumstruktur -> Directed Acyclic Word Graph -> DAWG in der dann ca. 200.000 deutsche Wörter gespeichert sind. Eine solche Liste als Textdatei würde ungefähr 3 Mb benötigen und ist als DAWG nur noch 800 Kb groß. Zusätzlich kann man in diesem DAWG Tree nun sehr schnell und effizient suchen. Neben der Komprimierung des Wörterbuches und der vollständigen Entfernung der redundanten Prefixes und Suffixe der Wörter ist die schnelle Suche die Hauptaufgabe dieses DAWG.

Das Program demonstriert nun wie man in einem solchen DAWG schnell suchen kann. Einerseits ein Pattern-Matching das Wildcards unterstützt, zb. für Rechtschreibprüfungen etc.pp. Und eine weitere Suchfunktion ist die kombinatorische Suche (Permutationen), wie zb. beim Scrabble, Kreuzworträtseln oder eben 9Live nötig.

Ich benutze dieses kleine Projekt immer wenn ich mal interessante Rätsel auf 9Live (beim Durch-Zappen wohlgemerkt :) ) sehe.

Die Organisation solcher Wortlisten in einem DAWG ist der/die beste und effizienteste Algorithmus/Datenstruktur die ich für diese Aufgabe kenne. Die Zielsetzung meinerseits für die Entwicklung dieses Source war es eben die performanteste Lösung zu kreieren. Ich kenne keine andere Tree-Implementierung die schneller ist. Und bei der weiteren Entwicklung von zb. Kreuzworträtseln oder meiner Scrabble Engine benötigte ich eben eine enorm schnelle Suche, auch kombinatorisch, über sehr große Wortlisten.

Der DWAG Source demonstriert

- Konstruktion eines DWAG Tree, als azyklische Datenstrukturen, Nodebäume mit multiplen Verlinkungen
- die dynamische und sequientielle "just in time" Erzeugung solcher Tree's
- Verwendung eines eigenen inplaced Speichermanagers für die Node Strukturen
- Verwendung simpler boolscher Algebra innerhalb der Nodes für deren hierarischem Aufbau, dh. die Treenodes sind keine dynaisch allozierten Datenstrukturen wie Records oder Objekte
- Verwendung von Hashfunktionen (nicht die kryptographischen Hashfunktion) bei der Komprimierung eines solchen Tree's -> entfernen der redundanten Wort Suffixe, dh. Wörter mit gleichen Endungen werden zusammengefasst
- Suche per multiplem Patternmatching und Wildcards
- Suche per Kombinatorik -> Permutation von Buchstaben
- sowohl iterative wie auch rekusive Algorithmen
- Enumeration per Callbacks in einem solchen Tree

Essentiell geht es, im Sinne dieses Threads, darum das man mit Hilfe einer Wörterdatenbank die erzeugten und möglichen Permutationen der Buchstaben auf sinnvolle Weise einschränkt. Man erzeugt also nur die Wörter die es auch in einer jeweiligen Sprache gibt. Technologisch wäre ein DAWG wie in meinem Beispiel nun eine Lösung die effizient in der algorithmischen Komplexität und im Speicherverbrauch ist.


Gruß Hagen


PS: hier ein Auszug aus dem Source
PPS: Tippfehler beseitigt

Delphi-Quellcode:

function TDawg.Search(const Pattern: String; Found: TDawg; WithLength: Integer): Boolean;
// search all words to pattern and insert into Dawg Found
// sample patterns
//  '*A*' , search any words with one or more 'A'
//  'A*'  , search words with leading 'A'
//  '*A'  , search words with trailing 'A'
//  '?A*' , search words with second char is 'A'
//  '*#*' , search words with a number
// Patterns can be concatenated, like
//  '*A,A*,*B,*B'

{ follow some benchmarks,
  - used a Dawg with 200023 german words,
  - this Dawg need 811 Kb memory, as text file it require 2.54 Mb
  - my machine is a P4 1.5 GHz 512 Mb
  - loading this textfile wordlist with .LoadWordsFromFile() take 127 ms
  - packing this Dawg take 134 ms, so both actions take 261 ms
  - Dawg binary load 4 ms, save 23 ms
  - unpacking with .Unpack take 32 ms
  - save this Dawg as textfile wordlist take 71 ms

pattern                    time      entries found

"haus"                   0.003 ms,          1
"haus?"                  0.004 ms,          2
"haus??"                 0.008 ms,          5
"haus???"                0.014 ms,          7
"haus????"               0.032 ms,         35
"haus?????"              0.039 ms,         37
"haus*"                  0.211 ms,        333
"haus*e"                 0.122 ms,         65
"haus*e*"                0.300 ms,        258
"haus?e*"                0.040 ms,         65
"?haus"                  0.010 ms,          0
"??haus"                 0.073 ms,          1
"???haus"                0.490 ms,          4
"????haus"               1.454 ms,         27
"?????haus"              2.899 ms,         31
"*haus"                 41.880 ms,        144
"*haus*"                42.224 ms,        672
"?a*haus*"               5.579 ms,         70
"*a*haus*"              66.794 ms,        136
"*a*haus*,*b*haus*"    118.996 ms,        172
"a*"                    14.242 ms,      21493
"k*"                     7.241 ms,      10373
"z*"                     5.541 ms,       8333
"*a"                    40.221 ms,        828
"*k"                    40.719 ms,       1709
"*z"                    40.697 ms,       1116
"*a*"                  126.564 ms,      97243
"*k*"                   73.401 ms,      41656
"*z*"                   61.417 ms,      27220
"#*"                     0.003 ms,          0
"*#*"                   43.483 ms,          0
"*#"                    40.526 ms,          0
"*"                    146.523 ms,     200023
"?"                      0.007 ms,         15
"??"                     0.060 ms,        121
"???"                    0.307 ms,        511
"????"                   1.316 ms,       1672
"?????"                  3.588 ms,       3917
"??????"                 6.868 ms,       6810
"???????"               10.748 ms,       9724
"????????"              16.141 ms,      13943
"?????????"             22.812 ms,      19172
"??????????"            28.357 ms,      22876
"???????????"           32.665 ms,      25113
"?,??"                   0.063 ms,        136
"?,??,???"               0.377 ms,        647
"?,??,???,????"          1.717 ms,       2319

follow searches search only words with 7 chars, eg. param WithLength = 7

"haus"                   0.002 ms,          0
"haus?"                  0.003 ms,          0
"haus??"                 0.006 ms,          0
"haus???"                0.015 ms,          7
"haus????"               0.011 ms,          0
"haus?????"              0.011 ms,          0
"haus*"                  0.013 ms,          7
"haus*e"                 0.019 ms,          0
"haus*e*"                0.021 ms,          3
"haus?e*"                0.008 ms,          2
"?haus"                  0.010 ms,          0
"??haus"                 0.071 ms,          0
"???haus"                0.478 ms,          4
"????haus"               1.469 ms,          0
"?????haus"              2.890 ms,          0
"*haus"                  9.834 ms,          4
"*haus*"                 9.776 ms,         15
"?a*haus*"               1.401 ms,          1
"*a*haus*"              13.499 ms,          1
"*a*haus*,*b*haus*"     24.725 ms,          2
"a*"                     0.835 ms,        775
"k*"                     0.535 ms,        572
"z*"                     0.292 ms,        304
"*a"                     9.511 ms,        124
"*k"                     9.389 ms,         87
"*z"                     9.319 ms,         56
"*a*"                   14.088 ms,       3753
"*k*"                   11.280 ms,       1497
"*z*"                   10.491 ms,        849
"#*"                     0.002 ms,          0
"*#*"                    9.892 ms,          0
"*#"                    10.190 ms,          0
"*"                     11.265 ms,       9724

}

[Luckie]

Darf ich das zu deinem DEC auf meiner Homepage packen? Deinen Beitragstext würde ich dann als Dwag.txt dazu hochladen.

Btw. Das Spiel heisst Scrabble. ;)

[negaH]

Hi Luckie,

ja natürlich.
Und meine ständigen Tippfehler dürften dir ja bekannt sein ;) Wir beide haben die Schule zu einer Zeit runter gerissen als Schreibmachine lernen noch unbekannt war.

Gruß Hagen

[Luckie]

Danke. Das gehört nämlich zu den Perlen, die nur allzuleicht wieder verloren gehen hier im Forum. Genau wie der API-Hook von toms oder einige Sachen von Nico.

[negaH]

Übrigens alle Rätsel die ich auf 9Live oder auch SAT1 in dieser Form gesehen habe, konnte ich mit der 200.000 Wörtern umfassenden Wortliste im DAWG lösen. Ich hatte also noch kein einzigsten Fall bei dem die Wortliste unvollständig war !

Ich hatte sogar mal ein zweites Program geschrieben das die 2D Wortsuch-Rätsel auf ähnliche Weise gelösst hat. Bei diesem Rätsel gibt es ein 2D Feld aus lauter Buchstaben und man soll dann zb. 5 Städtenamen oder Automarken finden.
Leider finde ich die Sourcen nicht mehr. Es war aber so programmiert das alle Buchstaben einer Zeile und Spalte dieses 2D Gitters als Suchpattern der kombinatorische Suche dienten. Man erzeugt also pro Spalte/Zeile aus diesen Buchstaben alle Wörter/Städtenamen/Automarken die möglich waren. Dann wurde diese erzeugte Liste einfach mit der Such-Spalte/Zeile abgeglichen.
Interessant dabei war folgendes: Alle diese Rätsel enthielten weit mehr als 5 gültige Namen. Dh. im Rätsel selber sind zb. 7 verschiedene Städtenamen versteckt. Macht bei 5 richtigen also insgesammt 210 mögliche richtige Antworten. Es ist damit ein leichtes für 9Live/SAT1 also erstmal 209 Lösungen abzuwarten und zu behaupten das keine dieser Lösung richtig ist. Die Frage lautet ja auch "finden sie die 5 Städtenamen die wir suchen !". Sehr geschickte Abzocke ;)

Gruß Hagen

[Luckie]

Da isses: http://www.michael-puff.de/dirindex....agen_Reddmann/ :)

[SubData]

Jedesmal wenn ich einen von Hagens Beiträgen lese, komme ich mir so endlos dumm vor -g-

[Mackhack]

Zitat:

Zitat von SubData

Jedesmal wenn ich einen von Hagens Beiträgen lese, komme ich mir so endlos dumm vor -g-

Jepp er weis ne Menge und ich lese gerne seine Beitraege!!! Er ist halt wie ne Library und hoffe er wird uns noch viel helfen!!!

Danke auch von mir an dich Hagen!