#-(and) "

P10 (*) Run-length encoding of a list.
    Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.
   
    Example:
    * (encode '(a a a a b c c a a d e e e e))
    ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))

"


;; Nice recursive solution, using the same design pattern as in P09:

(defun encode (list)
  (labels ((encode-run (element count list)
             (cond
               ((null list) (list (list count element)))
               ((eql element (first list)) (encode-run element (1+ count) (rest list)))
               (t (cons (list count element) (encode-run (first list) 1 (rest list)))))))
    (if (null list)
        '()
        (encode-run (first list) 1 (rest list)))))


;; Nice, functional solution, reusing functions from p09, uses O(n+r) space:

(defun encode (list)
  (mapcar (lambda (group) (list (length group) (first group)))
          (group list)))


;; Smartass solution, using Common Lisp reduce:

(defun encode (list)
  (reduce (lambda (item result)
            (print (list item result))
            (cond
              ((endp result)                      (list (list 1 item)))
              ((eql (second (first result)) item) (cons (list (1+ (first (first result))) item)
                                                        (rest result)))
              (t                                  (cons (list 1 item) result))))
          list
          :from-end t
          :initial-value '()))


;; Smartass solution, using Common Lisp reduce, and a closure; more
;; efficient since we don't call cons twice at each step, but
;; inelegant, since we have to add the last result as an afterthought:

(defun encode (list)
  (when list
    (let ((count     0)
          (last-item nil))
      (let ((tail-result (reduce (lambda (item result)
                                   (cond
                                     ((zerop count)
                                      (setf count 1
                                            last-item item)
                                      result)
                                     ((eql item last-item)
                                      (incf count)
                                      result)
                                     (t
                                      (prog1 (cons (list count last-item) result)
                                        (setf count 1
                                              last-item item)))))
                                 list
                                 :from-end t
                                 :initial-value '())))
        (cons (list count last-item) tail-result)))))


;; Iterative solution, uses only O(r) space:

(defun encode (list)
  (when list
    (loop
       :with count = 0
       :with last-item = nil
       :with result = '()
       :for item :in list
       :do (cond
             ((zerop count)        (setf count 1
                                         last-item item))
             ((eql item last-item) (incf count))
             (t                    (push (list count last-item) result)
                                   (setf count 1
                                         last-item item)))
       :finally (when (plusp count)
                  (push (list count last-item) result))
       (return (nreverse result)))))


;;;; THE END ;;;;