Errores y solución al concurso de programadores reales

En el artículo pasado puse mi programa en prolog, el cual sacaba la solución al problema propuesto, que tomar los 100 primeros enteros y descomponerlos como la suma de dos enteros al cuadrado (también del 0 al 100). El programa que puse era defectuoso, pero fue a "ojo de buen cubero" (que no resulté tan buen cubero). Ya con calma me senté a resolver el asunto y éste es el código que sí funciona:


predicates
   num(integer)
   cuenta(integer,integer,integer).
   checa(integer)


clauses
    num(0).
    num(1).
    num(2).
    num(3).
    num(4).
    num(5).
    num(6).
    num(7).
    num(8).
    num(9).
    num(10).
    num(11).
    num(12).
    num(13).
    num(14).
    num(15).
    num(16).
    num(17).
    num(18).
    num(19).
    num(20).
    num(21).
    num(22).
    num(23).
    num(24).
    num(25).
    num(26).
    num(27).
    num(28).
    num(29).
    num(30).
    num(31).
    num(32).
    num(33).
    num(34).
    num(35).
    num(36).
    num(37).
    num(38).
    num(39).
    num(40).
    num(41).
    num(42).
    num(43).
    num(44).
    num(45).
    num(46).
    num(47).
    num(48).
    num(49).
    num(50).
    num(51).
    num(52).
    num(53).
    num(54).
    num(55).
    num(56).
    num(57).
    num(58).
    num(59).
    num(60).
    num(61).
    num(62).
    num(63).
    num(64).
    num(65).
    num(66).
    num(67).
    num(68).
    num(69).
    num(70).
    num(71).
    num(72).
    num(73).
    num(74).
    num(75).
    num(76).
    num(77).
    num(78).
    num(79).
    num(80).
    num(81).
    num(82).
    num(83).
    num(84).
    num(85).
    num(86).
    num(87).
    num(88).
    num(89).
    num(90).
    num(91).
    num(92).
    num(93).
    num(94).
    num(95).
    num(96).
    num(97).
    num(98).
    num(99).
    num(100).
    
    checa(101) :- !,fail.
    checa(_).
          
    cuenta(X,A,B) :- 
               num(A),
               num(B),
               X = (A*A) + (B*B),
               write(X," = ", A,"^2 + ",B,"^2"), nl,
               X1 = X + 1, !,
               checa(X1),
               cuenta(X1,A1,B1).


    cuenta(X,A,B) :- X1 = X + 1,
                     checa(X1),
                     cuenta(X1,A,B).


La solución completa la dio en Mathematica Emmanuel Garcés, la cual realmente es elegante, mucho mejor que mi código en prolog. se ve que mi tocayo conoce bastante bine el programa de Wolfram

Usando Prolog para resolver sudokus

Hace tiempo ya, empecé con este asunto de los sudokus y la programación. La realidad es que este pasatiempo mental da muchas posibilidades para la ciencia de la computación. Por ejemplo, aquí esbozamos un sistema en Prolog para generar sudokus legales. El problema realmente es que puede llevar muchísimo tiempo que el sistema dé con una solución, pues Prolog está pensado para ser exhaustivo, para hallar todas las posibles soluciones. Si tomamos en cuenta que cada línea, columna y caja (3x3) debe tener 9 números diferentes, podemos usar un algoritmo primero para poner las 9 cifras diferentes en los casilleros y entonces hacer los cálculos que se necesitan. Sin embargo, para un sudoku real, de 9x9, es decir, 81 casillas, tenemos que calcular las permutaciones de 9 objetos, en 9 columnas. Ya escribí al respecto aquí.

Hoy me di a la tarea de escribir un programa en Prolog que resolviese sudokus. Se le da al sistema el sudoku con los números que son interrogantes y el sistema empieza a buscar todas las posibles soluciones. Por ejemplo, tomé este primer sudoku, uno muy sencillo:

Generé entonces mi programa en Prolog para resolver este sudoku en particular:

predicates

   sudoku
   suma(integer, integer, integer, integer, integer, 
        integer, integer, integer, integer, integer)
   num(integer)
  
