Friday, March 05, 2010

Anagramas para el Scrabble

Mi amigo Jesús, el "gemelo", fue campeón nacional de Scrabble, el cual es un juego de mesa en donde juegan de dos a cuatro contrincantes. Los jugadores obtienen siete fichas (si no me equivoco), las cuales contienen letras. Se trata de formar palabras con ellas y ponerlas en un tablero. Dicho tablero tiene casillas que dan dobles y triples puntos. Al final de la partida, cuando todas las fichas se agotan, se define al ganador contando los puntos que logró. El Gemelo tiene en su haber un récord: halló la palabra "chispeado" al inicio de una partida de Scrabble, que le dio ¡212 puntos!

Pues bien, hace un par de días platiqué con el Gemelo a través del mensaje instantáneo de Google. Me dijo que había escrito un programa en C para hallar todos los anagramas de las palabras legales del diccionario de Scrabble. Un anagrama es la p alabra que resulta de la transposición o reordenación de las letras de otra, por ejemplo, "Roma" es anagrama de "amor".

Para encontrar los anagramas de cualquier palabra basta con permutar los elementos de la palabra en cuestión y revisar cada permutación contra las palabras del diccionario, a ver cuál existe y cuál no. El Gemelo se quejaba de que el problema empezaba a hacerse difícil con palabras de 15 letras, pues hay que calcular ni más ni menos 15!, lo cual es 1,307,674,368,000.
Esto implica mil trescientos millones de permutaciones y un número igual de consultas a un diccionario (al menos una sola vez cada palabra), para ver si la permutación es una palabra legal o no.

Evidentemente buscar palabras en un diccionario debe hacerse con un método eficiente, el cual es la búsqueda binaria. En éste método, el programador sabe que tiene un conjunto de palabras ordenadas alfabéticamente y escribe un programa que define las búsquedas de la misma manera que cuando tomamos un diccionario: lo abrimos a la mitad. Si nuestra palabra está después de donde lo abrimos, tomamos la segunda mitad y la dividimos en dos. Así, podremos ver entonces si está la palabra aún después o antes. Y así sucesivamente.

La cantidad de búsquedas sobre el diccionario puede entonces hacerse muy eficiente de esta manera. Por ejemplo, con 20 búsquedas, siguiente el método mencionado, se puede saber si una palabra existe entre un total de 1,048,576. Si fuesen 30 búsquedas, podríamos encontrar (o no), una palabra entre 1,073,741,824. Desde luego, para que esto funcione, se necesita que el diccionario esté ordenado alfabéticamente.

Pues bien, puse manos a la obra y programé mi propio sistema para hallar anagramas. Le pedí a Jesús que me mandara el diccionario que se usa en scrabble, el cual puede bajarse de esta liga. Una vez con esto en mano, lo cargué a mi programa y me puse a buscar anagramas. Cabe señalar que el software no es el más rápido. ¿La razón? Las permutaciones pueden ser muchas y hay que considerar que el listado de palabras del diccionario rebasa el millón de ellas. De nuevo, pienso que esto podría ser un bonito trabajo para la supercomputadora de la UNAM. Una vez más enfrento el procesamiento masivo de datos. No sé qué hacer, o me compro una de esas máquinas o pido tiempo a la UNAM.


El software permite crear todas las permutaciones de las n letras de cada palabra. Puede buscar los anagramas "legales", es decir, que sean palabras y no solamente una mezcla de letras. Puede además (una vez cargado el diccionario al software), empezar en cualquiera de las palabras de la lista. Basta con dar click sobre la palabra de interés y listo.

Quien quiera el software para probarlo, con todo gusto se lo mando. Escríbame a morsa@la-morsa.com y a vuelta de correo recibirá el programa con instalador y toda la cosa.

13 comments:

Ernesto said...

A ver que te parece lo siguiente:

En lugar de buscar por anagramas.

Una consecuencia de los anagramas, es que las palabras, están formadas por las mismas letras.

Así que en lugar de buscar todas las permutaciones, seria mejor ordenar las letras por orden alfabético y comparar este conjunto contra las palabras del diccionario ordenadas alfabéticamente.

Para agilizar, puedes hacer duplas de palabras del diccionario, con sus letras ordenadas como hash.

Si las palabras coinciden son forzosamente anagramas. (tienen las mismas letras en diferente orden)


Saludos,
Ernesto

Morsa said...

Ernesto,

