sicp exercise 3.75

;; Exercise 3.75.  Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:

;(define (make-zero-crossings input-stream last-value)
;  (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
;    (cons-stream (sign-change-detector avpt last-value)
;                 (make-zero-crossings (stream-cdr input-stream)
;                                      avpt))))

;This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to make-zero-crossings.)


(define (make-zero-crossings input-stream last-value last-avg-value)
  (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
    (cons-stream (sign-change-detector avpt last-avg-value)
                 (make-zero-crossings (stream-cdr input-stream)
                                      (stream-car input-stream) avpt))))

sicp exercise 3.74

;;Exercise 3.74.  Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be

; ...1  2  1.5  1  0.5  -0.1  -2  -3  -2  -0.5  0.2  3  4 ......
;    0  0    0  0    0     -1  0   0   0     0    1  0  0 ...

;In Alyssa's system, the signal from the sensor is represented as a stream sense-data and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:

;(define (make-zero-crossings input-stream last-value)
;  (cons-stream
;   (sign-change-detector (stream-car input-stream) last-value)
;   (make-zero-crossings (stream-cdr input-stream)
;                        (stream-car input-stream))))
;
;(define zero-crossings (make-zero-crossings sense-data 0))

;Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50:

;(define zero-crossings
;  (stream-map sign-change-detector sense-data <expression>))

;Complete the program by supplying the indicated <expression>.


(define zero-crossings
  (stream-map sign-change-detector sense-data (cons-stream 0 sense-data)))

sicp exercise 3.73

;; Exercise 3.73. 

;;         v = v0 + (1/C)0ti dt + R i     




;;Figure 3.33:  An RC circuit and the associated signal-flow diagram.

;;We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an RC circuit consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in figure 3.33, whose structure is shown by the accompanying signal-flow diagram.

;;Write a procedure RC that models this circuit. RC should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v0 and produces as output the stream of voltages v. For example, you should be able to use RC to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating (define RC1 (RC 5 1 0.5)). This defines RC1 as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages.

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (integral integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (add-streams (scale-stream integrand dt)
                              int)))
  int)

(define (RC R C dt)
  (lambda(i v0)
    (add-stream (scale-stream i R)
                (integral (scale-stream i (/ 1 C)) v0 dt))))

(define RC1 (RC 5 1 0.5))

sicp exercise 3.72

; Exercise 3.72.  In a similar way to exercise 3.71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written).


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))

(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< (weight s1car) (weight s2car))
                  (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))
                 (else
                  (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (f1 s t)
  (cons-stream (list (stream-car s) (stream-car t))
               (f1 s (stream-cdr t))))
(define (f0 s t weight)
  (cons-stream (list (stream-car s) (stream-car t))
               (merge-weighted (f1 s (stream-cdr t))
                               (f0 (stream-cdr s) (stream-cdr t) weight)
                               weight)))
(define (weighted-pairs s t weight) (f0 s t weight))

(define (square x)(* x x))
(define square-weighted-pairs (weighted-pairs integers integers (lambda(s)(+ (square (car s)) (square (cadr s))))))
;(display-stream square-weighted-pairs 50)

(define (check-eq-weight s weight)
  (let ((a (stream-car s))
        (b (stream-car (stream-cdr s)))
        (c (stream-car (stream-cdr (stream-cdr s)))))
    (if (and (= (weight a) (weight b))
             (= (weight b) (weight c)))
        (cons-stream (list (weight a) a b c)
                     (check-eq-weight (stream-cdr s) weight))
        (check-eq-weight (stream-cdr s) weight))))

(define result (check-eq-weight square-weighted-pairs (lambda(s)
                                                        (+ (square (car s))
                                                           (square (cadr s))))))

(display-stream result 4)

;Loading "sicp_prob_03.72.scm"...
;(325 (10 15) (6 17) (1 18))
;(425 (13 16) (8 19) (5 20))
;(650 (17 19) (11 23) (5 25))
;(725 (14 23) (10 25) (7 26))
;(845 (19 22) (13 26) (2 29))
;... done

sicp exercise 3.71

;; Exercise 3.71.  Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i3 + j3 (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))

(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< (weight s1car) (weight s2car))
                  (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))
                 (else
                  (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (f1 s t)
  (cons-stream (list (stream-car s) (stream-car t))
               (f1 s (stream-cdr t))))
(define (f0 s t weight)
  (cons-stream (list (stream-car s) (stream-car t))
               (merge-weighted (f1 s (stream-cdr t))
                               (f0 (stream-cdr s) (stream-cdr t) weight)
                               weight)))
(define (weighted-pairs s t weight) (f0 s t weight))

(define (cube x)(* x x x))
(define cube-weighted-pairs (weighted-pairs integers integers (lambda(s)(+ (cube (car s)) (cube (cadr s))))))
;(display-stream cube-weighted-pairs 20)

(define (check-eq-weight s weight)
  (let ((a (stream-car s))
        (b (stream-car (stream-cdr s))))
    (if (= (weight a) (weight b))
        (cons-stream (list (weight a) a b)
                     (check-eq-weight (stream-cdr s) weight))
        (check-eq-weight (stream-cdr s) weight))))

(define ramanujan-numbers (check-eq-weight cube-weighted-pairs (lambda(s)
                                                                 (+ (cube (car s))
                                                                    (cube (cadr s))))))

(display-stream ramanujan-numbers 4)

;Loading "sicp_prob_03.71.scm"...
;(1729 (9 10) (1 12))
;(4104 (9 15) (2 16))
;(13832 (18 20) (2 24))
;(20683 (19 24) (10 27))
;(32832 (18 30) (4 32))
;... done

sicp exercise 3.70

;Exercise 3.70.  It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i1,j1) is less than (i2,j2) if W(i1,j1) < W(i2,j2). Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.69 Using this, generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate

