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

Concurso para programadores reales

Se supone que los programadores reales, los de verdad, son tan capaces que casi casi no necesitan herramientas de software para sus labores. Esto por supuesto es una exageración que se ha llevado ya al extremo del folklore urbano (*) en esta rama de la ciencia.

Pues bien, Facebook lanzó la segunda versión de su concurso "hacker-cup", para aquellos interesados en pasar a la historia como uno de los mejores programadores del planeta. El concurso está abierto a todo aquel que quiera participar, en cualquier parte del mundo y hasta donde he entendido no hay ninguna restricción sobre qué lenguaje de programación usar.

La justa se hará en sucesivas fechas, en las cuales se irá obteniendo a los ganadores. Por ejemplo, en la primera etapa se plantean tres problemas., Si se resuelve al menos uno, se pasa a la siguiente prueba. ¿Qué tipo de pruebas se exigen en el concurso? No lo sé, pero he aquí un ejemplo del año pasado: se trata de hallar dos números enteros, del 1 al cien, que pongan todas las posibles combinaciones de estos números en la forma A^2 + B^2.

Por ejemplo, 25 puede ponerse como 3^2 + 4^2 o bien, 0^2 + 5^2.

No pienso entrar en el concurso, porque francamente no tengo tiempo y seguro hay programadores mil veces más clavados que yo. Sin embargo, este pequeño problema, se me ocurre, se puede resolver fácilmente en Prolog. He aquí mi código, el cual probaré a la brevedad:

predicates
   suma (integer,integer,integer)
   num(integer)
   prueba

clauses
    suma(R, A, B) :- R = (A^2) + (B^2).
    num(0).
    num(1).
    num(2).
    num(3).
        .
        .
        .
    num(99).
    num(100).

    prueba :-
      num(A),
      num(B),
      R = A,         
      suma(R,A,B),
      write("Los valores de los números son ", A, " y  ", B), nl,
      fail.

 goal
    prueba.         


Ahora que pruebe mi código pondré las reflexiones del caso.
_____
(*) El término "programador real" describe a esos programadores "duros" que prácticamente reniegan de todas las herramientas y lenguajes modernos para hacerlo todo desde una manera más directa y efectiva, muchas veces relacionada con el hardware. El arquetipo de los programadores reales es sin duda Mel Kaye, de la McBee Computer Corporation, quien está inmortalizado en "La Historia de Mel", en la cual se dice que "escribió en código de máquina, sin adornos, todo su código en el inescrutable código hexadecimal. Directamente".

Fotos panorámicas de Acapulco

JC me acaba de mandar unas fotos panorámicas de Acapulco, que tomó con su maravillosa cámara que hace este proceso de forma automática (necesito uno de estos dispositivos urgentemente).

 

Sin embargo, para verlas mejor, tengo un programa que escribí hace tiempo, usando un componente explícitamente  escrito para manejar fotos panorámicas, el cual hace la experiencia mucho más sencilla. Pueden bajar el ejecutable con las dos fotos que ilustran este artículo para que vean la playa del revolcadero y el complejo en donde estuvimos hospedados. 

El enlace es éste.

Inteligencia artificial y sistemas expertos

La inteligencia artificial, término que acuñó John McCarthy me parece, se basa en la idea de hacer sistemas inteligentes, tan capaces como los que puede lograr el cerebro humano. Sin embargo, se halló, después de los primeros años frustrantes, que la inteligencia humano no sólo era complicada, sino mucho más complicada de lo que habíamos pensado. Por ello, hubo una división natural de tareas: visión por computadora; sistemas expertos; reconocimiento de patrones; entre otros.



Uno de los temas que por algunos años estuvieron en boga, pero que probablemente han caído en el desuso es el de los sistemas expertos, el cual se basa en escribir software que fuese tan bueno como un experto humano en un tema particular. En ese sentido por ejemplo, un programa de ajedrez como los actuales, que le ganan al 99.99% de los jugadores humanos,  es un sistema experto muy exitoso, pero las técnicas de programación para jugar tan bien están lejos de la teoría tradicional de los sistemas expertos. En este caso las cosas son así. Un sistema experto se basa en tres subtemas:

• Interfaz con el usuario
• Base de conocimientos (reglas de producción)
• Motor de inferencias

