% PD 2007-08: practica_4b.pl (17 de Enero de 2008, No presencial)
% Departamento de Ciencias de la Computación e I.A.
% Universidad de Sevilla 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 1: Definir el predicado divisores(+N,-L) que se verifique si
% L es la lista de los divisores del número N. Por ejemplo, 
%    ?- divisores(24,L).
%    L = [1, 2, 3, 4, 6, 8, 12, 24] 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 2: Definir la propiedad primo(+N) que se verifique si N es
% un número primo. Por ejemplo, 
%    ?- primo(7).
%    Yes
%    ?- primo(9).
%    No
% [Indicación: Hacer distintas definiciones basadas en las siguientes
% ideas: 
% (1) X es primo si el número de divisores de X es menor que 3 [Usar la
%     definición anterior de divisores].
% (2) X es primo si no hay ningún número entre 2 y la raiz cuadrada de X
%     que sea un divisor de X.
% (3) X es primo si no hay ningún número entre 2 y la raiz cuadrada de X
%     que sea primo y divida a X.]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 3: Se considera el siguiente polinomio p(X)=X^2-X+41.
% Definir la relación genera_primo(+X,+Y,-L) que se verifique si L es el
% conjunto de los pares (A,p(A)) tales A es un número del intervalo
% [X,Y] y p(A) es primo. Por ejemplo, 
%    ?- genera_primo(5,7,L).
%    L = [[5, 61], [6, 71], [7, 83]] 
% Comprobar que p(A) es primo para A desde 1 hasta 40, pero no es primo
% para A=41.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 4: Se dice que dos números X e Y son amigos cuando X es
% igual a la suma de los divisores de Y (exceptuando al propio Y) y
% viceversa. Por ejemplo, 6 es amigo de sí mismo puesto que los
% divisores de 6 (exceptuando al 6) son 1, 2 y 3 y 6=1+2+3. Igualmente
% 28 es amigo de sí mismo, puesto que 28=1+2+4+7+14. Definir el
% predicado amigos(+A,+B,-L) que se verifique si L es la lista de las
% parejas de números amigos comprendidos entre A y B. Por ejemplo,  
%    ?- amigos(1,300,L).
%    L = [6-6, 28-28, 220-284, 284-220] 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 5: Definir la relación lista_a_conjunto(+L,-C) que se
% verifique si C es el conjunto de los elementos de la lista no vacía
% L. Por ejemplo,
%    ?- lista_a_conjunto([b,c,d,a,c,f,a],C).
%    C = [a, b, c, d, f] 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 6: Definir la relación para_todos(+P,+L) que se verifica si
% todos los elementos de la lista L cumplen la propiedad P. Por ejemplo, 
%    ?- para_todos(number,[1,2,3]).
%    Yes
%    ?- para_todos(number,[1,2,3,a]).
%    No
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 7: Definir la relación existe(+P,+L) que se verifica si
% existe algún elemento de la lista L que cumple la propiedad P. Por
% ejemplo, 
%    ?- existe(number,[a,b,c]).
%    No
%    ?- existe(number,[a,1,b,c]).
%    Yes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 8: Definir la relación sublista(+P,+L1,?L2) que se verifica
% si L2 es la lista de los elementos de L1 que verifican la propiedad
% P. Por ejemplo,
%    ?- sublista(number,[1,a,2,b,1],L).
%    L = [1, 2, 1]
% (Nota: sublista/3 corresponde a la relación definida sublist/3).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 9: [Feb-2000] Definir el predicado rotaciones(L1,L2) que se
% verifique si L2 es la lista cuyos elementos son las listas formadas
% por las sucesivas rotaciones de los elementos de la lista L1. Por
% ejemplo, 
%    ?- rotaciones([1,2,3,4],L).
%    L = [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]] 
%    ?- rotaciones([2,3,4,1],L).
%    L = [[2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3], [1, 2, 3, 4]] 
%    No
% (NOTA: No importa el orden de los elementos en L2.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 10: Definir la relación capicúas(N,L) que tome como dato de
% entrada el número entero positivo N y devuelva  la lista L formada por
% todos los números enteros positivos capicúa menores que N. Por
% ejemplo,
%    ?- capicúas(100,L).
%    L = [1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99] ;
%    No
%    ?- capicúas(1000,L).
%    L = [1,2,3,4,5,6,7,8,9,11,22,33,44,55,...,979,989,999] ;
%    No
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 11: Definir la relación invierte_palabra(P1,P2) que tome
% como dato de entrada una palabra P1 y devuelva la palabra P2 formada
% invirtiendo el orden de las letras. Por ejemplo,
%    ?- invierte_palabra(arroz,P).
%    P = zorra
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 12: Definir la relación lista_mayor(+L1,-L2) que se verifica
% si L2 es una lista de la lista de listas L1 de máxima longitud. Por
% ejemplo,
%    ?- lista_mayor([[a,b,c],[d,e],[1,2,3]],L).
%    L = [a, b, c] ;
%    L = [1, 2, 3] ;
%    No
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 13: Un mapa puede representarse mediante la relación
% mapa(N,L) donde N es el nombre del mapa y L es la lista de los pares
% formados por cada una de las regiones del mapa y la lista de sus
% regiones vecinas. Por ejemplo, los mapas siguientes
%       +----------+----------+       +----+-----+-----+----+       
%       |    a     |     b    |       | a  |  b  |  c  | d  |       
%       +----+-----+-----+----+       +----+-----+-----+----+       
%       |    |           |    |       | e  |           | f  |       
%       | c  |     d     | e  |       +----+     k     +----+       
%       |    |           |    |       | g  |           | h  |       
%       +----+-----+-----+----+       +----+-----+-----+----+       
%       |    f     |     g    |       |    i     |     j    |       
%       +----------+----------+       +----------+----------+
% se pueden representar por
%    mapa(ejemplo_1,
%         [a-[b,c,d], b-[a,d,e], c-[a,d,f], d-[a,b,c,e,f,g],
%          e-[b,d,g], f-[c,d,g], g-[d,e,f]]).
%    mapa(ejemplo_2,
%         [a-[b,e,k],   b-[a,c,e,k], c-[b,d,f,k], d-[c,f,k], e-[a,b,g,k],
%          f-[c,d,h,k], g-[e,i,k],   h-[f,j,k],   i-[g,j,k], j-[i,h,k],
%          k-[a,b,c,d,e,f,g,h,i,j]]).
% Definir la relación coloración(+M,+LC,-S) que se verifica si S es una
% lista de pares formados por una región del mapa M y uno de los colores
% de la lista de colores LC tal que las regiones vecinas tengan colores
% distintos. Por ejemplo,
%    ?- coloración(ejemplo_1,[1,2,3],S).
%    S = [a-1, b-2, c-2, d-3, e-1, f-1, g-2]
% ¿Qué número de colores se necesitan para colorear el segundo
% mapa? ¿De cuántas formas distintas puede colorearse con dicho
% número?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 14:  Definir, usando un acumulador, las siguientes relaciones 
% * factorial(+X,-Y) que se verifica si Y es el factorial de X,
% * longitud(L,N) que se verifica si N es la longitud de la lista L.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 15: Consideremos la siguiente versión del problema de las
% torres de Hanoi: 
%   * Existen tres postes que llamaremos A, B y C.
%   * Hay N discos en el poste A ordenados por tamaño (el de arriba es
%     el de menor tamaño).
%   * Los postes B y C están vacíos.
%   * Sólo puede moverse un disco a la vez y todos los discos deben de
%     estar ensartados en algún poste.
%   * Ningún disco puede situarse sobre otro de menor tamaño.
% Definir la relación hanoi(+N,+A,+B,+C,-L) que se verifica si L es la
% lista de movimientos para mover N discos desde el poste A al poste B
% usando el C como auxiliar. Por ejemplo,
%    ?- hanoi_1(4,a,b,c,L).
%    L = [a-c,a-b,c-b,a-c,b-a,b-c,a-c, a-b, c-b,c-a,b-a,c-b,a-c,a-b,c-b] 
%    ?- hanoi_1(3,a,c,b,L).
%    L = [a-c,a-b,c-b,a-c,b-a,b-c,a-c] 
%    ?- hanoi_1(3,c,b,a,L).
%    L = [c-b,c-a,b-a,c-b,a-c,a-b,c-b] 
% Dar dos versiones (una sin memoria y otra con memoria) y comparar los
% resultados.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 16: El problema de la bandera tricolor consiste en lo
% siguiente: Dada un lista de objetos L1, que pueden ser rojos,
% amarillos o morados, se pide devolver una lista L2 que contiene los
% elementos de L1, primero los rojos, luego los amarillos y por último
% los morados. Definir la relación bandera_tricolor(+L1,-L2) que se
% verifica si L2 es la solución del problema de la bandera tricolor
% correspondiente a la lista L1. Por ejemplo,
%    ?- bandera_tricolor([m,m,a,a,r,r],L).
%    L = [r, r, a, a, m, m]
% Se dispone de los hechos
%    rojo(r).
%    amarillo(a).
%    morado(m).
% Dar distintas definiciones y comparar su eficiencia.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ejercicio 17: Se dice que L es una sucesión de Lanford si L es una
% lista de longitud 27 en la cual aparecen 3 veces cada uno de los
% dígitos del 1 al 9 y que además cumple la propiedad de que entre dos 1
% siempre hay un dígito, entre dos 2 hay  dos dígitos, entre dos 3 hay
% tres dígitos, etc.   
% Definir la relación lanford(?L) que se verifique si L es una longitud
% de Lanford. Por ejemplo,
%    ?- lanford(L).
%    L = [1,9,1,2,1,8,2,4,6,2,7,9,4,5,8,6,3,4,7,5,3,9,6,8,3,5,7] ;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
