La dificultad consistía en resolver el problema en los 45 segundos que daban en el programa de televisión, que entonces ponían en La2. Me parecía claro que por fuerza bruta se podía resolver, pero la gracia estaba en ser competitivo como concursante. Por aquel entonces estaba recibiendo un curso de Inteligencia Artificial, y mis magníficos profesores me ayudaron mucho. Les pareció que el problema sería resoluble, pero había que hacer pruebas.
Me puse como caso más difícil los números de partida 1, 2, 4, 8, 16 y 32. Ya sé que no es un caso válido, pero me parecía que era un caso con un número de posiblilidades cercano al máximo posible. Si resolvía este problema en digamos un minuto, pensaba que podría resolver cualquier otro en los 45 fatídicos segundos. Como número objetivo ponía cualquiera no alcanzable, porque se trataba de cubrir todas la posibilidades.
La técnica que iba a usar era la búsqueda en espacio de estados, que era la que me estaban explicando en el curso. Y el lenguaje tenía que ser C, obviamente, por muchos motivos: era una de las asignaturas, es un lenguaje que genera ejecutables muy rápidos, es fácil escribir con él programas multiplataforma y, por último, ¡era una magnífica oportunidad para aprender C! Efectivamente, había estudiado C un poco, pero nunca había afrontado un programa tan completo como este en C.
Así que hay que empezar por el modelado del problema. Los estados posibles son agrupaciones de números, desde un máximo de seis (el estado inicial) hasta un mínimo de uno (se han realizado todas las operaciones). Por ejemplo, (2,5,7,10,25,100), (3,67,8), (125) son estados válidos. Llamo "nodo" a cada estado posible. Realmente no hay muchos nodos en cada problema, creo recordar que no más de tres millones, lo que hace el problema atacable. Cada nodo tiene asociado lo que llamo un "camino", que es la descripción de las operaciones que hay que realizar para llegar a cada número. Por motivos de rendimiento, tras varias pruebas, decidí guardar los caminos en notación polaca inversa, usando una coma como separador. Veamos un ejemplo: si partimos del nodo (1,2,7,4,5,6) y sumamos los dos primeros números y multiplicamos los dos últimos llegaremos al nodo (3,7,4,30), con el camino asociado (1,2,+;7;4;5,6,*). Si ahora dividimos el último por el primero, llegamos al nodo (7,4,10) con camino (7;4;5,6,*,1,2,+,/). ¿Se entiende?
Ahora hay que definir los operadores que permiten pasar de un nodo al siguiente. Obviamente, los cuatro operadores son las cuatro operaciones, teniendo en cuenta que el cociente no siempre se puede aplicar. Cuando a un nodo le aplicamos un operador, debemos anotar en su camino la operación realizada. Los operadores hay que aplicarlos a todas las parejas que se pueden formar con los números del nodo.
Con los estados y los operadores, ahora hay que lanzar la exploración del árbol de estados. Como deseo dar una solución lo antes posible, la exploración la hago en profundidad, lo que se implementa con una función recursiva. Según voy haciendo la búsqueda, me voy quedando con el número que más se aproxime al número objetivo, y con su camino asociado. Si termino la búsqueda y no he encontrado el exacto, sé que no hay solución y doy la mejor aproximación encontrada.
Hasta aquí la cosa me funcionó correctamente. Probé en mi 386sx a lanzar problemas partiendo de cinco números, no de seis, y tardaba un minuto, lo que auguraba unos cuarenta minutos para el problema real. Nos pareció un buen comienzo. A partir de ahí, había que buscar optimizaciones. Si hubiera programado esto en una máquina actual, no hubiera tenido que estudiar más, y me hubiera perdido toda la diversión siguiente.
Un primer toque, muy sencillo pero que luego viene bien, es ordenar de mayor a menor los números del nodo de partida. Así comienzo a trabajar con los números mayores y por otra parte ahorro algo de tiempo para después.
Ya hemos visto que la búsqueda es exhaustiva, que no elimino ningún nodo sin comprobar si en él hay solución. Pero lo que no debo hacer es explorar dos nodos iguales, sólo explorarlo la primera vez que aparece. Aquí hay que hacer una reflexión: ¿se repiten muchos nodos? Está claro que sí, por la propiedad asociativa de las operaciones. Con los números 1, 2 y 3 llegas al 6 sumándolos todos, pero lo puedes hacer por varios caminos: 1,2,+,3+; 3,2,+,1+, 2,3,+,1+. Podría guardar una lista de nodos con cinco números, otra con nodos con cuatro, etc... y cuando venga un nodo nuevo, comprobar si ya lo he estudiado. Pues bien, si almaceno demasiados nodos podía tener problemas de memoria y, lo que es más importante, puedo tardar más tiempo en comprobar que ya he estudiado el nodo que en estudiarlo efectivamente. Haciendo unas pruebas, me di cuenta de que el punto óptimo es almacenar todos los nodos de cuatro números. El dato sobre "complejidad del análisis" que siempre imprimo con la solución es precisamente el número de nodos de cuatro números generados y cuántos de ellos son diferentes y por tanto han sido realmente explorados.
En este momento, ya resolvía los problemas peores en tres minutos, aunque algunos de los fáciles tardaban menos de un minuto. Estaba bastante bien, pero le faltaba un toque. Fue un momento muy emocionante. Recuerdo que me pase todo un sábado buscando alguna optimización más... sin encontrarla. Pero al levantarme el domingo, ya tenía la idea. Seguramente mi cerebro (que debe ser más listo que yo) había estado trabajando por la noche sin decirme nada. La clave está, según este planteamiento, en el último paso, cuando tenemos nodos de sólo dos números. En cualquier otro tipo de nodos, es imprescindible quedarse con el camino resultante de cada operación que intentas, lo que supone concatenar cadenas. Pero cuando sólo tienes dos números basta probar si operándolos vas a obtener una mejora respecto a la mejor solución hasta el momento y no necesitas el nuevo camino casi nunca. Así que escribí una versión ligeramente diferente para tratar los nodos de dos números. Esto me ahorró la mayoría de las operaciones de concatenar caminos, puesto que el grupo de nodos más poblado es el de dos números. El momento en que ejecuté la nueva versión y vi cómo el contador de casos estudiados iba sensiblemente más rápido fue absolutamente maravilloso. El problema era mío, lo había superado.
Una vez obtenida la solución del problema, sólo queda explicarla por pantalla. Tenemos el número más aproximado al objetivo y el camino que hemos usado para obtenerlo, que recordamos que está en notación polaca inversa. Basta leer el camino e ir traduciendo a notación algebraica la cadena con la notación polaca inversa, es muy sencillo.
El código original estaba escrito en un C muy portátil y no he tenido problemas al pasarlo de un compilador a otro. Las distintas versiones de Anarit para MS-DOS, QDOS, MS Windows y Linux han usado siempre el mismo código base, con pequeños retoques para adaptar el interfaz de entrada y salida de datos.
Cuando puse en esta página la resolución del problema para que lo pudiera usar vía web cualquer usuario, con independencia del sistema operativo que tuviera, le escribí un interfaz PHP que sólo sirve para recibir los datos y dar las soluciones. Y el retoque al programa en C fue que tomara los datos por la línea de órdenes y devolviera las soluciones en un formato preciso.
Podéis descargar el código del programa en C: anarit.zip
La idea clave es esta: se parte de un diccionario con las palabras válidas. Se eligen las de nueve letras (luego de ocho, siete, etc.). Se colocan por orden alfabético las letras de cada palabra (por ejemplo, de la palabra "nutritivo" obtenemos "iinorttuv"). Se guardan todas las palabras clasificadas y normales; valdría un archivo de texto, aunque es más cómodo usar un gestor de bases de datos. Ahora nos dan nueve letras para buscar una palabra con ellas. Colocamos las letras por orden alfabético y buscamos en la lista si aparece esa combinación. Si aparece, damos las palabras de la que partió. Por ejemplo, a partir de las letras "ntviriuto" obtenemos "iinorttuv", que tiene como palabra asociada "nutritivo". ¿A que es sencillo?
Pues bien, implementarlo también es sencillo. Primero hay que preparar una base de datos de palabras junto con sus transformadas. Originalmente lo hice en C, usando el sistema Olimpo, generando tablas dBase. Después lo hice con un programa en Perl que generaba archivos de texto que se importaban en una base de datos SQLite. Actualmente lo hago con un programa en Python que practicamente hace todo el trabajo desde el archivo de texto con las palabras hasta la base de datos SQLite.
Con la base de datos preparada, se puede pedir al usuario las letras con las que hay que formar palabras. A partir de las letras, se calculan todos los subconjuntos de letras que se puedan formar mediante un programa en C.
Por último se dispara una consulta a SQLite con todos esos subconjuntos y se recoge el resultado. Eso lo hago en PHP.
Podéis descargar el código de los programas y algún material adicional que utilicé: buscapal.zip