En ese sentido, cuando se va a trabajar con un sistema experto hay que reconocer cómo se diseñará cada parte. En el caso de la interfaz del usuario, aunque hay muchas alternativas, la más común es responder "sí" o "no" a las preguntas que hace el sistema. esto -desde luego- no es tan poderoso como aquellos sistemas que además de responder a preguntas con "sí" o "no", también puedes darle un valor de confiabilidad a la respuesta. Por ejemplo,

Pregunta: "¿Te duele la cabeza"
Respuesta: "sí"
Pregunta: Del 1 al 10, ¿cuánto te duele? (donde 10 es el dolor más fuerte)

este tipo de sistemas usan probabilidad para decidir el margen de confiabilidad de las respuestas que entrega el sistema experto, basado en las confiabilidades que se dieron en las diferentes respuestas por parte del usuario. Para ello se usa el teorema de Bayes Sin embargo, para poner las cosas de la manera más simple, muchos sistemas expertos solamente permiten responder "sí" o "no".

Pues bien, una vez hecho esto, tenemos que describir la base de conocimientos, la cual es la que nos dará información sobre el tema que nos ocupa. Por ejemplo, en el programa muestra que te mando, la base de conocimientos es la información sobre los diferentes perros que existen. Así, un snauzer será un perro pequeño, con cola y orejas cortas, de buen talante, etc. En esta base se definen algunos perros y sus características. La idea del sistema experto es que el programa vaya pidiéndole información al usuario para que éste pueda concluir de qué perro se trata. Las bases de conocimiento están puestas en general como predicados "causa - efecto". Así, una regla en general podría ser: "si te duele la cabeza es que tienes gripe". La causa: el tener gripe; el efecto: el dolor de cabeza.

El motor de inferencias es quien pregunta al usuario basándose en esas cláusulas causa - efecto. Los sistemas expertos usan tres posibles motores de inferencia:

• encadenamiento hacia atrás (backward chaining)
• encadenamiento hacia adelante (forward chaining)
• sistema de borrador (blackboard system)

El primer caso funciona así: Imagina que vas con el médico porque te sientes mal. Él te ve y te empieza a preguntar cosas sobre tus malestares. Sin embargo, antes de empezar las preguntas, las dirige asumiendo que tienes gripe, por ejemplo. Entonces te preguntará síntomas asociados de la gripe. Si le das más de una respuesta que no es presumiblemente de la gripe, se formulará mentalmente otra hipótesis y de nuevo empezará el interrogatorio.

El segundo caso es el encadenamiento hacia adelante. Siguiendo el ejemplo anterior, vas al médico y éste comienza a preguntarte qué te duele, pero no asume que tiene gripe o cualquier otra enfermedad. Lo que hace es acumular datos (respuestas) y entonces busca en su base de conocimientos qué es lo que más se parece a lo que puedes tener.

El sistema de borrador ya es obsoleto. Imagina un salón de clases lleno de expertos humanos en alguna materia. Entonces se plantea un problema y cada experto tiene un pedazo del borrador en la pared para poner su solución. Después de que todos hayan puesto su posible solución, un supervisor lee todas las respuestas y arma la respuesta final. Así funcionaba HearSay, un sistema de reconocimiento de voz de los años ochentas, actualmente en desuso.

Cabe señalar que los sistemas expertos deben estar construídos para no repetir hasta el hartazgo la misma pregunta. Por ejemplo, imagina que un sistema de encadenamiento hacia atrás te pregunta si te duele la cabeza y le contestas que no. Si es así, probablemente la primera hipótesis, la de tener gripe, no funcione. Entonces el sistema crea a través de la siguiente regla la nueva hipótesis. Si en esta nueva regla hay que preguntar de nuevo si te duele la cabeza, sería poco inteligente y serio de un sistema que te volviese a preguntar lo mismo. Así, el sistema experto (como el que te mando), guarda las respuestas del usuario y checa antes si ya respondiste a la pregunta para no volverla a preguntar.

Otra cuestión, que no está considerada en el sistema experto es la de explicar su funcionamiento. Es decir, ¿por qué el sistema experto llegó a las conclusiones y diagnósticos a los que llegó? Hay muchas maneras de hacer esto pero una de ellas es simplemente avisarle al programador, vía mensajes a la pantalla, en qué regla está trabajando. Otrso sistemas expertos pueden trazar la ruta de desarrollo. Por ejemplo, pueden decirte: "primero usé la regla 4, la cual me remitió a la regla 92 y por las respuestas del usuario tuve que probar las reglas 153 y 25", etc. Pero esto es mucho más sofisticado y difícil de programar.



