Tema 6: Estilo y eficiencia en programación lógica

• subconjunto(-L1,+L2) se verifica si L14 es un subconjunto de ~L2. Por ejemplo,

  ?- subconjunto(L,[a,b]).
  L = [a, b] ;
  L = [a] ;
  L = [b] ;
  L = [].
  

  Su definición es

  subconjunto([],[]).
  subconjunto([X|L1],[X|L2]) :-
     subconjunto(L1,L2).
  subconjunto(L1,[_|L2]) :-
     subconjunto(L1,L2).
  

• partes(+L1,-L2) se verifica si L2 es el conjunto de las partes de L1. Por ejemplo,

  ?- partes([a,b,c],L).
  L = [[a, b, c], [a, b], [a, c], [a], [b, c], [b], [c], []].
  

  Su definición es

  partes(L1,L2) :-
     findall(Y,subconjunto(Y,L1),L2).
  

• combinación(+L1,+N,-L2) se verifica si L2 es una combinación N-aria de L1. Por ejemplo,

  ?- combinación([a,b,c],2,L).
  L = [a, b] ;
  L = [a, c] ;
  L = [b, c] ;
  false.
  

  Su definición es

  % 1ª definición
  combinación_1(L1,N,L2) :-
     subconjunto(L2,L1),
     length(L2,N).
  
  % 2ª definición
  combinación_2(L1,N,L2) :-
     length(L2,N),
     subconjunto(L2,L1).
  
  % Usaremos la 2ª definición
  combinación(L1,N,L2) :-
     combinación_2(L1,N,L2).
  

• combinaciones(+L1,+N,-L2) se verifica si L2 es la lista de las combinaciones N–arias de L1. Por ejemplo,

  ?- combinaciones([a,b,c],2,L).
  L = [[a, b], [a, c], [b, c]].
  

  Su definición es

  % 1ª definición
  combinaciones_1(L1,N,L2) :-
     findall(L,combinación_1(L1,N,L),L2).
  
  % 2ª definición
  combinaciones_2(L1,N,L2) :-
     findall(L,combinación_2(L1,N,L),L2).
  
  % Usaremos la 2ª definición
  combinaciones(L1,N,L2) :-
     combinaciones_2(L1,N,L2).
  

• Comparación de eficiencia:

  %    ?- findall(_N,between(1,24,_N),_L1),
  %       time(combinaciones_1(_L1,2,_L2)),
  %       time(combinaciones_2(_L1,2,_L2)).
  %    % 67,109,150 inferences, 6.973 CPU in 6.973 seconds (100% CPU, 9624607 Lips)
  %    %      2,915 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 5684777 Lips)
  %    true.
  

• select(?X,?L1,?L2) se verifica si X es un elemento de la lista L1 y L2 es la lista de los restantes elementos. Por ejemplo,

  ?- select(X,[a,b,c],L).
  X = a,
  L = [b, c] ;
  X = b,
  L = [a, c] ;
  X = c,
  L = [a, b].
  
  ?- select(a,L,[b,c]).
  L = [a, b, c] ;
  L = [b, a, c] ;
  L = [b, c, a] ;
  false.
  

• permutación(+L1,-L2) se verifica si L2 es una permutación de L1. Por ejemplo,

  %    ?- permutación(L,[a,b,c]).
  %    L = [a, b, c] ;
  %    L = [b, a, c] ;
  %    L = [b, c, a] ;
  %    L = [a, c, b] ;
  %    L = [c, a, b] ;
  %    L = [c, b, a] ;
  %    false.
  

  Su definición es

  permutación([],[]).
  permutación(L1,[X|L2]) :-
     select(X,L1,L3),
     permutación(L3,L2).
  

• Nota: La relación predefinida correspondiente a permutación es permutation.

• variación(+L1,+N,-L2) se verifica si L2 es una variación N-aria de L1. Por ejemplo,

  ?- variación([a,b,c],2,L).
  L = [a, b] ;
  L = [a, c] ;
  L = [b, a] ;
  L = [b, c] ;
  L = [c, a] ;
  L = [c, b] ;
  false.
  

  Su definición es

  % 1ª definición
  variación_1(L1,N,L2) :-
     combinación(L1,N,L3),
     permutación(L2,L3).
  
  % 2ª definición
  variación_2(_,0,[]).
  variación_2(L1,N,[X|L2]) :-
     N > 0,
     M is N-1,
     select(X,L1,L3),
     variación_2(L3,M,L2).
  