clauses
  
   num(1).
   num(2).
   num(3).
   num(4).
   num(5).
   num(6).
   num(7).
   num(8).
   num(9).
  
   suma(A,B,C,D,E,F,G,H,I,R) :-
                                A+B+C+D+E+F+G+H+I = R.  

   sudoku :- num(A1), num(B1), num(C1), num(D1),
             num(A2), num(B2), num(C2), num(D2), 
             num(E2), num(F2), num(G2), num(H2),
             num(A3), num(B3), num(C3), num(D3), 
             num(E3),
             num(A4), num(B4), num(C4), num(D4),
             num(A5), num(B5), num(C5), num(D5),
             num(A6), num(B6), num(C6), num(D6),
             num(A7), num(B7), num(C7), num(D7), 
             num(E7),
             num(A8), num(B8), num(C8), num(D8), 
             num(E8),        
             num(F8), num(G8), num(H8),
             num(A9), num(B9), num(C9), num(D9),
            
             /* horizontales */
            
             suma(5,A1,4,3,B1,6,C1,7,D1,45),
             suma(A2,B2,1,C2,D2,E2,F2,G2,H2,45),
             suma(A3,7,6,B3,C3,2,9,D3,E3,45),
             suma(A4,8,B4,7,C4,5,6,D4,1,45),
             suma(7,6,A5,B5,3,C5,D5,8,9,45),
             suma(9,A6,3,8,B6,4,C6,2,D6,45),
             suma(A7,B7,8,1,C7,D7,2,9,E7,45),
             suma(A8,B8,C8,D8,E8,F8,3,G8,H8,45),
             suma(A9,3,B9,4,C9,7,1,D9,6,45),
            
             /* verticales */
            
             suma(5,A2,A3,A4,7,9,A7,A8,A9,45),
             suma(A1,B2,7,8,6,A6,B7,B8,3,45),
             suma(4,1,6,B4,A5,3,8,C8,B9,45),
             suma(3,C2,B3,7,B5,8,1,D8,4,45),
             suma(B1,D2,C3,C4,3,B6,C7,E8,C9,45),
             suma(6,E2,2,5,C5,4,D7,F8,7,45),
             suma(C1,F2,9,6,D5,C6,2,3,1,45),
             suma(7,G2,D3,D4,8,2,9,G8,D9,45),
             suma(D1,H2,E3,1,9,D6,E7,H8,6,45),
            
            
             /* cajas */
            
             suma(5,A1,4,A2,B2,1,A3,7,6,45),
             suma(3,B1,6,C2,D2,E2,B3,C3,2,45),
             suma(C1,7,D1,F2,G2,H2,9,D3,E3,45),
             suma(A4,8,B4,7,6,A5,9,A6,3,45),
             suma(7,C4,5,B5,3,C5,8,B6,4,45),
             suma(6,D4,1,D5,8,9,C6,2,D6,45),
             suma(A7,B7,8,A8,B8,C8,A9,3,B9,45),
             suma(1,C7,D7,D8,E8,F8,4,C9,7,45),
             suma(2,9,E7,3,G8,H8,1,D9,6,45).
            
Evidentemente éste es el enfoque de "fuerza bruta", el cual es clásico en Prolog. Los sudokus son un ejemplo de programa que en Prolog se vuelven no deterministico, es decir, no podemos saber a priori si existe una solución al problema hasta que Prolog no busque todas las soluciones posibles.

Curiosamente, aunque Prolog se usa como un enfoque de la Inteligencia Artificial (IA) para resolver problemas de forma inteligente, valga la redundancia, el programa que presentamos aquí no exhibe ninguna inteligencia, a lo más una terquedad del algoritmo de Robinsson, para poner todos las posibles valores en las incógnitas y así poderlo resolver.

¿Podrá mi programa resolver el sudoku planteado? ¿Cuánto tiempo le llevará? No voy a contestar por el momento a esto (se analizará en el siguiente artículo). En el mientras, ¿qué cree estimado lector/a que pase? ¿Cuánto tiempo sería el estimado para resolver este sudoku al cual le faltan 44 números? Será poco tiempo? ¿será mucho tiempo?  ¿Qué mejoras podrían hacerse al programa? ¿Esta técnica exhaustiva es lo correcto en este problema en particular?

De la eficiencia en cómputo

A mí me gusta Prolog, el lenguaje de programación, que a decir de la propaganda que Borland hacía de su compiladort (turbo Prolog), era "el lenguaje natural de la inteligencia artificial". Bonita frase publicitaria, nada más.

Y lo que me gusta de Prolog es su paradigma, que es totalmente diferente al que tienen los lenguajes de programación de cuarta generación como Pascal y C. En prolog actuamos en otra forma: definimos el problema y el lenguaje se encarga de darnos la solución. Suena a magia, pero no lo es.

Prolog es un lenguaje de programación declarativo y por ende, lo que tenemos que hacer es precisamente declarar las condiciones iniciales y de frontera. Por ejemplo, puedo decir:

ama(juan, ana).

Lo cual quiere decir, por ejemplo, que "juan ama a ana". Ojo, aquí es importante el orden de los términos. En prolog no es esto equivalente a lo que sigue:

ama(ana, juan).

Lo cual querría decir que "ana ama a juan", lo cual evidentemente no es equivalente.

Pero lo interesante aquí es el que declaramos, casi en el idioma que hablamos normalmente, un hecho que dentro de Prolog tiene sentido. No hablamos pues de hacer cálculos sofisticados por ejemplo, sino de declarar estas relaciones, que en los lenguajes de cuarta generación se dificulta hacerlo.