/*      Program: Dog Expert        */
/* Purpose: To show the working of */
/* an expert system. It is a pro-  */
/* duction rule-based system.      */
/*                                 */
/* Remarks: This is a dog classi-  */
/* cation expert system. It uses a */
/* set of production rules for the */
/* purpose of inferring.           */

domains

database

   xpositive(symbol,symbol)
   xnegative(symbol,symbol)


predicates

   do_expert_job
   do_consulting
   ask(symbol,symbol)
   dog_is(symbol)
   it_is(symbol)
   positive(symbol,symbol)
   negative(symbol,symbol)
   remember(symbol,symbol,symbol)
   clear_facts

goal

   do_expert_job.


clauses

/*  User Interface System (UIS) */

do_expert_job :-
     makewindow(1,7,7,"An Expert System",1,16,22,58),
     nl, write(" ************************************"),
     nl, write("    Welcome to a Dog Expert System"),
     nl, write("                                 "),
     nl, write(" This is a dog identification system"),
     nl, write(" Please, respond by typing in 'yes'"),
     nl, write(" or 'no'.            Thank you.    "),
     nl,nl,
     do_consulting,
     write("Press space bar..."), nl,
     readchar(_),
     clearwindow,
     exit.

do_consulting :-
     dog_is(X), !,
     nl, write(" Your dog may be a(n) ",X,"."),
     clear_facts.

do_consulting :-
     nl, write("Sorry, unable to determine the dog."),nl,
     clear_facts.

ask(X,Y) :-
     write("   Question :- ",X," it, ",Y," ? "),
     readln(Reply),
     remember(X,Y,Reply).


/* Inference Engine (INE) */

positive(X,Y) :-
     xpositive(X,Y),!.

positive(X,Y) :-
     not(negative(X,Y)),!,
     ask(X,Y).

negative(X,Y) :-
     xnegative(X,Y),!.

remember(X,Y,yes) :-
     asserta(xpositive(X,Y)).

remember(X,Y,no) :-
     asserta(xnegative(X,Y)),
     fail.

clear_facts :-
     retract(xpositive(_,_)),
     fail.

clear_facts :-
     retract(xnegative(_,_)),
     fail.


/* Production Rules */


dog_is("English Bulldog") :-
     it_is("short-haired dog"),
     positive(has,"height under 22 inches"),
     positive(has,"low-set tail"),
     positive(has,"good natured personality"),!.

dog_is("Beagle") :-
     it_is("short-haired dog"),
     positive(has,"height under 22 inches"),
     positive(has,"long ears"),
     positive(has,"good natured personality"),!.

dog_is("Great Dane") :-
     it_is("short-haired dog"),
     positive(has,"low-set tail"),
     positive(has,"longer ears"),
     positive(has,"good natured personality"),
     positive(has,"weight over 100 lb"),!.

dog_is("American Foxhound") :-
     it_is("short-haired dog"),
     positive(has,"height under 30 inches"),
     positive(has,"longer ears"),
     positive(has,"good natured personality"),!.
    
dog_is("Cocker Spaniel") :-
     it_is("long-haired dog"),
     positive(has,"height under 22 inches"),
     positive(has,"low-set tail"),
     positive(has,"longer ears"),
     positive(has,"good natured personality"),!.

dog_is("Irish Setter") :-
     it_is("long-haired dog"),
     positive(has,"height under 30 inches"),
     positive(has,"low-set tail"),
     positive(has,"good natured personality"),!.

dog_is("Collie") :-
     it_is("long-haired dog"),
     positive(has,"height under 30 inches"),
     positive(has,"low-set tail"),
     positive(has,"good natured personality"),!.

dog_is("St. Bernard") :-
     it_is("long-haired dog"),
     positive(has,"low-set tail"),
     positive(has,"good natured personality"),
     positive(has,"weight over 100 lb"),!.
    
it_is("short-haired dog") :-
     positive(has,"short-haired"),!.
    
it_is("long-haired dog") :-         
     positive(has,"long-haired"),!.

Este sistema experto está escrito para turbo prolog, que funciona bajo MsDOS y está sacado del libro -si mal no recuerdo- Exploring Artificial Intelligence With Turbo PROLOG por Keith Weiskamp, el cual no sé dónde está. No lo halló más.

Sobre resolver con Prolog el problema de los sudokus