; a. the stream of all pairs of positive integers (i,j) with i < j ordered according to the sum i + j

; b. the stream of all pairs of positive integers (i,j) with i < j, where neither i nor j is divisible by 2, 3, or 5, and the pairs are ordered according to the sum 2 i + 3 j + 5 i j.


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))

(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< (weight s1car) (weight s2car))
                  (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))
                 (else
                  (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))

(define (f1 s t)
  (cons-stream (list (stream-car s) (stream-car t))
               (f1 s (stream-cdr t))))
(define (f0 s t weight)
  (cons-stream (list (stream-car s) (stream-car t))
               (merge-weighted (f1 s (stream-cdr t))
                               (f0 (stream-cdr s) (stream-cdr t) weight)
                               weight)))
(define (weighted-pairs s t weight) (f0 s t weight))

(display-stream (weighted-pairs integers integers (lambda(s)(+ (car s) (cadr s)))) 20)

(define (div-by x y)(= 0 (remainder x y)))
(define integers-not-div-by-2-3-5
  (stream-filter (lambda(x)
                   (not (or (div-by x 2)
                            (div-by x 3)
                            (div-by x 5))))
                 integers))

;(display-stream integers-not-div-by-2-3-5 20)

(define result (weighted-pairs integers-not-div-by-2-3-5
                               integers-not-div-by-2-3-5
                               (lambda(s)
                                 (let ((i (car s))
                                       (j (cadr s)))
                                   (+ (* 2 i)
                                      (* 3 j)
                                      (* 5 i j))))))

(display-stream result 20)

;Loading "sicp_prob_03.70.scm"...
;(1 1)
;(1 2)
;(2 2)
;(1 3)
;(2 3)
;(1 4)
;(3 3)
;(2 4)
;(1 5)
;(3 4)
;(2 5)
;(1 6)
;(4 4)
;(3 5)
;(2 6)
;(1 7)
;(4 5)
;(3 6)
;(2 7)
;(1 8)
;(5 5)

;(1 1)
;(1 7)
;(1 11)
;(1 13)
;(1 17)
;(1 19)
;(1 23)
;(1 29)
;(1 31)
;(7 7)
;(1 37)
;(1 41)
;(1 43)
;(1 47)
;(1 49)
;(1 53)
;(7 11)
;(1 59)
;(1 61)
;(7 13)
;(1 67)
;... done

sicp exercise 3.69

; Exercise 3.69.  Write a procedure triples that takes three infinite streams, S, T, and U, and produces the stream of triples (Si,Tj,Uk) such that i < j < k. Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i < j and i^2 + j^2 = k^2.

(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)(internal 0))

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))


;; another way to construct all pairs <i,j>, same as produces in exercise 67
;; the same idea is being used to produce triples below
(define (incr1 s t)
  (cons-stream (list (stream-car s) (stream-car t)) (incr1 (stream-cdr s) t)))
(define (incr2 s t)
  (cons-stream (list (stream-car s) (stream-car t)) (incr2 s (stream-cdr t))))
(define (pair2 s t)
  (cons-stream (list (stream-car s)
                     (stream-car t))
               (interleave (incr2 s (stream-cdr t))
                           (interleave (incr1 (stream-cdr s) t)
                                       (pair2 (stream-cdr s) (stream-cdr t))))))
;;(newline)
;;(display-stream (pair2 integers integers) 20)


(define (f1 s t u)
  (cons-stream (list (stream-car s)
                     (stream-car t)
                     (stream-car u))
               (f1 s t (stream-cdr u))))

(define (f2 s t u)
  (cons-stream (list (stream-car s)
                     (stream-car t)
                     (stream-car u))
               (interleave (f1 s t (stream-cdr u))
                           (f2 s (stream-cdr t) (stream-cdr u)))))

(define (f0 s t u)
  (cons-stream (list (stream-car s)
                     (stream-car t)
                     (stream-car u))
               (interleave (f1 s t (stream-cdr u))
                           (interleave (f2 s (stream-cdr t) (stream-cdr u))
                                       (f0 (stream-cdr s)
                                           (stream-cdr t)
                                           (stream-cdr u))))))

(define triples (f0 integers integers integers))

;(newline)
;(display-stream triples 20)

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (pythagorean? p)
  (= (+ (square (car p))
        (square (cadr p)))
     (square (caddr p))))

(display-stream (stream-filter pythagorean? triples) 2)

;; Output:
;Loading "sicp_prob_03.69.scm"...
;(3 4 5)
;(6 8 10)
;(5 12 13)
;... done