cifras y letras

Leyendo el otro día la Investigación y Ciencia, me sorprendió encontrar en el apartado de juegos matemáticos un artículo sobre uno algoritmo para resolver los problemas que se presentaban en aquel entrañable concurso llamado Cifras y Letras.

Para aquellos que no lo recuerden, había dos problemas distintos, el de cifras y el de letras. El de cifras consistía en, partiendo de 6 números al azar (que podían ser del 1 al 10, 25, 50, 75 y 100) y aplicando las cuatro operaciones elementales de suma, resta, multiplicación y división, tratar de acercarse lo más posible a un número objetivo entre 101 y 999. El problema de letras consistía en dadas 9 letras al azar, tratar de construir la palabra más larga posible.

Pues bien, el algoritmo que da cuenta del problema de cifras no me parece especialmente curioso ya que básicamente consiste en calcular todas las posibles combinaciones de cifras y operaciones (que, a pesar de lo que pueda parecer, no son tantas), y quedarse con el resultado que más se acerque al número objetivo. Lo que se conoce como resolver el problema por fuerza bruta.

Sin embargo, para resolver el problema de letras, el algoritmo recurre a una artimaña que me parece muy ingeniosa. Este algoritmo encuentra la palabra más larga realizando una búsqueda en el diccionario de la RAE, pero cualquiera que haya intentado realizar esto partiendo de las letras desordenadas, verá que no es tarea fácil. El truco que utiliza es el siguiente.

El programa almacena en memoria una versión modificada de el diccionario de la siguiente forma:

1. Toma cada palabra (menor de nueve letras) y ordena sus letras por orden alfabético. Es decir, 'casa' pasaría a ser 'aacs' y 'cultusaurios' pasaría a ser 'acilorsstuuu' (sí, ya se que tiene más de nueve letras, es sólo un ejemplo).
2. Crea grupos de palabras en función del número de letras que tienen. Un grupo de palabras de nueve letras, otro de palabras de ocho letras, etc.
3. A continuación, ordena las palabras de cada grupo alfabéticamente, pero en su forma modificada.

Una vez realizada esta operación, cuando al algoritmo se le introducen nueve letras cualesquiera, las ordena alfabéticamente de la misma manera que en el paso 1 y puede realizar búsquedas en cada grupo, comenzando por el de más letras y terminando en el de menos. Estas búsquedas son ahora muy rápidas, ya que los grupos están ordenados y no tiene que recorrer todas y cada una de las palabras.

Cabe mencionar que, aunque el trabajo de crear el diccionario modificado puede ser muy pesado, este se tiene que realizar únicamente una vez. Luego puede almacenarse en memoria y cada siguiente llamada al algoritmo tardará un tiempo ínfimo en obtener la palabra más larga posible.

Ambos algoritmos se pueden probar en la web del autor, Pedro Reina.