Últimamente, el juego al que más le dedico tiempo (además de Tekken) es a Angry Words (apalabrados en español). Con eso que me gusta Scrabble desde hace mucho, me relaja mientras voy en el tren y al mismo tiempo me ayuda a practicar mi vocabulario.
De la misma manera, le he estado dedicando tiempo a aprender Haskell, ya que veo que algunas cosas de PLN podrían ser implementadas más fácilmente con programación funcional.
Buscaba un problema que me ayudara a practicar Haskell, a dar mis primeros pinitos en el lenguaje. Y mientras disfrutaba el mencionado juego y veía que es más de “ponle lo que sea a ver si pega” en vez de “piensa en alguna palabra interesante”, se me ocurrió crear un programa que, dada una serie de letras, mostrara todas la combinaciones posibles entre ellas. Lo veía fácil y factible, por lo que me decidí a poner manos a la obra.
¿Qué tan difícil puede ser?… me pregunté. Y aunque no es algo tan complicado, sí me tomó más tiempo del que pensaba debido a que había que hacer el cambio a programación funcional y no a imperativa.
Primero, a definir el algoritmo:
Tomemos una palabra de 3 letras (por conveniencia, más adelante verán por qué), digamos “ola”. ¿Qué es lo que quiero obtener? La lista de posibles permutaciones con esas 3 letras, es decir: ola, oal, loa, lao, aol, alo. Aquí me di cuenta de un patrón: tomo una letra de la palabra, la pongo al principio, y simplemente tomo las otras 2 letras restantes y les cambio el orden. Para comenzar, tomo la “o” como la letra principal, entonces me quedo con “la”, y las únicas combinaciones posibles son “la” y “al”; después, agrego la letra principal “o” y la pongo al principio de cada palabra, obteniendo “ola”,”oal”. Continúo con la siguiente letra, la “l”, la tomo como principal, quedándome “oa”, de la cual obtengo “oa” y “ao”; le pongo la “l” al principio de cada una y obtengo “loa”,”lao”. Por último tomo la “a” como letra principal, lo que me deja con “ol” como el resto, obteniendo “ol” y “lo”; le pongo la “a” al principio de cada una y resultan “aol”, “alo”. Juntando todos los resultados parciales, obtengo la lista de palabras que estoy buscando.
Con la definición anterior, recursivamente se pueden analizar palabras de cualquier longitud. ¿Buenas noticias para los que juegan apalabrados? En teoría, si es que tienen la paciencia de ver todos los resultados. ¿Cuántos son? Saquemos cuentas:
Una palabra de 3 letras resultó en una lista de 6 palabras. ¿Cuántas resultarán de una de 4? Como lo que buscamos son permutaciones, la fórmula es sencilla:
n!
Revisemos: 3! = 3x2x1 = 6. ¡Bien! Si cuadra el resultado
Entonces, con 4 letras tendremos: 4! = 4x3x2x1 = 24 Todavía no son muchas…
Con 5 : 5! = 5x4x3x2x1 = 120 ya da flojera ver tantas permutaciones…
¿Y con 7? Pues 7! = 7x6x5x4x3x2x1 = 5040 Está bien que no haya límite de tiempo en cada jugada de apalabrados, pero qué flojera (o ganas de ganar) de aquél(la) que se ponga a leerla cada vez.
¡Ajá! Dirán ustedes: ¿qué pasa si hay letras repetidas? Obviamente habrá palabras repetidas también, lo cual reduce nuestra lista. ¿A cuánto? Oh benditas matemáticas:
n!/(a!b!c!…)
En donde a es el número de veces que se repite una letra, b es el número de veces que se repite otra, c es el número de veces que se repite otra… y así sucesivamente.
Supongamos que tenemos las letras “atajada” (si las tienen, ¡no la piensen y jueguen esa palabra!). La letra “a” se repite 4 veces, entonces, tendremos:
7!/4! = 7x6x5 = 210
Quizá pude haber pensado el algoritmo con una palabra de 4 letras desde el principio, y aunque sí revisé a mano después, me era más fácil iniciar con una de 3 (sólo 6 posibles permutaciones).
Luego, a hacer el programa. El resultado, a sabiendas de que puede haber una mucho mejor implementación, es una belleza de 18 líneas de código (y porque puse doble enter en algunos lugares):
Continue reading “Obteniendo todas las posibles “palabras” de 7 letras (o menos)”