From: Kassian
Subject: newby Q: Recursion
Date: 
Message-ID: <81c65b$jb7$1@trumpet.uni-mannheim.de>
Hello
I'm totaly new to lisp, but now I've got to write that classical programm to
solve that Missonaries-and-Cannibals-Problem in school.
Ok, did this, now my teacher said that could be written recusiv, but want
tell me how.
Does any body know a place where i can find some exampls of that
M-C-Problem?
Thanx a lot
Dino

From: Christopher R. Barry
Subject: Re: newby Q: Recursion
Date: 
Message-ID: <874sedjz7m.fsf@2xtreme.net>
"Kassian" <······@rumms.uni-mannheim.de> writes:

> Hello
> I'm totaly new to lisp, but now I've got to write that classical programm to
> solve that Missonaries-and-Cannibals-Problem in school.
> Ok, did this, now my teacher said that could be written recusiv, but want
> tell me how.

Okay, you're saying you've solved the problem iteratively ("did this") 
but don't know to do it recursively? If this is the case, then post 
your working, iterative code. 
 
Many algorithms can be used to solve this problem, and your teacher
probably wants you to use a specific type of algorithm, such as an
uninformed search method like bread-first-search or an
iterative-improvement technique.

> Does any body know a place where i can find some exampls of that
> M-C-Problem?

Sure. This one is the most common:

  --------------------

                  /\
	         |  |
	         |  |   <- boat
  --------------------

      M M M  C C C

 M == missionary
 C == cannibal


Assuming your teacher is happy with breadth-first-search, I'll show you
how to do this 100% iteratively. I'll leave it as an exercise to you to
convert all the LOOPs to recursion. First you'll need queues for
breadth-first-search:

(defun make-queue ()
  (cons nil nil))

(defun enqueue-at-end (queue elements)		; ELEMENTS is a fresh list
  (setf (car queue) (nconc (car queue) elements)
	(cdr queue) (last elements))
  queue)

(defun dequeue-front (queue)
  (pop (car queue)))

(defun queue-contents (queue)
  (car queue))


Next, you'll need a node datatype for breadth-first-search, and to
decide how you are going to represent the state of the environment.
Using a six element list is a simple way. The left three elements
represent the start bank and the right three the end bank. The first and
fourth elements are the missionaries, the second and fifth the
cannibals, and the third and sixth the boat. The initial state would
thus be '(3 3 1 0 0 0).

(defstruct (node (:print-function		; You can ignore this
		   (lambda (node stream depth)
		     (declare (ignore depth))
		     (print-unreadable-object (node stream :type 'node)
		       (format stream "state:~S" (node-state node))))))
  (state nil)					; Six element list
  (parent nil))					; I'll explain....


You now need to be able to determine which moves can be made from any
position. Each move that can be made from a position (a NODE) becomes a
new NODE with the NODE you made the move from becoming its parent.

(defun node-successors (node)
  (loop with node-state = (node-state node)
	for action in '((+1 +1 +1) (+1 0 +1) (0 +1 +1) (+2 0 +1) (0 +2 +1)
			(-1 -1 -1) (-1 0 -1) (0 -1 -1) (-2 0 -1) (0 -2 -1))
	for state = (apply-action-to-state action node-state)
	when state				; If the state is legal...
	  collect (make-node			; Then it's a move.
	            :parent node
	            :state state)))


APPLY-ACTION-TO-STATE returns the result state from applying the action
triplet to the six-element state or NIL if applying the action is
illegal. The action is illegal if the cannibals on one side outnumber
the missionaries on the same side unless there is zero missionaries, if
there isn't exactly one boat on one side and zero boats on the other, or
if any of the values are negative.

