Cannibals and missionaries help!!!

You have problems, and we're glad to hear them. Explain the problem, what you have tried, and where you got stuck.
Feel free to share a little info on yourself and the course.
Forum rules
Please respect your teacher's guidelines. Homework is a learning tool. If we just post answers, we aren't actually helping. When you post questions, be sure to show what you have tried or what you don't understand.

Cannibals and missionaries help!!!

Postby Diesel298 » Fri Nov 01, 2013 6:29 am

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))
Diesel298
 
Posts: 1
Joined: Fri Nov 01, 2013 6:21 am

Re: Cannibals and missionaries help!!!

Postby saulgoode » Fri Nov 01, 2013 10:22 am

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.
saulgoode
 
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am


Return to Homework

Who is online

Users browsing this forum: No registered users and 1 guest