sicp-ex-3.81



<< Previous exercise (3.80) | Index | Next exercise (3.82) >>


meteorgan

  
  
  
  
 (define (random-update x) 
         (remainder (+ (* 13 x) 5) 24)) 
 (define random-init (random-update (expt 2 32))) 
  
 ;; assume the operation 'generator and 'reset is a stream,  
 ;; and if the command is 'generator, the element of 
 ;; stream is a string, if the command is 'reset,  
 ;; it is a pair whose first element is 'reset,  
 ;; the other element is the reset value. 
 (define (random-number-generator command-stream) 
         (define random-number 
                 (cons-stream random-init 
                                 (stream-map (lambda (number command)  
                                                                 (cond ((null? command) the-empty-stream) 
                                                                           ((eq? command 'generator) 
                                                                            (random-update number)) 
                                                                           ((and (pair? command)  
                                                                                    (eq? (car command) 'reset)) 
                                                                            (cdr command)) 
                                                                           (else  
                                                                              (error "bad command -- " commmand)))) 
                                                          random-number 
                                                          command-stream))) 
         random-number) 
  

hi-artem

  I think this code has a bug:
  First element in generated stream is always the same - "random-init", even  if command stream started with  'reset OTHER_NUMBER'

mathieuborderé

  
  
  
 (define (rand-generator commands) 
   (define (rand-helper num remaining-commands) 
     (let ((next-command (stream-car remaining-commands))) 
       (cond ((eq? next-command 'generate) 
              (cons-stream num 
                           (rand-helper (rand-update num) 
                                        (stream-cdr remaining-commands)))) 
             ((pair? next-command) 
              (if (eq? (car next-command) 'reset) 
                  (cons-stream (cdr (stream-car remaining-commands)) 
                      (rand-helper (rand-update (cdr (stream-car remaining-commands))) 
                                   (stream-cdr remaining-commands))) 
                  (error "bad command -- " next-commmand))) 
             (else (error "bad command -- " next-commmand))))) 
   (rand-helper rand-init commands)) 
  
 ;;; testing 
  
 ;;; generate stream of commands 
 (define gen-stream  
   (cons-stream  
     (cons 'reset 12) 
     (cons-stream 'generate 
                  (cons-stream (cons 'reset 100) 
                               (cons-stream 'generate 
                                            gen-stream))))) 
  
 (define rands (rand-generator gen-stream)) 
  
 (stream-ref rands 0) 
 (stream-ref rands 1) 
 (stream-ref rands 2) 
 (stream-ref rands 3) 
 (stream-ref rands 4) 
 (stream-ref rands 5) 
  
 ;output: 
  
 ;(stream-ref rands 0) 
 ;Value: 12 
  
 ;(stream-ref rands 1) 
 ;Value: 1033878523 
  
 ;(stream-ref rands 2) 
 ;Value: 100 
  
 ;(stream-ref rands 3) 
 ;Value: 1180356723 
  
 ;(stream-ref rands 4) 
 ;Value: 12 
  
 ; (stream-ref rands 5) 
 ;Value: 1033878523 
  

karthikk

Here is a different solution from mathiebordere's that separates the dispatch on message from the stream construction:

 (define (random-numbers continue-val input-stream) 
   (define (constructor start-val) 
     (cons-stream start-val 
                  (random-numbers (rand-update start-val) 
                                  (stream-cdr input-stream)))) 
   (if (stream-null? input-stream) 
       'done 
       (let ((msg (stream-car input-stream))) 
         (cond ((eq? msg 'generate) 
                (constructor continue-val)) 
               ((and (pair? msg)(eq? (car msg) 'reset)(number? (cadr msg))) 
                (constructor (cadr msg))) 
               (else 
                (error "Invalid message found in input-stream" msg)))))) 
  

frostoov

Here is my solution

  
 (define (random-generator requests seed) 
   (define s 
     (cons-stream 
      seed 
      (stream-map 
       (lambda (request value) 
         (cond ([eq? request 'generate] (rand-update value)) 
               ([and (pair? request) (eq? (car request) 'reset)] 
                (cdr request)) 
               (else (error "random-generator invalid request")))) 
       requests 
       s))) 
   s) 
  

awkravchuk

It's also possible to store the reset values along with the commands. Here's (Racket-based) proof-of-concept:

 (define (random-numbers actions seed) 
     (let ((action (stream-car actions)) 
           (rest-actions (stream-cdr actions))) 
         (cond ((eq? action 'generate) 
                 (begin 
                     (random-seed (inexact->exact (floor (* 1000 seed)))) 
                     (let ((random-number (random))) 
                         (cons-stream 
                          random-number 
                          (random-numbers rest-actions random-number))))) 
               ((eq? action 'reset) 
                (random-numbers 
                 (stream-cdr rest-actions) 
                 (stream-car rest-actions))) 
               (else (error "Unknown action"))))) 
  
 (define test-actions 
     (cons-stream 'reset (cons-stream 100 (cons-stream 'generate (cons-stream 'generate (cons-stream 'reset (cons-stream 100 (cons-stream 'generate (cons-stream 'generate (cons-stream 'reset (cons-stream 200 (cons-stream 'generate (cons-stream 'generate nil))))))))))))) 
  
 (define stream (random-numbers test-actions 0)) 
  
 (stream-ref stream 0)  ;; 0.46989804756333914 
 (stream-ref stream 1)  ;; 0.2932693988550536 
 (stream-ref stream 2)  ;; 0.46989804756333914, reset to the same seed 
 (stream-ref stream 3)  ;; 0.2932693988550536 
 (stream-ref stream 4)  ;; 0.7791954700538558, reset to different seed 
 (stream-ref stream 5)  ;; 0.16903652324331853 
  

xdavidliu

The purpose of this exercise is to generate a stream of random numbers upon given a stream of *requests*, where each element of input request stream is either 'generate or (list request x), where x is some given number.

 (define (rand-update x) 
   (modulo (+ 101 (* x 713)) 53)) 
 ;; for much better parameters to use here, see 
 ;; https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use 
  
 (define random-init (rand-update 10)) 
  
 (define (random-request-generator requests) 
   (define (update x request) 
     (cond ((eq? request 'generate) 
            (rand-update x)) 
           ((and (pair? request) 
                 (eq? (car request) 'reset) 
                 (number? (cadr request))) 
            (cadr request)) 
           (else (error "invalid request" request)))) 
   (define requested-stream 
     (cons-stream 
      random-init 
      (stream-map update requested-stream requests))) 
   requested-stream) 
  
 (define example-requests 
   (list->stream 
     '(generate generate generate (reset 5) 
       generate generate (reset 5) generate))) 
  
 (stream->list (random-request-generator example-requests)) 
 ;; -> (23 17 32 21 5 9 52 5 9)