%   File   : sticks.pl
%   Author : Tim Smith, 19/10/04
%   Purpose: AIPP Practical 4 optional search component

/* This implementation of the sticks problem uses a list notation to
represent a state in the problem. An uncrossed stick is symbolised by
an 'i' and a crossed stick a 'x'. An example state is [x,x,i,i,x]

You begin the search by either calling: 
go(Search).

 where Search is the name of the type of search you wish to perform
 ('breadth' or 'depth'); or calling

sticks(Start_state,Search).

where Start_state is the state you want the problem to be solved
from. This should mostly be [i,i,i,i,i,i,i,i] (hence why I included
go/1 to make initialising the problem easier).

sticks/2 initiates the search by calling agenda_search/4. This is a
derivative of the general agenda search algorithm provided in the
lectures. Once a solution is returned by agenda_search it is written
to the screen along with Count, the number of nodes expanded during
the search (this will differ between search algorithms), and the depth
of the solution. The solution has to be reversed as it is constructed
in the agenda back-to-front.  */

go(Search):-
	sticks([i,i,i,i,i,i,i,i],Search).

sticks(Initial_state,Search):-
	agenda_search(Search, 0, [[Initial_state]],[Count,Solution]),
	length(Solution,Length),
	Steps is Length-1,
	reverse(Solution,[],Reverse),
	write(Search), write(' first search expands '), write(Count), 
	write(' nodes to find a solution at depth '), write(Steps), nl,
	write_list(Reverse).


/* The search is performed using an agenda to keep track of all nodes
that are yet to be expanded (i.e. the states obtainable from that node
found).

Search = the search algorithm, breadth or depth

Count = a counter used to keep track of how many nodes are expanded
durign the search. This is a good indication of the efficiency of the
search algorithm. Run both searches and see which one is best. Were
you surprised?

The 3rd argument is the agenda. It is constructed as a list of paths
which store the deepest states at the beginning and the initial state
at the very end. We expand a state by choosing the left-most path,
extracting its head state and finding all the states reachable from
it. findall/3 is used for this. It calls applymove/2 which will find
the first move possible and return an updated form of the state.

Once all possible new states are generated from the surrent state the
predicate recurses.

Recursion stops if the head state of the head Path matches the goal
state: [x,x,x,x].

*/

agenda_search(_,Count,[[[x,x,x,x]|Path]|_],[Count,[[x,x,x,x]|Path]]).

agenda_search(Search, Count, [[State|Path]|Rest], Solution):-
	write(State), nl,
	Count1 is Count + 1,
	findall([NewState,State|Path],applymove(State, NewState),Successors),
	update_agenda(Search, Rest, Successors, NewAgenda),
	agenda_search(Search, Count1, NewAgenda, Solution).


/* applymove/2 has three clauses corresponding to the three types if move that can be made: either a stick jumps over two sticks to its right, two sticks to its left, or a crossed stick (direction is irrelevant given this representation). By representing them as seperate clauses findall/3 can be used to continually fail the clause to generate all the possible moves possible from a single state. */

applymove(State, NewState):-
	jump_right2(State, NewState).

applymove(State, NewState):-
	jump_left2(State, NewState).

applymove(State, NewState):-
	jump_x(State, NewState).

/* Once findall/3 has generated a list of all possible new states from the current state we want to add these to our agenda. As described in the lectures there are two ways to do this: either you add the new states to the beginning of the agenda to search depth-first, or you add them to the end of the agenda to search breadth-first. A simple difference creates vastly different search patterns. */ 

update_agenda(breadth, Rest, Successors, NewAgenda):-
	append(Rest, Successors, NewAgenda).

update_agenda(depth, Rest, Successors, NewAgenda):-
	append(Successors, Rest, NewAgenda).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This is where you need to include your code for 
% jump_right2(State,NewState). 

% This predicate should 
% match the condition that your state includes four 'i's 
% in a row and replaces them with two 'i's and a 'x'.











%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Include your code for jump_left2/2 here: 

% This does the reverse of jump_right2: it matches 
% four 'i's in a row and replaces them with an 'x' 
% and two 'i's. I've included reverse/3 for you to use.











%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Include your code for jump_x/2 here: 

% This matches i,x,i and returns x,x 
% (i.e. it jumps two crossed sticks). 
% Direction is not important as the initial 
% pattern and resulting pattern is the same.











%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Utility predicates

/* write_list/1 is a general operator that can be used to print elements of a list in order, one line at a time */

write_list([]).
write_list([H|T]):-
    write(H), nl,
    write_list(T).

append([],Y,Y).
append([H|T],Y,[H|O]):-
    append(T,Y,O).

reverse([],X,X).
reverse([H|T],Y,O):-
    reverse(T,[H|Y],O).