algorithm - primaria - frases anagramas

Escribiendo un algoritmo para scrabble.

Question

Estoy trabajando en un problema parecido a un crucigrama, pero no sé cómo diseñar el algoritmo.

Por ejemplo:

• hay palabras como ''coche'', ''manzana'' en el diccionario.
• La palabra ''aplicación'' se da en la pizarra.
• hay letras como ''l'' ''e'' ''c'' ''r'' ... para hacer palabras.

Así que la tarea del algoritmo es hacer que las palabras correctas se almacenen en el diccionario.

aplicación -> lapp -> leapp -> lecapp -> .... -> lappe -> eappc -> ... -> appl -> apple (respuesta correcta)

¿Cuál es la mejor solución para este algoritmo?

Answer 1

Almacena tu diccionario como un árbol, por ejemplo:

          *
          |
     +----+----+
     |         |
     A*        B
     |         |
  +--+--+      E*
  |     |      |
  P     S    +-+-+
  |     |    |   |
  P*    K*   A   E*
  |          |
+-+-+      +-+-+
|   |      |   |
E   L      D*  N*
|   |
A   E*
|
L*

Gracias paxdiablo por hacer mi árbol más legible.

Este árbol tiene las palabras a, app, ape, apple, ask, bead, bean, be y bee. Los nodos marcados con un asterisco indican "Si tuviera que detenerme aquí, esta sería una palabra válida", como la ''e'' debajo de ''b'' para ''ser''.

Cuando encuentre una letra que no conozca, use un comodín (es decir, elija a todos los niños y repita todos los caminos).

Dijiste crucigrama, pero luego tus "letras ... para formar palabras" parecían indicar Scrabble. Esto funcionaría para cualquiera. No el más rápido, pero mucho más rápido.

Gracias Andreas por recordarnos que esto se llama trie.

Si quisiera decir "la segunda letra es una P", comenzaría desde el nodo raíz y tomaría cada rama (que sería cada letra del alfabeto, suponiendo que es un diccionario adecuado) y luego la rama "P" y luego irá a partir de ahí

Answer 2

Busque el trabajo de tesis doctoral titulado "Hacia el juego perfecto de Scrabble" por Brian Sheppard (autor de Maven). Es informativo y muy interesante. Pero también muy largo.

Answer 3

Es posible que esté interesado en buscar en Google el documento de investigación "El Programa Scrabble más rápido del mundo" de Appel y Jacobson (1988). Los algoritmos se describen en pseudocódigo, por lo que se necesita un poco de trabajo para moldear eso en una forma utilizable y pegarlo todo junto; Sin embargo, el programa que los autores describen funciona muy bien.

Answer 4

He escrito un programa de crucigramas antes (críptico, pero la teoría detrás de la construcción es idéntica).

Tenía una base de datos de palabras y sus pistas que podrían ordenarse por tiempos utilizados (de modo que no tendría a obtener crucigramas duplicados en ejecuciones posteriores).

Lo primero que debes hacer es diseñar tus patrones (negros donde no puedes poner letras y blancos donde puedes). Intentar encajar palabras en una cuadrícula mientras crea el patrón sobre la marcha requiere mucho tiempo y es propenso a errores. Si observas la mayoría de los crucigramas, tienden a seguir ciertas reglas para que sea más fácil. Cosas como ser simétrico alrededor de una de las diagonales y rechazar un cuadrado de cuatro celdas blancas (para facilitar la tarea de seleccionar palabras adecuadas).

Una vez que tienes el patrón, entonces comienzas a encontrar palabras para colocar en él. De esa manera, sabría que "aplicación" fue el comienzo de la palabra y podría limitar sus búsquedas a aquellas que comienzan con "aplicación", no todas las palabras que tienen "aplicación" en ella. Del mismo modo para palabras donde haya conocido letras en cualquier posición. Es mucho más fácil localizar palabras con letras en posiciones conocidas que evaluarlas en cualquier posición inicial dentro de una palabra.

