Obteniendo todas las posibles “palabras” de 7 letras (o menos)

Ú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):

import Data.List
import System.Environment(getArgs)

main = do
  words <- getArgs
  processArguments words    

processArguments :: [String] -> IO ()
processArguments ws
  | length ws == 0 = putStrLn "Need a word to shuffle..."
  | length ws > 1 = putStrLn "Only a word per run..."
  | otherwise = mapM_ putStrLn $ shuffle $ head ws

shuffle :: String -> [String]
shuffle [] = []
shuffle (x:[]) = [[x]]
shuffle str@(x:y:[]) =  str : [reverse str]
shuffle (xs) = nub $ fst $ foldl (\acc c -> (fst acc ++ (map (++) $ shuffle $ snd acc ++ drop ((+1) . length $ snd acc) xs),  ++ snd acc)) ([],"") xs

Estoy casi seguro que tengo paréntesis de más, pero eso ya lo veré en futuros programas.

Sí. Es cierto que el código intimida al principio, sobre todo la última línea, que es la que hace el “trabajo sucio” en caso de ser necesario. Explico el código abajo, con la aclaración de que no comentaré esta vez sobre function composition, IO y valores monádicos en general:

shuffle es una función que recibe una palabra (String) y regresa una lista de palabras, que es la lista de todas las palabras posibles permutando las letras ([String]). Ahora bien, pensando en forma funcional, hay que definir qué es algo en vez de que cómo obtenerlo (y miren que todavía estoy muy verde en el tema), por lo que, sabiendo que un String es lo mismo que una lista de Char ([Char]):

shuffle de una lista vacía es una lista vacía.

shuffle de una palabra de una letra es una lista que contiene a la misma palabra.

shuffle de una palabra de 2 letras es una lista que contiene a la palabra y a su inverso (por ejemplo: shuffle de “la” sería [“la”,”al”]).

shuffle de una palabra de más de 2 letras es (y aquí vamos… agarren aire):

1. La lista de elementos únicos incluidos en… (nub)
2. el primer elemento de la tupla… (fst)
3. obtenida de hacer la operación foldl a la palabra…
4. usando como valor inicial una tupla de una lista vacía y una cadena vacía… ([],””)
5. aplicando como función una abstracción lambda que toma el acumulador y el siguiente elemento a analizar de la lista… (\acc c ->)
6. y regresa una tupla que contiene…
7. como primer elemento, el primer elemento del acumulador (fst acc) concatenado con…
8. la lista de palabras obtenida al…
9. mapear  a la palabra original la función que agrega el carácter que está siendo analizado a cada una de las palabras obtenidas al… (map (++) … xs)
10. aplicar shuffle a la palabra formada por el segundo elemento del acumulador (snd acc) concatenado con…
11. la palabra formada por quitar los n+1 primeros caracteres de la palabra original…
12. donde n = longitud de la palabra que haya en el segundo elemento del acumulador… (shuffle $ snd acc ++ drop (+1) . length $ snd acc)
13. y como segundo elemento la palabra formado por unir el carácter que está siendo analizado con el segundo elemento del acumulador ( ++ snd acc)

Lo más difícil fue que se me ocurriera cómo llevar la cuenta de las letras ya revisadas, para que con cada pasada del foldl siempre revisara una palabra de longitud menor a la anterior. Sabiendo que el acumulador es el valor que regresa un fold, mi única opción era meter en él lo que ya había revisado sin alterar el resultado que debía devolver. De ahí la idea de una tupla.

Todo muy bonito, si, pero… ¿funciona? Compilemos y ejecutemos:

mmedina@yggdrasil-m:~$ ghc --make shuffle.hs
[1 of 1] Compiling Main             ( shuffle.hs, shuffle.o )
Linking shuffle ...

mmedina@yggdrasil-m:~$ ./shuffle ola
ola
oal
loa
lao
alo
aol

Al parecer todo bien. Esperaba 6 palabras en específico y las obtuve correctamente. Ahora con “hola”:

mmedina@yggdrasil-m:~$ ./shuffle hola
hola
hoal
hloa
hlao
halo
haol
ohla
ohal
olha
olah
oalh
oahl
loha
loah
lhoa
lhao
laho
laoh
aloh
alho
aolh
aohl
ahol
ahlo

Espero 24 palabras. Contemos…

mmedina@yggdrasil-m:~$ ./shuffle hola | wc -l
24

¿A poco pensaron que contaría a mano? Bueno, sí, sí lo hice la primera vez, jeje. Entonces, si pongo algo como “marinos”, 7 letras, no hay repetidas se supone que espero 5040 posibles permutaciones. ¿Será?

mmedina@yggdrasil-m:~$ ./shuffle marinos | wc -l
5040

¡Bien! Parece que todo está en orden. Y claro que no podía faltar el ejemplo de “atajada”: 7 letras, 1 de ellas repetida 4 veces = debo obtener 210 permutaciones. Veamos:

mmedina@yggdrasil-m:~$ ./shuffle atajada | wc -l
210

