From: Kirit Patel
Subject: Newbie question
Date:
Message-ID: <380B8C3B.DEB9A4CB@cse.msu.edu>
This is a multi-part message in MIME format.
--------------2236232DB585A57EA16FFA95
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hi, I am very new to lisp and i am trying to figure out what i am doing
wrong. Hopefully some one out there can help with me with this.
I am writting a program that will take a farmer,a wolf,a goat,and a
cabbage across a river. This program is currently using a breadth first
search. I think there might be something wrong in my BFS function,it
seems to return nil instead of actually running through the search tree.
I hope that someone with more talent then me can spot this error.
the command line argument i am using to start the program is:
(bfs '((f w g c right 0 0 0 0)) () '(0 0 0 0 left f w g c) 'gs)
By using this command my program should return all the states that it
took to get from the start state to the goal.
Thanking you for any help in advance.
Kirit Patel
Please mail me at ········@cse.msu.edu if you can spot my mistake.
--------------2236232DB585A57EA16FFA95
Content-Type: text/plain; charset=us-ascii;
name="proj4.lisp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="proj4.lisp"
(defun fwgcstate (lf lw lg lc b rf rw rg rc)
(list lf lw lg lc b rf rw rg rc))
(defun fl (state)
(nth 0 state))
(defun wl (state)
(nth 1 state))
(defun gl (state)
(nth 2 state))
(defun cl (state)
(nth 3 state))
(defun boat_pos (state)
(nth 4 state))
(defun fr (state)
(nth 5 state))
(defun wr (state)
(nth 6 state))
(defun gr (state)
(nth 7 state))
(defun cr (state)
(nth 8 state))
(defun opposite (side)
(if (equal side 'left) 'right 'left))
(defun mvf (side)
(if (equal side 'f) 0 'f))
(defun mvw (side)
(if (equal side 'w) 0 'w))
(defun mvg (side)
(if (equal side 'g) 0 'g))
(defun mvc (side)
(if (equal side 'c) 0 'c))
(defun safe (s)
(cond ((eq (fl s) 0)
(if (or (and (and (eq (wl s) 'w) (eq (gl s) 'g)) (eq (gl s) 'g)) (and (and (eq (gl s) 'g) (eq (cl s) 'c)) (eq (cl s) 'c))) nil s))
((eq (fr s) 0)
(if (or (and (and (eq (wr s) 'w) (eq (gr s) 'g)) (eq (gr s) 'g)) (and (and (eq (gr s) 'g) (eq (cr s) 'c)) (eq (cr s) 'c))) nil s))))
(defun f (s)
(cond ((if (eq (boat_pos s) 'right)
(safe( fwgcstate
(mvf (fl s))
(wl s)
(gl s)
(cl s)
(opposite (boat_pos s))
(mvf (fr s))
(wr s)
(gr s)
(cr s)))))
((if (eq (boat_pos s) 'left)
(safe( fwgcstate
(mvf (fl s))
(wl s)
(gl s)
(cl s)
(opposite (boat_pos s))
(mvf (fr s))
(wr s)
(gr s)
(cr s)))))))
(defun fw (s)
(cond ((if (eq (boat_pos s) 'right)
(safe( fwgcstate
(mvf (fl s))
(mvw (wl s))
(gl s)
(cl s)
(opposite (boat_pos s))
(mvf (fr s))
(mvw (wr s))
(gr s)
(cr s)))))
((if (eq (boat_pos s) 'left)
(safe( fwgcstate
(mvf (fl s))
(mvw (wl s))
(gl s)
(cl s)
(opposite (boat_pos s))
(mvf (fr s))
(mvw (wr s))
(gr s)
(cr s)))))))
(defun fg (s)
(cond ((if (eq (boat_pos s) 'right)
(safe( fwgcstate
(mvf (fl s))
(wl s)
(mvg (gl s))
(cl s)
(opposite (boat_pos s))
(mvf (fr s))
(wr s)
(mvg (gr s))
(cr s)))))
((if (eq (boat_pos s) 'left)
(safe( fwgcstate
(mvf (fl s))
(wl s)
(mvg (gl s))
(cl s)
(opposite (boat_pos s))
(mvf (fr s))
(wr s)
(mvg (gr s))
(cr s)))))))
(defun fc (s)
(cond ((if (eq (boat_pos s) 'right)
(safe( fwgcstate
(mvf (fl s))
(wl s)
(gl s)
(mvc (cl s))
(opposite (boat_pos s))
(mvf (fr s))
(wr s)
(gr s)
(mvc (cr s))))))
((if (eq (boat_pos s) 'left)
(safe( fwgcstate
(mvf (fl s))
(wl s)
(gl s)
(mvc (cl s))
(opposite (boat_pos s))
(mvf (fr s))
(wr s)
(gr s)
(mvc (cr s))))))))
(defun gs (s)
(remove 'nil (list (f s) (fw s) (fg s) (fc s)):test 'equal))
(defun rem-dup (a b)
(cond ((null a) ()) ;; return empty list to cons into.
((member (car a) b :test 'compare-cars) (rem-dup (cdr a) b) )
(t (cons (car a) (rem-dup (cdr a) b)))))
(defun compare-cars (lis1 lis2)
(equal (car lis1) (car lis2)))
(defun bfs (open closed goal genfunc)
(if (null open) nil
(let ((next (car open)) children)
(cond ((equal next goal) (sucess closed))
(T (setf children (funcall genfunc next))
(setf children (rem-dup children open))
(setf children (rem-dup children closed))
(bfs (append (rest open) children)
(cons next closed)
goal
genfunc))))))
;(defun bfs (open closed goal genfunc)
;(if (null open) nil
; (let ((next (car open)) children)
; (cond ((equal next goal) (success closed))
; (T (setf children (funcall genfunc next))
; (setf children (rem-dup children open))
; (setf children (rem-dup children closed))
; (bfs (append (rest open) children)
; (cons next closed)
; goal
; genfunc))))))
(defun sucess (s)
(cond ((null s) )
(T (sucess (cdr s)) (print (car s)))))
--------------2236232DB585A57EA16FFA95--