%%%%%%%%%% Solucion - Ejercicio 1 Final del 29-07-02 %%%%%%%%%%%%%%%%
%%%%%%%%%% Juanjo Conti - Marzo 2005 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Había una vez un gran capitán llamado "El gran Julio Cesar" familiar
% lejano del emperador Julio Cesar. Este capitán viajaba por los mares
% buscando a su bella sirena y evitando a malvados piratas, que querían
% atraparlo antes que este llegara a encontrarla.
%
% Julio Cesar contaba con un mapa de navegación el cual tenia
% información de las diferentes islas por donde debía pasar, las rutas
% donde se encontraban los piratas y la isla donde habitaba la sirena.
%
% El Capitán, debía llegar hasta la sirena, pero para ello tenía que
% encontrar un camino que le permitiera llegar venciendo a los
% piratas. Si en el camino encuentra un barco pirata, puede enfrentarse
% a él siempre que el número de tripulantes en su barco sea mayor que el
% número en el barco pirata.
%
% La cantidad de tripulantes en el barco pirata es conocida y siempre es
% fija, mientras que la cantidad de tripulantes en el barco del Capitán
% se calcula de la siguiente manera:
%
%   * Por cada isla visitada se agrega dos.
%   * Por cada batalla con Piratas se pierde uno.
%
%                      (C) i5
%                           |
%                           |
%   i1---(P)-----i2--------i6-----(P)-------i4----i3 (S)
%    |                      |                |
%    |                      |                |
%    |                      \---------------i7
%    \--------------------------------------/
%
%       (C) Capitán
%       (P) Piratas
%       (S) Sirena
%
% Se le solicita que defina en Prolog los predicados necesarios para
% representar el conocimiento que se tiene sobre las islas, sus
% conexiones, los lugares donde están los piratas, la sirena y el
% capitán. Asuma que la cantidad de piratas que hay en la ruta entre la
% isla i6 y i4 es de 25, y en la ruta que une las islas i1 y i2 es de
% 32.
%
% Defina el predicado
%      julioCesar(Islas,TripulaciónInicial, TripulaciónFinal)
% que encuentre una secuencia de islas por donde deba
% pasar el Capitán para llegar a la isla donde se encuentra la sirena
% sin ser vencidos por los piratas.
%
%    * TripulaciónInicial es el valor inicial de la tripulación del
%      barco del Capitán y se considera que para toda consulta el mismo
%      es ground.
%
%    * TripulaciónFinal: es una variable que debe unificar con un valor
%      entero que representa la cantidad de tripulantes que tiene el
%      barco del Capitán cuando llega a la isla de la Sirena.
%
%    * Islas: es una variable que unifica con una lista conteniendo las
%      islas por donde el Capitán pasa.
%
% Ejemplo:
%
%       ? julioCesar(L, 30, X).
%       L= [i5, i6, i7, i4, i3]
%       X= 36;
%       L=[ i5,i6,i4,i3]
%       X= 35;
%       ...

% DATOS %

isla(i1).
isla(i2).
isla(i3).
isla(i4).
isla(i5).
isla(i6).
isla(i7).

% ruta(extremo1,extremo2,nroPiratas)

ruta(i1,i2,32).
ruta(12,16,0).
ruta(i1,i7,0).
ruta(i5,i6,0).
ruta(i3,i4,0).
ruta(i7,i4,0).
ruta(i6,i4,25).
ruta(i6,i7,0).

% camino(extremo1,extremo2,nroPiratas) 
% los caminos son bidireccionales, el camino 11-12 es
% el mismo que el 12-11.

camino(C1,C2,P):-ruta(C1,C2,P).
camino(C1,C2,P):-ruta(C2,C1,P).

% Ubicación de la Sirena

sirena(i3).

% Ubicación del Campitan

capitan(i5).

% PROGRAMA %

% julioCesar(islas,tripInic,tripFinal)

julioCesar(L,N,X1):-capitan(C),julioAux(L,N,X,C,[]),X1 is X-2.

% julioAux(islas,tripInic,tripFinal,capitan,visitadas)

julioAux([L1,L2],N,X,L1,T):-puedeAvanzar(L1,L2,N,X),sirena(L2).
julioAux([L1|Ls],N,X,L1,T):-isla(L2),not(member(L2,T)),
                            puedeAvanzar(L1,L2,N,X1),
                            append([L2],T,Ti),julioAux(Ls,X1,X,L2,Ti).

% puedeAvanzar(origen,destino,tripInic,tripFinal)

puedeAvanzar(L1,L2,N,X):-camino(L1,L2,0),X is N+2,!.
puedeAvanzar(L1,L2,N,X):-camino(L1,L2,P),P < N,X is N + 1.

% Si hay piratas en el camino, se suma 1 ya que se pierde 1 y 
% se suman 2 en la isla alcanzada.
                                             
% COMENTARIOS %

% Compilado/Interpretado con SWI-Prolog (http://www.swi-prolog.org)
%
% Resultado de la ejecución:
%
% ?- julioCesar(L,30,X).
% L = [15, 16, 12, 11, 17, 14, 13].
% X = 39
%
% L = [15, 16, 14, 13].
% X = 33
%
% L = [15, 16, 17, 14, 13].
% X = 36