Criptogramas aritméticos y Prolog

Hay una historia, evidentemente falsa, en la cual se dice que un joven estaba en un país extranjero estudiando, pero después de algunas semanas, se halló sin dinero. Contó su remanente y halló que podía mandar un telegrama a su padre, para que éste le enviará más dinero. Sin embargo, su capital sólo alcanzaba para poner tres palabras.

¿Cómo decirle qué cantidad necesitaba? En un acto de ingenio, decidió escribir SEND + MORE = MONEY, asumiendo que su padre entendería que en clave le estaba diciendo qué cantidad necesitaba.

Pues bien, este tipo de criptogramas no son muy complicados de resolver en Prolog, porque en este tipo de lenguajes, en donde se hace hincapié en dos temas, la recursión y el backtrack. Así, la técnica para resolver el criptograma aritmético implica simplemente pasar todos los posibles valores por las variables que se necesitan y ver si se cumplen las condiciones exigidas. A esto se le llama un árbol solución y si dibujáramos todas las posibles alternativas, tendríamos un nodo principal con una serie de ramas, que muchas veces se ramifican generando muchas pequeñas ramas o bien, muchas ramas cortas.

La recursión es otra técnica presente. En este caso, se trata de hacer una llamada de una función a la misma función, en donde nuevos parámetros son involucrados. Pero antes de procesar la llamada, podemos observar si se cumple una condición terminal. Si es así, salimos de la recursión y en caso contrario, entramos en un ciclo más de ella.


La recursión tiene su importancia porque a pesar de que mcuhos lenguajes de cuarta generación, como Pascal y C, lo tienen disponible, es claro que se requiere de más recursos de cómputo, memoria en particular. Para ilustrarlo, pensemos en una oficina en donde existen unos diez teléfonos. Suena el primero y una secretaria lo contesta. Se pone a atender a quien habla cuando suena el segundo teléfono. Entonces la secretaria le dice al interlocutor del teléfono 1: "espere un momento por favor". Entonces la mujer contesta el segundo teléfono. Mientras habla con el interlocutor 2, suena un tercer teléfono. de nuevo, la secretaria le dice al interlocutor 2 que espere. Atiende al tercer teléfono y cuando termina la comunicación con éste tercer interlocutor, regresa al segundo y continúa la conversación en donde se quedó. Cuelga con este segundo interlocutor y retoma la conversación con el primer interlocutor en el punto donde la dejó. ¿Cómo se acuerda en qué punto se quedó en cada llamada? Bien pues la eficiente secretaria lleva un stack interno, lo cual es una estructura en donde se van apilando las conversaciones. Cuando empieza la primera llamada, la secretaria habla, pero entonces, al sonar el segundo teléfono, la secretaria pone en la pila la conversación en el punto que está al contestar el segundo teléfono. Al sonar el tercer teléfono, la secretaria pone encima de la pila, el estado de la segunda llamada. Cuando cuelga el tercer teléfono, va al anterior y ve en qué momento de la conversación se quedó y saca ese dato de la pila. Hace lo mismo al colgar.

El stack/pila, es una estructura FILO - First In, Last Out, (el primero que entra es el último que se va). Solamente para comparar con otras estructuras, ¿qué tipo de estructura es FIFO (First In, First Out)? ¿Qué ejemplo de la vida cotidiana contiene una estructura FIFO? (*)

Pero regresando al punto del criptograma aritmético, he aquí el programa que resuelve el acertijo en Prolog. ¿Podrá escribirse una versión más corta que ésta en cualquier otro lenguaje? Tengo mis dudas.


smm :-
        X = [S,E,N,D,M,O,R,Y],
        Digits = [0,1,2,3,4,5,6,7,8,9],
        assign_digits(X, Digits),
        M > 0,
        S > 0,
                  1000*S + 100*E + 10*N + D +
                  1000*M + 100*O + 10*R + E =:=
        10000*M + 1000*O + 100*N + 10*E + Y,
        write(X).

select(X, [X|R], R).
select(X, [Y|Xs], [Y|Ys]):- select(X, Xs, Ys).

assign_digits([], _List).
assign_digits([D|Ds], List):-
        select(D, List, NewList),
        assign_digits(Ds, NewList).


No es de sorprenderse que el programa no sea una virtud de eficiencia. De hecho, requiere revisar 10!/2 posibilidades para ver en cuáles se cumplen las condiciones del problema. No obstante esto, hay que aclarar que en Prolog jamás se habla de eficiencia, o de uso de recursos en forma mínima.

A todo esto, una posible solución al criptograma es:


    [9,5,6,7]       SEND
    [1,0,8,5]     + MORE
                 ---------
  [1,0,6,5,2]      MONEY


________
(*) La cola de un banco es FIFO. La gente llega, se forma, un cajero atiende a un cliente. Hasta que no termina sus operaciones ese cliente, los demás deben esperar en la cola.