;;;  mission.scm    Dave Reed    2/04/04
;;;
;;;  Defines a state space for the Missionaries and Cannibals puzzle.
;;;    A state is assumed to be of the form: ((mLeft cLeft) boatLoc (mRight cRight))
;;;    where (mLeft cLeft) specifies the number of missionaries and cannibals on the
;;;    left bank, boatLoc specifies the boat location (either 'left or 'right), and
;;;    where (mRight cRight) specifies the number of missionaries and cannibals on the
;;;    right bank.
;;;
;;;  The HEURISTIC function defines a heuristic value for each state, which is the
;;;    number of people (and boat) in the correct position relative to the goal state.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (GET-MOVES state)
  
  (define (move-people m c)
    (let ((leftSide (car state)) (boat (cadr state)) (rightSide (caddr state)))
      (let ((mLeft (car leftSide)) (cLeft (cadr leftSide)) 
            (mRight (car rightSide)) (cRight (cadr rightSide)))
        (if (equal? boat 'left) 
          (list (list (- mLeft m) (- cLeft c)) 'right
                (list (+ mright m) (+ cRight c)))
          (list (list (+ mLeft m) (+ cLeft c)) 'left
                (list (- mright m) (- cRight c)))))))
    
  (define (prune-illegal statelist)
    (cond ((null? statelist) '())
          ((or (apply < (cons 0 (caar statelist)))    
               (< (apply min (caar statelist)) 0)      
               (apply < (cons 0 (caddar statelist)))
               (< (apply min (caddar statelist)) 0))   
           (prune-illegal (cdr statelist)))
          (else (cons (car statelist) (prune-illegal (cdr statelist))))))
  
  (prune-illegal (list (move-people 0 1) (move-people 1 0)
                       (move-people 1 1) (move-people 2 0) (move-people 0 2))))

(define (HEURISTIC state goal)
  (let ((diffLeft (+ (abs (- (caar state) (caar goal)))
                     (abs (- (cadar state) (cadar goal))))))
    (if (equal? (caddr state) (caddr goal))
        diffLeft
        (+ diffLeft 1))))