Hi,
I am getting error in following function : generate_legal_moves
All other functions are working fine.
Here is the complete code :
;;; Missionaries and cannibals problem
;;; $Id: missionaries.lisp,v 1.2 2006/01/29 18:08:17 jcollins Exp $
;;; Put this in its own package -
(unless (find-package :mc)
(defpackage :mc))
(in-package :mc)
;;; A state gives the locations of the various missionaries and cannibals,
;;; the location of the boat, and the state from which this state was
;;; derived. You can extract the full sequence of states leading to this
;;; one by following the previous links back to the state having a previous
;;; value of nil.
(defstruct state
"a state of the world"
left ; missionaries & cannibals on the left bank
right ; missionaries & cannibals on the right bank
boat ; missionaries & cannibals in the boat
loc ; location of the boat
previous ; previous state in search
)
;;; A place has missionaries and cannibals
(defstruct place
"left, right, and boat are places"
missionaries
cannibals)
(defun initial-state ()
"Creates an initial state, with everyone on the left bank"
(make-state :left (make-place :missionaries 3 :cannibals 3)
:right (make-place :missionaries 0 :cannibals 0)
:boat (make-place :missionaries 0 :cannibals 0)
:loc 'left
:previous nil))
(defun new-state (state)
"Creates a new state, identical to state, but on the other shore,
and having state as its previous state"
(make-state
:left (make-place :missionaries (place-missionaries (state-left state))
:cannibals (place-cannibals (state-left state)))
:right (make-place :missionaries (place-missionaries (state-right state))
:cannibals (place-cannibals (state-right state)))
:boat (make-place :missionaries (place-missionaries (state-boat state))
:cannibals (place-cannibals (state-boat state)))
:loc (other-shore (state-loc state))
:previous state))
(defun other-shore (location)
"returns the opposite shore"
(cond ((eq location 'left)
'right)
((eq location 'right)
'left)
(t ;should not happen...
'left)))
;;; state checking
(defun goal-state (state)
"goal is reached when right bank has 3 missionaries and 3 cannibals"
(and (= (place-missionaries (state-right state)) 3)
(= (place-cannibals (state-right state)) 3)))
(defun legal-state (state)
;;JEC"state is legal if ..."
;; to be completed
"state is legal if number of missionaries on left and right are always greater then or equal to cannibals"
(and (>=(place-missionaries(sta
te-right state))(place-cannibals(st
ate-right state)))
(>=(place-missionaries(sta
te-left state))(place-cannibals(st
ate-left state))))
)
(defun has-room (state n)
"true if the boat has room for n more people"
(let ((boat (state-boat state)))
(<= (+ (place-missionaries boat)
(place-cannibals boat))
(- 2 n) ;; boat can hold at most 2 people
)))
(defun generate-legal-moves (state)
(let ((result nil))
(if(eq(state-loc state)'left)
;;JEC - removed extra paren (
;; JEC - probably this let should be outside the if, because this if
;; is not the last form in the defun and so there's no way to return
;; this value
;;
;; JEC - Each of these variables will be global. That's
;; probably not your intent.
(setf orig_can_left (place-cannibals (state-left state)))
(setf orig_miss_left (place-missionaries (state-left state)))
(setf orig_can_right (place-cannibals (state-right state)))
(setf orig_miss_right (place-missionaries (state-right state)))
(setf can2_left (place-cannibals (state-left state)))
(setf miss2_left (place-missionaries (state-left state)))
(setf can1_left (place-cannibals (state-left state)))
(setf miss1_left (place-missionaries (state-left state)))
(setf can2_right (place-cannibals (state-right state)))
(setf miss2_right (place-missionaries (state-right state)))
(setf can1_right (place-cannibals (state-right state)))
(setf miss1_right (place-missionaries (state-right state)))
;;try either of three conditions below and cons to result
;;reduce no. of cannibals on left by 1 and reduce no. of missionaries on left by 1 (use decf)
;;Increase no. of cannibals on right by a and increase no. of missionaries on right by1 (use incf)
(decf can1_left)
(decf miss1_left)
(decf can2_left 2)
(decf miss2_left 2)
(incf can1_right)
(incf miss1_right)
(incf can2_right 2)
(incf miss2_right 2)
;;cond - canibals reduced by 1 and miss red by 1 of left
(if (and (or (equal(miss1_left 0))
(>=(miss1_left cann1_left))
;; JEC - probably this last or is in the wrong place?
(or (equal(miss1_right 0))(>=(miss1_right cann1_right)))))
;;setf the following values to new values
(progn ; JEC - added progn
(decf (place-missionaries (state-left state)))
(decf (place-cannibals (state-left state)))
(incf (place-missionaries (state-right state)))
(incf (place-cannibals (state-right state)))
(setf (place-missionaries (state-boat state)) 1)
(setf (place-cannibals(state-boa
t state)) 1)
(let ((new1-state (new-state state)))
(setf (state-previous new1-state)) ; JEC - setf takes 2 args
(new-state (new1-state)) ; JEC - what do you do with the
; result of this?
(setf result (cons new1-state result)))))
;; Check if we can shift 2 missionaries from left without violating constraints
(if (and (or (equal(miss2_left 0))
(>=(miss2_left orig_can_left))
(or (equal(miss2_right 0))
(>=(miss2_right orig_can_left)))))
;;setf the following values to new values
(progn ; JEC - added progn
(decf (place-missionaries (state-left state)) 2)
(setf (place-cannibals (state-left state)) orig_can_left)
(incf (place-missionaries (state-right state)) 2)
(setf (place-cannibals (state-right state)) orig_can_right)
(setf (place-missionaries (state-boat state)) 2)
(setf (place-cannibals(state-boa
t state)) 0)
(let ((new1-state (new-state state)))
(setf (state-previous new1-state))
(new-state (new1-state))
(setf result (cons new1-state result)))))
;; check if we can shift 2 cannibals without violating constraints
(if (and (or (equal(orig_miss_left 0))
(>=(orig_miss_left can2_left))
(or (equal(orig_miss_right 0))
(>=(orig_miss_right can2_right)))))
;;setf the following values to new values
(progn ; JEC - added progn
(setf (place-missionaries (state-left state)) orig_miss_left )
(decf (place-cannibals (state-left state)) 2)
(setf (place-missionaries (state-right state)) orig_miss_right)
(incf (place-cannibals (state-right state)) cann2_right)
(setf (place-missionaries (state-boat state)) 0)
(setf (place-cannibals(state-boa
t state)) 2)
(let ((new1-state (new-state state)))
(setf (state-previous new1-state))
(new-state (new1-state))
(setf result (cons new1-state result)))))
) ;; JEC -- removed paren
;; this won't get returned, because there's another form here
(if (eq (state-loc state) 'right)
;; JEC - removed paren (
;; JEC - lots of global vars again
(setf orig_can_left (place-cannibals (state-left state)))
(setf orig_miss_left (place-missionaries (state-left state)))
(setf orig_can_right (place-cannibals (state-right state)))
(setf orig_miss_right (place-missionaries (state-right state)))
(setf can2_right (place-cannibals (state-right state)))
(setf miss2_right (place-missionaries (state-right state)))
(setf can1_right (place-cannibals (state-right state)))
(setf miss1_right (place-missionaries (state-right state)))
(setf can2_left (place-cannibals (state-left state)))
(setf miss2_left (place-missionaries (state-left state)))
(setf can1_left (place-cannibals (state-left state)))
(setf miss1_left (place-missionaries (state-left state)))
;;try either of three conditions below and cons to result
;;reduce no. of cannibals on right by 1 and reduce no. of missionaries on right by 1 (use decf)
(decf can1_right)
(decf miss1_right)
(decf can2_right 2)
(decf miss2_right 2)
(incf can1_left)
(incf miss1_left)
(incf can2_left 2)
(incf miss2_left 2)
(if (and (or (equal(miss1_right 0))
(>=(miss1_right cann1_right))
(or (equal(miss1_left 0))(>=(miss1_left cann1_left)))))
(progn ; JEC - added progn
;;setf the following values to new values
(decf (place-missionaries (state-right state)) 1 )
(decf (place-cannibals (state-right state)) 1)
(incf (place-missionaries (state-left state)) 1)
(incf (place-cannibals (state-left state)) 1)
(setf(place-missionaries (state-boat state)) 1)
(setf(place-cannibals(stat
e-boat state)) 1)
(let ((new1-state (new-state state)))
(setf (state-previous new1-state))
(new-state (new1-state))
(setf result (cons new1-state result)))))
;; Check if we can shift 2 missionaries to left without violating constraints
(if (and (or (equal(miss2_right 0))
(>=(miss2_right orig_can_right))
(or (equal(miss2_left 0))
(>=(miss2_left orig_can_left)))))
(progn ; JEC - added progn
;;setf the following values to new values
(decf (place-missionaries (state-right state)) 2 )
(setf (place-cannibals (state-right state)) orig_can_right)
(incf (place-missionaries (state-left state)) 2)
(setf (place-cannibals (state-left state)) orig_can_left)
(setf (place-missionaries (state-boat state)) 2)
(setf (place-cannibals(state-boa
t state)) 0)
(let ((new1-state (new-state state)))
(setf (state-previous new1-state))
(new-state (new1-state))
(setf result (cons new1-state result)))))
;; check if we can shift 2 cannibals to left without violating constraints
(if (and (or (equal(orig_miss_right 0))
(>=(orig_miss_right can2_right))
(or (equal(orig_miss_left 0))
(>=(orig_miss_left can2_left)))))
(progn ; JEC - added progn
;;setf the following values to new values
(setf (place-missionaries (state-right state)) orig_miss_right )
(decf (place-cannibals (state-right state)) 2)
(setf (place-missionaries (state-left state)) orig_miss_left)
(incf (place-cannibals (state-left state)) 2)
(setf (place-missionaries (state-boat state)) 0)
(setf (place-cannibals(state-boa
t state)) 2)
(let ((new1-state (new-state state)))
(setf (state-previous new1-state))
(new-state (new1-state))
(setf result (cons new1-state result))))))
result)) ;; JEC - this result includes only the info from the
;; second if form
(defun do-search ()
"searches for a sequence of legal moves that achieves the goal"
(let ((queue (list (initial-state))))
(do ((entry (pop queue)
(pop queue)))
((goal-state entry)
(print-sequence entry))
(setf queue (nconc queue (generate-legal-moves entry))))))
(defun print-sequence (state &key flat)
"prints the sequence of states leading to state"
;; print previous, then print this one
(if (and (not flat) (state-previous state))
(print-sequence (state-previous state)))
(format t "~:[<~;>~] left (~D ~D), boat (~D ~D), right (~D ~D)~%"
(eq (state-loc state) 'right)
(place-missionaries (state-left state))
(place-cannibals (state-left state))
(place-missionaries (state-boat state))
(place-cannibals (state-boat state))
(place-missionaries (state-right state))
(place-cannibals (state-right state))))
Start Free Trial