Los míos terminaron siendo escritos en shell script (créanlo o no) y usando el diccionario que viene de Linux como una herramienta de búsqueda de palabras. Si sabes que tienes una palabra de 5 letras que comienza con "aplicación", es muy fácil de usar:

grep ''^app..$'' words.txt

Para obtener una lista de todas las posibilidades válidas.

Y, a medida que se encontraba cada palabra, se copiaba en un archivo clues.txt que contenía tanto la palabra como varias pistas posibles. El formato real fue el uso de {count, word, clue}, donde la misma palabra puede existir en varias líneas con una pista diferente, esto permitía la grep del grep través del sort modo que las palabras / pistas menos usadas flotaban en la parte superior (siempre que una palabra / se usó la pista, su cuenta se incrementó, lo que hace que sea menos probable que se use la próxima vez).

Una vez que el archivo tuviera un tamaño adecuado, el programa lo usaría primero para localizar palabras y, si no se encontraba uno, volvería al archivo de palabras (sin pistas) donde se requeriría la intervención manual.

De hecho, terminó siendo bastante bueno haciendo el trabajo. No fue cegadoramente rápido, pero no tuve que generar uno cada tres segundos, esto fue para un boletín de la comunidad que se envía una vez a la semana.

Ahora que ha cambiado la pregunta a una variante de Scrabble, en realidad eso es mucho más difícil.

Debe tener en cuenta las letras que tiene, las letras en la pizarra y el hecho de que hay muchos más lugares que tiene que evaluar. Esto hace que un método de fuerza bruta sea mucho más difícil.

Lo que haría como un corte inicial sería seleccionar las posibilidades (posición de inicio y dirección en la pizarra) elegidas al azar, luego usar el mismo algoritmo que para la variante del crucigrama anterior para ubicar todas las palabras que pueden encajar allí. Luego, si tiene las letras para satisfacer esa palabra, guárdela (junto con su puntaje) en una lista.

Tenga en cuenta que debe tener cuidado de no interferir con otras palabras en la pizarra.

Yo continuaría examinando las posibilidades hasta que uno de:

• tu lista es lo suficientemente grande como para elegir.
• te quedas sin tiempo
• Has examinado suficientes posibilidades para satisfacer tu nivel de competencia.

Lo último es importante: si estás jugando como principiante, no querrás examinar exhaustivamente millones de posibilidades.

Luego, elige el mejor movimiento de tu lista (o quizás no el mejor si juegas a nivel principiante, todo depende de qué tan bueno quieras que sea la computadora).

Answer 5

La mayoría de los documentos de Scrabble hablan sobre buscar en la pizarra la mejor palabra para jugar. Pero para resolver su problema, como se dijo, hay un algoritmo bastante simple.

Primero, sabe que la palabra que desea contiene "aplicación", y sabe que la palabra más grande que puede formar es de siete letras (3 letras ya en la pizarra y 4 en su bandeja). Por lo tanto, busque en su base de datos con una declaración SQL como:

Seleccione la palabra del diccionario donde la palabra LIKE ''% app%'' y len (palabra) <= 7

Luego, ponga las siete letras en una matriz {l, e, c, r, a, p, p}

Lea cada palabra de la base de datos, una a la vez. Luego mire cada carácter de la palabra del diccionario y vea si existe en la matriz. Si la primera letra de la palabra del diccionario se encuentra en la matriz, elimine ese elemento en la matriz y pase a la siguiente letra del diccionario.

Si no se encuentra ninguna letra de la palabra del diccionario en la matriz, entonces la palabra no califica, por lo tanto, pase a la siguiente palabra.

Si ha visto todas las letras en el diccionario y todas se han encontrado en la matriz, entonces la palabra califica, y entonces la escribe en la lista.