Pero pensando en esto y en los problemas que Prolog puede resolver, vía el mecanismo de la recursividad, hallé que en realidad habría que preguntarse si Prolog es un lenguaje víable para aplicaciones reales y no para meramente problemas académicos como los que ya he tratado aquí (crear crucigramas, pasear por un laberinto, resovlver sudokus, etc.). Y la realidad es que pienso que Prolog bien puede ser una herramienta víable, pero solamente para unos pocos casos en donde las simbologías son muy importantes.

Por ejemplo, pienso en un diccionario que tengo que consultar. Si mi diccionario cuenta con digamos medio  millón de palabras, y necesito saber si una palabra determinada existe en mi archivo (y considerando que las palabras están debidamente ordenadas), requiero de hacer unas 19 búsquedas, pues 2^N = 500,000 es aproximadamente 19.

Escribir un programa en Prolog que haga una búsqueda binaria no es difícil. La idea es colocarse en la palabra 250,000 inicialmente y e si la palabra que busco es la que está en esa posición. Si no es, entonces debo ver si "me pasé", es decir, la palabra está antes de la que hallé o "me quedé corto", es decir, la palabra está después de la que leí. Así, divido esa región del archivo 0 a 249,000; o 250,001 a 500,000 entre dos y vuelvo a hacer la búsqueda. En Prolog, naturalmente esto se hace de forma recursiva, lo cual implica guardar el estado del sistema, vía el stack, que es una estructura de datos LIFO (Last In, First Out), cada vez que se hace la llamada recursiva. Obviamente necesito una condición terminal o de salida para no ciclar al programa y que éste termine por quedarse sin memoria.

Si intento hacer, en cambio, una búsqueda binaria en un lenguaje de cuarta generación, hallaré que no necesito usar ninguna función recursiva y con un ciclo WHILE puedo resolver mis dificultades. Aquí no hay que llevar cuenta del stack y resulta muy eficiente en términos de memoria.

Aún así, 19, 20 búsquedas usando un stack en un algoritmo recursivo no sólo no es terriblemente ineficiente, sino que es además muy elegante. Niklaus Wirth decía: "Iteratum humanum est, recursivitum divinum est" (la iteración es humana, la recursion es divina)

Pero pensando en esto, me pregunté si quisiese hacer una búsqueda linea, es decir, buscar de la primera a la última palabra en mi diccionario. Si hago esto, en el mejor de los casos haré una búsqueda: la palabra que busco está en la primera posición. En el peor de los casos la palabra que busco estará en la última línea de mi archivo, por lo cual haré medio millón de consultas.

Si quiero hacer esto en Prolog, y además lo quiero hacer recursivo, debo prepararme para guardar en el stack medio millón de estados. Por lo menos eso en un principio. Mi esquema en Prolog sería algo así:


Si la variable I es mayor que medio millón termina.

Define la variable I como 1
busca en la iésima palabra si es la que busco
si no lo es, crea una nueva variable I1 que sea igual a I+1
ve al principio del procedimiento y vuelve a buscar con estos valores
Si es el valor, imprime el resultado y asigna a la variable el valor de medio millón + 1 y ve al procedimiento recursivo


Obviamente estoy asumiendo que quienes me leen ya han tenido contacto con Prolog, pero aquí el asunto que quiero ilustrar es la dificultad que voy a enfrentar, que es la de guardar el estado del sistema en el stack a cada llamada recursiva. Dudo que el programa soporte medio millón de llamadas guardadas en el stack. ¿Qué hacer entonces? La solución es usar la instrucción corte (cut), la cual se identifica con un signo de admiración "!" y entonces le decimos al sistema en prolog que no guarde todos estos estados temporales de la recursión, porque en el fondo no me interesa saber qué pasa cuando regreso de la recursión en sí.

Si se me ocurre hacer esto en algún lenguaje de cuarta generación como Pascal, lo que haría es:

repite
  asigna a I el valor de 1
  asigna termina = falso
  lee el registro cuyo valor es I
  Si es la palabra que busco, entonces
      asigna a la varianble termina = verdadero
      escribe resultado
  Si la palabra no es la que busco, incremento la variable I
hasta que termina = verdadero



Aquí no llevo control del stack y no tengo que preocuparme por nada de eso. Por ende, parece ser más fácil usar para este asunto en particular, un lenguaje de cuarta generación.

Pero un momento, hasta los lenguajes declarativos, que usan simbologías, no se salvan de tener que hacer procedimientos repetitivos como en los lenguajes tradicionales. Aquí la cuestión es que el programador necesita definir las cosas de manera que el sistema sea eficiente y no se quede sin memoria.

En suma, pienso que Prolog es un lenguaje comercialmente víable, pero en este caso, el programador requiere de ser más cuidadoso, mucho más, de los recursos de memoria con los que cuenta. No tener esto presente puede hacer de prolog un lenguaje por demás ineficiente y poco usable.

