Misjonarer og Kannibaler problemet:

3 misjonarer og 3 kannibaler paaa en side av en elv, en baat kan frakte 2
stykker max, viss det er overtall av kannibaler paa en side av elva spises
misjonarerene. Maalet er at ingen misjonarer blir spist (og at ingen
kannibaler blir omvendt).

ta filen nedenfor, lagre den hos deg, hent den inn i gcl (load "filnavn"),
og kjoer:

>(mandc)

studer koden, og hva programmet gjoer, vi ser paa dette pa fredag.


kode:

(defun mandc ()

; Top level function for the missionaires and cannibals problem

      	(princ ";") (terpri)	 
	(initmandc)
	(tryall possiblemoves)	; Start search for solution
	(cond ((not (equal leftbank nil)) (print '(no solution found)))))



(defun initmandc ()

; Initialize all global variables and print the starting state

	(setq leftbank '(m m m c c c boat)
	      rightbank nil
	      stateseen '(())
	      possiblemoves '((c c boat) (c boat) (m c boat)
			       (m m boat) (m boat)))
	(printstate))



(defun tryall (setofmoves)

; Solve the problem with depth-first search, implemented with the two 
; functions tryall and explorestate

	(cond ((null setofmoves) nil)
	      (t (explorestate (car setofmoves))
		   (cond ((equal leftbank nil))
		         (t (tryall (cdr setofmoves)))))))



(defun explorestate (movelist)

; Explore the state reached with the current move (movelist), 
; if applicable

	(let (lbank rbank)
	     (setq lbank leftbank rbank rightbank)	; Set local 
							; variables for 
							; easy recovery 
							; from "bad"
							; states
	     (cond ((not (applicable? movelist)) nil)
		     (t (applymove movelist)	
			  (princ ";appliedmove                    ") 
			  (princ movelist)
			  (cond ((missionaireseaten?) 
				   (princ "missionaireseaten") 
				   (terpri) (princ ";") (terpri)
				   (recover lbank rbank) nil)	; Reset
								; state
		      	  ((stateseenbefore? movelist) 
				   (princ "stateseenbefore") 
				   (terpri)  (princ ";") (terpri)
				   (recover lbank rbank) nil)	; Reset
								; state
		      	  (t (princ "newstate")  	; The move leads 
							; to new state,
							; update global
							; variables and 
							; procede
							; recursively,
							; unless goal
			     (terpri) (princ ";") (terpri) (printstate)
			     (cond ((null leftbank) (print "success"))
			    	   (t (recordnewstate movelist)
			 	      (tryall possiblemoves)))))))))



(defun recover (lbank rbank)

; Reset global variables (leftbank and rightbank)

	(setq leftbank lbank
	      rightbank rbank))



(defun stateseenbefore? (movelist)

; Check if state is seen before, to avoid going into loops

	(equal movelist stateseen))



(defun applicable? (move)

; Predicate to check if the move is valid, 
; in other words, enough m's, c's and boat on the from side

	(and (not (> (numberof 'm move)
		       (numberof 'm (fromside))))
	     (not (> (numberof 'c move)
	               (numberof 'c (fromside))))))

(defun numberof (item lis)

; Counts and returns the number of items (item) in the list (lis)

	(cond ((null lis) 0)
	      ((equal item (car lis))
	       (+ 1 (numberof item (cdr lis))))
	      (t (numberof item (cdr lis)))))



(defun fromside ()

; Checks and returns the side the boat is on

	(cond ((member 'boat leftbank) leftbank)
	      ((member 'boat rightbank) rightbank)))



(defun printstate ()

; Prints the value of leftbank and rightbank

	(princ ";leftbank               ")(princ "is                    ")
	(princ leftbank)(terpri)
        (princ ";rightbank              ")(princ "is                    ")
        (princ rightbank)(terpri)
	(princ ";") (terpri))



(defun missionaireseaten? ()

; Checks if missionaires will be eaten at the current state

	(or (meaten? leftbank)
	    (meaten? rightbank)))



(defun meaten? (bank)

; Checks if missionaires will be eaten at the bank (bank)

	(and (> (numberof 'c bank)(numberof 'm bank))
	     (> (numberof 'm bank) 0)))



(defun deleteitem (atm lis)

; Delete an item (atm) from a list (lis), and returns resulting list

	(cond ((null lis) nil)
	      ((equal atm (car lis))(cdr lis))
	      (t (cons (car lis)
		         (deleteitem atm (cdr lis))))))

(defun removefrom (lis deletionlis)

; Remove a list (deletionlis) from a list (lis), 
; and returns resulting list

	(cond ((null deletionlis) lis)
	      (t (removefrom (deleteitem (car deletionlis) lis)
			         (cdr deletionlis)))))



(defun recordnewstate (movelist)

; Updates the global variable stateseen

	(setq stateseen movelist))



(defun applymove (movelist)

; Apply boat movement to current bank

	(cond ((member 'boat leftbank)(moveltor movelist))
	      ((member 'boat rightbank)(movertol movelist))
	      (t (print '(error in applymove)))))



(defun moveltor (movelist)

; Transfer items in list (movelist) from leftbank to rightbank

	(setq leftbank (removefrom leftbank movelist))
	(setq rightbank (append rightbank movelist)))



(defun movertol (movelist)

; Transfer items in list (movelist) from rightbank to leftbank

	(setq rightbank (removefrom rightbank movelist))
	(setq leftbank (append leftbank movelist)))