;; Pascal Triangle stuff!
;; Whee....
;; Sid Stamm 2003
;; WARNING: there are some advanced techniques used to re-define
;; factorial in this file.

;1
;1  1
;1  2  1
;1  3  3  1
;1  4  6  4  1
;1  5 10 10  5  1
;1  6 15 20 15  6  1


;; prints out the pascal triangle of depth n
;; given a proc to compute each index.
(define pascal-printer
  (lambda (pascal-proc n) ;;triangle depth (0-based)
    (let loop ([row 0])
      (if (> row n)
	  (printf "Done ~%")
	  (begin
	    (let loop2 ([col 0])
	      (if (> col row)
		  (printf "~%")
		  (begin 
		    (printf "~s " (pascal-proc row col))
		    (loop2 (add1 col)))))
	    (loop (add1 row)))))))

(define pascal
  (lambda (row col)
    (if (or (= col row)
	    (= col 0)
	    (= row 0))
	1
	(+ (pascal (sub1 row) (sub1 col))
	   (pascal (sub1 row) col)))))

;; You can't make this tail recursive!  It has two simultaneous recursive
;; calls!

(define pascal-cached
  (lambda (row col)
    (let ([cache (make-vector (add1 row) #f)])
      (let cachemaker ([n 0])
	(unless (> n row)
	  (vector-set! cache n (make-vector (add1 n) #f))
	  (cachemaker (add1 n))))
      (let calculator ([r row] [c col])
	(if (or (= c r) (= c 0) (= r 0))
	    1
	    (if (vector-ref (vector-ref cache r) c) ;;check the cache
		(vector-ref (vector-ref cache r) c)
		(let ([result (+ (calculator (sub1 r) (sub1 c))
				 (calculator (sub1 r) c))])
		  (vector-set! (vector-ref cache r) c result)
		  result)))))))


;; to get the number in the x'th column and y'th row:
;; y! / (x! * (y-x)!)
;; see website for derivation of this formula.
;; http://www.shout.net/~mathman/html/prob9a.html


;; need this to compute factorial.  I'll write it tail recursively
(define !
  (lambda (n)
    (let loop ([acc 1] [n n])
      (if (zero? n)
	  acc
	  (loop (* n acc) (sub1 n))))))

(define pascal-smart
  (lambda (row col)
    (if (> col row)
	(error 'pascal-smart "Column (~s) is bigger than row (~s)!" col row)
	(/ (! row)
	   (* (! col)
	      (! (- row col)))))))


;; some test results:

;> (time (pascal 25 10))
;(time (pascal 25 ...))
;    272 collections
;    9710 ms elapsed cpu time, including 140 ms collecting
;    9800 ms elapsed real time, including 150 ms collecting
;    292911312 bytes allocated, including 293339288 bytes reclaimed
;3268760
;> (time (pascal-cached 25 10))
;(time (pascal-cached 25 ...))
;    no collections
;    0 ms elapsed cpu time
;    0 ms elapsed real time
;    20952 bytes allocated
;3268760
;> (time (pascal-smart 25 10))
;(time (pascal-smart 25 ...))
;    no collections
;    0 ms elapsed cpu time
;    0 ms elapsed real time
;    576 bytes allocated
;3268760
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;> (time (pascal 30 15))
;(time (pascal 30 ...))
;    12657 collections
;    446780 ms elapsed cpu time, including 3650 ms collecting
;    454230 ms elapsed real time, including 3560 ms collecting
;    13651842688 bytes allocated, including 13651328984 bytes reclaimed
;155117520
;> (time (pascal-cached 30 15))
;(time (pascal-cached 30 ...))
;    1 collection
;    0 ms elapsed cpu time, including 0 ms collecting
;    0 ms elapsed real time, including 0 ms collecting
;    31216 bytes allocated, including 1078600 bytes reclaimed
;155117520
;> (time (pascal-smart 30 15))
;(time (pascal-smart 30 ...))
;    no collections
;    0 ms elapsed cpu time
;    0 ms elapsed real time
;    824 bytes allocated
;155117520

;; OUCH

;> (time (pascal-cached 1500 700))
;(time (pascal-cached 1500 ...))
;    123 collections
;    7860 ms elapsed cpu time, including 3750 ms collecting
;    7920 ms elapsed real time, including 3750 ms collecting
;    127864464 bytes allocated, including 79867888 bytes reclaimed
;2576676215[...]54211175140
;> (time (pascal-smart 1500 700))
;(time (pascal-smart 1500 ...))
;    2 collections
;    70 ms elapsed cpu time, including 20 ms collecting
;    70 ms elapsed real time, including 20 ms collecting
;    2042128 bytes allocated, including 1658600 bytes reclaimed
;2576676215[...]54211175140

;; Significantly better, no?  Less space, much faster.
;; I cut the middle digits out of the huge resulting 448 digit number.
;; Based on the implementation of !, it can even get better!
(define !
  (lambda (n)
    (fact n (lambda (v) v))))

(define fact
  (lambda (n k)
    (if (zero? n)
	(k 1)
	(fact (sub1 n) (lambda (v) (k (* n v)))))))

;> (time (pascal-smart 1500 700))
;(time (pascal-smart 1500 ...))
;    2 collections
;    60 ms elapsed cpu time, including 10 ms collecting
;    60 ms elapsed real time, including 10 ms collecting
;    1828712 bytes allocated, including 2440816 bytes reclaimed

;;And once again as a pseudo y-combinator

(define !
  (lambda (n)
    ((fact fact) n)))

(define fact
  (lambda (proc)
    (lambda (n)
      (if (zero? n)
	  1
	  (* n ((proc proc) (sub1 n)))))))

;> (time (pascal-smart 1500 700))
;(time (pascal-smart 1500 ...))
;    1 collection
;    50 ms elapsed cpu time, including 0 ms collecting
;    50 ms elapsed real time, including 0 ms collecting
;    1813496 bytes allocated, including 1120440 bytes reclaimed

;; This was the fastest I tested.  Trampolining didn't help and it shouldn't.	

;; All my tests were run on a SunBlade 150