Bosquejo de un lector de archivos PGN

PGN son las siglas de Portable Game Notation, un sistema para anotar partidas de ajedrez, usando el esquema de la notación algebraica, que es el único sistema de escritura oficial de la Federación Internacional de Ajedrez (FIDE). Gracias a este mecanismo, cualquiera puede leer una partida de ajedrez sin prácticamente importar en qué parte del mundo se encuentre. La notación de una partida de ajedrez contempla los siguientes rubros: Evento (en qué torneo se jugó el torneo), lugar del evento, fecha completa, ronda, nombre del conductor de las blancas, nombre del conductor de las negras, resultado, ECO (código de la apertura de acuerdo a la Encyclopedia of Chess Openings - ECO), el rating de las blancas, el rating de las negras, entre otros apartados (estos son los más generalizados). Inmediatamente después de esto, viene la partida, codificada de la siguiente manera: número de jugada, jugada del blanco,  jugada del negro, número de jugada, etc. hasta llegar va 1-0, 0-1 o 1/2 (ganan blancas, ganan negras, empate).

Por ejemplo, esta es la partida entre Leko e Ivanchuk, del torneo alemán de Dortmund, del 2008:


[Event "Sparkassen"]
[Site "Dortmund GER"]
[Date "2008.06.29"]
[Round "2"]
[White "Leko, P."]
[Black "Ivanchuk, V."]
[Result "1-0"]
[ECO "B46"]
[WhiteElo "2741"]
[BlackElo "2740"]

1. e4 c5 2. Nf3 e6 3. d4 cxd4 4. Nxd4 Nc6 5. Nc3 a6 6. Nxc6 bxc6 7. Bd3 d5 8. O-O Nf6 9. Qf3 Be7 10. Qg3 Nh5 11. Qf3 Nf6 12. e5 Nd7 13. Qg3 g6 14. Bh6 c5 15. Na4 c4 16. Be2 Bb7 17. b3 Bc6 18. Nb2 Rb8 19. Nd1 Nc5 20. Ne3 Ne4 21. Qh3 Ng5 22. Qg4 c3 23. a3 Bb5 24. Bxb5+ axb5 25. f3 Qb6 26. Rae1 d4 27. Nd1 d3+ 28. Kh1 dxc2 29. Nf2 Bc5 30. Nd3 Be3 31. Bxg5 Bd2 32. Re2 O-O 33. Nc1 b4 34. Bxd2 cxd2 35. Rxd2 bxa3 36. Rxc2 Rfc8 37. Qe4 Rxc2 38. Qxc2 Qd4 39. Na2 Qxe5 40. b4 Rd8 41. h3 h5 42. Rb1 Qe3 43. Rd1 Rd5 44. Qb1 Qe2 45. Re1 Qd2 46. Rc1 Rd8 47. b5 Rb8 48. Rc3 h4 49. b6 Qd6 50. Rb3 Rb7 51. Nc3 Qc6 52. Rxa3 Qxb6 53. Qxb6 Rxb6 54. Ra4 g5 55. f4 Rb3 56. Ne2 Re3 57. Ng1 1-0

Aquí las piezas se denominan por sus siglas en inglés: K-king (rey), Q-queen (dama), B-bishop (alfil), N-knight (caballo), R-rook (torre). No se pone la "P" de peón porque como hay dieciseís, se tomó la decisión que sería redundante. Si no hay pieza que se mueve, se asume que es un peón. Cabe hacer notar además, que aquí hemos puesto la partida en notación larga, es decir, indicando de qué casilla se mueve la pieza o peón y a qué casilla llega. En general se usa la notación corta, que es simplemente la pieza que se mueve y hacia qué casilla se mueve. Si dos piezas iguales pueden acceder a la casilla a la que se mueve la pieza, hay entonces que indicar cuál es la que se mueve, poniendo las coordenadas de donde nace la jugada. Por ejemplo, una partida en notación larga se ve así:

[Event ""]
[Site "Breslau"]
[Date "1912"]
[Round ""]
[White "Levitzky"]
[Black "Marshall"]
[Result "0-1"]

1.e2-e4 e7-e6 2.d2-d4 d7-d5 3.Nb1-c3 c7-c5 4.Ng1-f3 Nb8-c6 5.e4xd5 e6xd5 6.Bf1-e2 Ng8-f6 7.O-O Bf8-e7 8.Bc1-g5 O-O 9.d4xc5 Bc8-e6 10.Nf3-d4 Be7xc5 11.Nd4xe6 f7xe6 12.Be2-g4 Qd8-d6 13.Bg4-h3 Ra8-e8 14.Qd1-d2 Bc5-b4 15.Bg5xf6 Rf8xf6 16.Ra1-d1 Qd6-c5 17.Qd2-e2 Bb4xc3 18.b2xc3 Qc5xc3 19.Rd1xd5 Nc6-d4 20.Qe2-h5 Re8-f8 21.Rd5-e5 Rf6-h6 22.Qh5-g5 Rh6xh3 23.Re5-c5 Qc3-g3 0-1