• variaciones(+L1,+N,-L2) se verifica si L2 es la lista de las variaciones N-arias de L1. Por ejemplo,

  ?- variaciones([a,b,c],2,L).
  L = [[a, b], [a, c], [b, c]] ;
  

  Su definición es

  % 1ª definición
  variaciones_1(L1,N,L2) :-
     setof(L,variación_1(L1,N,L),L2).
  
  % 2ª definición
  variaciones_2(L1,N,L2) :-
     setof(L,variación_2(L1,N,L),L2).
  

• Comparación de eficiencia

  ?- findall(_N,between(1,400,_N),_L1),
     time(variaciones_1(_L1,2,_L2)),
     time(variaciones_2(_L1,2,_L2)).
  % 12,024,020 inferences, 0.845 CPU in 0.844 seconds (100% CPU, 14237961 Lips)
  %    640,016 inferences, 0.096 CPU in 0.096 seconds (100% CPU, 6646804 Lips)
  true.
  

• ordenación(+L1,-L2) se verifica si L2 es la lista obtenida ordenando la lista L1 en orden creciente. Por ejemplo,

  ?- ordenación([2,1,a,2,b,3],L).
  L = [1, 2, 2, 3, a, b]
  

  Su definición es

      ordenación(L,L1) :-
         permutation(L,L1),
         ordenada(L1).
  
  % ordenada(+L) se verifica si L es una lista ordenada (según el criterio
  % de ordenación de Prolog).
  ordenada([]).
  ordenada([_]).
  ordenada([X,Y|L]) :-
     X @=< Y,
     ordenada([Y|L]).
  

• La definición de ordenación por selección es

  ordenación_por_selección(L1,[X|L2]) :-
     selecciona_menor(X,L1,L3),
     ordenación_por_selección(L3,L2).
  ordenación_por_selección([],[]).
  
  % seleccióna_menor(?X,+L1,?L2) se verifica si X es el menor elemento de
  % la lista de números L1 y L2 son los restantes elementos. Por ejemplo,
  %    ?- selecciona_menor(X,[4,1,3],L).
  %    X = 1
  %    L = [4, 3]
  selecciona_menor(X,L1,L2) :-
     select(X,L1,L2),
     not((member(Y,L2), Y @< X)).
  

• La definición de ordenación rápida es

  ordenación_rápida([],[]).
  ordenación_rápida([X|R],Ordenada) :-
     divide(X,R,Menores,Mayores),
     ordenación_rápida(Menores,Menores_ord),
     ordenación_rápida(Mayores,Mayores_ord),
     append(Menores_ord,[X|Mayores_ord],Ordenada).
  
  divide(_,[],[],[]).
  divide(X,[Y|R],[Y|Menores],Mayores) :-
     Y @< X, !,
     divide(X,R,Menores,Mayores).
  divide(X,[Y|R],Menores,[Y|Mayores]) :-
     % Y @>= X,
     divide(X,R,Menores,Mayores).
  

• Comparación de eficiencia en la ordenación de la lista [N,N-1,N-2,...,2,1]

  N	ordena	selección	rápida
  1	10 inf 0.00 s	9 inf 0.00 s	3 inf 0.00 s
  2	22 inf 0.00 s	23 inf 0.00 s	10 inf 0.00 s
  4	256 inf 0.00 s	80 inf 0.00 s	33 inf 0.00 s
  8	427,048 inf 0.03 s	366 inf 0.00 s	115 inf 0.00 s
  16		2,074 inf 0.00 s	423 inf 0.00 s
  32		13,618 inf 0.00 s	1,615 inf 0.00 s
  64		97,890 inf 0.01 s	6,303 inf 0.00 s
  128		740,546 inf 0.08 s	24,895 inf 0.01 s
  256		5,757,314 inf 0.34 s	98,943 inf 0.03 s
  512		45,396,738 inf 2.58 s	394,495 inf 0.04 s
  1024			1,575,423 inf 0.16 s

• El problema de los cuadrados mágicos consiste en colocar los números 1,2,3,4,5,6,7,8,9 en un cuadrado 3x3 de forma que todas las líneas (filas, columnas y diagonales) sumen igual; es decir, buscar los valores para las variables A, B ,C, D, E, F, G, H, I

  +---+---+---+
  | A | B | C |
  +---+---+---+
  | D | E | F |
  +---+---+---+
  | G | H | I |
  +---+---+---+
  

  tales que

  {A,B,C,D,E,F,G,H,I} = {1,2,3,4,5,6,7,8,9},
  A+B+C = 15,
  D+E+F = 15,
  G+H+I = 15,
  A+D+G = 15,
  B+E+H = 15,
  C+F+I = 15,
  A+E+I = 15,
  C+E+G = 15.
  

