;;; =========================
;;;  CMPU-145, Spring 2013
;;;  Lab 10 Solutions!!
;;;  April 29, 2013
;;; -------------------------
;;;  Biased Coin Tosser

(load "asmt5-helper.txt")

(header "Lab 10 -- Biased Coin Tosser" "April 29, 2013")

;;; =============================================================
(problem "1A:  BIASED-TOSSER")
;;; =============================================================

;;;  BIASED-TOSSER
;;; --------------------------------------
;;;  INPUT:  A list of binary digits (zeroes and ones), representing
;;;            some real number B in the interval between 0 and 1
;;;  OUTPUT:  1 or 0, randomly selected to simulate the
;;;    tossing of a biased coin where the probability of HEADS (i.e., 1)
;;;    is equal to B.
;;; --------------------------------------
;;;  Use (RANDOM 2) to simulate the repeated tossing of a fair coin.
;;;  As long as the random coin tosses (0s or 1s) exactly match the
;;;    contents of LISTY, keep tossing.  
;;;      NOTE:  If LISTY empty, it represents an infinitely long list of zeros
;;;  As soon as the random coin toss deviates from the contents of LISTY,
;;;    make the Heads/Tails determination, as follows:
;;;    If tossed a 1, when LISTY showed a 0 (or LISTY empty), return 0 for TAILS
;;;    Otherwise, return 1 for HEADS.

(define biased-tosser
  (lambda (listy)
    (cond
      ;; Case 1:  LISTY is empty (i.e., all the rest of the
      ;;          digits are zero)
      ((null? listy)
       ;; Since the fair coin would eventually come out with a 1,
       ;; which would not match the unending list of 0s, we would
       ;; eventually have to report TAILS.  So, might as well do it now:
       0)
      ;; Case 2:  Need to toss the fair coin at least one more time
      (#t
       (let (;; RND-DIGIT:  A random toss of a coin
             (rnd-digit (random 2))
             ;; LISTY-DIGIT:  The next digit in the bias fraction
             (listy-digit (first listy)))
         (cond
           ;; Recursive Case:  RND-DIGIT matches first digit in LISTY
           ((= rnd-digit listy-digit)
            ;; So keep tossing using (REST LISTY)
            (biased-tosser (rest listy)))
           ;; Base Case 1:  RND-DIGIT is a ZERO (and thus LISTY-DIGIT = 1)
           ((zero? rnd-digit)
            ;; Thus, the number we have randomly selected is < B
            ;; So we tossed HEADS!
            1)
           ;; Base Case 2:  RND-DIGIT is a 1 (and LISTY-DIGIT is 0)
           (#t
            ;; Tails!
            0)))))))

(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))
(tester '(biased-tosser '(1 0 1)))

;;; =============================================================
(problem "1B:  BIAS-5-8, BIAS-3-4, BIAS-1-8, IS-ONE?")
;;; =============================================================

;;;  The LISTs of binary digits for some common fractions

(define listy-three-quarters '(1 1))
(define listy-five-eighths '(1 0 1))
(define listy-almost-one-third '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1))

;;;  The following "generate" functions take NO inputs
;;;  and generate an output that is either 0 or 1 with the
;;;  desired bias.

;;;  BIAS-5-8:  bias = 5/8

(define bias-5-8
  (lambda ()
    (biased-tosser listy-five-eighths)))

;;;  BIAS-3-4:  bias = 3/4

(define bias-3-4
  (lambda ()
    (biased-tosser listy-three-quarters)))

;;;  BIAS-1-3:  bias = 1/3 (approx.)

(define bias-1-3
  (lambda ()
    (biased-tosser listy-almost-one-third)))

;;;  IS-ONE?
;;; -----------------------------
;;;  INPUT:  NUM, a number
;;;  OUTPUT:  #t if NUM = 1; #f otherwise.

(define is-one?
  (lambda (num)
    (= num 1)))

(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))
(tester '(bias-3-4))

;;; =============================================================
(problem "1C: Using GEN-AND-TEST to test BIASED-TOSSER")
;;; =============================================================

(tester '(gen-and-test 10000 bias-5-8 is-one?))
(tester '(gen-and-test 10000 bias-3-4 is-one?))
(tester '(gen-and-test 10000 bias-1-3 is-one?))
(newline)

(define mystery '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0))
(define mystery-two '(0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1))
(define listy-half '(1))

(tester '(gen-and-test 1000000
                       (lambda () (biased-tosser mystery)) 
                       is-one?))
(newline)
(tester '(gen-and-test 1000000 
                       (lambda () (biased-tosser mystery-two)) 
                       is-one?))
(newline)
(tester '(gen-and-test 100000 
                       (lambda () (biased-tosser listy-half)) 
                       is-one?))

;;; =============================================================
(problem "2:  Expected Number of Tosses for Biased-Tosser")
;;; =============================================================

;;;  BIASED-COUNTER
;;; -------------------------------
;;;  INPUT:  LISTY, a list of 1s and 0s representing a fraction in binary
;;;  OUTPUT:  The number of coin tosses (i.e., 1s and 0s) that were
;;;    required to generate the first deviation from the sequence of
;;;    1s and 0s in LISTY.

(define biased-counter
  (lambda (listy)
    ;;; Just call a helper function with a counter initialized to 0
    (biased-counter-helper listy 0)))
  
;;;  BIASED-COUNTER-HELPER
;;; -------------------------------
;;;  INPUTS:  LISTY, as above
;;;           CTR, a counter
;;;  OUTPUT:  As above.

(define biased-counter-helper
  (lambda (listy ctr)
    (cond
      ;; Case 1:  LISTY is empty
      ((null? listy)
       ;; So we don't need to toss our fair coin any more:  return CTR
       ctr)
      ;; Case 2:  LISTY non-empty:  need to toss at least one more time
      (#t
       (let (;; RND-DIGIT:  A random coin toss
             (rnd-digit (random 2))
             ;; LISTY-DIGIT:  The next digit in the bias fraction
             (listy-digit (first listy)))
         (cond
           ;; Recursive Case:  RND-DIGIT matches LISTY-DIGIT
           ((= rnd-digit listy-digit)
            ;; So keep tossing using (REST LISTY) (or () if LISTY is empty)
            (biased-counter-helper (rest listy)
                                   (+ ctr 1)))
           ;; Base Case:  RND-DIGIT does NOT match,
           (#t
            ;; So we're done... but need to return (+ 1 CTR)
            ;; because we DID just toss the die!
            (+ ctr 1))))))))
    
;;; Use DOTIMES to average the output values returned by a large number
;;; of calls to BIASED-COUNTER.  This function was copy-and-pasted from
;;; lab10.txt.

(define estimate-biased-counter-exp-value
  (lambda (n listy)
    (let ((acc 0))
      (dotimes (i n)
               (set! acc (+ acc (biased-counter listy))))
      (/ acc n 1.0))))

(tester '(estimate-biased-counter-exp-value 100000 listy-three-quarters))
(tester '(estimate-biased-counter-exp-value 100000 listy-five-eighths))
(tester '(estimate-biased-counter-exp-value 100000 listy-almost-one-third))
(printf "Notice that the expected number of tosses gets closer to two as the length of LISTY gets longer~%"