pedroreina.net

Código de Cifras y Letras, Pedro Reina
Analizador aritmético
Programé el "Analizador aritmético" (Anarit, para los amigos), en un ordenador portátil 386sx a 20 MHz sobre MS-DOS con el compilador Turbo C++. En ese momento yo deseaba comprar Coherent, un sistema UNIX muy barato que venía en cinco disquetes, pero aún tuve que esperar un poco para tenerlo. Luego vendrían Linux, gcc,... pero tiempo al tiempo.

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 5 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

Buscador de palabras
Una vez terminado el Analizador aritmético, era evidente que el siguiente paso era atacar el problema de las palabras. La solución la dio Antonio Salmerón (uno de mi profesores de aquel curso) con tanta rapidez que hasta resultó trivial. Es lo que ocurre cuando una persona muy brillante habla de algo que conoce bien. Pero con la idea solo no podríamos hacer nada, ya que hacía falta un diccionario. En un CD-ROM antiguo conseguí un pequeño diccionario con el que pude comenzar a escribir código; más adelante me decidí a usar el DRAE, aunque hizo falta paciencia.

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 las bases de datos de palabras junto con sus transformadas. Originalmente lo hice en C, usando el sistema Olimpo, generando tablas dBase. Para dar el código ahora, he preparado un programa en Perl que hace lo mismo, pero genera archivos de texto. Estos archivos se convierten en tablas SQLite fácilmente, siguiendo las instrucciones que doy con el código.

Con las tablas preparadas, 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

Posibilidades para seguir
Mejor visto con cualquier navegador HTML 4.01 válido CSS válido