• La definición es

  cuadrado_1([A,B,C,D,E,F,G,H,I]) :-
     permutation([1,2,3,4,5,6,7,8,9],[A,B,C,D,E,F,G,H,I]),
     A+B+C =:= 15,
     D+E+F =:= 15,
     G+H+I =:= 15,
     A+D+G =:= 15,
     B+E+H =:= 15,
     C+F+I =:= 15,
     A+E+I =:= 15,
     C+E+G =:= 15.
  

• Cálculo de las primeras soluciones

  ?- cuadrado_1(L).
  L = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
  L = [2, 9, 4, 7, 5, 3, 6, 1, 8]
  

• Cálculo del número de soluciones

  ?- findall(_X,cuadrado_1(_X),_L),length(_L,N).
  N = 8.
  

• La definición es

  cuadrado_2([A,B,C,D,E,F,G,H,I]) :-
     select(A,[1,2,3,4,5,6,7,8,9],L1),
     select(B,L1,L2),
     select(C,L2,L3),
     A+B+C =:= 15,
     select(D,L3,L4),
     select(G,L4,L5),
     A+D+G =:= 15,
     select(E,L5,L6),
     C+E+G =:= 15,
     select(I,L6,L7),
     A+E+I =:= 15,
     select(F,L7,[H]),
     C+F+I =:= 15,
     D+E+F =:= 15.
  

• Cálculo de las primeras soluciones

  ?- cuadrado_2(L).
  L = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
  L = [2, 9, 4, 7, 5, 3, 6, 1, 8]
  

• Cálculo del número de soluciones

  ?- findall(_X,cuadrado_2(_X),_L),length(_L,N).
  N = 8.
  

• Comprobación de la equivalencia de las definiciones

  ?- setof(_X,cuadrado_1(_X),_L),setof(_X,cuadrado_2(_X),_L).
  true.
  

• Comparación de eficiencia

  ?- time(setof(_X,cuadrado_1(_X),_L)).
  % 2,999,645 inferences, 0.236 CPU in 0.236 seconds (100% CPU, 12690432 Lips)
  true.
  
  ?- time(setof(_X,cuadrado_2(_X),_L)).
  % 7,216 inferences, 0.005 CPU in 0.005 seconds (100% CPU, 1511635 Lips)
  true.
  

• intercambia(+T1,-T2) se verifica si T1 es un término con dos argumentos y T2 es un término con el mismo símbolo de función que T1 pero sus argumentos intercambiados. Por ejemplo,

  ?- intercambia(opuesto(3,-3),T).
  T = opuesto(-3, 3)
  

  Sus definiciones (que se encuentra en intercambia.pl) son

  % 1ª definición
  intercambia_1(T1, T2):-
     functor(T1,F,2),
     functor(T2,F,2),
     arg(1,T1,X1),
     arg(2,T1,Y1),
     arg(1,T2,X2),
     arg(2,T2,Y2),
     X1 = Y2,
     X2 = Y1.
  
  % 2ª definición
  intercambia_2(T1,T2) :-
     T1 =.. [F,X,Y],
     T2 =.. [F,Y,X].
  

• lista_de_tres(L) se verifica si L es una lista de 3 elementos. Sus definiciones son

  % 1ª definición
  lista_de_tres(L) :- length(L, N), N = 3.
  
  % 2ª definición
  lista_de_tres(L) :- length(L,3).
  
  % 3ª definición
  lista_de_tres([_,_,_]).
  

• inversa(+L1,-L2), reverse(L1,L2), se verifica si L2 es la lista inversa de L1. Por ejemplo,

  ?- inversa([a,b,c],L).
  L = [c, b, a]
  

• La definición es

  inversa_1([],[]).
  inversa_1([X|L1],L2):-
     inversa_1(L1,L3),
     append(L3,[X],L2).
  

• La definición es

  inversa_2(L1,L2):-
     inversa_2_aux(L1,[],L2).
  
  inversa_2_aux([],L,L).
  inversa_2_aux([X|L1],L3,L2):-
     inversa_2_aux(L1,[X|L3],L2).
  

• La comparación es

  ?- numlist(1,4000,_L1), time(inversa_1(_L1,_)).
  % 8,006,000 inferences, 0.428 CPU in 0.428 seconds (100% CPU, 18686454 Lips)
  true.
  
  ?- numlist(1,4000,_L1), time(inversa_2(_L1,_)).
  % 4,001 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 5305472 Lips)
  true.
  