(defun apply-action-to-state (action state)
  (let ((new-state (copy-list state))
	(missionaries (first action))
	(cannibals (second action))
	(boat (third action)))
    ;; Now send them over the river
    (decf (first new-state) missionaries)(incf (fourth new-state) missionaries)
    (decf (second new-state) cannibals)  (incf (fifth new-state) cannibals)
    (decf (third new-state) boat)        (incf (sixth new-state) boat)
    ;; Now check if NEW-STATE is legal
    (when (and (or (zerop (first new-state))
		   (>= (first new-state) (second new-state) 0))
	       (or (zerop (fourth new-state))
		   (>= (fourth new-state) (fifth new-state) 0))
	       (typep (third new-state) 'bit)
	       (typep (sixth new-state) 'bit)
	       (/= (third new-state) (sixth new-state)))
      new-state)))


Now you need to know how to test when you've made the move that gets all
the missionaries and cannibals on the end-bank. If the first and second
elements of the six-element state list are zero then there are no
missionaries and cannibals left on the start bank and you've reached the
goal.

(defun goal-state? (state)
  (= (first state) (second state) 0))


Now that all that stuff is out of the way, you can now implement the
search. One problem with using breadth-first-search for this problem is
generating duplicate nodes, since from any position other than the
initial one you can legally move right back to the position you were
just in, which is useless. I've used an EQUAL hash-table to store every
node created so that no path is followed more than once. (The hash-table
is keyed with the node's state.) There aren't that many unique legal
states that can be reached from the initial state of the
cannibals-and-missionaries problem so the number of nodes that will be
stored in the table is not large. (This is rarely the case, however....)

(let ((table-of-nodes (make-hash-table :test #'equal)))
  (defun solve-cannibals (&optional (initial-state '(3 3 1 0 0 0)))
    (loop with node
	  with nodes = (enqueue-at-end (make-queue)
				       (list (make-node :state initial-state)))
	  initially (clrhash table-of-nodes)
	  do (unless (queue-contents nodes)
	       (return-from solve-cannibals 'no-solution))
	     (setf node (dequeue-front nodes))
	     (when (goal-state? (node-state node))
	       (return-from solve-cannibals node))
	     (setf nodes (enqueue-at-end
			   nodes
			   ;; Don't enqueue any duplicate nodes
			   (loop with node-successors = (node-successors node)
				 for node in node-successors
				 for node-state = (node-state node)
				 unless (gethash node-state table-of-nodes)
				   collect node
				 do (setf (gethash node-state table-of-nodes)
					  node)))))))


The search will return a node with the goal-state (0 0 0 3 3 1). If you
keep following the parents of this node you will reach the node with the
initial-state (3 3 1 0 0 0).  [Or whatever initial state was specified.]
The path followed is the solution.

(defun print-node-path (node)
  (loop with path = '()
	for node-on-path = node then (node-parent node-on-path)
	while node-on-path
	do (push node-on-path path)
	finally (dolist (node path)
		  (format t "~&~S~%" (node-state node)))))


You can now do:

  > (print-node-path (solve-cannibals))
  (3 3 1 0 0 0)
  (2 2 0 1 1 1)
  (3 2 1 0 1 0)
  (3 0 0 0 3 1)
  (3 1 1 0 2 0)
  (1 1 0 2 2 1)
  (2 2 1 1 1 0)
  (0 2 0 3 1 1)
  (0 3 1 3 0 0)
  (0 1 0 3 2 1)
  (1 1 1 2 2 0)
  (0 0 0 3 3 1)


Etc....

Christopher
(Who is feeling strangely charitable with his precious time tonight....)
From: Stig Hemmer
Subject: Re: newby Q: Recursion
Date: 
Message-ID: <ekv3dtqg43w.fsf@lizard.pvv.ntnu.no>
"Kassian" <······@rumms.uni-mannheim.de> writes:
> Ok, did this, now my teacher said that could be written recusiv, but
> want tell me how.

A recursive function is one that is defined in terms of itself.

One example goes like this:

(defun some-name (parameter  &optional really-do-it)
  (if really-do-it
     (... the code for solving the problem ...)
     (some-name parameter t)))

The middle part is just the same iterative code that you have already
written.

Your teacher will probably say that this isn't answering the question.
Make him tell you _exactly_ why he thinks so.  This might give both of
you some idea of what he _really_ wants.

Stig Hemmer,
Jack of a Few Trades.