Page 1 of 1

Cannibals and missionaries help!!!

Posted: Fri Nov 01, 2013 6:29 am
by Diesel298
Hello,
I am fairly new to lisp and need help with what seems to be a well known lisp problem. For one of my classes we are doing the cannibals and missionaries problem where there are 3 of both and 1 boat that can hold 2 people. The objective is to get all members across a river but if the missionaries ever outnumber the cannibals then the cannibals will be converted. We need to write a program to solve this problem, then have it solve it with a breadth or depth first search and a best-first search. The code below is what I have but I cannot get it to work please any help would be appreciated.

Code: Select all

;; Name: 
;; Project Name: Cannibals and Missionaries
;; Description : To safely transport all members across the river
;; to the other side

(defun solve-cm (state goal) 
	(path state goal nil))

;; Define the start state

(setf *start* '(3 3 0 0 start-bank))

;; Define the goal state

(setf *goal* '(0 0 3 3 goal-bank))

;; Safe returns nil if a state is not safe; it returns the state unchanged if it is safe.

(defun safe (state)
    (cond ((or 
            (> (missionaries-at-start state)(cannibals-at-start state))
    	    (> (missionaries-at-goal state)(cannibals-at-goal state)) 
            (> (cannibals-at-start state) 0)
            (< (cannibals-at-start state) 3)
               nil))
          (t( state)) ) )

;; The recursive path algorithm searches the space in a depth first fashion.

(defun path (state goal been-list)
   (cond ((null state) nil)
	 ((equal state goal) (reverse (cons state been-list)))
	 ((not (member state been-list :test #'equal))
	      (or (path (move-two-cannibals state) goal (cons state been-list))
	          (path (move-two-missionaries state) goal (cons state been-list))
	          (path (move-one-cannibal state) goal (cons state been-list))
	          (path (move-one-missionary state) goal (cons state been-list))
                  (path (move-one-of-each state) goal (cons state been-list))
))))

;; These functions define legal moves in the state space. The take
;; a state as argument, and return the state produced by that operation.

(defun move-two-cannibals(state)
  (cond 
         ((equal (boat-position state) 'start-bank)
         (safe (make-state 
                (- (cannibals-at-start state) 2)
		(missionaries-at-start state)
	 	(+ (cannibals-at-goal state) 2)
	 	(missionaries-at-goal state)
                (opposite (boat-poition state))
                )))
        ((equal (boat-position state) 'goal-bank)
        (safe (make-state 
                (+ (cannibals-at-start state) 2)
		(missionaries-at-start state)
	 	(- (cannibals-at-goal state) 2)
	 	(missionaries-at-goal state)
                (opposite (boat-poition state))
                )))
))

(defun move-one-cannibal(state)
  (cond 
        ((equal (boat-position state) 'start-bank)
         (safe (make-state 
                (- (cannibals-at-start state) 1)
		(missionaries-at-start state)
	 	(+ (cannibals-at-goal state) 1)
	 	(missionaries-at-goal state)
                (opposite (boat-poition state))
                )))
       ((equal (boat-position state) 'goal-bank)
        (safe (make-state 
                (+ (cannibals-at-start state) 1)
		(missionaries-at-start state)
	 	(- (cannibals-at-goal state) 1)
	 	(missionaries-at-goal state)
                (opposite (boat-poition state))
                )))
))

(defun move-two-missionaries(state)
  (cond 
         ((equal (boat-position state) 'start-bank)
         (safe (make-state 
                (cannibals-at-start state)
		(- (missionaries-at-start state) 2)
	 	(cannibals-at-goal state)
	 	(+ (missionaries-at-goal state) 2)
                (opposite (boat-poition state))
                )))
        ((equal (boat-position state) 'goal-bank)
        (safe (make-state 
                (cannibals-at-start state)
		(+ (missionaries-at-start state) 2)
	 	(cannibals-at-goal state)
	 	(- (missionaries-at-goal state) 2)
                (opposite (boat-poition state))
                )))
))

(defun move-one-missionary(state)
  (cond 
         ((equal (boat-position state) 'start-bank)
         (safe (make-state 
                (cannibals-at-start state)
		(- (missionaries-at-start state) 1)
	 	(cannibals-at-goal state)
	 	(+ (missionaries-at-goal state) 1)
                (opposite (boat-poition state))
                )))
        ((equal (boat-position state) 'goal-bank)
        (safe (make-state 
                (cannibals-at-start state)
		(+ (missionaries-at-start state) 1)
	 	(cannibals-at-goal state)
	 	(- (missionaries-at-goal state) 1)
                (opposite (boat-poition state))
                )))
))

(defun move-one-of-each(state)
  (cond 
         ((equal (boat-position state) 'start-bank)
         (safe (make-state 
                (- (cannibals-at-start state) 1)
		(- (missionaries-at-start state) 1)
	 	(+ (cannibals-at-goal state) 1)
	 	(+ (missionaries-at-goal state) 1)
                (opposite (boat-poition state))
                )))
        ((equal (boat-position state) 'goal-bank)
        (safe (make-state 
                (+ (cannibals-at-start state) 1)
		(+ (missionaries-at-start state) 1)
	 	(- (cannibals-at-goal state) 1)
	 	(- (missionaries-at-goal state) 1)
                (opposite (boat-poition state))
                )))))


(defun opposite (boat-position)
  (cond ((equal boat-position 'start-bank) 'goal-bank)
        ((equal boat-position 'goal-bank) 'start-bank)))


;; These functions define states of the world as an abstract data type.

(defun make-state (cs ms cg mg boat-position)
    (list cs ms cg mg boat-position))

(defun cannibals-at-start ( state )
   (first state))

(defun missionaries-at-start ( state )
   (second state))

(defun cannibals-at-goal ( state )
   (third state))

(defun missionaries-at-goal ( state )
   (fourth state))

(defun boat-position ( state )
  (fifth state))

Re: Cannibals and missionaries help!!!

Posted: Fri Nov 01, 2013 10:22 am
by saulgoode
In your 'safe' procedure, you have 'nil' as part of the first predicate of the 'cond' (and serves no purpose in this position). It should be the evaluated consequent.

In other words, one of the closing parentheses is in the wrong place.