:<

fibonnachi.lisp

;;;; Fibonacchi recursive tree solution in non-exponential time challenge code.


(defun fib (n)
  (check-type n (integer 0 *))
  (labels ((fib-inner (n)
	     (case n
	       ((0) 0)
	       ((1) 1)
	       (otherwise (+ (fib (- n 1))
			     (fib (- n 2)))))))
    (fib-inner n)))

(let ((range (loop for n from 0 to 10 collect n))
      (sequence '(0 1 1 2 3 5 8 13 21 34 55)))
  (assert (equal (map 'list #'fib range) sequence)))

;;; Memoized version does not cut time much.

(defun fib-memo (n)
  (check-type n (integer 0 *))
  (let ((mem (make-hash-table :test 'eq)))
    (setf (gethash 0 mem) 0)
    (setf (gethash 1 mem) 1)
    (labels ((fib-inner (n)
	       (let ((r (gethash n mem)))
		 (if r
		     r
		     (+ (fib-inner (- n 1))
			(fib-inner (- n 2)))))))
      (fib-inner n))))

(let ((range (loop for n from 0 to 10 collect n))
      (sequence '(0 1 1 2 3 5 8 13 21 34 55)))
  (assert (equal (map 'list #'fib-memo range) sequence)))

;;; The linear-time solution is to add up the numbers from 0, 1, 1, 2, 3, 5...
;;; using a stack.
;;; To convert the recursive tree solution to this it must be evaluated in such
;;; a manner that it uses the call stack for the stack and evaluates it
;;; linearly, backwards.

(defun fib-linear (n)
  (check-type n (integer 0 *))
  (if (zerop n)
      0
      (labels ((fib-inner (x y n)
		 (if (= n 1)
		     y
		     (fib-inner y (+ x y) (1- n)))))
	(fib-inner 0 1 n))))

(let ((range (loop for n from 0 to 10 collect n))
      (sequence '(0 1 1 2 3 5 8 13 21 34 55)))
  (assert (equal (map 'list #'fib-linear range) sequence)))

;; 5
;; (4 3)
;; (3 2) (2 1)
;; (2 1) (1 0) (1 0) 1
;; (1 0) 1 1 1 1
;; 1 1 1 1 1
;; 5

;;; The tree must somehow be flattened.