;;; ========================
;;;  CMPU-145, Spring 2013
;;;  Asmt. 6 Solutions
;;; ========================

(load "asmt6-helper.txt")

(header "Asmt. 6" "Solutions!")

;;; =============================================================
;;;  1.  ROLLING 5 DICE and GETTING EXACTLY TWO PAIR
;;; =============================================================

(problem "1:  Rolling 5 dice and getting exactly two pair!")

;;; *NUM-WAYS-OF-GETTING-2-PAIR* -- number of ways of getting two-pair
;;;      when tossing 5 dice at random

(define *num-ways-of-getting-2-pair*
  (* 5                ;; Choose slot holding singleton
     (n-choose-k 4 2) ;; Choose pair of slots for one pair
                      ;;   This also determines the slots for the other pair
     (n-choose-k 6 2) ;; Choose numerical values for the two pairs
     4                ;; Choose numerical value for the singleton
     ))

;;;  Example:  Suppose you choose the 3rd slot for the singleton
;;;            and the 1st and 4th slots for one pair.  That
;;;     leaves slots 2 and 5 for the other pair:  X Y Z X Y.
;;;     Now, suppose you choose 5 and 3 for the values of the pairs;
;;;     and suppose that 4 is the value for the singleton.
;;;     Which is the "first pair"?  It doesn't matter.  Suppose 5
;;;     is the first pair.  Then we have 5 6 4 5 6.  You might wonder,
;;;     What about 6 5 4 6 5?  That will be taken care of when slots
;;;     2 and 5 are chosen for the "first pair", leaving slots 1 adn 4
;;;     for the other pair.

;;;    Alternatively:  Think of 4-choose-2 choices for slots for
;;;    the first pair; but need to divide by 2 to avoid double-counting.
;;;    Then there are 6*5 choices for the dice values for the first
;;;    and second pairs.  But this gives the same answer.

;;;  *NUM-WAYS-OF-ROLLING-5-DICE*

(define *num-ways-of-rolling-5-dice*
  (expt 6 5))  ;; 6 choices for each die:  6*6*6*6*6

;;;  *PROB-GETTING-2-PAIR-IN-5-DICE* -- probability of getting 2-pair
;;;     when rolling 5 dice at random

(define *prob-getting-2-pair-in-5-dice*
  (/ *num-ways-of-getting-2-pair*
     *num-ways-of-rolling-5-dice*
     1.0))

