9Live Buchstaben Salat-Spiel

**Der Jan**

Zitat von Nicolai1605:

Zitat von Luckie:

Zitat von negaH:

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

) sehe.

Gerade bei Live: enthaaroung. Da findet dein Programm nichts.

Das einzige wäre evtl. Orangenhaut aber irgendwie bezweifel ich, dass die solche Wörter nehmen.

oder: Haartoenung

**vlees91**

So
ich habe sowas vor wenigen Wochen für sowas ähnliches gemacht. Und zwar habe ich ein Array mit 150k Wörtern die im Deutschen gebräuchlich sind und habe anschließend die Wörter verglichen
Sodass es schnell geht habe ich alle "a" im eingabe-wort gezählt
alle b
usw
dann das gleiche bei den Wörtern im array
und wo eine übereinstimmung war, wurde es ausgegeben
das ganze war in php, wird in Delphi aber bestimmt auch ganz gut gehen

**Der Jan**

@vlees: Sowas macht das klar schneller. Um zu testen, ob ein Wort mit einem Buchstabensalat übereinstimmt, muß man nicht tausende Permutationen bilden. Bei mir mach ich es einfach so, das ich pro Buchstabe einen Flag setze, wenn alle gesetzt sind, passt es

**vlees91**

Meine Funktion in einem lahmen PHP (XAMPP), der auf einem Intel Pentium III 933Mhz läuft, der irgendwie gaaaaaanz langsam ist, brauche ich 5 Sekunden um alle Wörter durchzugehen. Also wie auch der Jan sagte: es ist schnell!

Hier mal mein Code: (Die Funktion um die Buchstaben zu zählen ist von PHP (ich glaube das ist schneller für PHP als eine eigene Schleife), aber es wäre sehr einfach sowas selber zu machen)

markieren

Code:

			<html>

<head>

<title>Char-Sorter</title>

<style type="text/css">

<!--

body {

 font-family: Tahoma;

}

-->

</style>

</head>

<body>

<?php

  $word = trim($_GET['word']);

  $word2 = count_chars($word, 1);

  include 'list.php';

  echo 'Es sind [b]'. count($wordlist) .'[/b] Wörter in der Liste vorhanden.

';

  $possible = array();

  $i = 0;

  while ($i < count($wordlist)) {

    if ($word2 == count_chars($wordlist[$i], 1)) {

      $possible[] = $wordlist[$i];

    }

    $i++;

  }

  if (count($possible)) {

    echo 'Möglichkeiten:

';

    $i = 0;

    while ($i < count($possible)) {

      echo ($i + 1) .': [b]'. $possible[$i] .'[/b]

';

      $i++;

    }

  }

  $word2 = count_chars(strtolower($word), 1);

  $possible = array();

  $i = 0;

  while ($i < count($wordlist)) {

    if ($word2 == count_chars($wordlist[$i], 1)) {

      $possible[] = $wordlist[$i];

    }

    $i++;

  }

  if (count($possible)) {

    echo 'Möglichkeiten (kleingeschrieben):

';

    $i = 0;

    while ($i < count($possible)) {

      echo ($i + 1) .': [b]'. $possible[$i] .'[/b]

';

      $i++;

    }

  }

  $possible = array();

  $i = 0;

  while ($i < count($wordlist)) {

    if ($word2 == count_chars(strtolower($wordlist[$i]), 1)) {

      $possible[] = $wordlist[$i];

    }

    $i++;

  }

  if (count($possible)) {

    echo 'Möglichkeiten (verglichen mit kleingeschriebener Wortliste):

';

    $i = 0;

    while ($i < count($possible)) {

      echo ($i + 1) .': [b]'. $possible[$i] .'[/b]

';

      $i++;

    }

  }

?>

</body>

</html>

EDIT: in der list.php steht <? $wordlist = array(.......); ?>

**vlees91**

zu Hagen: ist das ein DWAG oder ein DAWG

zur anfänglichen Frage: Du kannste jetzt z.B. den Code von mir nehmen und eine Wortliste aus dem Internet (ich habe eine die frei verfügbar ist, und eigentlich als Wörterbuch dient, ich habe sie aber missbracuht

) oder Hagens aus dem DAWG oder dem DWAG (wer weiß)
Dann wartest du, bis 9Live/DSF/etc. wieder losgeht und dann rufst du da ann und nennst denen 50 Wörter!

**negaH**

DAWG ist richtig, heist ja auch Directed Acyclic Word Graph -> gerichteter azyklischer Wörter Baum.

Übrigens enthält mein mitgeliefertes DAWG 200000 Wörter und alle diese Wörter zu durchsuchen, sprich die Suchmaske '*' zb. dauert 250 Millisekunden. Das ist aber der absolute Worstcase denn wer sucht schon ALLE Wörter auf einmal. Und so ergibt sich zb. bei der Suche aller Wörter die mit A anfangen eine Zeit von ca. 14 Millisekunden und er findet 21493 Wörter dabei. Das DAWG wird nun deutlich schneller je mehr man die Suchmaske einschränkt. Bei der Kombinatorischen Suche heist dies, das zb. bei 7 Buchstaben die gesucht werden sollen, im Durchschnitt weniger als 1 Millisekunde benötigt wird, es sind sogar meistens so um die 0,02 Millisekunden, sprich ca. 20 Mikrosekunden.

