;;;
;;; The Missionaries & Cannibals Domain
;;;
;;; By Philip W. L. Fong
;;;

;;
;; State Representation
;;

(defun make-mc-state (MN CN MS CS LOC)
  "Create a Missionaries-and-Cannibals state with MN missionaries and
CN cannibals on the North bank, MS missionaries and CS cannibals on 
the South bank, and the boat docked on bank LOC."
  (list MN CN MS CS LOC))

(defun mc-state-MN (mc-state)
  "The number of missionaries on the North bank in MC-STATE."
  (first mc-state))

(defun mc-state-CN (mc-state)
  "The number of cannibals on the North bank in MC-STATE."
  (second mc-state))

(defun mc-state-MS (mc-state)
  "The number of missionaries on the South bank in MC-STATE."
  (third mc-state))

(defun mc-state-CS (mc-state)
  "The number of cannibals on the South bank in MC-STATE."
  (fourth mc-state))

(defun mc-state-LOC (mc-state)
  "The location of the boat in MC-STATE."
  (fifth mc-state))

;;
;; Initial State
;;

(defparameter *mc-init-state* '(3 3 0 0 N)
  "The initial state of the M&C problem.")

;;
;; Goal Test
;;

(defun mc-state-goal-test (mc-state)
  "Test if a MC-STATE is a goal."
  (and (zerop (mc-state-MN  mc-state)) 
       (zerop (mc-state-CN  mc-state))
       (eq 'S (mc-state-LOC mc-state))))

;;
;; Successor Function
;;

;; preconditions

(defun mc-state-legal-p (mc-state)
  "Check if MC-STATE is a well-defined state."
  (let ((MN (mc-state-MN mc-state))
	(CN (mc-state-CN mc-state))
	(MS (mc-state-MS mc-state))
	(CS (mc-state-CS mc-state)))
    (and (>= MN 0) (>= CN 0) (>= MS 0) (>= CS 0))))

(defun mc-state-safe-p (mc-state)
  "Check if MC-STATE is a safe state."
  (let ((MN (mc-state-MN mc-state))
	(CN (mc-state-CN mc-state))
	(MS (mc-state-MS mc-state))
	(CS (mc-state-CS mc-state)))
    (and (or (zerop MN) (>= MN CN))
	 (or (zerop MS) (>= MS CS)))))

;; effects

(defun mc-state-move (mc-state delta-m delta-c)
  "Move DELTA-M missionaries and DELTA-C cannibals accross the river
in MC-STATE."
  (let ((MN  (mc-state-MN mc-state))
	(CN  (mc-state-CN mc-state))
	(MS  (mc-state-MS mc-state))
	(CS  (mc-state-CS mc-state))
	(LOC (mc-state-LOC mc-state)))
    (if (eq LOC 'N)
	(make-mc-state (- MN delta-m) (- CN delta-c)
		       (+ MS delta-m) (+ CS delta-c) 
		       'S)
      (make-mc-state (+ MN delta-m) (+ CN delta-c) 
		     (- MS delta-m) (- CS delta-c)
		     'N))))

;; operators

(defun make-mc-operator-id (mc-state delta-m delta-c)
  "Create the identifier for an operator that moves DELTA-M missionaries
and DELTA-C cannibals accross the river in MC-STATE."
  (let ((src (mc-state-LOC mc-state))
	(des (if (eq (mc-state-LOC mc-state) 'N) 'S 'N)))
    (list 'move delta-m 'missionaries 'and delta-c 'cannibals 'from 
	  src 'bank 'to des 'bank)))

(defun mc-generic-move-operator (mc-state delta-m delta-c A)
  "Attempt to move DELTA-M missionaries and DELTA-C cannibals accross
the river in MC-STATE.  If the result of the move is illegal or unsafe,
then return A.  Otherwise, return a list containing all the members
of A plus an EFFECT object describing the effect of the moving."
  (let ((new-mc-state (mc-state-move mc-state delta-m delta-c)))
    (if (and (mc-state-legal-p new-mc-state)
	     (mc-state-safe-p  new-mc-state))
	(cons (make-effect (make-mc-operator-id mc-state delta-m delta-c)
			   1 new-mc-state)
	      A)
      A)))
	
(defun mc-move-1C (mc-state A)
  "An M&C operator: move one cannibal across the river."
  (mc-generic-move-operator mc-state 0 1 A))

(defun mc-move-1M (mc-state A)
  "An M&C operator: move one missionary across the river."
  (mc-generic-move-operator mc-state 1 0 A))

(defun mc-move-1C1M (mc-state A)
  "An M&C operator: move one cannibal and one missionary across the river."
  (mc-generic-move-operator mc-state 1 1 A))

(defun mc-move-2C (mc-state A)
  "An M&C operator: move two cannibals across the river."
  (mc-generic-move-operator mc-state 0 2 A))

(defun mc-move-2M (mc-state A)
  "An M&C operator: move two missionaries across the river."
  (mc-generic-move-operator mc-state 2 0 A))

;; successor function

(defun mc-successor-func (mc-state)
  "The M&C successor function: given an MC-STATE, it returns a list
of effect structures."
  (mc-move-1C mc-state
	      (mc-move-1M mc-state
			  (mc-move-1C1M mc-state
					(mc-move-2C mc-state
						    (mc-move-2M mc-state 
								nil))))))
;;
;; mc-problem				      
;;

(defun make-mc-problem ()
  "Create an instance of the M&C problem."
  (make-problem *mc-init-state*        ; initial state
		#'mc-successor-func    ; successor function
		#'mc-state-goal-test)) ; goal test

(defun solve-mc-problem (strategy)
  "Solve the M&C problem using the STRATEGY and report result."
  (solve-problem (make-mc-problem) strategy))