(defvar fullTransList)

;; main function -- gets user input and calls recursive search.
(defun mc ()
  ;; make global list of possible transitions
  (setf fullTransList '(MML CCL MCL ML CL MMR CCR MCR MR CR))
  (print '(enter n ))
  (let ((n (read)))
    (cond
     ((< n 1) (print '(invalid n)))
     (T (doSearch (list n n 'l) NIL fullTransList n))
     )					; end cond
    )					; end let
  )  

;; recursive search function.
;; given current state, search history, list of transitions remaining 
;; for this state, and n.
;; assumes n > 0.
;; if curState is valid, dead, or final, pops out of recursion.
;; if there is no transition to take, pops out of recursion.
;; otherwise, recurses down to the next state and through the list of transitions.
(defun doSearch (curState searchPath transList n)
  (cond 
   ((null curState) NIL) 
   ((isDead curState searchPath n) NIL) ;; found a dead state 
   ((isFinal curState) (print '(found solution)) (print (reverse (cons curState searchPath))))
   ((null transList) NIL) ;; reached end of transition list 
   (T 
    ;; recurse down the tree -- find nextState, update searchPath, 
    ;; send full transition list 
    (doSearch (nextState curState (first transList) n) 
	      (cons (first transList) (cons curState searchPath)) fullTransList n)
    ;; recurse through transition list -- keep state and searchPath the same
    (doSearch curState searchPath (rest transList) n))
   )	
  )

;; given a state (M C S) and a transition (e.g. 'MMR, 'CL), finds the next state
;; if the move is possible.
(defun nextState (curState transition n)
  (let* ((ml (getM curState)) (cl (getC curState)) (side (getS curState))
	 (mr (- n ml)) (cr (- n cl)))
    ;; ml = missionaries on left
    ;; cl = cannibals on left
    ;; mr = missionaries on right
    ;; cr = missionaries on right
    ;; side = boat location
    (cond
     ((null curState) NIL)
     ((eq side 'L)
      ;; on left, only consider moves to right
      (cond 
	((and (eq transition 'MMR) (> ml 1)) (list (- ml 2) cl 'R))
        ((and (eq transition 'CCR) (> cl 1)) (list ml (- cl 2) 'R))
	((and (eq transition 'MCR) (and (> ml 0) (> cl 0))) (list (1- ml) (1- cl) 'R))
	((and (eq transition 'MR) (> ml 0)) (list (1- ml) cl 'R))
	((and (eq transition 'CR) (> cl 0)) (list ml (1- cl) 'R))
	(T NIL)
	)				; end inner cond
      )					; end (eq side 'L)
     ((eq side 'R)
      ;; on right, only consider moves to left
      (cond
       ((and (eq transition 'MML) (> mr 1)) (list (+ ml 2) cl 'L))
       ((and (eq transition 'CCL) (> cr 1)) (list ml (+ cl 2) 'L))
       ((and (eq transition 'MCL) (and (> mr 0) (> cr 0))) (list (1+ ml) (1+ cl) 'L))
       ((and (eq transition 'ML) (> mr 0)) (list (1+ ml) cl 'L))
       ((and (eq transition 'CL) (> cr 0)) (list ml (1+ cl) 'L))
       (T NIL)
       )				; end inner cond
      )					; end (eq side 'R)
     (T NIL)
     )					; end outer cond
    )					; end let
  )					; end nextState function
      
;; checks to see if cannibals outnumber missionaries on either side.
;; checks to see if we've been here before.
(defun isDead (curState searchPath n)
  (let ((m (getM curState)) (c (getC curState)))
    (cond
     ((null curState) T)
     ((and (> c m) (> m 0)) T)
     ((and (> (- n c) (- n m)) (> (- n m) 0) ) T) 
     ((member curState searchPath :test #'equal) T)
     (T NIL)
     )
    )
  )

;; checks to see if we are done -- state is (0 0 'R).
(defun isFinal (state)
  (cond 
   ((null state) NIL)
   ((and (and (= (getM state) 0) (= (getC state) 0)) (eq (getS state) 'R)) T)
   (T NIL)
   )
  )

;; picks # of missionaries out of state.
(defun getM (state)
  (cond 
   ((null state) NIL)
   (T (first state))
   )
  )

;; picks # of cannibals out of state.
(defun getC (state)
  (cond
   ((null state) NIL)
   (T (second state))
   )
  )

;; picks boat location out of state.
(defun getS (state)
  (cond 
   ((null state) NIL)
   (T (first (last state)))
   )
  )