% -*- coding:iso-8859-1.unix; -*-
% $Id: ej01.pl,v 1.2 2003/11/18 14:36:44 cballard Exp $
%
% 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;
%	...
%

% Clave para interpretar el significado de los argumentos:
%
% +: el argumento debe estar instanciado.
% -: el argumento debe ser una variable (será instanciado si el predicado tiene éxito).
% ?: el argumento puede estar instanciado o ser una variable.

% Información de las islas:
% isla(?NombreDeLaIsla).
isla(i1).
isla(i2).
isla(i3).
isla(i4).
isla(i5).
isla(i6).
isla(i7).

% Información del estado de las rutas
% ruta(?DesdeIsla, ?HastaIsla, ?CantidadDePiratas).
ruta(i1, i2, 32).
ruta(i1, i7, 0).
ruta(i2, i6, 0).
ruta(i3, i4, 0).
ruta(i4, i6, 25).
ruta(i4, i7, 0).
ruta(i5, i6, 0).
ruta(i6, i7, 0).
%                      (C) I5
%                           |
%                           |
%   I1---(P)-----I2--------I6-----(P)-------I4----I3 (S)
%    |                      |                |
%    |                      |                |
%    |                      \---------------I7
%    \--------------------------------------/

% Islas iniciales del capitan y de la sirena:

% capitan(?NombreDeLaIsla).
capitan(i5).

% sirena(?NombreDeLaIsla).
sirena(i3).



% julioCesar(-Islas, +TripulacionInicial, -TripulacionFinal)
%
julioCesar(Islas, TripulacionInicial, TripulacionFinal) :-
	capitan(Inicio), isla(Inicio),
	sirena(Final),   isla(Final),
	camino(Inicio, Final, [Inicio], IslasInvertidas,
	       TripulacionInicial, Trip),
	reverse(IslasInvertidas, Islas),
	TripulacionFinal is Trip-2. % en la isla de destino no
                                    % se cargan marineros


% camino(+DesdeIsla, +HastaIsla, 
%        +VisitadasHastaAhora, -RecorridoFinal,
%        +TripulacionInicial, -TripulacionFinal)

% Por si la sirena está en la misma isla que el capitán
camino(Isla, Isla, Visitadas, Visitadas, Tripulacion, Tripulacion):-
	isla(Isla), !.

% Por cada isla visitada se agrega dos.
% Por cada batalla con Piratas se pierde uno.

% hay una ruta directa
camino(I1, I2, Visitadas, Islas, Ti, Tf) :-
	isla(I1), isla(I2),
	ruta(I1, I2, Piratas), !, 
	\+(member(I2, Visitadas)),
	(	Piratas =:= 0, NuevaTrip is Ti+2                % no hay batalla
	;
		Piratas > 0, Ti > Piratas, NuevaTrip is Ti-1+2  % hay batalla
        ),
	!, camino(I2, I2, [I2|Visitadas], Islas, NuevaTrip, Tf).

% hay una ruta directa (busca el par ordenado inverso de islas)
camino(I1, I2, Visitadas, Islas, Ti, Tf) :-
	isla(I1), isla(I2),
	ruta(I2, I1, Piratas), !,
	\+(member(I2, Visitadas)),
	(	Piratas =:= 0, NuevaTrip is Ti+2                 % no hay batalla
	;
		Piratas > 0, Ti > Piratas, NuevaTrip is Ti-1+2   % hay batalla
	),
	!, camino(I2, I2, [I2|Visitadas], Islas, NuevaTrip, Tf).

% En las rutas directas hay cuts para impedir que se encuentren
% caminos no directos que en realidad son los rutas directas
% pero con el final que va desde y hacia el propio extremo.

% hay un camino que no es directo
camino(I1, I2, Visitadas, Islas, Ti, Tf) :-
	isla(I1), isla(I2),
	ruta(I1, I3, Piratas), isla(I3),
	\+(member(I3, Visitadas)),
	(	Piratas =:= 0, NuevaTrip is Ti+2                % no hay batalla
	;
		Piratas > 0, Ti > Piratas, NuevaTrip is Ti-1+2  % hay batalla
	),
	camino(I3, I2, [I3|Visitadas], Islas, NuevaTrip, Tf).

% hay un camino que no es directo (busca el par ordenado inverso de islas)
camino(I1, I2, Visitadas, Islas, Ti, Tf) :-
	isla(I1), isla(I2),
	ruta(I3, I1, Piratas), isla(I3),
	\+(member(I3, Visitadas)),
	(	Piratas =:= 0, NuevaTrip is Ti+2                % no hay batalla
	;
		Piratas > 0, Ti > Piratas, NuevaTrip is Ti-1+2  % hay batalla
	),
	camino(I3, I2, [I3|Visitadas], Islas, NuevaTrip, Tf).


% --------------------------------------------------
% Resultado de la ejecución: 
%
% | ?- consult('ej01b.pl').
% | ?- julioCesar(L, 30, X).
%
% L = [i5,i6,i7,i4,i3]
% X = 36 ?
%
% L = [i5,i6,i2,i1,i7,i4,i3]
% X = 39 ?
%
% L = [i5,i6,i4,i3]
% X = 33 ?
%
% no
%

%
% Compilado/Interpretado con gprolog:
%          http://www.gnu.org/software/prolog/
%          http://gnu-prolog.inria.fr
%
% ISO Prolog: http://www.logic-programming.org/prolog_std.html
% Manual: ftp://ftp.inria.fr/INRIA/Projects/contraintes/gprolog/manual.pdf.gz
% Win32: ftp://ftp.inria.fr/INRIA/Projects/contraintes/gprolog/setup-gprolog-1.2.13.exe
% GNU/Linux: ftp://ftp.inria.fr/INRIA/Projects/contraintes/gprolog/gprolog-1.2.13-1.i386.rpm
% Fuentes: ftp://ftp.inria.fr/INRIA/Projects/contraintes/gprolog/gprolog-1.2.13.tar.gz


% Predicados que no forman parte del estándar ISO Prolog:

% member(?term, ?list)
% member(H, [H|_]).
% member(H, [_|T]) :- member(H,T).


% reverse(?list, ?list)
% reverse(L1, L2) :-
%	reverse_aux(L1, [], L2).
%
% reverse_aux([], L, L):- !. % para evitar bucle infinito al llamarla: reverse_aux(-L1,+L2,+L3)
% reverse_aux([H|L1], L2, L3) :-
%        reverse_aux(L1, [H|L2], L3).

% EOF ej01b.pl