martes, 6 de noviembre de 2018

Resolviendo acertijos con Prolog

Empecé a aprender Prolog hace unos 2 días. Aunque ya había oído sobre él hace años, me entró mucha curiosidad de aprender a usar este lenguaje en agosto durante un simposio en el IIMAS en dónde presentaron las investigaciones del grupo Golem, quienes desarrollan robots de asistencia. Me impresionó el grado de entendimiento que parecían tener sus robots sobre su entorno a la hora de procesar lenguaje natural y realizar tareas. El sesión de Q@A se comentó que sus programas estaban basados en buena parte en Prolog. La verdad me costó bastante comenzar a pensar como un programador declarativo de forma fluida. Afortunadamente hay bastantes recursos para principiantes, aunque se vuelve más difícil encontrar material claro conforme se avanza en el lenguaje. En esta entrada sólo quiero hacer una corrección a una solución que se da aquí. (Si quieren aprender Prolog desde 0, les recomiendo este curso en Youtube en español. No recuerdo si lo menciona pero pueden usar este compilador en linea: https://swish.swi-prolog.org/ [Este otro curso es más completo pero esta en inglés]). Bien, el acertijo es el siguiente:

”Un alumno de ITS, debido al nerviosismo del primer día de clase, ha anotado el nombre de sus profesores (Elisa, Fernando y Carlos), las asignaturas que se imparten (Lógica, Programación y Matemáticas) y el día de la semana de las distintas clases (lunes, miércoles y viernes), pero sólo
recuerda que:
- La clase de Programación, impartida por Elisa, es posterior a la de Lógica
- A Carlos no le gusta trabajar los lunes, día en el que no se imparte Lógica
Ayudale a relacionar cada profesor con su asignatura, así como el día de la semana que se imparte
(Sabemos que cada profesor imparte una única asignatura y que las clases se dan en días diferentes)”


El acertijo es sencillo y se puede resolver mentalmente. Pero aquí lo interesante es pensar en como resolver este problema con un lenguaje declarativo como Prolog. La falla en el programa de respuesta de este acertijo radica justamente en no considerar que es necesario decirle a la máquina de forma clara cuales son las restricciones del problema. Porque en Prolog, como en el dicho popular, "lo que no está prohibido está permitido". Si se hace la consulta con la base de datos del programa original se puede verificar que trabaja(P,D),imparte(P,M),clase(M,D) devuelve la respuesta correcta del acertijo:

D = miercoles,
M = logica,
P = carlos
D = viernes,
M = programacion,
P = elisa
D = lunes,
M = matematicas,
P = fernando

Si pensamos como un programador tradicional imperativo esto nos debería parecer suficiente. El punto es encontrar esa respuesta ¿no?. El problema es que en un programa de Prolog, todas las consultas deben ser consistentes con las restricciones y soluciones del problema. Observen ahora que si hacemos, por ejemplo, la consulta trabaja(fernando,viernes) ¡la respuesta es verdadera! Esto significa que la computadora no está "entendiendo" realmente la situación. Mi versión de la respuesta que corrige este inconveniente es la siguiente:

Puede verificarse que ahora todas las consultas son consistentes con el problema. La solución la estructuro como una lista de listas con la forma:

S = [[P0,M0,lunes],[P1,M0,miercoles] ,[P2,M0,viernes] ]

Se debe dejar claro que las variables en la lista no pueden repetirse una vez usadas (como lo establece el acertijo). Declaro esto con:

    permutation([P0,P1,P2],Profesores),
    permutation([M0,M1,M2],Materias),  

La función permutation(listaA,listaB) retorna verdadero si listaA es alguna de las posibles permutaciones de listaB. Para entender el resto del programa hará falta revisar el manejo de listas y variables anónimas en los cursos que enlacé. En lo que quiero hacer énfasis es  en que buena parte de los problemas lógicos en los que se requiere repartir atributos a un grupo de objetos pueden resolverse estructurando la respuesta como una lista o una lista de listas y jugando con los operadores de pertenencia, permutación y relaciones de posición entre los elementos de la lista.

No hay comentarios: