;;; implementation-specific comments have been removed from the code
;;; and some simplifications have been made for the sake of
;;; brevity. i'll be glad to explain how it all works as well as any
;;; known bugs, issues, and tradeoffs at the interview.  :-)
;;;
;;; the point of the code was to explore the `stream' concept of
;;; programming.  the verbosity is due to the fact that we are working
;;; at a low level of expressivity w.r.t. the problem.  compare, for
;;; example, to the one line solution (without streams) one can
;;; formulate in a language, such as Mathematica, with pre-existing
;;; primitives to compute e and manipulate high-precision numbers.
;;;
;;; this code has been tested on Guile, the GNU Scheme interpreter and
;;; implicitly uses bignums to provide the required precision.

;;; returns an infinite stream of factorials.
(define (factorial-stream)
  (define (helper factorial factor)
    (let ((next-factorial (* factorial factor))
          (next-factor    (+ 1 factor)))
      (cons-stream next-factorial (helper next-factorial next-factor))))
  (helper 1 1))

;;; returns an infinite stream of quotients.
(define (quotient-stream numerator denominator-stream)
  (if (null? denominator-stream)
      denominator-stream
      (cons-stream (quotient numerator (head denominator-stream))
                   (quotient-stream numerator (tail denominator-stream)))))

;;; construct a stream of the digits of e with the given maximum
;;; precision based on the classic formula:
;;; e = 1 + 1/1! + 1/2! + 1/3! + ...
;;; naturally, e-stream uses a quotient-of-factorial-stream for the
;;; calculation.
(define (e-stream max-number-of-digits)
  (let ((one (expt 10 (+ max-number-of-digits 1))))
    (define (helper e digit fquotients)
      (if (> digit max-number-of-digits) 
          '()
          (let ((digit-magnitude (/ one (expt 10 (- digit 1))))
                (fquotient       (head fquotients)))
            (if (> (quotient digit-magnitude fquotient) 100)
                (cons-stream (quotient e digit-magnitude) 
                             (helper (remainder e digit-magnitude) (+ 1 digit) fquotients))
                (helper (+ e fquotient) digit (tail fquotients))))))
    (helper one 1 (quotient-stream one (factorial-stream)))))

;;; takes a stream of 1-digits and returns a stream of 10-digits (the
;;; 1-digits followed by their 9-consecutives)
(define (ten-consecutive-digits-stream stream)
  (n-consecutive-digits-stream 10 stream))

;;; note: assumes stream is infinite.
(define (n-consecutive-digits-stream n stream)
  (define (helper stream lizt)
    (cons-stream (list-to-number lizt) 
                 (helper (tail stream) (append (cdr lizt) (list (head stream))))))
  (helper (nthtail n stream) (stream-to-list stream n)))

;;; note: assumes stream is infinite.
(define (stream-to-list stream number-of-elements)
  (define (iterate stream number-of-elements list)
    (if (zero? number-of-elements)
        list
        (iterate (tail stream) (- number-of-elements 1) (cons (head stream) list))))
  (reverse (iterate stream number-of-elements '())))

;;; (1 2 3 4) becomes 1234
(define (list-to-number list)
  (reduce (lambda (x y) (+ (* x 10) y)) 0 list))

(define (nthtail n stream)
  (if (zero? n)
      stream
      (nthtail (- n 1) (tail stream))))

;;; returns true if the digits of number add up to 49
(define (sum-49? number)
  (sum-n? 49 number))

(define (sum-n? n number)
  (= n (sum-digits number)))

;;; finds the sum of the digits of n
(define (sum-digits n)
  (define (helper qtient sum)
    (if (zero? qtient)
        sum
        (helper (quotient qtient 10) (+ sum (remainder qtient 10)))))
  (helper n 0))

;;; from SICP
(define (prime? n)
  (define (square x) (* x x))
  (define (divides? a b)
    (= (remainder b a) 0))
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (+ test-divisor 1)))))
  (define (smallest-divisor n)
    (find-divisor n 2))
  (= n (smallest-divisor n)))

;;; from slib, stream primitive
(defmacro cons-stream ( . args)
  `(cons ,(car args) (delay ,(cadr args))))

;;; stream primitive
(define head car)

;;; stream primitive
(define (tail stream) (force (cdr stream)))

;;; stream util
(define (filter-stream pred? stream)
  (cond ((null? stream) stream)
        ((pred? (head stream))
         (cons-stream (head stream)
                      (filter-stream pred? (tail stream))))
        (else (filter-stream pred? (tail stream)))))

;;; list util
(define (reduce function base list)
  (if (null? list)
      base
      (reduce function (function base (car list)) (cdr list))))

;;; The Solution!
(define ten-e-stream (ten-consecutive-digits-stream (e-stream 10000)))
(define prime-stream (filter-stream prime? ten-e-stream))
(define sum-49-stream (filter-stream sum-49? ten-e-stream))

(display "primes:  ")
(display (stream-to-list prime-stream 5))
(newline)
(display "sum 49s: ")
(display (stream-to-list sum-49-stream 5))
(newline)