% experimental Post Correspondence system explorer -- Prolog
% examples of problem in /u/faculty/dick/cs505/pg3??.pl
:-consult(append).

change([T,X,Y], [NT,NX,NY]):-pair(L,A,B), 
		append(X,A,NX), append(Y,B,NY),append(T,[L],NT).
:-print('change([T,X,Y],[T1,X1,Y1]) loaded.').

start([[], [], []]).
:- write('start(X) loaded'), nl.

solution([T,X,X]):-print('Solution is ', T),ps(T).

% Printing out solution so it looks good
ps(T):-ps1(T),nl,
	 write('------------------------'), nl,
	ps2(T), nl.
ps1([]):-!.
ps2([]):-!.
ps1([T0]):-pair(T0, X, Y), prin(X),!.
ps1([T0|TS]):-pair(T0,X,Y),prin(X),ps1(TS),!.
ps2([T0]):-pair(T0, X, Y), prin(Y),!.
ps2([T0|TS]):-pair(T0,X,Y),prin(Y),ps2(TS),!.
:- write('solution(X) loaded'), nl.

trim1([T, [X], [X]], [T, [],[]]):-!.
trim1([T, [X|Y], [X|Z]], [T, Y,Z]).
trim(X,Y):-trim1(X,T),!,trim(T,Y).
trim(X,X).
:-print('trim(X,Y) loaded.').

shortcut([T, [],X]):-!.
shortcut([T, X,[]]).
:- write('shortcut(X) loaded'), nl.

search:-prin('Number of steps? '), ratom(N), search(N,X),  write(X), nl.

search(0,X):-start(X),!.
search(N,Z):-N1 is N-1, search(N1,X), change(X,Y), trim(Y,Z),shortcut(Z).
:-print('seach(N,Y) is loaded').
:-nl.
:-nl.
:-print('Try search(N,X),solution(X)? for various N=1,2,3,4...').
:-nl! nl.