Todo esto viene a cuento porque la cuestión es que se me había ocurrido hacer en prolog, sí, en prolog, un programa que leyera archivos de esta naturaleza y desplegara la partida en formato PGN en un tablerito electrónico. Para simplificar las cosas, decidí primero usar la notación larga, porque así resulta más fácil ya que la propia notación me dice qué movimiento hay que hacer, considerando la casilla inicial y la casilla de llegada de la pieza que hace la jugada.

Un problema inicial que observé es que en prolog no hay arreglos como en muchos lenguajes como Pascal o C. No incluyo Basic porque esto es de la "Tierra Primitiva". Pero en prolog lo equivalente son las listas. Así, puedo definir una lista con ocho casilleros: [tb,cb,ab,db,ab,cb,tb], lo cual representaría la primera fila del tablero. Quizás haya que ser más precisos y poner: fila(1,[tb,cb,ab,db,ab,cb,tb]).

Si quisiéramos usar esta representación para el tablero completo, podríamos poner:

fila(8,[tn,cn,an,dn,an,cn,tn]).
fila(7,[pn,pn,pn,pn,pn,pn,pn,pn]).
fila(6,[b,b,b,b,b,b,b,b]).
fila(5,[b,b,b,b,b,b,b,b]).
fila(4,[b,b,b,b,b,b,b,b]).
fila(3,[b,b,b,b,b,b,b,b]).
fila(2,[pb,pb,pb,pb,pb,pb,pb]).
fila(1,[tb,cb,ab,db,ab,cb,tb]).

donde tb, cb, ab, db, pb y rb son torre blanca, caballo blanco, alfil blanco, dama blanca, peon blanco y rey blanco, respectivamente (y con sus equivalentes para torre negra, caballo negro,alfil negro, etc.) La "b" representa una casilla vacía.

Muy bien, aquí ya tenemos parte del asunto zanjado. ya podemos representar en claúsulas de prolog el tablero de ajedrez. Ahora sólo resta poder manipular las jugadas y hacer que éstas se representen en el tablero.

En prolog, podemos encontrar el enésimo elemento de una lista de manera muy fácil:

% Hallar el enésimo elemento de una lista.
% El primer elemento de la lista es el 1.

element_at(X,[X|_],1).
element_at(X,[_|L],K) :- K > 1, K1 is K - 1, 
                         element_at(X,L,K1).

Esto significa que hallar, digamos, el quinto elemento de una lista es equivalente a hallar el cuarto elemento de una lista menos su primer elemento, o el tercer elemento de una lista sin considerar los dos primeros elementos, etc. Así se hace fácilmente en prolog.

Ahora basta ver la partida y describir cada jugada como una acción en prolog. Por ejemplo, si tengo la jugada "e2-e4", basta con poner lo que hay en la casilla 52 y pasarlo a la casilla 54. Para ello, ponemos una "b" (de blanco) en la casilla 52 (e2) y lo que había en esa casilla, lo escribimos en la casilla 54. (ver el tablero en la siguiente imagen - correspondence-chess.jpg).

Para hacer la traducción de las coordenadas de cada columna a, b, c, d, e, f, g, h, podemos hacer el siguiente predicado de equivalencias:

equivalencia(a,1).
equivalencia(b,2).
equivalencia(c,3).
equivalencia(d,4).
equivalencia(e,5).
equivalencia(f,6).
equivalencia(g,7).
equivalencia(h,8).

Así, basta ir de jugada en jugada y hacer una rutina que lea las coordenadas, inicial y final, así como la pieza que debe ir ahí y listo, el tablero cambiará su posición. Si la jugada la tenemos como una lista, por ejemplo: [e,2,e,4], el pseudocódigo podría ser algo así:

haz_jugada([X1,Y1,X2,Y2], Pieza) :- 
    /*saca las coordenadas de la posición inicial y final de la pieza que se mueve*/
    /*revisa qué pieza hay en la lista (fila) correspondiente a la posición de la coordenada inicial*/
    /*sustituye el valor que haya ahí por un blanco*/
    /*ve a la posición final y pon la pieza en la coordenada de la fila correspondiente*/

Es claro que este algoritmo no valida si las jugadas son legales o no, pero la idea es que las partidas dadas en formato PGN son correctas y no contienen errores. En caso de contenerlos caemos en "garbage in -> garbage out" (si le das basura al programa regresará basura).

Con esto en mente, podemos hacer un programa que lea el archivo PGN y pase jugada por jugada una partida. Sin embargo, esto sólo puede hacerse de ida, es decir, en una dirección, porque cuando se captura una pieza, por ejemplo, la pieza capturada desaparece y no llevamos registro de esto. Así, si queremos ir, por decir algo, una jugada hacia atrás, pues no podemos hacerlo porque no tenemos información de qué pieza fue eliminada del tablero.