• La sucesión de Fibonacci es 1, 1, 2, 3, 5, 8, ... y está definida por
  • f(1) = 1
  • f(2) = 1
  • f(n) = f(n-1)+f(n-2), si n > 2

• fibonacci(N,X) se verifica si X es el N-ésimo término de la sucesión de Fibonacci. Por ejemplo,

  ?- fibonacci_1(6,X).
  X = 8
  

• La definición es

  fibonacci_1(1,1).
  fibonacci_1(2,1).
  fibonacci_1(N,F) :-
     N > 2,
     N1 is N-1,
     fibonacci_1(N1,F1),
     N2 is N-2,
     fibonacci_1(N2,F2),
     F is F1 + F2.
  

• La definición es

  :- dynamic fibonacci_2/2.
  
  fibonacci_2(1,1).
  fibonacci_2(2,1).
  fibonacci_2(N,F) :-
     N > 2,
     N1 is N-1,
     fibonacci_2(N1,F1),
     N2 is N-2,
     fibonacci_2(N2,F2),
     F is F1 + F2,
     asserta(fibonacci_2(N,F)).
  

• La definición es

  fibonacci_3(N,F) :-
     fibonacci_3_aux(N,_,F).
  
  fibonacci_3_aux(0,_,0).
  fibonacci_3_aux(1,0,1).
  fibonacci_3_aux(N,F1,F) :-
     N > 1,
     N1 is N-1,
     fibonacci_3_aux(N1,F2,F1),
     F is F1 + F2.
  

• La comparación es

  ?- time(fibonacci_1(30,N)).
  % 3,328,155 inferences, 1.025 CPU in 1.026 seconds (100% CPU, 3245858 Lips)
  N = 832040
  ?- time(fibonacci_2(30,N)).
  % 49 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 833532 Lips)
  N = 832040
  ?- time(fibonacci_3(30,N)).
  % 87 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 1649696 Lips)
  N = 832040
  

• descompone(+E,-N1,-N2) se verifica si N1 y N2 son dos enteros no negativos tales que N1+N2=E. Por ejemplo,

  ?- descompone_1(4,X,Y).
  X = 0,
  Y = 4 ;
  X = 1,
  Y = 3 ;
  X = Y, Y = 2 ;
  X = 3,
  Y = 1 ;
  X = 4,
  Y = 0 ;
  false.
  

• La definición (que se encuentra en descompone.pl) es

  descompone_1(E, N1, N2) :-
     between(0, E, N1),
     between(0, E, N2),
     E =:= N1 + N2.
  

• La definición (que se encuentra en descompone.pl) es

  descompone_2(E, N1, N2) :-
     between(0, E, N1),
     N2 is E - N1.
  

• La comparación es

  ?- time(setof(_N1+_N2,descompone_1(1000,_N1,_N2),_L)).
  % 2,006,017 inferences, 0.169 CPU in 0.169 seconds (100% CPU, 11848576 Lips)
  true.
  
  ?- time(setof(_N1+_N2,descompone_2(1000,_N1,_N2),_L)).
  % 3,016 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 2107629 Lips)
  true.
  

Ejercicio 1. 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]

1ª solución

lista_mayor_1(L1,L2) :-
   member(L2,L1),
   length(L2,N2),
   \+ (member(L,L1), length(L,N), N2 < N).

2ª solución

lista_mayor_2(L1,L2) :-
   máxima_longitud(L1,N),
   length(L2,N),
   member(L2,L1).

% máxima_longitud(+L,-N) se verifica si N es la máxima longitud de la
% lista L. Por ejemplo,
%    ?- máxima_longitud([[a],[a,b,c],[b,a]],N).
%    N = 3
máxima_longitud([L],N) :-
   length(L,N).
máxima_longitud([L|R],N) :-
   length(L,N1),
   máxima_longitud(R,N2),
   N is max(N1,N2).

3ª solución

lista_mayor_3([X|L1],L2):-
   length(X,N), !,
   lista_mayor_3_aux(L1,N-[X],L),
   member(L2,L).

lista_mayor_3_aux([],_-L,L).
lista_mayor_3_aux([Y|L1],N-Ac,L) :-
   length(Y,M),
   ( M < N ->
     lista_mayor_3_aux(L1,N-Ac,L)
   ; M = N ->
     lista_mayor_3_aux(L1,N-[Y|Ac],L)
   ; % M > N ->
     lista_mayor_3_aux(L1,M-[Y],L)
   ).

Comparación de eficiencia

Para la comparación se usará la relación ejemplo_1(+N,-L) se verifica si L es la lista [[1],[1,2],[1,2,3],…,[1,2,…,N]]. Por ejemplo,

