;
;circle.lisp
;

;algorithm to repeatedly remove k'th item 
;from circular list and determine which
;element is last to remain.

;algorithm is o(n) given input n, size of list

;note that algorithm is independent of k because
;(mod k n) is always used to determine which element
;of list to remove

(defun circle-nth(l k)

  "Compute index, from 0 to length of list, of k-th item in list l.
   Uses the trick that for any k, (mod k (length l))
   is the correct index which is equivalent to walking through the list
   circularly to get the k-th item -- saves steps for k > (length l)... "

  (mod k (length l))
 
)

(defun circle-remove(l n)

  "Remove (circle-nth n)-th item in list l"

  (let 
    (
     (k-th (circle-nth l n))
     )

    (format t "Remove #~d from ~s~%" k-th l)
  
    (cond
      ((null l) nil)				; can't remove from empty list
      ((zerop k-th) (butlast l))		; index 0 means remove last element
      (t 
       (append					; construct returned list from
	 (nthcdr k-th l)			; succeeding cdr and
	 (firstn (sub1 k-th) l) 		; list preceding removed element
	 )
      )
    )
  )
)

(defun circle-last(l k-th)

 "Remove k-th item in list l until only 1 element left"

 (format t "~%") 

 (if
   (cdr l)
   (circle-last (circle-remove l k-th) k-th)	; recurse 'til only one element left
   (car l)
   )
)

(defun circle-demo(n k)

  "Demonstrate circular removal algorithm for a given n, k"

  (cond
    ((null (integerp n)) (format t "~%N must be an integer!~%"))
    ((null (integerp k)) (format t "~%K must be an integer!~%"))
    ((lessp n 1)         (format t "~%N must be >= 1!~%"))
    ((lessp k 1)         (format t "~%K must be >= 1!~%"))
    ((greaterp n 26)     (format t "~%N must be <= 26!~%"))
    (t
     (prog (demlist last-one)
	   (setq demlist '(a b c d e f g h i j k l m n o p q r s t u v w x y z))
	   (setq demlist (firstn n demlist))
	   (format t "~%Remove every ~d~a" k
		   (case k
		     (1 "st")
		     (2 "nd")
		     (3 "rd")
		     (t "th")
		     )
		   )
	   (format t " element from ~s~%" demlist)
	   (setq last-one (circle-last demlist k))
	   (format t "~%Only ~a remains.~%" last-one)
	   (return last-one)
	   )
     )
    )
  )