/* SYS$USER2:[PROLOG.PRO]MONKEY.DAT;3 */


/* This is the "monkey and bananas" problem
   using backward-chaining depth-first search of a graph.

   The monkey and bananas problem is as follows:
      A hungry monkey finds himself in a room in which
      a bunch of bananas is hanging from the ceiling.
      The monkey, unfortunately, cannot reach the
      bananas.  However, in the room there is a chair
      and a stick.  The ceiling is just the right
      height so that the monkey, standing on the chair,
      can knock the bananas down with the stick.  What
      is a sequence of actions which will permit the
      monkey to acquire lunch?

*/

?-op(100,xfy,':').  /* define : as a left-associative operator */

/* The major predicate is

   solve(Current_state, Goal_state, Traversed_path, Solution_path).

   where Traversed_path is a list of moves made so far.
*/


solve(Start, Start, Path, Path).  /* If the current state is the
                 start state, then output the path to the 4th argument */

solve(Current, Start, Path, Solution) :-  /*searching backward
                                            to the start state */
      edge(Step, Previous, Current),

      not(marked(node(Previous))),  /* Graph search requires
                      checking whether we've searched this node before */
	/* Backward search: add step to front*/
      solve(Previous, Start, Step:Path, Solution). 


/* States are represented as a vector
   [Monkey-position, Monkey-on-chair?, Chair-position,
    Monkey-has-stick?, Stick-position, Bananas-knocked-down? ]
*/


edge(go_to(Loc), [Curloc,no,C,D,E,no], [Loc,no,C,D,E,no]) :- pos(Curloc).

edge(push_chair(Loc), [A,no,A,D,E,no], [Loc,no,Loc,D,E,no]) :- pos(A),
    A=chair_location, D=no . /*can't push chair if holding stick */

edge(climb_chair, [A,no,A,D,E,no], [A,yes,A,D,E,no]).

edge(get_stick, [A,no,C,no,A,no], [A,no,C,yes,A,no]).

edge(move_stick(Loc), [A,no,C,yes,A,no], [Loc,no,C,yes,Loc,no])
         :- pos(A), A=stick_location.

edge(knock_down,[A,yes,A,yes,A,no], [A,yes,A,yes,A,yes])
         :-    A=banana_location.

pos(monkey_location).
pos(banana_location).
pos(stick_location).
pos(chair_location).

/*
Check whether a node was already searched.  The rule

    marked(X) :- asserta((marked(X):- !)), fail.

causes a node to be marked if it was not marked before, and fails.

The next time it checks this node, it will succeed since that node
had been asserted to be marked.  Reset_marked permits the
depth-first search to be done several times.

*/

reset_marked :- retractall(marked(_)),
      asserta( (marked(X) :- asserta((marked(X):- !)), fail) ).

monkey_bananas_problem(X,Y,Z) :- reset_marked, solve(X,Y,eatBanana,Z).


run(Answer) :- monkey_bananas_problem(
               [ X, Y, Z, W, U, yes ],  /*search backward from goal*/
               [monkey_location, no, chair_location, no, stick_location, no], /*to start*/
               Answer).
not(X) :- \+(X).

/* ?- run(X). */