Using Lisp, implement a program that solves the Missionaries and Cannibals problem that uses a DFS( depth first search). The function call should use (mac start(this is the current state of the problem) end(this is the desired state)). So the problem should output sequences of moves to go from the start state to the desired state! For example, the call should be like: Call: (mac '(3 3 l) '(0 0 r)) Output: ((3 3 L) (2 2 R) (3 2 L) (3 0 R) (3 1 L) (1 1 R) (2 2 L) (0 2 R) (0 3 L) (0 1 R) (1 1 L) (0 0 R))
Using Lisp, implement a program that solves the Missionaries and Cannibals problem that uses a DFS( depth first search). The function call should use (mac start(this is the current state of the problem) end(this is the desired state)). So the problem should output sequences of moves to go from the start state to the desired state!
For example, the call should be like:
Call: (mac '(3 3 l) '(0 0 r))
Output: ((3 3 L) (2 2 R) (3 2 L) (3 0 R) (3 1 L) (1 1 R) (2 2 L) (0 2 R) (0 3 L) (0 1 R) (1 1 L) (0 0 R))
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
(defmacro mac (start end)
`(dfs ,start ,end nil nil))
(defun dfs (current-state goal-state path &optional (solution-found nil))
(cond
((and solution-found (equal current-state goal-state))
(format t "Solution: ~A~%" (reverse path)))
((member current-state path)
nil)
(t
(let ((new-paths (generate-next-states current-state)))
(dolist (new-state new-paths)
(dfs new-state goal-state (cons current-state path) t))))))
(defun generate-next-states (state)
(let* ((m (car state))
(c (cadr state))
(b (caddr state))
(next-states '()))
(loop for m-move from 0 to m
do (loop for c-move from 0 to c
do (when (valid-move m-move c-move m c b)
(let* ((new-state (update-state state m-move c-move))
(missionaries-on-left (- m m-move))
(cannibals-on-left (- c c-move))
(boat-position (if (eq b 'l) 'r 'l)))
(push (list missionaries-on-left cannibals-on-left boat-position) next-states)))))
next-states))
(defun valid-move (m-move c-move m c b)
(and (<= 0 m-move m) (<= 0 c-move c)
(<= (+ m-move c-move) 2)
(or (and (eq b 'l) (>= (- m m-move) (- c c-move)))
(and (eq b 'r) (>= (- c c-move) (- m m-move))))))
(defun update-state (state m-move c-move)
(let* ((m (car state))
(c (cadr state))
(b (caddr state)))
(if (eq b 'l)
(list (- m m-move) (- c c-move) 'r)
(list (+ m m-move) (+ c c-move) 'l))))
;; Example usage:
(mac '(3 3 l) '(0 0 r))
This is the code provided that runs, but gives the incorrect output. Check the attached image to see what I get.
The solution should simply be:
((3 3 L) (2 2 R) (3 2 L) (3 0 R) (3 1 L) (1 1 R) (2 2 L) (0 2 R) (0 3 L) (0 1 R) (1 1 L) (0 0 R))
Please help me fix!
by Bartleby ExpertThe code still does not seem to work for me. The error I get is: "Program stack overflow." I am using GNU Common Lisp Listener, perhaps this code can be tweaked again to ensure this error does not pop up again?
by Bartleby ExpertThis code is still not working, can you fix it? I get the same error: "L is not a number".
by Bartleby ExpertI have tried to run the code, using the example usage as well and I get the error: "L is not a number".
I will note that I am using GNU Common Lisp to run the code. Do you know how I could fix that?
by Bartleby Expert