La solución a esto es en realidad crear tantos tableros de ajedrez completos en donde cada jugada esté en uno de ellos. Así, si quiero ir a la jugada 27, entonces pinto inmediatamente el tablero 27. No me tengo que acordar si ahí hubo captura o no de alguna pieza. Si hago así las cosas, entonces mi definición del tablero de ajedrez debo modificarlo para que contemple en qué jugada está el programa en ese momento desplegando el tablero:

             
/*ejemplo de la estructura del tablero para el primer movimiento*/
fila(8,[tn,cn,an,dn,an,cn,tn],1).
fila(7,[pn,pn,pn,pn,pn,pn,pn,pn],1).
fila(6,[b,b,b,b,b,b,b,b],1).
fila(5,[b,b,b,b,b,b,b,b],1).
fila(4,[b,b,b,b,b,b,b,b]1,).
fila(3,[b,b,b,b,b,b,b,b],1).
fila(2,[pb,pb,pb,pb,pb,pb,pb],1).
fila(1,[tb,cb,ab,db,ab,cb,tb],1).
                    

Una partida promedio, digamos de 40 jugadas tendría entences 80 tableros (8 claúsulas por tablero), que se generarían en tiempo de ejecución como claúsulas de prolog. esto significa 640 claúsulas para guardar en memoria, cosa que actualmente cualquier computadora puede hacer sin mayores dificultades.

De hecho, los programas comerciales como Chessbase hacen precisamente esto, aunque como no lo hacen en prolog, usan otras técnicas. No sé en qué lenguaje está escrito Chessbase, pero pienso que es C. Si este es el caso, y si se sigue lo que aquí hemos comentado, entonces un programa que lea una partida PGN creará en tiempo de ejecución un diagrama por cada movimiento. Como en C se pueden crear arreglos bidimensionales, probablemente el tablero esté definido de esta manera y entonces, cuando se hace una jugada, se crea un tablero nuevo, en una estructura dinámica, que solamente pide la memoria necesaria cuando el sistema lo necesita.

Cuando se termina de ver esa partida, se libera toda esa memoria (es mandar los apuntadores a nil, por ejemplo), y entonces tenemos un sistema por demás eficiente.

El sistema de lectura de partidas PGN en Prolog no es el más eficiente, pero es un problema que puede ser atacado por Prolog de manera razonable y además, sin necesidad de pensar en estructuras dinámicas como en otros lenguajes, cosa que en general se aprende hasta un segundo curso de programación.

Para escribir cheques (II)

Hace un par de días (aquí) escribí sobre un programa que transforma una cifra en números a letras.La idea es que ponía una cifra: 2347, por ejemplo, y el programa debía darme como resultado "dos mil trescientos cuarenta y siete pesos". Puse en el artículo mencionado mi primera solución en Prolog, pero he aquí que un avezado lector, buen  programador, mejor amigo y técnicamente infalible, Ernesto Blum, me dijo que no estaba considerando algunos casos.

Hoy que fui a dar mi clase, expuse el código fuente y al irlo escribiendo en el pizarrón hallé que algo andaba mal. Así pues, decidí que al llegar a casa re-escribiría el problema para darle una solución definitiva. En un rato hallé las dificultades y según yo, ya las resolví. He aquí mi código fuente:

/********************************************/
/* Programa que traduce de números a letras */
/*             Versión 1.1                  */
/*            18 mayo 2011                  */
/*          Programó: La Morsa              */
/********************************************/ 

predicates

   equiv(integer,symbol)
   pasa_num_a_letras(integer)
   
   