Tenga en cuenta que la razón por la que coloca sus mosaicos en una matriz es que, una vez que haga coincidir una letra de la palabra del diccionario con un mosaico de su matriz, deberá eliminar esa carta de la consideración posterior, eliminando ese elemento en la matriz.

Así, por ejemplo, la base de datos del diccionario devuelve la palabra ''apelación''. Las primeras cuatro letras se encuentran en su matriz, y esos elementos se eliminan, dejando solo {l, c, r} en la matriz. Cuando busca la quinta letra ''a'' no la encontrará, por lo que la palabra queda descalificada.

La palabra ''manzana'' calificará, dejando {c, r} en su matriz.

Es bastante fácil codificar esto en cualquier idioma. Sin embargo, no es la forma más rápida de hacerlo. ¡Estoy buscando una manera más rápida para mí!

Answer 6

Lo que está buscando es la capacidad de su solucionador de anagramas de encontrar letras "comodín" para ver qué palabras pueden generar con letras adicionales. Tengo un solucionador de anagramas que escribí que hace exactamente esto. Una cosa importante que descubrí para hacer esto, y también para la velocidad del solucionador, es predefinir cuántas letras y la puntuación de cada palabra en tu tabla de palabras.

Por ejemplo, tu tabla debería estar estructurada así.

word | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | score
-------------------------------------------------------------------------------------------------------------
test | 0 | 0 | 0 | 0 | 1 | 0 | 0 | h | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 4

Como puede ver, hay una columna separada para la palabra, la letra y la cantidad de esa letra que contienen y el puntaje de esa palabra. Creé esto con anticipación con un script separado que simplemente corría para cada palabra y lo llenaba por mí hasta que estaba listo.

Aquí está el guión que escribí para calcular cuántas letras había en cada palabra, así como la puntuación y actualizar cada registro. Debe comenzar con una tabla que solo tenga las palabras antes de poder ejecutar este script. Una vez que lo ejecute, habrá terminado y no tendrá que volver a ejecutarlo a menos que agregue nuevas palabras.