?- ejemplo_1(4,L).
L = [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]

Su definición es

ejemplo_1(N,L) :-
   findall(L1,(between(1,N,M),numlist(1,M,L1)),L).

La comparación es

?- ejemplo_1(800,_L), time(lista_mayor_1(_L,_L1)).
% 1,287,998 inferences, 0.298 CPU in 0.298 seconds (100% CPU, 4327972 Lips)
true.

?- ejemplo_1(800,_L), time(lista_mayor_2(_L,_L1)).
% 4,002 inferences, 0.007 CPU in 0.007 seconds (100% CPU, 541456 Lips)
true

?- ejemplo_1(800,_L), time(lista_mayor_3(_L,_L1)).
% 4,000 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 3062536 Lips)
true.

Ejercicio 2.1. Definir, usando un acumulador, la relación factorial(+X,-Y) que se verifica si Y es el factorial de X, Por ejemplo,

?- factorial(3,X).
X = 6

Solución

factorial(X,Y) :-
   factorial_aux(X,1,Y).

factorial_aux(0,Y,Y).
factorial_aux(X,A,Y) :-
   X > 0,
   A1 is X*A,
   X1 is X-1,
   factorial_aux(X1,A1,Y).

Ejercicio 2.2. Definir, usando un acumulador, la relación longitud(L,N) que se verifica si N es la longitud de la lista L. Por ejemplo,

?- longitud([a,b,a],X).
X = 3.

Solución

longitud(L,N) :-
   longitud_aux(L,0,N).

longitud_aux([],N,N).
longitud_aux([_|L],A,N) :-
   A1 is A+1,
   longitud_aux(L,A1,N).