En mi último artículo sobre programación y sudokus, hablé de un programa que podría resolver, en esencia, cualquier sudoku que se le pusiese, utilizando para ello fuerza bruta, es decir, considerando todas las posibilidades de números a poner en cada casilla. Alguna combinación debe ser la adecuada y con ello el asunto estaría resuelto.

Cuando corrí mi programa, pensé que se tardaría algunas horas quizás, de hecho no lo sabía, pero sospechaba que así sería. Un par de horas después de haber empezado el proceso lo aborté porque me hartó. No se veía para cuando terminaría. Así que decidí primero ver cuántos cálculos tiene que hacer el programa para poder resolver el sudoku planteado, que en ese caso hablamos de 46 números por hallar. Si usamos Prolog, tenemos que calcular la cantidad de combinaciones con repetición de 9 números tomados de 46 en 46.

La fórmula para ello es:

                               (n+r-1)!

Combinaciones =  ----------

                                r!(n-1)!

 donde n es la cantidad de números diferentes y r es la cantidad de espacios a llenar. Además, se pueden repetir los números, es decir, no todos tienen que ser siempre distintos. El resultado de esto es 1,040,465,790, es decir, mil cuatrocientos millones de posibles combinaciones. Para entender la magnitud de este número, si cada combinación se genera en un segundo (muy lento), entonces tardará unos 32 años en probar todas las posibles combinaciones. Si hace 1000 combinaciones por segundo (una aproximación más razonable), el sistema tardará unos 120 días en resolver todas las posibles combinaciones de números. Algo sin duda, demasiado lento. Vaya, si hiciese 10000 combinaciones por segundo, tardaría 12 días en resolverlo. Aún así es muy lento.

La razón de esto es que el programa, como originalmente está escrito, está obligado a prtimero poner a todos los números que buscamos, un "1". Se prueban entonces la combinación (como si fuese una caja fuerte). Si no "se abre", entonces probamos con otra combinación, haciendo backtrack. El resultado es un gigantesco proceso de ir cambiando números.

¿Cómo se podría mejorar? Desde luego que la técnica de prolog de examinar hasta agotar todas las posibilidades (simple fuerza bruta), no es práctica en este caso. Se necesita más inteligencia. Aún así, si no se quiere pensar mucho, bien podría intercalarse la búsqueda de unos pocos números, y entonces checar algunas de las ecuaciones, si eso está correcto, entonces buscar las restantes. Esto es lo que en principio sugirió el buen amigo Eduardo Ramos, aunque aún así los resultados pueden tardar si bien nos va, muchos días. De hecho, el programa se vería esta intercalación así:

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 :-
            / horizontales */
          
             num(A1), num(B1), num(C1), num(D1),
             suma(5,A1,4,3,B1,6,C1,7,D1,45),
           
             num(A2), num(B2), num(C2), num(D2), num(E2),   
             num(F2), num(G2), num(H2),
             suma(A2,B2,1,C2,D2,E2,F2,G2,H2,45),
           
             num(A3), num(B3), num(C3), num(D3), num(E3),
             suma(A3,7,6,B3,C3,2,9,D3,E3,45),
           
             num(A4), num(B4), num(C4), num(D4),
             suma(A4,8,B4,7,C4,5,6,D4,1,45),
                       
             num(A5), num(B5), num(C5), num(D5),
             suma(7,6,A5,B5,3,C5,D5,8,9,45),
           
             num(A6), num(B6), num(C6), num(D6),
             suma(9,A6,3,8,B6,4,C6,2,D6,45),
           
             num(A7), num(B7), num(C7), num(D7), num(E7),
             suma(A7,B7,8,1,C7,D7,2,9,E7,45),

             num(A8), num(B8), num(C8), num(D8), num(E8), 
             num(F8), num(G8), num(H8),
             suma(A8,B8,C8,D8,E8,F8,3,G8,H8,45),

             num(A9), num(B9), num(C9), num(D9),
             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).
            
por cierto, este programa está en el antiguo turbo Prolog 2.0 de Borland.

La conclusión inicial es que si tuviésemos memoria infinita y poder de procesamiento infinito, las soluciones tipo prolog, resolviendo todo el árbol de búsquedas (árbol solución), podría llegar a la conclusión del resultado correcto. Pero en la vida real, al tener limitaciones en memoria y velocidad de proceso, esto desde luego vuelve impráctico este enfoque.

Cabe decir que no por ello prolog no es útil para resolver problemas. Simplemente el sudoku -utilizando el esquema de fuerza bruta- no es el más adecuado.