/* LOUIS GUZIK */

/*	?- go.	TYPE FOR COMMANDS	*/

/* FACTS */

adj(rennes,nantes,107).
adj(nantes,bordeaux,329).
adj(bordeaux,toulouse,253).
adj(toulouse,limoges,313).
adj(limoges,paris,396).
adj(paris,dijon,313).
adj(dijon,lyon,192).
adj(lyon,avignon,216).
adj(lyon,grenoble,104).
adj(grenoble,avignon,227).
adj(toulouse,montpellier,240).
adj(montpellier,avignon,121).
adj(nantes,limoges,329).
adj(rennes,paris,348).

long(avignon,48).
long(bordeaux,-6).
long(dijon,51).
long(grenoble,57).
long(limoges,12).
long(lyon,48).
long(montpellier,36).
long(paris,23).
long(rennes,-17).
long(toulouse,14).
long(nantes,-16).

adj(X,Y) :- adj(X,Y,Z). /* throw away KMs when not needed */
        
/* DEPTH FIRST SEARCH */

df(Start,Dest,Route) :-
        tell(traces),
	nl, print("Queue trace for depth-first search. DESTINATION IS "),
        print(Dest), nl, nl,
        print("[["), print(Start), print("]]"), nl, nl,
        tell(user),
        df1([[Start]],Dest,R), rev(R,Route).

df1([First|Rest],Dest,First) :- First = [Dest|_].

df1([[Last|Trail]|Others],Dest,Route) :-
        findall([Z,Last|Trail],legalnode(Last,Trail,Z),List),
        append(List,Others,NewRoutes),
        tell(traces),
        print(NewRoutes), nl, nl,
        tell(user),
        df1(NewRoutes,Dest,Route).


/* BEST-FIRST SEARCH */

bestf(Start,Dest,Route) :-
        tell(traces),
        nl, print("Queue trace for best-first search.  DESTINATION IS "),
        print(Dest), nl, nl,
        print("[["), print(Start), print("]]"), nl, nl,
        tell(user),
        bestf1([[Start]],Dest,R), rev(R,Route).

bestf1([First|Rest],Dest,First) :- First = [Dest|_].

bestf1([[Last|Trail]|Others],Dest,Route) :-
        findall([Z,Last|Trail],legalnode(Last,Trail,Z),List),
        append(Others,List,NewRoutes),
        busort(NewRoutes,SRoutes,Dest),
        tell(traces),
        print(SRoutes), nl, nl,
        tell(user),
        bestf1(SRoutes,Dest,Route).


/* SLIGHTLY MODIFIED DYNAMIC PROGRAMMING SEARCH */

dprog(Start,Dest,Route) :-
        tell(traces),
        nl, print("Queue trace for dynamic-prog search. DESTINATION IS "),
        print(Dest), nl, nl,
        print("[["), print(Start), print("]]"), nl, nl,
        tell(user),
        dprog1([[0,Start]],Dest,R), rev(R,Route).

dprog1([First|Rest],Dest,First) :- First = [Num,Dest|_].

dprog1([[Num,Last|Trail]|Others],Dest,Route) :-
        findall([Z,Last|Trail],legalnode(Last,Trail,Z),List),
        sumkilos(List,Num,Klist),
        append(Klist,Others,NewRoutes),
        busort2(NewRoutes,SRoutes),
        tell(traces),
        print(SRoutes), nl, nl,
        tell(user),
        dprog1(SRoutes,Dest,Route).


/* BREATH-FIRST SEARCH */

breathf(Start,Dest,Route) :-
        tell(traces),
        nl, print("Queue trace for breath-first search. DESTINATION IS "),
        print(Dest), nl, nl,
        print("[["), print(Start), print("]]"), nl, nl,
        tell(user),
        breathf1([[Start]],Dest,R), rev(R,Route).

breathf1([First|Rest],Dest,First) :- First = [Dest|_].

breathf1([[Last|Trail]|Others],Dest,Route) :-
        findall([Z,Last|Trail],legalnode(Last,Trail,Z),List),
        append(Others,List,NewRoutes),
        tell(traces),
        print(NewRoutes), nl, nl,
        tell(user),
        breathf1(NewRoutes,Dest,Route).


/* HILL CLIMB SEARCH */

hillc(Start,Dest,Route) :-
        tell(traces),
	nl, print("Queue trace for hill climb search.  DESTINATION IS "),
        print(Dest), nl, nl,
        print("[["), print(Start), print("]]"), nl, nl,
        tell(user),
        hillc1([[Start]],Dest,R), rev(R,Route).

hillc1([First|Rest],Dest,First) :- First = [Dest|_].