Ejercicio 3. 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(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(3,a,c,b,L).
L = [a-c,a-b,c-b,a-c,b-a,b-c,a-c]
?- hanoi(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.

1ª solución (sin memoria)

hanoi_1(1,A,B,_C,[A-B]).
hanoi_1(N,A,B,C,L) :-
   N > 1,
   N1 is N-1,
   hanoi_1(N1,A,C,B,L1),
   hanoi_1(N1,C,B,A,L2),
   append(L1,[A-B|L2],L).

2ª solución (con memoria)

:- dynamic hanoi_2/5.

hanoi_2(1,A,B,_C,[A-B]).
hanoi_2(N,A,B,C,L) :-
   N > 1,
   N1 is N-1,
   lema(hanoi_2(N1,A,C,B,L1)),
   hanoi_2(N1,C,B,A,L2),
   append(L1,[A-B|L2],L).

lema(P) :-
   P,
   asserta((P :- !)).

Comparación de eficiencia

La comparación es

?- time(hanoi_1(20,a,b,c,_L)).
% 11,534,332 inferences, 2.083 CPU in 2.083 seconds (100% CPU, 5537864 Lips)
true

?- time(hanoi_2(20,a,b,c,_L)).
% 1,966,421 inferences, 0.387 CPU in 0.387 seconds (100% CPU, 5086393 Lips)

Ejercicio 4. 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.

1ª solución

bandera_tricolor_1(L1,L2) :-
   permutation(L1,L2),
   rojo_amarillo_morado(L2).

rojo_amarillo_morado(L) :-
   append(Rojo,Amarillo_y_morado,L),
   lista(rojo,Rojo),
   append(Amarillo,Morado,Amarillo_y_morado),
   lista(amarillo,Amarillo),
   lista(morado,Morado).

lista(_,[]).
lista(C,[X|L]) :-
   apply(C,[X]),
   lista(C,L).

2ª solución (con separación mediante bagof)

bandera_tricolor_2(L1,L2) :-
   bagof(X,(member(X,L1),rojo(X)),Rojos),
   bagof(X,(member(X,L1),amarillo(X)),Amarillos),
   bagof(X,(member(X,L1),morado(X)),Morados),
   append(Amarillos,Morados,AmarillosMorados),
   append(Rojos,AmarillosMorados,L2).

3ª solución (mediante selección y negación)

bandera_tricolor_3(L1,L2) :-
   bandera_tricolor_3_aux(L1,[],L2).

bandera_tricolor_3_aux(L1,L2,L3) :-
   select(X,L1,RL1), morado(X),
   bandera_tricolor_3_aux(RL1,[X|L2],L3).
bandera_tricolor_3_aux(L1,L2,L3) :-
   not((select(X,L1,_),morado(X))),
   select(Y,L1,RL1), amarillo(Y),
   bandera_tricolor_3_aux(RL1,[Y|L2],L3).
bandera_tricolor_3_aux(L1,L2,L3) :-
   not((select(X,L1,_), morado(X))),
   not((select(Y,L1,_), amarillo(Y))),
   append(L1,L2,L3).

4ª solución (mediante selección y corte)

bandera_tricolor_4(L1,L2) :-
   bandera_tricolor_4_aux(L1,[],L2).

bandera_tricolor_4_aux(L1,L2,L3) :-
   select(X,L1,RL1), morado(X), !,
   bandera_tricolor_4_aux(RL1,[X|L2],L3).
bandera_tricolor_4_aux(L1,L2,L3) :-
   % not((select(X,L1,_), morado(X))),
   select(Y,L1,RL1), amarillo(Y), !,
   bandera_tricolor_4_aux(RL1,[Y|L2],L3).
bandera_tricolor_4_aux(L1,L2,L3) :-
   % not((select(X,L1,_), morado(X))),
   % not((select(Y,L1,_), amarillo(Y))),
   append(L1,L2,L3).

5ª Solución (mediante separación)

bandera_tricolor_5(L1,L2) :-
   separa(L1,R,A,M),
   une(R,A,M,L2).

separa([],[],[],[]).
separa([X|L],[X|R],A,M) :-
   rojo(X), !,
   separa(L,R,A,M).
separa([X|L],R,[X|A],M) :-
   amarillo(X), !,
   separa(L,R,A,M).
separa([X|L],R,A,[X|M]) :-
   % morado(X),
   separa(L,R,A,M).

une(R,A,M,L) :-
   append(A,M,AM),
   append(R,AM,L).

6ª solución

bandera_tricolor_6(L1,L2) :-
   aux_1(L1,L2,X,X,Y,Y,[]).

aux_1([],R,R,B,B,A,A).
aux_1([X|Resto],R0,R,B0,B,A0,A) :-
   color(X,Color),
   aux_2(Color,R0,R,B0,B,A0,A,X,Resto).

aux_2(rojo,[X|R1],R,B0,B,A0,A,X,Resto) :-
   aux_1(Resto,R1,R,B0,B,A0,A).
aux_2(amarillo,R0,R,[X|B1],B,A0,A,X,Resto) :-
   aux_1(Resto,R0,R,B1,B,A0,A).
aux_2(morado,R0,R,B0,B,[X|A1],A,X,Resto) :-
   aux_1(Resto,R0,R,B0,B,A1,A).

color(X,Color) :-
   member(Color,[morado,rojo,amarillo]),
   Atom =.. [Color,X],
   Atom.

7ª solución (con include)

bandera_tricolor_7(L1,L2) :-
   include(rojo,L1,Rojos),
   include(amarillo,L1,Amarillos),
   include(morado,L1,Morados),
   append(Amarillos,Morados,AmarillosMorados),
   append(Rojos,AmarillosMorados,L2).

Comparación de eficiencia

La comparación es

?- time(bandera_tricolor_1([m,a,r,m,a,r,m,a,r],L)).
% 16,262,993 inferences, 1.442 CPU in 1.442 seconds (100% CPU, 11281493 Lips)
L = [r, r, r, a, a, a, m, m, m]

?- time(bandera_tricolor_2([m,a,r,m,a,r,m,a,r],L)).
% 110 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 1054397 Lips)
L = [r, r, r, a, a, a, m, m, m].

?- time(bandera_tricolor_3([m,a,r,m,a,r,m,a,r],L)).
% 159 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1468144 Lips)
L = [r, r, r, a, a, a, m, m, m]

?- time(bandera_tricolor_4([m,a,r,m,a,r,m,a,r],L)).
% 94 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 1563228 Lips)
L = [r, r, r, a, a, a, m, m, m].

?- time(bandera_tricolor_5([m,a,r,m,a,r,m,a,r],L)).
% 34 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 603875 Lips)
L = [r, r, r, a, a, a, m, m, m].

?- time(bandera_tricolor_6([m,a,r,m,a,r,m,a,r],L)).
% 90 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 1261069 Lips)
L = [r, r, r, a, a, a, m, m, m]

?- time(bandera_tricolor_7([m,a,r,m,a,r,m,a,r],L)).
% 86 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 847357 Lips)
L = [r, r, r, a, a, a, m, m, m].

Ejercicio 5. 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 sucesión 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]

Solución

