; Missionaries & Cannibals problem
;
; This is the code I wrote in class on Thursday 9/16/2004.  I've
; cleaned it up a little bit and added some comments.  We'll make a
; few modifications to this in class next week and then write BFS to
; solve this problem.
; 

; state:  (boat-side l-miss l-cann r-miss r-cann)
;
; accessors for the state:
(define boat-side first)
(define l-miss second)
(define l-cann third)
(define r-miss fourth)
(define r-cann fifth)

; start and goal states
(define mc-start '(left 3 3 0 0))
(define mc-end '(right 0 0 3 3))

; actually, we're going to redefine this to work on a node instead of
; a state
(define (mc-goal? state)
  (equal? mc-end state))

(define rest cdr)



; create a list of all states that can be reached from the given state
;
; if the boat is on the right side, then reverse the state, give it to
; real-boat-trip to generate the child states, and then reverse each
; of those states
; 
(define (boat-trip state)
  (if (equal? (boat-side state) 'left)
      (real-boat-trip state)
      (map mc-reverse (real-boat-trip (mc-reverse state)))))

; create the mirror problem --- switch the boat from right to left (or
; vice versa) and swap the people on the left and right sides of the
; river.
(define (mc-reverse state)
  (list (if (equal? (boat-side state) 'left)
	    'right
	    'left)
	(r-miss state)
	(r-cann state)
	(l-miss state)
	(l-cann state)))

; return all the states from sending people across on the boat
; assumes boat starts on left side
(define (real-boat-trip state)
  (map (lambda (x) (cons 'right x))
       (simulate-boat-trips (rest state))))

; "people" is a list of four numbers
; this procedure
(define (simulate-boat-trips people)
  (filter-people (map (lambda (p)
			(map + people p))
		      '((-1 0 1 0)
			(-2 0 2 0)
			(-1 -1 1 1)
			(0 -1 0 1)
			(0 -2 0 2)))))

; this procedure takes a list of people (i.e. a list where each
; element is a list of four numbers) and it removes each element that
; does not satisfy the constraints for the M&C problem
(define (filter-people people-lists)
  (if (null? people-lists)
      '()
      (if (valid-people? (first people-lists))
	  (cons (first people-lists)
		(filter-people (rest people-lists)))
	  (filter-people (rest people-lists)))))
			  
; a predicate (i.e. a procedure that returns #t or #f) that determines
; whether "p" (a list of four numbers) satisfies the constraints of
; the M&C problem.
(define (valid-people? p)
  (let ((people (cons 'left p))) ; hack --- make "people" a state
				 ; so i can use accessors like l-miss
    (and (or (zero? (l-miss people))
	     (>= (l-miss people) (l-cann people)))
	 (or (zero? (r-miss people))
	     (>= (r-miss people) (r-cann people)))
	 ; make sure all the numbers are nonnegative!
	 (>= (apply min p) 0))))