<?
include(''/includes/connect.php'');
$sql = "SELECT * FROM SOWPODS WHERE word LIKE ''z%'' ORDER BY word ASC";
$result = mysql_query($sql);
while($row = mysql_fetch_array($result)) {
$string = $row[''word''];
$rowwordid = $row[''ID''];
echo $thisword = strtoupper($row[''word'']);
echo " - ";
for ($ii = 0; $ii < strlen($string); ++$ii) {
    $thisletter = strtolower($string{$ii});
    if ($thisletter == ''a'') {
        $a = $a+1;
    } elseif ($thisletter == ''b'') {
        $b = $b+1;
    } elseif ($thisletter == ''c'') {
        $c = $c+1;
    } elseif ($thisletter == ''d'') {
        $d = $d+1;
    } elseif ($thisletter == ''e'') {
        $e = $e+1;
    } elseif ($thisletter == ''f'') {
        $f = $f+1;
    } elseif ($thisletter == ''g'') {
        $g = $g+1;
    } elseif ($thisletter == ''h'') {
        $h = $h+1;
    } elseif ($thisletter == ''i'') {
        $i = $i+1;
    } elseif ($thisletter == ''j'') {
        $j = $j+1;
    } elseif ($thisletter == ''k'') {
        $k = $k+1;
    } elseif ($thisletter == ''l'') {
        $l = $l+1;
    } elseif ($thisletter == ''m'') {
        $m = $m+1;
    } elseif ($thisletter == ''n'') {
        $n = $n+1;
    } elseif ($thisletter == ''o'') {
        $o = $o+1;
    } elseif ($thisletter == ''p'') {
        $p = $p+1;
    } elseif ($thisletter == ''q'') {
        $q = $q+1;
    } elseif ($thisletter == ''r'') {
        $r = $r+1;
    } elseif ($thisletter == ''s'') {
        $s = $s+1;
    } elseif ($thisletter == ''t'') {
        $t = $t+1;
    } elseif ($thisletter == ''u'') {
        $u = $u+1;
    } elseif ($thisletter == ''v'') {
        $v = $v+1;
    } elseif ($thisletter == ''w'') {
        $w = $w+1;
    } elseif ($thisletter == ''x'') {
        $x = $x+1;
    } elseif ($thisletter == ''y'') {
        $y = $y+1;
    } elseif ($thisletter == ''z'') {
        $z = $z+1;
    }
}
$scorea = $a*1;
$scoreb = $b*4;
$scorec = $c*4;
$scored = $d*2;
$scoree = $e*1;
$scoref = $f*4;
$scoreg = $g*3;
$scoreh = $h*3;
$scorei = $i*1;
$scorej = $j*10;
$scorek = $k*5;
$scorel = $l*2;
$scorem = $m*4;
$scoren = $n*2;
$scoreo = $o*1;
$scorep = $p*4;
$scoreq = $q*10;
$scorer = $r*1;
$scores = $s*1;
$scoret = $t*1;
$scoreu = $u*2;
$scorev = $v*5;
$scorew = $w*4;
$scorex = $x*8;
$scorey = $y*3;
$scorez = $z*10;

$totalscore = $scorea + $scoreb + $scorec + $scored + $scoree + $scoref + $scoreg +     $scoreh + $scorei + $scorej + $scorek + $scorel + $scorem + $scoren + $scoreo + $scorep +      $scoreq + $scorer + $scores + $scoret + $scoreu + $scorev + $scorew + $scorex + $scorey + $scorez;
$SQL_update_count = "UPDATE TWL06 SET a = ''$a'', b = ''$b'', c = ''$c'', d = ''$d'', e = ''$e'', f = ''$f'', g = ''$g'', h = ''$h'', i = ''$i'', j = ''$j'', k = ''$k'', l = ''$l'', m = ''$m'', n= ''$n'', o = ''$o'', p = ''$p'', q = ''$q'', r = ''$r'', s = ''$s'', t = ''$t'', u = ''$u'', v = ''$v'', w = ''$w'', x = ''$x'', y = ''$y'', z = ''$z'', score = ''$totalscore'' WHERE ID = ''$rowwordid''";
echo "<br>";
$result_update_count = mysql_query($SQL_update_count);

$a = 0;
$b = 0;
$c = 0;
$d = 0;
$e = 0;
$f = 0;
$g = 0;
$h = 0;
$i = 0;
$j = 0;
$k = 0;
$l = 0;
$m = 0;
$n = 0;
$o = 0;
$p = 0;
$q = 0;
$r = 0;
$s = 0;
$t = 0;
$u = 0;
$v = 0;
$w = 0;
$x = 0;
$y = 0;
$z = 0;
 }
?>

Una vez hecho esto, todo lo que tienes que hacer es crear un guión que cuente las letras de las columnas y las asocie con las letras que le das. Primero tendrá que explotar las letras y averiguar cuántas de cada letra tiene. A continuación, ejecute una instrucción SQL que encuentre esas cantidades de letra o menos.

Answer 7

Si entendí la pregunta correctamente (empiezas con letras, una subcadena de palabras e intentas reorganizar las letras para obtener una palabra correcta), esta es otra solución:

Puedes empezar retrocediendo. Ya tiene las palabras en el diccionario y necesita mostrar parte de la palabra (una subcadena) y una lista de letras de la palabra para que las personas puedan organizarlas. Dado todo esto, comienza con la palabra del diccionario y crea una gráfica de palabras de 1 distancia de edición.

Ejemplo

Empieza con manzana y sigue quitando una letra. Aquí hay un pequeño gráfico (para el cual no dibujé todos los bordes para reducir el desorden):

manzana -> appe -> simio -> ...
/ /
/ _-> appl -> app -> ...

A medida que elimina la carta, la coloca en una lista de sugerencias.