(tester '*num-ways-of-getting-2-pair*)
(tester '*num-ways-of-rolling-5-dice*)
(tester '*prob-getting-2-pair-in-5-dice*)

;;;  ROLL-ONE
;;; -----------------------
;;;  INPUTS:  none
;;;  OUTPUT:  A randomly generated number from 1 to 6

(define roll-one
  (lambda ()
    (+ 1 (random 6))))

;;;  ROLL-5-DICE
;;; -----------------------------------
;;;  INPUTS:  None
;;;  OUTPUT:  A list containing 5 randomly generated numbers,
;;;    each in the range from 1 to 6.

(define roll-5-dice
  (lambda ()
    (list (roll-one) (roll-one) (roll-one) (roll-one) (roll-one))))

(newline)
(tester '(roll-5-dice))
(tester '(roll-5-dice))
(tester '(roll-5-dice))

;;;  HAS-2-PAIR?
;;; -------------------------------------------
;;;  INPUT:  DICE, a list of 5 dice values
;;;  OUTPUT:  #t if the input list has exactly 2 pair (nothing more);
;;;           #f otherwise.

(define has-2-pair?
  (lambda (dice)
    ;; Again, we use a sorted histogram...
    (let* ((dice-histy (get-histy dice))
           (sorted-dice-histy (sort dice-histy <=))
           (no-zeroes-sorted-dice-histy (remove-all 0 sorted-dice-histy)))
      (equal? '(1 2 2)
              no-zeroes-sorted-dice-histy))))

(newline)
(tester '(has-2-pair? '(1 2 3 2 1)))
(tester '(has-2-pair? '(2 2 3 3 4)))
(tester '(has-2-pair? '(5 2 3 4 3)))

(newline)
(tester '(gen-and-test 100000 roll-5-dice has-2-pair?))

;;; ===============================================
(problem "2:  Powerball Expected Winnings")
;;; ===============================================

;;;  *PB-PAYOFFS* -- the payoffs for the game of powerball
;;; -------------------------------------------------------
;;;  Events:  5+PB, 5, 4+PB, 4, 3+PB, 3, 2+PB, 1+PB, 1

(define *pb-payoffs*
  '(200000000 1000000 10000 100 100 7 7 4 4))

;;;  NOTE:  54 of the 59 numbers do NOT match 
;;;         34 of the 35 numbers do NOT match the chosen powerball

;;;  *PB-NUM-OUTCOMES*  -- The outcomes for the various kinds of
;;;      winning tickets in powerball.

(define *pb-num-outcomes*
  (list ;; 5 + powerball
        1
        ;; 5 - powerball
        34 ;; there are 34 Non-Matching powerball numbers
        ;; 4 + powerball
        (* 5   ;; pick one of the 5 numbers *NOT* to match
           54  ;; pick one of the 54 non-matching numbers
           )
        ;; 4 - powerball
        (* 5
           54
           34  ;; same as above, but 34 choices for non-matching pb number
           )
        ;; 3 + powerball
        (* (n-choose-k 5 2) ;; pick 2 of 5 numbers NOT to match
           (n-choose-k 54 2) ;; pick values for those non-matchers
           )
        ;; 3 - powerball
        (* (n-choose-k 5 2)
           (n-choose-k 54 2)
           34 ;; same as above, but 34 choices for non-matching pb
           )
        ;; 2 + powerball
        (* (n-choose-k 5 3) ;; pick 3 of 5 nums NOT to match
           (n-choose-k 54 3) ;; pick values for those non-matchers
           )
        ;; 1 + powerball
        (* (n-choose-k 5 4) ;; pick 4 of 5 nums NOT to match
           (n-choose-k 54 4) ;; pick values for those non-matchers
           )
        ;; 0 + powerball
        (* (n-choose-k 54 5) ;; choose 5 non-matching numbers
           )))

;;;  *NUM-PB-TIX*  --  The number of distinct tickets in powerball

(define *num-pb-tix* (* 35 ;; num choices for powerball
                        (n-choose-k 59 5) ;; num choices for 5 numbers out of 59 
                        ))
(tester '*num-pb-tix*)

;;;  *PB-PROBABILITIES*  -- The probabilities for each of the winning
;;;     events in powerball.

(define *pb-probabilities*
  ;; Divide each entry in *PB-NUM-OUTCOMES* by *NUM-PB-TIX*
  (map (lambda (num-outcomes)
         (/ num-outcomes
            *num-pb-tix*
            1.0 ;; <--- force the number to be in "floating point notation"
            ))
       *pb-num-outcomes*))

;;;  *PB-ODDS*  --  The "odds" of various kinds of wins in powerball
;;; ------------------------------------------------------------------
;;;  NOTE:  The "odds" of a particular event are expressed as "1 in X"
;;;          where X is simply one-over-the-probability.  

(define *pb-odds*
  (map (lambda (p)
         (round (/ 1.0 p)))
       *pb-probabilities*))


(tester-show-list '*pb-payoffs*)

(tester-show-list '*pb-num-outcomes*)

(tester-show-list '*pb-probabilities*)

(tester-show-list '*pb-odds*)

(define *pb-exp-winnings*
  (apply + (map * 
                *pb-payoffs* 
                *pb-probabilities*)))

(tester '*pb-exp-winnings*)

(define *pb-exp-winnings-no-grand-prize*
  (apply + (map *
                (rest *pb-payoffs*)
                (rest *pb-probabilities*))))

(tester '*pb-exp-winnings-no-grand-prize*)

(define *pb-no-winnings* (- 1 (apply + *pb-probabilities*)))

(tester '*pb-no-winnings*)

;;; ==========================================================
(problem "3:  Estimating Expected Winnings in Powerball")
;;; ==========================================================

;;;  PB-WINNINGS
;;; ------------------------------------------
;;;  INPUT:  PB-TICKET, a powerball ticket
;;;  OUTPUT:  The winnings for that ticket assuming that the
;;;    DRAW TICKET is (1,2,3,4,5;20).

(define pb-winnings
  (lambda (pb-ticket)
    (let* (;; PB? -- #t if the powerball on PB-TICKET matches the winner, 20
           (pb? (= 20 (sixth pb-ticket)))
           ;; MATCHES -- the number of matches among the first five numbers
           ;;   on PB-TICKET and the first five numbers of the DRAW TICKET
           (matches (num-matches (rest (reverse pb-ticket))
                                 '(1 2 3 4 5 20)))
           ;; EVENT-INDEX -- If PB-TICKET is a winner, then EVENT-INDEX
           ;;   will be the index of the corresponding event, as follows:
           ;;      0 -- Grand Prize (5 + pb)
           ;;      1 -- 5, no pb
           ;;      2 -- 4 + pb
           ;;     etc.
           ;;   If PB-TICKET is not a winner, then EVENT-INDEX is set to -1.
           (event-index (cond
                          ;; NOTE:  We examine the MOST likely outcomes first!!
                          ;; Case -1:  No Winner
                          ((and (not pb?) (< matches 3))
                           -1)
                          ;; Case 8:  PB only
                          ((and pb? (= matches 0))
                           8)
                          ;; Case 7:  1 + PB
                          ((and pb? (= matches 1))
                           7)
                          ;; Case 6:  2 + PB
                          ((and pb? (= matches 2))
                           6)
                          ;; Case 5:  3, no PB
                          ((and (not pb?) (= matches 3))
                           5)
                          ;; Case 4:  3 + PB
                          ((= matches 3)
                           4)
                          ;; Case 3:  4, no PB
                          ((and (not pb?) (= matches 4))
                           3)
                          ;; Case 2:  4 + PB
                          ((= matches 4)
                           2)
                          ;; Case 1:  5, no PB
                          ((and (not pb?) (= matches 5))
                           1)
                          ;; Case 0:  Grand Prize!!
                          ((and pb? (= matches 5))
                           0)
                          ;; If got here, then something's wrong
                          (#t
                           (printf "ERROR!")
                           'error))))
      ;; If EVENT-INDEX is negative number, then we don't
      ;; have any kind of winner
      (if (< event-index 0)
          ;; So the payoff is zero
          0
          ;; Otherwise, we use the EVENT-INDEX to fetch the
          ;; corresponding payoff
          (nth *pb-payoffs* event-index)))))

;;;  ESTIMATE-PB-EXP-WINNINGS
;;; ===========================================
;;;  INPUT:  N, number of trials to run
;;;  OUTPUT:  The average winnings over N random trials of Powerball
;;; -------------------------------------------------------------
;;;  Note:  See Lab9 solutions for a similar function definition

(define estimate-pb-exp-winnings
  (lambda (n)
    ;; ACC accumulates the total winnings 
    (let ((acc 0))
      ;; Use DOTIMES to run N trials
      (dotimes (i n)
               ;; GEN-RAND-PB-TICKET generates a random powerball ticket
               ;; PB-WINNINGS computes the winnings
               ;; SET! adds that amount to the value of ACC
               (set! acc (+ acc (pb-winnings (gen-rand-pb-ticket)))))
      ;; Return the AVERAGE winnings over N trials, as a floating point number
      (/ acc n 1.0))))

(tester '(estimate-pb-exp-winnings 1000))
(tester '(estimate-pb-exp-winnings 1000))
(tester '(estimate-pb-exp-winnings 1000))
(tester '(estimate-pb-exp-winnings 1000))
(tester '(estimate-pb-exp-winnings 100000))
(tester '(estimate-pb-exp-winnings 100000))
(tester '(estimate-pb-exp-winnings 1000000))