hillc1([[Last|Trail]|Others],Dest,Route) :-
        findall([Z,Last|Trail],legalnode(Last,Trail,Z),List),
        busort(List,SRoutes,Dest),
        append(Others,SRoutes,NewRoutes),
        tell(traces),
        print(SRoutes), nl, nl,
        tell(user),
        hillc1(SRoutes,Dest,Route).


/* A-STAR SEARCH */

astar(Start,Dest,Route) :-
        tell(traces),
	nl, print("Queue trace for astar search. DESTINATION IS "),
        print(Dest), nl, nl,
        print("[["), print(Start), print("]]"), nl, nl,
        tell(user),
	longdif(Start,Dest,L),
        astar1([[0,0,Start]],Dest,Route).

/* , rev(Route,R). */

astar1([First|Rest],Dest,First) :- First = [_,_,Dest|_].

astar1([[A,D,Last|Trail]|Others],Dest,Route) :-
        findall([Z,Last|Trail],legalnode(Last,Trail,Z),List),
        sumkilos(List,D,Klist),
	sumastar(Klist,Dest,Alist),
	append(Alist,Others,NewRoutes),
	busort3(NewRoutes,SRoutes),
        tell(traces),
        print(SRoutes), nl, nl,
        tell(user),
        astar1(SRoutes,Dest,Route).

busort3(L,S) :-
	append(X,[A,B|Y],L),
	astarless(B,A),
	append(X,[B,A|Y],M),
	busort3(M,S).

busort3(L,L).

sumastar(Paths,Dest,Alist) :-
	sumastar1(Paths,Dest,[],Alist).

sumastar1([],Dest,Alist,Alist).

sumastar1([[Dist,C1|Rpath]|Others],Dest,Temp,Alist) :-
	asumpath(C1,Dist,Dest,Rpath,Npath),
	append([Npath],Temp,New),
	sumastar1(Others,Dest,New,Alist).

asumpath(Loc,Dist,Dest,Rpath,Npath) :-
	longdif(Loc,Dest,Est),
	A is Dist+Est,
	append([A,Dist,Loc],Rpath,Npath).

astarless([A1|_],[A2|_]) :-
	A1<A2.


/* AUXILIARY CODE */

legalnode(X,Trail,Y) :- (adj(X,Y); adj(Y,X)), not(member(Y,Trail)).

member(X, [X|_]).
member(X, [_|Y]) :- member(X,Y).

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

rev(L1,L2) :- revzap(L1,[],L2).

revzap([X|L],L2,L3) :- revzap(L,[X|L2],L3).
revzap([],L,L).

findall(X,G,_) :- asserta(found(mark)),
		  call(G),
		  asserta(found(X)),
		  fail.

findall(_,_,L) :- collect_found([],M),
		  !,
		  L=M.

collect_found(S,L) :- getnext(X),
		      !,
		      collect_found([X|S],L).

collect_found(L,L).

getnext(X) :- retract(found(X)),
	     !,
	     X \== mark.


busort(L,S,G) :-
        append(X,[A,B|Y],L),
        longless(B,A,G),
        append(X,[B,A|Y],M),
        busort(M,S,G).

busort(L,L,G).

absval(X,Y) :- X<0, Y is X-X-X.
absval(X,Y) :- X>=0, Y is X.

longdif(City1,City2,Z) :- long(City1,X), long(City2,Y),
                          P is X-Y, absval(P,Z).

longless([City1|_],[City2|_],Goal) :- longdif(City1,Goal,N1),
                                      longdif(City2,Goal,N2),
                                      N1<N2.

busort2(L,S) :-
        append(X,[A,B|Y],L),
        kmless(B,A),
        append(X,[B,A|Y],M),
        busort2(M,S).

busort2(L,L).

kmless([Km1|Rest1],[Km2|Rest2]) :- Km1<Km2.

sumkilos(Paths,Num,Numlist) :- sumkilos1(Paths,Num,[],Numlist).

sumkilos1([],Num,Numlist,Numlist).

sumkilos1([[C1,C2|Rpath]|Others],Num,Temp,Numlist) :-
	                		sumforpath(C1,C2,Rpath,Num,NPath),
	        		        append([NPath],Temp,New),
        		        	sumkilos1(Others,Num,New,Numlist).

sumforpath(City1,City2,Rpath,Num,NPath) :-
                                (adj(City1,City2,Km) ; adj(City2,City1,Km)),
                                Sum is Km + Num,
                                append([Sum,City1,City2],Rpath,NPath).

go :-	nl, nl, 
	print( "COMANDS: bestf(start,end,X) df(start,end,X) dprog(start,end,X)"),
	nl,
	print( "         breathf(start,end,X) hillc(start,end,X) astar(start,end,X)"),
	nl, nl,
	print( " OUTPUT IS IN TRACES.PRO" ),
	nl.