Una idea -que no he puesto en práctica aún, es la de usar las parejas de letras (como en el corrector fonético - http://la-morsa.blogspot.com/2009/07/corrector-fonetico.html), en donde (me parece ya discutimos algo al respecto), solamente hay una serie de parejas de letras que se pueden poner en el español. Así, en lugar de tener que verificar cada permutación para ver si está en el diccionario, podemos descartarlas de entrada si encontramos que tienen alguna pareja de letras inválida para el castellano. De hecho, el programa del corrector fonético busca incluso con búsqueda binaria para optimizar la velocidad. Pienso que es la idea que estás proponiendo.

Hoy me dediqué toda la tarde a este programita y no implanté esta posibilidad. A ver si mañana me doy un tiempo y hago esa parte...

un abrazo,
Manuel

Ernesto said...

Yo lo veía como unas optimización.

Es mucho más pequeño el conjunto de todas las palabras del diccionario que el conjunto de todas las permutaciones de una palabra de 15 letras.

También pasó por mi mente lo de detectar si es una palabra que cumple con las reglas fonéticas pero sospecho que podrían salir falsos positivos.

Saludos!
Ernesto

Ernesto said...

Este es el código en Ruby del algoritmo que propuse:

Utilizo el diccionario en inglés.

#!/usr/bin/ruby


palabra = ARGV[0] # Pasa argumento al llamar el programa

def ordena_string(x)
# Cambia la palabra a minusculas,
# convierte la palabra en arreglo,
# lo ordena y lo conviarte a string de nuevo
return (x.downcase.split(//).sort.join)
end


palabra_preparada = ordena_string(palabra)

diccionario=File::open("/usr/share/dict/words", mode="r")

diccionario.each do |renglon|
if palabra_preparada == ordena_string(renglon.chomp)
p renglon.chomp
end

end


Saludos!
Ernesto

Luisillo said...

Hola que tal. y este programa funciona para el ahorcado? =)

es decir... buscando las palabras a partir de una letra en especìfico en un número determinado de espacios que tendrà la palabra...
supongo que no, pero serìa interesante también. saludos

Ernesto said...

Luisillo,

Para el ahorcado, yo usaría mejor una expresión regular, para filtrar las palabras que cumplen con la longitud y con las letras que vayan saliendo.


Ya probando el mi programa pero con el diccionario que Manuel me hizo favor de enviar por correo:

(solo cambié la ruta del archivo)

$ ./s.rb morsa
"armos"
"maros"
"marso"
"moras"
"morsa"
"ramos"
"romas"


$ time ./s.rb destapar
"aprestad"
"departas"
"desparta"
"destapar"
"espartad"
"petardas"
"prestada"
"repastad"
"trepadas"

real 0m11.691s
user 0m11.653s
sys 0m0.027s


Saludos,
Ernesto

Jesús said...

Todo esto surge porque puse en mi sitio una función para hallar todos los anagramas de una palabra. El problema es que el proveedor pone la condición de que, en promedio, cada request no debe requerir más de dos segundos de procesamiento. Aunque probablemente el servidor del hosting es más rápido que el que uso en local, usando el algoritmo que propone Ernesto PHP tarda más de dos segundos en terminar y no quise arriesgarme a que cancelaran mi cuenta.
Por eso preprocesé la lista con un programa en C y escribí otra en la que ya cada palabra tiene escritos junto a sí sus anagramas pero fue sólo para palabras de longitud 9 o menos y aún así me tardé 10 horas corriendo dos procesos simultáneos.
Por cierto, el algoritmo propuesto por Ernesto se hace más rápido si antes de comparar los arreglos completos se comprueba antes que la letra inicial de cada uno sea la misma (al menos en PHP).

Ernesto said...

Una solución en lugar de calcular los anagramas cada vez que te hacen una solicitud, sería precalcular todos los anagramas base de todas las palabras del diccionario.

Los de "anagramas base" me lo inventé, pero son las letras de cada palabra ordenadas alfabéticamente.

Por ejemplo la palabra "morsa" le correspondería "amors". Si ponemos este par en una base de datos en una tabla que contenga dos columnas.

Una columna con las palabras del diccionario y otra columna con las letras ordenadas.

Cualesquiera dos o más palabras que tengan un anagrama base común, son anagramas entre si.

De esta forma, lees una palabra del usuario en la página web, ordenas sus letras alfabéticamente y la buscas en la base de datos.

Imprimes todas las coincidencias.

Seguramente el tiempo de procesamiento será de milisegundos.


No es una solución muy elegante, pero creo que funcionará bien.

Ernesto said...

Se me pasó Jesús,

¿Te interesan los anagramas que son palabras del mismo diccionario o literalmente TODOS los anagramas?

Saludos,
Ernesto

Ernesto said...

Perdón Jesús,

Me acabo de dar cuenta que estoy proponiendo exactamente lo que tu ya habías dicho.

Jesús said...

Más o menos, Ernesto, pero yo escribí los anagramas en un archivo de texto. Sería interesante probar usando la base de datos.
Me interesan los anagramas de la lista completa de palabras válidas para el scrabble, que son las que están en el link que Manuel pone en el post.

Ernesto said...

Jesús,

Creo que no vale la pena hacer una base de datos. Un simple archivo de texto funciona bien para una búsqueda sencilla.

Modifiqué el script para que en lugar de imprimir las palabras que tienen el mismo anagrama base, se impriman los anagramas base de cada pa;agra del diccionario.

Después con un simple grep buscamos cuales coinciden.

Manuel, por favor te pido que le hagas llegar el archivo de los anagramas a Jesús.

Muchas gracias!

Saludos,
Ernesto


Script modificado:

#!/usr/bin/ruby


def ordena_string(x)
# Cambia la palabra a minusculas,
# convierte la palabra en arreglo,
# lo ordena y lo conviarte a string de nuevo
return (x.downcase.split(//).sort.join)
end

ana=[]

diccionario=File::open("L.txt", mode="r")

diccionario.each do |renglon|
ana.push([ordena_string(renglon.chomp),renglon.chomp])
end

ana.sort.each do |x|
print ";" + x[0] + ";" + x[1] + ";\n"
end


Esto genera una lista de palabras delimitadas entre ";" y es lo que está en el archivo que envié, direccionando la salida del script a un archivo.

El tiempo de búsqueda se reduce a 0.033segundos (en un core 2 duo)

$ time grep ";amors;" anagramas_morsa.txt
;amors;armos;
;amors;maros;
;amors;marso;
;amors;moras;
;amors;morsa;
;amors;ramos;
;amors;romas;

real 0m0.033s
user 0m0.020s
sys 0m0.013s

Jesus Casillas said...

Manuel, ahi te va un anagrama
Luna Morsa Pez Mole
saludos