clauses
   equiv(1,un).
   equiv(2,dos).
   equiv(3,tres).
   equiv(4,cuatro).
   equiv(5,cinco).
   equiv(6,seis).
   equiv(7,siete).
   equiv(8,ocho).
   equiv(9,nueve).
   equiv(10,diez).
   equiv(11,once).
   equiv(12,doce).
   equiv(13,trece).
   equiv(14,catorce).
   equiv(15,quince).
   equiv(16,dieciseis).
   equiv(17,diecisiete).
   equiv(18,dieciocho).
   equiv(19,diecinueve).
   equiv(20,veinte).
   equiv(21,veintiuno).
   equiv(22,veintidos).
   equiv(23,veintitres).
   equiv(24,veinticuatro).
   equiv(25,veinticinco).
   equiv(26,veintiseis).
   equiv(27,veintisiete).
   equiv(28,veintiocho).
   equiv(29,veintinueve).
   equiv(30,treinta).
   equiv(40,cuarenta).
   equiv(50,cincuenta).
   equiv(60,sesenta).
   equiv(70,setenta).
   equiv(80,ochenta).
   equiv(90,noventa).
   equiv(100,ciento).
   equiv(200,doscientos).
   equiv(300,trescientos).
   equiv(400,cuatrocientos).
   equiv(500,quinientos).
   equiv(600,seiscientos).
   equiv(700,setecientos).
   equiv(800,ochocientos).
   equiv(900,novecientos).
   equiv(1000,mil).
   
   pasa_num_a_letras(X) :- /* condicion terminales */
      X < 30,
      equiv(X,Resultado),
      write(Resultado).


   /* predicados recursivos */
   
   pasa_num_a_letras(Cifra) :-
      Cifra div 1000 <> 0,          /* la cifra tiene diez miles */
      DMiles = Cifra div 1000,
      DMiles > 30,
      pasa_num_a_letras(DMiles), /*doble recursion */
      write(" mil "),
      Miles = Cifra - (DMiles * 1000),
      pasa_num_a_letras(Miles).      
      
   pasa_num_a_letras(Cifra) :-
      Cifra div 1000 <> 0,           /* la cifra tiene miles */
      Miles = Cifra div 1000,
      equiv(Miles,Resultado),
      write(Resultado, " mil "),
      Cientos = Cifra - (Miles * 1000),
      pasa_num_a_letras(Cientos).      
         
   pasa_num_a_letras(Cifra) :-
      Cifra div 100 <> 0,           /* la cifra tiene cientos */
      Cien = Cifra div 100,
      Cien1 = Cien * 100,
      equiv(Cien1,Resultado),
      write(Resultado," "),
      Decenas = Cifra - (Cien * 100),
      pasa_num_a_letras(Decenas).    
      
   pasa_num_a_letras(Cifra) :-
      Cifra div 10 <> 0,           /* la cifra tiene decenas */
      Dec = Cifra div 10,
      Dec1 = Dec * 10,
      equiv(Dec1,Resultado),
      write(Resultado," y "),
      Unidades = Cifra - (Dec * 10),
      pasa_num_a_letras(Unidades).    
      


      

Cabe señalar que el programa está escrito en Turbo Prolog 2.0 y que se está usando el tamaño de variable entera para el procesamiento de la cifra, por ende, solamente puede resolver el problema para números enteros mayores a cero y menores a 32768, que es el límite de un entero. Entre otras cosas, este código ya me dejó más contento porque solamente contiene una salida de la función recursiva y eso me parece más "elegante", valga la expresión.

Igualmente, expresiones como: 

Cientos = Cifra - (Miles * 1000),

Podrían ponerse como

Cientos = Cifra mod 1000

Hice algunas pruebas y parece que ahora sí todo funciona bien.

A todo esto, el mismo Ernesto Blum me mandó la solución de este programa en el lenguaje de programación Ruby:

#!/usr/bin/ruby



def cen_out(numero)
 uni = numero % 10 / 1
 dec = numero % 100 / 10
 cen = numero % 1000 / 100
 case cen 
 when 0; return ""
 when 1; if uni == 0 && dec == 0
   return "cien"
  else
   return "ciento "
  end
 when 2; return "doscientos "
 when 3; return "trescientos "
 when 4; return "cuatrocientos "
 when 5; return "quinientos "
 when 6; return "seiscientos "
 when 7; return "setecientos "
 when 8; return "ochocientos "
 when 9; return "novecientos "
 end
end



def dec_out(numero)
 uni = numero % 10 / 1
 dec = numero % 100 / 10
 if dec == 1
  case uni
  when 0; return "diez"
  when 1; return "once"
  when 2; return "doce"
  when 3; return "trece"
  when 4; return "catorce"
  when 5; return "quince"
  when 6; return "dieciseis"
  when 7; return "diecisiete"
  when 8; return "dieciocho"
  when 9; return "diecinueve"
  end
 elsif uni == 0
  case dec
  when 0;  return ""
  when 1;  return ""
  when 2;  return "veinte"
  when 3;  return "treinta"
  when 4;  return "cuarenta"
  when 5;  return "cincuenta"
  when 6;  return "sesenta"
  when 7;  return "setenta"
  when 8;  return "ochenta"
  when 9;  return "noventa"
  end
 else
  case dec
  when 0;  return ""
  when 1;  return ""
  when 2;  return "veinti"
  when 3;  return "treinta y "
  when 4;  return "cuarenta y "
  when 5;  return "cincuenta y "
  when 6;  return "sesenta y "
  when 7;  return "setenta y "
  when 8;  return "ochenta y "
  when 9;  return "noventa y "
  end
 end
end




def uni_out(numero)
 uni = numero % 10 / 1
 dec = numero % 100 / 10
 if dec == 1
  return ""
 else
 case uni
  when 0; return ""
  when 1; return "un"
  when 2; return "dos"
  when 3; return "tres"
  when 4; return "cuatro"
  when 5; return "cinco"
  when 6; return "seis"
  when 7; return "siete"
  when 8; return "ocho"
  when 9; return "nueve"
  end
 end
