anchor.diff:  ;;;;
   ;;;; The program is structured so that the easiest parts go first, then a bit harder ones, finally the hardest part.
   ;;;; Saying 'hardest' is a great overstatement. This is still simple backtracking, so really this is no hard.
  -;;;; Everywhere I tried to maintain this functional fasion - no hidden variables, limit use of 'setf'.
  -;;;; This indeed make things simpler to develop and test.
  -;;;; So the main function backtracking function is 'find-next-move'. It receives current states stack, and searches
  -;;;; for next possible move.n
  -;;;; If it does find a next possible move, it adds it to the front of states stack and returns new states stack.
  +;;;; I tried to maintain a functional fashion - no hidden variables, limit use of 'setf'.
  +;;;; This indeed makes things simpler to develop and test.
  +;;;; So the main backtracking function is 'find-next-move'. It receives current states stack, and searches
  +;;;; for a next possible move.
  +;;;; If it finds one, it will add it to the front of states stack and returns new states stack.
   ;;;; Otherwise, it returns a modified states stack, with last state removed, and this new last state has
   ;;;; its :branch-idx argument increased, so that next time we look for a solution, we do not enter this dead alley again.
   
   ;;;; 
  -(in-package :org.ostaszewski.tomasz.missionaries)
  +;(in-package :org.ostaszewski.tomasz.missionaries)
   
  -(declaim (optimize (speed 3) (safety 0)))
  +;;(declaim (optimize (speed 3) (safety 0)))
   
   ;;; A function that creates a new state with given parameters
  -(defun new-state (&key missionaries cannibals has-boat (branch-idx 0))
  -  (declare (fixnum missionaries cannibals branch-idx))
  -  (list :missionaries missionaries :cannibals cannibals :has-boat has-boat :branch-idx branch-idx))
  -
  -(defparameter *winning-state* (new-state :missionaries 0 :cannibals 0 :has-boat nil))
  -
  -(defun make-move (&key missionaries cannibals)
  -  (declare (fixnum missionaries cannibals))
  -  (list :missionaries missionaries :cannibals cannibals))
  -
  -(defun negate-move (a-move)
  -  (make-move
  -   :missionaries (- 0 (the fixnum (getf a-move :missionaries)))
  -   :cannibals (- 0 (the fixnum (getf a-move :cannibals)))))
  +(defparameter *winning-state* `(:missionaries 0 :cannibals 0 :has-boat nil))
   
   ;;; a list of valid moves from right to left side of the river
  -(defparameter *valid-moves-r-to-l* (list
  -                                    (make-move :missionaries 1 :cannibals 1)
  -                                    (make-move :missionaries 1 :cannibals 0)
  -                                    (make-move :missionaries 2 :cannibals 0)
  -                                    ))
  -
  -;;; a list of valid moves from left to right side of the river
  -(defparameter *valid-moves-l-to-r* (list
  -                                    (negate-move (nth 0 *valid-moves-r-to-l*))
  -                                    (negate-move (nth 1 *valid-moves-r-to-l*))
  -                                    (negate-move (nth 2 *valid-moves-r-to-l*))))
  +(defparameter *valid-moves*
  +  `(:without-boat ((:missionaries 1 :cannibals 1)
  +                   (:missionaries 1 :cannibals 0)
  +                   (:missionaries 2 :cannibals 0))
  +     :with-boat ((:missionaries -1 :cannibals -1)
  +                 (:missionaries -1 :cannibals 0)
  +                 (:missionaries -2 :cannibals 0))))
   
   (defparameter *moves-limit* (1- (length *valid-moves-r-to-l*)))
   
   (defun states-equal-p (lhs-state rhs-state)
  -  (and (equal (the fixnum (getf lhs-state :missionaries)) (the fixnum (getf rhs-state :missionaries)))
  -       (equal (the fixnum (getf lhs-state :cannibals))    (the fixnum (getf rhs-state :cannibals)))
  -       (equal (the fixnum (getf lhs-state :has-boat))     (the fixnum (getf rhs-state :has-boat)))))
  +  (and (equal (getf lhs-state :missionaries) (getf rhs-state :missionaries))
  +       (equal (getf lhs-state :cannibals) (getf rhs-state :cannibals))
  +       (equal (getf lhs-state :has-boat) (getf rhs-state :has-boat))))
   
   (defun winning-state-p (a-state)
     (states-equal-p *winning-state* a-state))
  
positive.code: ;;;; The last key, :branch-idx, represents how did we get to this state, i.e. which move, among
  ;;;; 3 possible moves from left to right, and 3 possible moves from right to left, got us where we are.
  ;;;;
  ;;;; For instance, a states stack like below:
  ;;;;   ((:missionaries 2 :cannibals 1 :has-boat nil :branch-idx 2) (:missionaries 3 :cannibals 2 :has-boat t :branch-idx 0))
  ;;;; represents a situation when we had 3 missionaries and 2 cannibals on the left side,
  ;;;; and then we have 2 missionaries and 1 cannibal on the left side, with 1 missionary and 1 cannibal
  
negative.code: 
  ;;; Check if a given state have already been visited
  (defun visited-state-p (state states-stack)
    (find-if #'(lambda(s) (states-equal-p s state)) states-stack))
  
  ;;; Returns next possible state
  ;;; given current state and one of the
  ;;; possible moves.
  (defun get-next-state (m c state-stack move-idx)
    (let* ((current-state (first state-stack))
           (move (nth move-idx
                      (if (getf current-state :has-boat)
                          (getf *valid-moves* :with-boat)
                          (getf *valid-moves* :without-boat)))))
      (if move
          (let ((missionaries (+ (getf current-state :missionaries) (getf move :missionaries)))
                (cannibals (+ (getf current-state :cannibals) (getf move :cannibals)))
                (has-boat (not (getf current-state :has-boat))))
            (let ((next-state (new-state :missionaries missionaries :cannibals cannibals :has-boat has-boat)))
              (and (valid-state-p m c next-state) (not (visited-state-p next-state state-stack)) next-state))))))
  
  ;;; Finds a valid next state for given current state
  