lanford(L):-
   length(L,27),
   sublista([1,_,1,_,1],L),
   sublista([2,_,_,2,_,_,2],L),
   sublista([3,_,_,_,3,_,_,_,3],L),
   sublista([4,_,_,_,_,4,_,_,_,_,4],L),
   sublista([5,_,_,_,_,_,5,_,_,_,_,_,5],L),
   sublista([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6],L),
   sublista([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7],L),
   sublista([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8],L),
   sublista([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9],L).

sublista(L1,L2):-
   append(_,L3,L2),
   append(L1,_,L3).

Ejercicio 7.1. En cierta ocasión, el matemático Ramanujan estaba en un hospital en Inglaterra y su amigo Hardy fue a visitarlo. Hardy comentó que había llegado al hospital en un taxi de matrícula N y esperaba que éste no fuese un mal presagio, ya que N era un número poco interesante. Ramanujan no estuvo de acuerdo ya que inmediatamente dijo que N tiene una propiedad muy especial: N es el menor entero positivo que puede descomponerse de dos maneras distintas como suma de dos cubos.

El objetivo de este ejercicio es averiguar la matrícula del taxi que llevó a Hardy a visitar a Ramanujan.

Definir la relación es_cubo(+N) que se verifique si N es el cubo de un entero. Por ejemplo,

?- es_cubo_1(1000).
true.
?- es_cubo_1(1001).
false.

1ª solución

es_cubo_1(N) :-  
   between(1,N,X),
   N is X*X*X.    

2ª solución

es_cubo_2(N) :-
   Cota is round(N^(1/3)),   
   between(1,Cota,X),        
   N is X*X*X.               

3ª solución

es_cubo_3(N) :-
   N =:= round(N ** (1/3)) ** 3.

Comparación de eficiencia:

?- time(es_cubo_1(1000001)).
% 2,000,005 inferences, 0.153 CPU in 0.153 seconds (100% CPU, 13041583 Lips)
false.

?- time(es_cubo_2(1000001)).
% 202 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 1422045 Lips)
false.

?- time(es_cubo_3(1000001)).
% 2 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 51219 Lips)
false.

En lo que sigue adoptaremos la tercera como definición de es_cubo.

es_cubo(N) :-
   es_cubo_3(N).

Ejercicio 7.2. Definir la relación descompone(+N,-X,-Y) que se verifique si X e Y son dos cubos cuya suma es N y, además, X es menor o igual que Y. Por ejemplo,

?- descompone(1008,X,Y).
X = 8
Y = 1000 ;
false.

1ª solución

descompone_1(N,X,Y) :- 
    between(1,N,X),         
    between(1,N,Y),         
    es_cubo(X),            
    es_cubo(Y),            
    X =< Y,            
    N is X+Y.          

2ª solución

descompone_2(N,X,Y) :- 
    between(1,N,X),    
    es_cubo(X),        
    Y is N - X,        
    X =< Y,            
    es_cubo(Y).        

3ª solución

descompone_3(N,X,Y) :-  
    Cota is round((N/2)^(1/3)), 
    between(1,Cota,M),          
    X is M*M*M,             
    Y is N-X,          
    X =< Y,            
    es_cubo(Y).            

Comparación de eficiencia

?- time(descompone_1(1707,X,Y)).
% 11,713,622 inferences, 1.061 CPU in 1.061 seconds (100% CPU, 11036044 Lips)
false.

?- time(descompone_2(1707,X,Y)).
% 6,878 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 6876583 Lips)
false.

?- time(descompone_3(1707,X,Y)).
% 65 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 907479 Lips)
false.

En lo que sigue adoptaremos la tercera como definición de descompone.

descompone(N,X,Y) :-
   descompone_3(N,X,Y).

Ejercicio 7.3. Definir la relación ramanujan(+N) que se verifique si N puede descomponerse en suma de dos cubos exactamente de dos maneras distintas.

Solución

ramanujan(N) :-
    setof(par(X,Y),descompone(N,X,Y),[_,_]).

Ejercicio 7.4. Definir la relación hardy(-N) que se verifique si N es el menor entero positivo que satisface el predicado ramanujan anterior. ¿Cuál es la la matrícula del taxi que llevó a Hardy a visitar a Ramanujan?

Solución

hardy(N) :-         
    hardy_aux(N,1). 
hardy_aux(N,N) :-   
    ramanujan(N),   
    !.              
hardy_aux(N,M) :-   
    M1 is M+1,     
    hardy_aux(N,M1).

La matrícula del taxi que llevó a Hardy a visitar a Ramanujan se calcula mediante la siguiente consulta

?- hardy(N).
N = 1729

Por tanto, la matrícula del taxi es 1729.

