;;; EXAMPLE LISP CODE FOR MIDTERM 1 in CSE 415, WINTER 2004

;;; Many AI programs are based around searching through a space
;;; of possible configurations of objects.  One of the simplest
;;; kinds of configuration is the permutation of a list of objects.
;;; Manipulating permutations is therefore a common operation
;;; in such programs.

;;; The example code here has two parts.  The first deals
;;; with counting combinations.  The second deals with
;;; permutation functions.


;;; Computing numbers of combinations:

(defun c (n k)
  (cond ((= k 1) n)
        ((= k n) 1)
        (t (+ (c (1- n) k)
              (c (1- n) (1- k)) )) ) )

;;; A test function. Try (PASCAL 15)

(defun pascal (n)
  (dotimes (i n)
    (dotimes (j i)
      (format t " ~D " (c (1+ i) (1+ j)))
      )
    (format t "~%")
) )


;;; Creating and manipulating permutation functions:

(defun make-permuter (indices)
  "Returns a function that implements a permutation
   described by the given sequence of INDICES."
  #'(lambda (lst) 
      (mapcar #'(lambda (e) (elt lst e)) indices)))

(setq shuffler  (make-permuter '(0 4 1 5 2 6 3 7)))
(setq reverser  (make-permuter '(7 6 5 4 3 2 1 0)))
(setq midcut    (make-permuter '(4 5 6 7 0 1 2 3)))
(setq flipper01 (make-permuter '(1 0 2 3 4 5 6 7)))
(setq rotator   (make-permuter '(1 2 3 4 5 6 7 0)))

;;; Now here are some functions to combine permuation
;;; functions, getting new permutation functions.

(defun compose-2 (f1 f2)
  "Returns a new function that is F1 composed with F2."
  #'(lambda (n) (funcall f1 (funcall f2 n))) )

(defun compose-n (functions)
  "Returns a new function that is the n-way functional
   composition of all the functions in the list FUNCTIONS."
  (cond ((null functions) #'(lambda (n) n))
        ((null (cdr functions)) (car functions))
        (t (compose-2 (car functions)
                      (compose-n (cdr functions)) )) ) )

;;; Define a deck of 8 cards:
(setq cards '(ace-of-spades ace-of-hearts ace-of-diamonds ace-of-clubs
              king-of-spades king-of-hearts king-of-diamonds king-of-clubs))

;;; Try out various permutation functions:
(defun test1 ()
  (funcall shuffler cards) )

(defun test2 ()
  (funcall (compose-2 shuffler flipper01) cards) )

(defun test3 ()
  (let ((my-mixer
        (compose-n (list shuffler reverser midcut flipper01 rotator)) ))
    (funcall my-mixer cards) ) )