20 Mikrosekunden zu 5 Sekunden ist ein sehr deutlicher Unterschied in der Effizienz. In einigen Fällen benötigt man eine so enorme Performance, zb. wenn man Millionen von möglichen Kombinationen in einem Kreuzworträtzel oder bei einem Scrabble-Computer-Gegner pro Sekunde durchrechnen möchte. Also quasi in einer KI eines Wortbasierten Spieles.

In Falle des Problemes hier dürfte aber das nicht so entscheidend sein.
Ich möchte halt nur betonen das ein Vergleich zwischen meinem DAWG und einer simplen PHP Lösung ein Vergleich zwischen Äpfeln und Birnen sein muß, auch wenn beide Algorithmen im Endeffekt das gleiche Resultat liefern.

Gruß Hagen

**vlees91**

dein programm ist bei mir langsamer dann deine werte. naja. mein php-server läuft ja auch nicht optimal

... langsamer sicher nur, weil der Hagen einen total schnieken und neuen Multiprozessor-Compi mit superviel RAM und einem getunten Betriebssystem hat - du aber nur eine 386er-Möhre mit 64MB RAM

Fragt mich nicht woher ich es weiß, ich sage nur: Telepathie

Was wir oft vergessen ist, daß die Laufzeit eines Programms zu einem nicht geringen Teil von der Prozessorleistung abhängt.

**negaH**

Das ist schon richtig, bezieht sich aber NICHT auf die Komplexität eines Algorithmus ansich.

Das mein DAWG Algo. langsammer als eine Scriptsprache wie PHP sein soll die dann sogar noch einen Algo benutzt der von seiner Komplexität wesentlich schlechter sein muß, halte ich für ein Gerücht. Sorry das ich das so deutlich sagen muß, das hat nichts mit einem persönlichen Angriff zu tuen.

Du sagst das du mit einem sortierten Array arbeitest. Gut, denn die Suchkomplexität in einem solchen Array ist O(ln n). Das ist defakto die gleiche Komplexität wie in einem Baum auf eine Node bezogen. Mit dem Unterschied das das Array[] als solches ja linear alle Einträge enthält der Baum aber linear alle Einträge zu einem Buchstaben. Somit ist die Gesamtkomplexität eines Suchbaumes abhängig von dem Alphabeth mit 256 Elementen mindestens 256 mal schneller als ein solches Array ! Das ist aber der Worstcase, denn in einer Wortliste werden ja nur 26+10 Buchstaben des Alphabeths tatsächlich benutzt. Wenn also bei einer Patternsuche oder kombinatorischen Suche in einem solchen Baum die Entscheidung für einen gefundenen Buchstaben gefallen ist so heist dies das alle nachfolgenden Kombinationen von vornherein 255/256'tel==99.6% aller Wörter ausgeschließen. Bei einem simplen sortierten Array ist dies nicht zwangsläufig der Fall.

Nun das DAWG ist ein solcher Suchbaum, aber mit der besonderen Eigenschaft der zusätzlich hohen Komprimierung im Vergleich zu einem Array[].

Wie gesagt ich kann es mir nicht vorstellen das eine Scriptsprache wie PHP mit einem schlechteren Algorithmus schneller sein sollte als eine nativ kompilierte Anwendung die einen mathematisch besseren Algo verwendet.

Sollte das tatsächlich der Fall sein so gibt es ein gewaltig großes Beben in meinem Glauben

Gruß Hagen

**negaH**

Sag mal, ich bin ja nicht sooo fit in PHP, aber kann es sein das dein Code nur alle Wörter raussucht die zb. 7 Buchstaben enthalten ? Also wir haben 7 Buchstaben wie "AACDHIK" und suchen nun alle Wörter die exakt aus diesen 7 Buchstaben bestehen. Kann es sein das es deinem PHP Code schnuppe ist welche 7 Buchstaben gesucht werden und einfach alle Wörter mit 7 Buchstaben raussucht ??

Wenn ja, sind das Äpfel mit Birnen verglichen, denn meine kombinatorische DAWG Suche findet nur die Wörter die sich aus diesen 7 Buchstaben bilden lassen, also gültige Wörter !

Für eine Suche wie die deinige wäre es angebrachter einfach eine Listenstruktur zu benutzen die nach Anzahl der Buchstaben im Wort sortiert ist. Klar das der einfachste Fall eine Liste aus allen Wörtern mit zb. 7 Buchstaben wäre. In diesem Falle muß man garnichts mehr suchen sondern nur diese Liste komplett laden und als reguläre Antwort zählen.

Gruß Hagen

9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Re: 9Live Buchstaben Salat-Spiel

Forumregeln

Der Jan Registriert seit: 22. Dez 2005 289 Beiträge Delphi XE7 Ultimate	#33 Re: 9Live Buchstaben Salat-Spiel 16. Mai 2006, 18:45 @vlees: Sowas macht das klar schneller. Um zu testen, ob ein Wort mit einem Buchstabensalat übereinstimmt, muß man nicht tausende Permutationen bilden. Bei mir mach ich es einfach so, das ich pro Buchstabe einen Flag setze, wenn alle gesetzt sind, passt es Gruß, Jan
	Zitat

vlees91 Registriert seit: 19. Apr 2004 843 Beiträge Turbo Delphi für Win32	#37 Re: 9Live Buchstaben Salat-Spiel 17. Mai 2006, 12:54 dein programm ist bei mir langsamer dann deine werte. naja. mein php-server läuft ja auch nicht optimal vlees91
	Zitat