*Ejercicio 8. Definir la relación subconjunto_suma(+L1,+N,?L2) que se verifique si L2 es un subconjunto de L1 tal que la suma de los elementos de L2 es N. Por ejemplo,

?- subconjunto_suma([10,7,3,4,2,1],7,L).
L = [7] ;
L = [3,4] ;
L = [4,2,1] ;
false.

?- subconjunto_suma([1,2,3],0,L).
L = [].

1ª solución

subconjunto_suma_1(L1,N,L2) :-
   subconjunto(L1,L2),
   sumlist(L2,N).

• subconjunto(+L1,?L2) se verifica si L2 es un subconjunto de L1. Por ejemplo,

  ?- subconjunto([a,b,c],L).
  L = [a,b,c] ;
  L = [a,b] ;
  L = [a,c] ;
  L = [a] ;
  L = [b,c] ;
  L = [b] ;
  L = [c] ;
  L = [].
  

  Su definición es

  subconjunto([],[]).
  subconjunto([X|L1],[X|L2]) :-
     subconjunto(L1,L2).
  subconjunto([_|L1],L2) :-
     subconjunto(L1,L2).
  

2ª solución

subconjunto_suma_2([],0,[]).
subconjunto_suma_2([X|L1],N,[X|L2]) :-
   N >= X,
   N1 is N-X,
   subconjunto_suma_2(L1,N1,L2).
subconjunto_suma_2([_|L1],N,L2) :-
   subconjunto_suma_2(L1,N,L2).

3ª solución

:- dynamic subconjuntos_suma_calculados_3/3.

subconjunto_suma_3(L1,N,L2) :-
   subconjuntos_suma_calculados_3(L1,N,S), !,
   member(L2,S).
subconjunto_suma_3(L1,N,L2) :-
   findall(L,subconjunto_suma_3_aux(L1,N,L),S),
   asserta(subconjuntos_suma_calculados_3(L1,N,S)),
   member(L2,S).

subconjunto_suma_3_aux([],0,[]).
subconjunto_suma_3_aux([X|L1],N,[X|L2]) :-
   N >= X,
   N1 is N-X,
   subconjunto_suma_3(L1,N1,L2).
subconjunto_suma_3_aux([_|L1],N,L2) :-
   subconjunto_suma_3(L1,N,L2).

4ª solución

:- dynamic subconjuntos_suma_calculados_4/3.

subconjunto_suma_4(L1,N,L2) :-
   subconjuntos_suma_calculados_4(N,L1,S), !,
   member(L2,S).
subconjunto_suma_4(L1,N,L2) :-
   findall(L,subconjunto_suma_4_aux(L1,N,L),S),
   asserta(subconjuntos_suma_calculados_4(N,L1,S)),
   member(L2,S).

subconjunto_suma_4_aux([],0,[]).
subconjunto_suma_4_aux([X|L1],N,[X|L2]) :-
   N >= X,
   N1 is N-X,
   subconjunto_suma_4(L1,N1,L2).
subconjunto_suma_4_aux([_|L1],N,L2) :-
   subconjunto_suma_4(L1,N,L2).

Comparación de eficiencia

?- numlist(1,20,_L1), time(findall(L,subconjunto_suma_1(_L1,10,L),_S)).
% 26,214,419 inferences, 1.553 CPU in 1.553 seconds (100% CPU, 16884175 Lips)
true.

?- numlist(1,20,_L1), time(findall(L,subconjunto_suma_2(_L1,10,L),_S)).
% 1,378 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 2496051 Lips)
true.

?- numlist(1,20,_L1), time(findall(L,subconjunto_suma_3(_L1,10,L),_S)).
% 3,599 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1118906 Lips)
true.

?- numlist(1,20,_L1), time(findall(L,subconjunto_suma_4(_L1,10,L),_S)).
% 3,497 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 1416180 Lips)
true.

?- numlist(1,140,_L1), time(findall(L,subconjunto_suma_2(_L1,70,L),_S)).
% 70,315,223 inferences, 4.936 CPU in 4.936 seconds (100% CPU, 14244753 Lips)
true.

?- numlist(1,140,_L1), time(findall(L,subconjunto_suma_3(_L1,70,L),_S)).
% 607,584 inferences, 0.201 CPU in 0.201 seconds (100% CPU, 3022065 Lips)
true.

?- numlist(1,140,_L1), time(findall(L,subconjunto_suma_4(_L1,70,L),_S)).
% 607,584 inferences, 0.171 CPU in 0.171 seconds (100% CPU, 3552533 Lips)
true.

Se observa que la más eficiente es la cuarta definición.