consejos: l, p

consejos: l, e

Como el jugador usa letras de la lista para formar la palabra original, solo acepta las entradas correctas que son nodos que conducen a un padre anterior. Simplemente recorra el gráfico hacia atrás para encontrar la palabra original.

Ejemplo

Si la palabra es aplicación y sugerencias: l, p

Si el usuario te da l: appl, te mueves a un nodo anterior de la aplicación que es appl.

Si el usuario le da e: appe, se muda a un nodo anterior de la aplicación que se encuentra en este caso.

Cualquier otra letra que ingrese el usuario, usted no puede permitir permanecer en el nodo actual.

Answer 8

Si está tratando de crear un índice de palabras tal como podría intentar "resolver" (o crear) crucigramas, entonces supongo que comenzaría con un diccionario de palabras indexadas por longitud. Luego crearía otro diccionario de diccionarios de diccionarios ... el primer índice es por la longitud total de la palabra, mientras que el segundo es por la longitud, luego por la posición de la letra y finalmente por la letra (palabras de seis letras con una segunda letra de "i " por ejemplo).

Una vez que haya creado este índice, puede expresar cada paso al tratar de establecer o resolver un rompecabezas en términos de las operaciones de configuración realizadas en estos. (Por ejemplo, una palabra de 8 letras que comienza con "w" y termina con "k" sería la intersección de todas las palabras de 8 letras que comienzan con "w" y todas aquellas que terminan con "k" --- que, como era de esperar, incluiría "tarea" "). Habiendo construido la estructura de datos indexados que describí, por supuesto, permitir búsquedas mucho más eficientes para posibles coincidencias, entonces sería posible realizando escaneos lineales de la lista global de palabras o incluso escaneos lineales de las listas separadas por longitud).

Una vez que tenga esta estructura de datos básica, entonces el resto del programa, presumiblemente, será una generación de árbol y un recorrido transversal (por supuesto, con retroceso). Cree un programa que genere todas las posibilidades (utilizando la estructura de datos descrita) y siempre que se "atasque", retroceda hasta que encuentre nuevas posibilidades.

Como lo indica paxdiablo, tendrá que incluir una gran cantidad de "palabras" para que el generador tenga una posibilidad razonable de crear una "solución" completa. Cualquiera que tenga experiencia con crucigramas se da cuenta de que permite que el colocador se tome algunas libertades (como el uso frecuente de los puntos de la brújula, los términos arcaicos y los contratos poéticos) para obtener la joroba por así decirlo.

No he escrito personalmente un generador de crucigramas. He escrito solucionadores de criptogramas que utilizan una estructura de indexación similar, aunque mucho más simple. (Para encontrar todas las palabras que zyzxw podría estar en un criptograma, se "abstrae" en un patrón: abacd. Su diccionario contiene todas las palabras indexadas por su abstracción, y puede encontrar fácilmente que "cada" coincide con "zyzxw"). En ese caso, las búsquedas lineales a través de las listas iniciadas en cada abstracción son razonablemente rápidas incluso cuando se está correlacionando para descubrir que "uvz" con "zyzxw" podría ser, de hecho, "the" ... por ejemplo). También he escrito un juego simple "Jotto" que no se beneficia de la indexación en absoluto: escaneo lineal a través de los pocos miles de palabras de 5 o 6 letras en cada paso de eliminación que se usa para tomar mucho menos de un segundo en mi viejo 6 Mhz XT en la prehistoria de la computación moderna en PC).

Answer 9

Steven A. Gordon escribió un interesante artículo sobre cómo buscar posibles movimientos de Scrabble (creo que sí) (vea el artículo de Gordon en GADDAG ). Si bien hay una gran brecha entre buscar movimientos y ganar en Scrabble, como lo menciona el documento, esto no es relevante para la pregunta original.

En caso de que te resulte más útil ir directamente a leer un código, hay un buen reproductor de código abierto, Quackle .