Por puro ocio, y con eso de que no tuve nada que hacer en el trabajo, me puse a implementar el mismo algoritmo en Java, tratando de mantener la forma de programar de forma funcional. Éste es el código:

package org.mmg.langcomp;

import java.util.HashSet;
import java.util.Set;

public class Shuffle {

	private static Set<String> shuffle (String word) {
		Set<String> words = new HashSet<String>();
		Set<String> newWords = new HashSet<String>();
		String newWord = "";
		String curChar = "";
		String revWord = "";
		String checked = "";

		switch (word.length()) {
			case 0:
				System.out.println("Nothing to add here");
				break;
			case 1:
				System.out.println("Length 1: Adding \"" + word + "\"");
				newWords.add(word);
				break;
			case 2:
				StringBuilder sb = new StringBuilder(word);
				revWord = sb.reverse().toString();
				System.out.println("Length 2: Adding \"" + word + "\" and its reverse: " + revWord);
				newWords.add(word);
				newWords.add(revWord);
				break;
			default:
				System.out.println("Length > 2: Adding \"" + word + "\"");
				newWords.add(word);

				for (int i = 0; i < word.length(); i++) {
					curChar = word.substring(i, i+1);
					newWord = "";
					words.clear();

					// New word to check
					newWord = checked + word.substring(i + 1);

					if (newWord.length() >= 2) {
						System.out.println("* Going to check \"" + newWord + "\"");

						words.addAll(shuffle(newWord));
						if (!words.isEmpty()) {
							System.out.println(words.size());
							for (String w : words) {
								System.out.println("Composing and adding \"" + (curChar + w) + "\"");
								newWords.add(curChar + w);
							}
						}
					}

					checked += curChar;
					System.out.println("Already checked chars: " + checked);

				} // for

		}

		return newWords;
	}

	public static void main (String a[]) {
		Set<String> words = null;

		if (a.length == 0) {
			System.out.println("Need a word to shuffle...");
			System.exit(1);
		}
		else if (a.length > 1) {
			System.out.println("Only a word per run...");
			System.exit(1);
		}
		else {
			words = shuffle(a[0]);
			for (String w : words) {
				System.out.println("+ " + w);
			}
		}

	}
}

 

A lo mejor se me fue algún detalle en la forma de programar, pero al menos compila. Noten que le tuve que poner println (me dio flojera implementar log4j o similares nada más para esto) para ir guiándome al momento de hacerlo y ver que entrara donde debía entrar.

Como pueden ver, la idea general no cambia. La diferencia radica en cómo se define lo que hace una función, y que en programación imperativa hay que, por lo general, escribir más (y dicen que cuanto más letras, la probabilidad de cometer errores aumenta). Probemos. Me tomaré la libertad de filtrar nada más los resultados (líneas que comienzan con “+”):

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle hola | grep "^\+"
+ hloa
+ hola
+ halo
+ ohal
+ haol
+ oahl
+ ahol
+ lhao
+ lhoa
+ alho
+ olha
+ aolh
+ ahlo
+ laho
+ aohl
+ laoh
+ olah
+ loah
+ aloh
+ loha
+ oalh
+ hoal
+ hlao
+ ohla

Me da flojera contar a mano, así que:

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle hola | grep "^\+" | wc -l
24

Se ve bien. Veamos con los demás casos:

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle ola | grep "^\+" | wc -l
6
mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle marinos | grep "^\+" | wc -l
5040
mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle atajada | grep "^\+" | wc -l
210

Los números cuadran. Pero también sería bueno ver si hay diferencias con los resultados obtenidos con el programa en Haskell. Para eso, ordeno y guardo los resultados de ambos en archivos de texto para después aplicarles un diff. Gracias al ordenamiento, se supone que no debe haber diferencias entre los archivos. Probemos directamente con “marinos”. Un detalle nada más: como los resultados en Java comienzan con “+ “, les daré formato para que queden igual que los de Haskell (quitarles el signo de más y el espacio, dejando sólo a las palabras):

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle marinos | grep "^\+" | tr -s -d "\+" "" | sed s/\\s//g | sort > results-java.txt
mmedina@yggdrasil-m:~$ ./shuffle marinos | sort > results-haskell.txt
mmedina@yggdrasil-m:~$ diff results-haskell.txt results-java.txt
mmedina@yggdrasil-m:~$

Si quieren ver si en realidad nada más hay una palabra de cada una, pueden hacer un cat | uniq -c | sort -n.

Obviamente esto dista mucho de ser un programa para hacer trampa en el juego. Para ello, habría que agregar un diccionario, filtrar las palabras que no estén en él para que solamente queden palabras válidas, pero también tendríamos que tomar en cuenta conjugaciones de verbos (que son permitidas en apalabrados). En resumen: sí, es un mini proyecto interesante. Quizá le dé seguimiento. Mi prioridad técnica (no de la especialidad) en este momento es programación funcional. De momento tengo suficiente con el buscador de formspring que nomás no me doy tiempo para terminar.

Se aceptan observaciones, correcciones y sugerencias 🙂