% CS/ECE348 - Summer 2001
% HW4 - Prolog
% Name: Joseph S Kim
% Email: jskim5@uiuc.edu

% type "reload." to reload this file
reload :- ['hw4.pl'].

% 1. Reverse

% The reverse(List1, List2) predicate is a built-in predicate in GNU Prolog.
% Re-implement reverse(), calling it reverse2(), without the use of any
% built-in predicates.
reverse(L1,L2) :- reverse2(L1,L2,[]).

reverse2([],L2,L2) :- !.
reverse2([X|Xs],L2,Int) :- reverse2(Xs,L2,[X|Int]).




% 2. Substitute

% Write a predicate, substitute(Atom1, Atom2, List1, List2). If called with
% Atom1 and Atom2 as constants, List1 as a constant list, and List2 as a
% variable, will bind List2 to a list with all instances of Atom1 in List1
% replaced with List2. For example:

% | ?- substitute(p, q, [h,i,p,p,o], X).
% X = [h,i,q,q,o]
% | ?- substitute(p, Q, [h,i,p,p,o], [h,i,q,q,o]).
% Q = q

substitute(A1,A2,[],[]).	   %base case when L1 & L2 are empty. 

substitute(A1,A2,[A1|L1],[A2|L2]):-substitute(A1,A2,L1,L2).
substitute(A1,A2,[Z|L1],[Z|L2]):- A1\=Z, substitute(A1,A2,L1,L2).




% 3. Insert (BST)

% Implement the insert(Node, Tree1, Tree2) predicate for a Binary Search
% Tree (BST). Each node is defined by the predicate "node(Root, Left, Right)",
% or by the constant "empty". For example:

% | ?- insert(a, empty, T).
% T = node(a, empty, empty)
% | ?- insert(3, node(2,empty,empty), T).
% T = node(2,empty,node(3,empty,empty))
% insert(1.5, node(3,node(1,empty,empty),node(5,empty,empty)), T).
% T = node(3,node(1,empty,node(1.5,empty,empty)),node(5,empty,empty))

% Note that for your predicate to sucessfully work with non-integers (letters,
% for example), you'll need to use the term comparison operators, @<, @>=,
% etc, rather than the numberic comparison operators, <, >=, etc. See the
% gprolog documentation for details.

% You'll need five separate cases, as follows:
% case 1 - T1 is empty
% case 2 - N is smaller than the root, and left is empty
% case 3 - N is smaller than the root, but left is a tree
% case 4 - N is greater/equal the root, and right is empty
% case 5 - N is greater/equal the root, and right is a tree


insert(N, empty, node(N, empty, empty)).  % base case: Tree1 is empty
insert(N, node(N,L,R), node(N,L,R)).

insert(N, node(Y,L,R), node(Y,L1,R)):-
  N < Y,				% node(N) is smaller than the Root(Y)
  insert(N,L,L1).

insert(N, node(Y,L,R),node(Y,L,R1)):-
  N > Y,				% node(N) is greater than the Root(Y)
  insert(N,R,R1).





% 4. Inorder 

% Write a set of rules to do an inorder traversal of the BST structure
% used in the previous problem. The predicate should be defined as
% inorder(Tree, List). For example:

% | ?- inorder(node(3,node(1,empty,node(1.5,empty,empty)),node(5,empty,empty)),
%		I).
% I = [1,1.5,3,5]

% You'll probably need about four rules to define this predicate. You'll want
% to use the append() predicate to keep track of the list. 

inorder(Tree, List) :- inorder(Tree, List, []).
inorder(node(X,L,R), Xs, Zs) :-
	inorder(R, Ys, Zs), inorder(L, Xs, [X|Ys]).
inorder(empty,Xs,Xs).		% base case that tree is empty






% 5. Path

% Define a predicate, path(From, To, Path) which is true if there is a path
% from location From to location To via the locations in Path. The predicate
% should also work to return all possible paths. For example:

% | ?- path(urbana,champaign,P).
% P = [urbana,champaign] ? 
% | ?- path(urbana,chicago,P).
% P = [urbana,champaign,chicago] ? ;
% P = [urbana,champaign,pittsburgh,buffalo,newyork,atlanta,chicago] ? 

% Here are the locations, defined for you. Keep in mind that you can go
% both ways on an edge.
edge(champaign, urbana).
edge(chicago, champaign).
edge(buffalo, newyork).
edge(newyork, atlanta).
edge(pittsburgh, buffalo).
edge(pittsburgh, champaign).
edge(chicago, atlanta).

% You'll need to define several additional small predicates, in addition
% to path(). Watch out for loops!
connected(X,Y) :- edge(X,Y) ; edge(Y,X).

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connected(A,B).
travel(A,B,Visited,Path) :-
       connected(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path). 




% 6. Shortest Path

% Now define a predicate called shortestpath(From, To, Route) which is true
% if Route is the shortest path from From to To. Assume all edges are of
% length 1. 

% There are a couple of different ways to do this. The "best" way is to
% implement a breadth-first-search in Prolog, but that's a pain. Given that
% Prolog does a depth-first-search, what's a related search algorithm that
% finds optimal goals when the costs are of constant length?


shortestpath(Start,Goal,Route) :-    
  shortestpath1([[Start]],Goal,R),reverse(R,Route).

shortestpath1([First| Rest],Goal,First) :- First = [Goal| _].

shortestpath1([[Last| Trail]| Others],Goal,Route) :-
  findall([Z,Last| Trail],
  legalnode(Last,Trail,Z),List),
  append(Others,List,Newroutes),
  shortestpath1(Newroutes,Goal,Route).


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