end



def letra(numero)
 return  cen_out(numero), dec_out(numero), uni_out(numero), "\n"
end

for n in 1..1000
 print letra(n)
end 

Por el momento así las cosas. Cualquier cambio o problema con el código mío, lo pondré en el blog en su oportunidad.

Para escribir cheques

Prolog es uno de los lenguajes más fascinantes que hayan sido creados. Basado en el paradigma de la programación lógica, en donde el programador describe el problema y Prolog, a través de su algoritmo de resolución y unificación,  llamado algoritmo de Roberts, resuelve la dificultad planteada.

A diferencia de los lenguajes tradicionales de cuarta generación como Pascal o C, Prolog pide al programador definir las condiciones iniciales y de frontera, así como las rutinas que describen lo que queremos que el programa haga para hallar una solución. En términos generales, Prolog es una especie de "case" gigantesco, como el de los lenguajes más comunes, con la diferencia de que siempre actúa igual, siguiendo un orden determinado de acuerdo a la posición física de las cláusulas en el programa.

Además, Prolog hace énfasis en la recursión, lo cual hace que los programas sean por demás elegantes. Ya lo decía Niklaus Wirth (el inventor de Pascal): "iteratum humanum est, recursivitum divinum est", lo cual es algo así como "iterar es de humano, hacer recursión es de dioses".

Pues bien, hoy en mi clase de Programación Lógica y Funcional les dije a mis alumnos que resolveríamos un problema típico: el de pasar una cifra numérica a su equivalente en texto. Así, si el sistema recibe 2345 deberá dar como resultado "dos mil trescientos cuarenta y cinco". Este tipo de transformaciones hay que hacerlas comúnmente cuando escribimos, por ejemplo, un cheque.

Pues bien, me senté a escribir el programa en cuestión, que había bosquejado en la clase y en el que me comprometí a diseñar y mostrarles en la siguiente clase, que será el próximo miércoles. He aquí el código en turbo Prolog 2.0:



/********************************************/
/* Programa que traduce de números a letras */
/*                Versión 1.0               */
/*                16 mayo 2011              */
/*             Programó: La Morsa           */
/********************************************/

predicates

equiv(integer,symbol)
pasa_num_a_letras(integer)


clauses
equiv(1,uno).
equiv(2,dos).
equiv(3,tres).
equiv(4,cuatro).
equiv(5,cinco).
equiv(6,seis).
equiv(7,siete).
equiv(8,ocho).
equiv(9,nueve).
equiv(10,diez).
equiv(11,once).
equiv(12,doce).
equiv(13,trece).
equiv(14,catorce).
equiv(15,quince).
equiv(16,dieciseis).
equiv(17,diecisiete).
equiv(18,dieciocho).
equiv(19,diecinueve).
equiv(20,veinte).
equiv(30,treinta).
equiv(40,cuarenta).
equiv(50,cincuenta).
equiv(60,sesenta).
equiv(70,setenta).
equiv(80,ochenta).
equiv(90,noventa).
equiv(100,cien).
equiv(200,doscientos).
equiv(300,trescientos).
equiv(400,cuatrocientos).
equiv(500,quinientos).
equiv(600,seiscientos).
equiv(700,setecientos).
equiv(800,ochocientos).
equiv(900,novecientos).
equiv(1000,mil).

pasa_num_a_letras(X) :-   /* condiciones terminales */
   X < 10, 
   equiv(X,Resultado), 
   write(Resultado, " pesos. " ),nl. 

/* predicados recursivos */ 

pasa_num_a_letras(Cifra) :- 
   Cifra div 1000 <> 0, /* la cifra tiene miles */
   Miles = Cifra div 1000,
   equiv(Miles,Resultado),
   write(Resultado, " mil "),
   Cientos = Cifra - (Miles * 1000),
   pasa_num_a_letras(Cientos).

pasa_num_a_letras(Cifra) :-
   Cifra div 100 <> 0, /* la cifra tiene cientos */
   Cien = Cifra div 100,
   Cien1 = Cien * 100,
   equiv(Cien1,Resultado),
   write(Resultado," "),
   Decenas = Cifra - (Cien * 100),
   pasa_num_a_letras(Decenas).

pasa_num_a_letras(Cifra) :- /* unidades entre 11 y 20 */
    Cifra > 9,
    Cifra < 21, 
    equiv(Cifra,Resultado), 
    write(Resultado," pesos"). 

pasa_num_a_letras(Cifra) :- 
   Cifra div 10 <> 0, /* la cifra tiene decenas */
   Dec = Cifra div 10,
   Dec1 = Dec * 10,
   equiv(Dec1,Resultado),
   write(Resultado," y "),
   Unidades = Cifra - (Dec * 10),
   pasa_num_a_letras(Unidades).

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.