% -----------------------------------------------
%                    Exercice 5
%           Florian Lepot & Maxime Fabre
% -----------------------------------------------

% Question 1
% -------------------------

arc(bachant, aulnoye).
arc(bachant, friche).
arc(bachant, croix).
arc(bachant, denain).
arc(eclaibes, aulnoye).
arc(eclaibes, bachant).
arc(eclaibes, friche).
arc(friche, gommegnies).
arc(croix, denain).
arc(denain, gommegnies).



% Question 2
% -------------------------

% Titre : Calcul la taille d''une liste
% Prédicat : size/2
% Usage : size(?Liste, ?Taille) | Taille contiendra la taille de Liste

size([], 0).

size([_|T], N):-
            size(T, M),
            N is M + 1. % A chaque récursion, on incrémente la taille de la liste


% Titre : Cherche si un chemin existe entre 2 points, et si oui la liste des villes entre les 2.
% Prédicat : chemin/3
% Usage : chemin(?Depart, ?Arrivee, ?Liste) | Liste contiendra la liste des villes entre Depart et Arrivee

chemin(B, B, T) :-
                T = [B].

chemin(A, B, T) :-
                arc(A, C),
                chemin(C, B, P),
                T = [A|P].


% Question 3
% -------------------------

arc(bachant, aulnoye, 8).
arc(bachant, friche, 4).
arc(bachant, croix, 3).
arc(bachant, denain, 6).
arc(eclaibes, aulnoye, 4).
arc(eclaibes, bachant, 7).
arc(eclaibes, friche, 5).
arc(friche, gommegnies, 6).
arc(croix, denain, 7).
arc(denain, gommegnies, 5).



% Question 4
% -------------------------

% Titre : Cherche si un chemin existe entre 2 points, et si oui la liste des villes entre les 2 ainsi que le cout du déplacement.
% Prédicat : chemin/4
% Usage : chemin(?Depart, ?Arrivee, ?Liste, ?Cout) | Liste contiendra la liste des villes entre Depart et Arrivee, Cout contiendra le cout total du déplacement

chemin(B, B, T, P) :-
                    T = [B],
                    P is 0.

chemin(A, B, [A|R], P) :-
                        arc(A, C, PAC),
                        chemin(C, B, R, PCB),
                        P is PAC + PCB.



% Question 5
% -------------------------

% chemin(bachant, gommegnies, T, X), member(denain, T). % On ne prend que les chemins contenant denain dans la liste des villes intermédiaires
% chemin(eclaibes, B, T, X), X >= 11. % On ne prend que les chemins dont le cout est supérieur ou égal à 11



% Question 6
% -------------------------

voisin(X, Y) :- arc(X, Y).
voisin(X, Y) :- arc(Y, X).



% Question 7
% -------------------------

% On l''appelle cheminl car chemin/4 est déjà défini et cela crée un conflit.
% Titre : Cherche si un chemin existe entre 2 points, et si oui la liste des villes entre les 2 ainsi que la liste des villes par lesquelles on est déjà passé
% Prédicat : cheminl/4
% Usage : cheminl(?Depart, ?Arrivee, ?Trace, ?Liste)

cheminl(B, B, _, T) :-
                    T = [B].

cheminl(A, B, Trace, [A|Route]) :-
                            voisin(A, C),
                            Histo = [A|Trace],
                            not(member(C, Histo)),
                            cheminl(C, B, Histo, Route).



% Question 8
% -------------------------

% cheminl(aulnoye, croix, T, L).



% Question 9
% -------------------------

voisin(X, Y, P) :- arc(X, Y, P).
voisin(X, Y, P) :- arc(Y, X, P).


% Nom : chemin (Le nom chemin posait problème, )
% Titre : Cherche si un chemin existe entre 2 points, et si oui la liste des villes entre les 2, la liste des villes par lesquelles on est déjà passé ainsi que le cout du déplacement
% Prédicat : chemin/5
% Usage : chemin(?Depart, ?Arrivee, ?Trace, ?Liste, ?Cout)

chemin(B, B, _, T, P) :-
                        T = [B],
                        P is 0.

chemin(A, B, Trace, [A|Route], P) :-
                                voisin(A, C, PAC),
                                Histo = [A|Trace],
                                not(member(C, Histo)),
                                chemin(C, B, Histo, Route, PCB),
                                P is PAC + PCB.



% Question 10
% -------------------------

% chemin(aulnoye, gommegnies, T, L, P), P < 20.