% CS/ECE348 - Summer 2001
% HW4 - Logic Programming in Prolog
% Harlan Harris - KEY


% utility predicates...
append([],L,L).
append([X|Y],L,[X|Z]) :- append(Y,L,Z).

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

reload :- ['4-sol.pl'].

% 1. Reverse

reverse([], []).
reverse([Head|Tail], RList) :- reverse(Tail, RTail), 
			       addtoend(RTail, Head, RList).

% from the book...
addtoend([], X, [X]).
addtoend([Y|L], X, [Y|M]) :- addtoend(L,X,M).

% 2. Substitute

substitute(_, _, [], []).
substitute(X, Y, [X|T], [Y|T1]) :- substitute(X, Y, T, T1).
substitute(X, Y, [Z|T], [Z|T1]) :- substitute(X, Y, T, T1).

% 3. Insert (BST)

% case 1 - T1 is empty
insert(N, empty, node(N, empty, empty)).
% case 2 - N is smaller than the root, and left is empty
insert(N, node(Root, empty, Right), node(Root, node(N, empty, empty), Right)) 
	:- N < Root.
% case 3 - N is smaller than the root, but left is a tree
insert(N, node(Root, Left, Right), node(Root, NewLeft, Right)) :- N < Root,
	insert(N, Left, NewLeft).
% case 4 - N is greater/equal the root, and right is empty
insert(N, node(Root, Left, empty), node(Root, Left, node(N, empty, empty))) 
	:- N >= Root.
% case 5 - N is greater/equal the root, and right is a tree
insert(N, node(Root, Left, Right), node(Root, Left, NewRight)) :- N >= Root,
	insert(N, Right, NewRight).

% 4. Inorder 

inorder(node(X,empty,empty), [X]) :- !.
inorder(node(X,Left,empty), L) :- inorder(Left, LL), addtoend(LL, X, L), !.
inorder(node(X,empty,Right), [X|LR]) :- inorder(Right, LR), !.
inorder(node(X,Left,Right), L) :- inorder(Left, LL), inorder(Right, LR),
	addtoend(LL, X, LLX), append(LLX, LR, L), !.

% 5. Path

edge(champaign, urbana).
edge(chicago, champaign).
edge(buffalo, newyork).
edge(newyork, atlanta).
edge(pittsburgh, buffalo).
edge(pittsburgh, champaign).
edge(chicago, atlanta).

canget(X,Y) :- edge(X,Y).
canget(X,Y) :- edge(Y,X).

path(X,Y,L) :- path2(X,Y,L,[]).

path2(Z,Z,[Z],_).
% GNU Prolog: not = \+
% path2(X,Y,[X|L],Been) :- canget(X,Z), not(member(Z,Been)), 
%	path2(Z,Y,L,[X|Been]).
path2(X,Y,[X|L],Been) :- canget(X,Z), \+(member(Z,Been)), 
	path2(Z,Y,L,[X|Been]).

% 6. Shortest Path

% this is cheating, a bit. The "correct" way is to implement a breadth-first-
%  search, but that's a pain in Prolog. So instead, I'll get all possible
%  answers, and find the shortest one.

shortpath(X,Y,Shortest) :- bagof(L,path(X,Y,L),Possible),
	shortest(Possible,Shortest).

% the first element of a list is shortest if it is the only element, or if
% it is shorter than the shortest list in the rest of the list

shortest([X],X).
shortest([X|Rest],X) :- length(X,XL), shortest(Rest, R), length(R,RL), XL<RL, !.
shortest([X|Rest],R) :- shortest(Rest,R).