;;; ============================
;;;  CMPU-145, Spring 2013
;;;  Code from class
;;;  April 15, 2013
;;; ============================

(load "asmt-helper.txt")

(header "Lab 8" "Helper file")

;;;  N-CHOOSE-K
;;; ---------------------------
;;;  INPUTS:  N, K, non-negative integers with K <= N
;;;  OUTPUT:  The value "N choose K"

(define n-choose-k-acc
  (lambda (n k acc)
    (cond
      ;; Base Case:  K <= 0
      ((<= k 0)
       ;; Return the accumulator!
       acc)
      ;; Recursive Case:  K > 0
      (#t
       ;; Tail-recursive function call with updated inputs
       (n-choose-k-acc (- n 1) 
                       (- k 1) 
                       (* acc n (/ 1 k)))))))

(define n-choose-k
  (lambda (n k)
    ;; Just call helper function with suitably initialized accumulator
    (n-choose-k-acc n k 1)))

;;; ==================================================

;;; (problem "1: Poker Hands")

;;;  The number of distinct 5-card poker hands (O-R-) is 52-choose-5.

(define *num-5-card-hands* (n-choose-k 52 5))

;;; (tester '*num-5-card-hands*)

;;;  The number of 5-card hands having four-of-a-kind = 13 * 48
;;;    13 choices for rank of the four-of-a-kind
;;;    48 choices for the non-matching card

(define *num-hands-with-4-of-a-kind* (* 13 48))

;;; (tester '*num-hands-with-4-of-a-kind*)

;;;  Probability of getting 4-of-a-kind is just the
;;;  number of hands having 4 of a kind divided by
;;;  the total number of possible hands.

(define *prob-of-4-of-a-kind* (/ *num-hands-with-4-of-a-kind*
                                  *num-5-card-hands*
                                  1.0))

;;; (tester '*prob-of-4-of-a-kind*)


;;; (problem "2: USING GEN-AND-TEST")

;;;  GEN-AND-TEST
;;; ------------------------------------
;;;  INPUTS:  N, a non-negative integer
;;;           GEN, a function of one input that is used to generate random
;;;                 instances of some event (e.g., tossing a die, dealing a card)
;;;           TEST, a function that tests whether some given instance has some
;;;                 property (e.g., die > three, or card is a face card)
;;;  OUTPUT:  The fraction of N random trials in which the randomly generated
;;;           instances satisfied the TEST.

(define gen-and-test
  (lambda (n gen test)
    ;; COUNT is a counter variable
    (let ((count 0))
      ;; DOTIMES executes its body N times
      (dotimes (i n)
               ;; Use (GEN) to generate a random instance;
               ;; Use TEST to determine whether that instance has the 
               ;; desired property
               (if (test (gen))
                   ;; If it does, then destructively increment the counter!
                   (set! count (+ count 1))))
      ;; After the DOTIMES loop finishes, return the fraction of the 
      ;; trials that satisfied the TEST.
      (/ count n 1.0))))

;;;  TOSS-DIE
;;; -------------------------
;;;  INPUTS:  None
;;;  OUTPUT:  A randomly generated number from 1 to 6

(define toss-die
  (lambda ()
    (+ 1 (random 6))))

;;;  TEST-DIE
;;; --------------------------
;;;  INPUT:  A number from 1 to 6
;;;  OUTPUT:  #t if that number is either 5 or 6

(define test-die
  (lambda (die)
    (or (= die 5) (= die 6))))

;;;(tester '(gen-and-test 1000 toss-die test-die))
;;;(tester '(gen-and-test 10000 toss-die test-die))
;;;(tester "answer-should-be-one-third")
;;;(newline)

;;; ----------------------

;;;  TOSS-PAIR-DICE
;;; ----------------------------
;;;  INPUTS:  None
;;;  OUTPUT:  A two-element list containing a pair of randomly generated
;;;           numbers from 1 to 6

(define toss-pair-dice
  (lambda ()
    ;; Note the use of TOSS-DIE
    (list (toss-die) (toss-die))))

;;;  TEST-PAIR-DICE
;;; ----------------------------
;;;  INPUT:  A two-element list containing a pair of numbers each between 1 and 6
;;;  OUTPUT:  #t if the sum of those two numbers is at least 8

(define test-pair-dice
  (lambda (pr)
    (>= (+ (first pr) (second pr))
        10)))

;;;(tester '(gen-and-test 10000 toss-pair-dice test-pair-dice))
;;;(tester '(gen-and-test 10000 toss-pair-dice test-pair-dice))
;;;(tester '(gen-and-test 1000000 toss-pair-dice test-pair-dice))
;;;(tester '"answer-should-be-one-sixth")


;;;(problem "3: Dealing cards")

;;;  Cards
;;; -----------------------------------------
;;;  Each card represented by an integer from 0 to 51 (inclusive).
;;;  Rank of a card is (the remainder when dividing by 13) plus one!
;;;    -- Rank guaranteed to be between 1 and 13
;;;    --   11-->Jack, 12-->Queen, 13-->King
;;;  Suit of a card is (the quotient when dividing by 13).
;;;    -- Suit guaranteed to be between 0 and 3
;;;    --   0-->Club; 1-->Diamond, 2-->Heart, 3-->Spade

;;;  RANK
;;; --------------------------
;;;  INPUT:  CARD, an integer between 0 and 51 inclusive
;;;  OUTPUT:  The "rank" of that card (an integer between 1 and 13, inclusive)

(define rank
  (lambda (card)
    (+ 1 (remainder card 13))))

;;;  CHOOSE-K-FROM
;;; -------------------------------------
;;;  INPUTS:  K, a non-negative integer
;;;           LISTY, a list containing at least K items
;;;  OUTPUT:  A list containing K items chosen at random from LISTY
;;;            where order doesn't matter and repetition not allowed: O-R-.

(define choose-k-from
  (lambda (k listy)
    ;; Just call accumulator-based helper function with 
    ;; accumulator initialized to the empty list
    (choose-k-from-acc k listy ())))

(define choose-k-from-acc
  (lambda (k listy acc)
    (cond
      ;; Base Case:  K <= 0
      ((<= k 0)
       ;; Return the accumulator!
       acc)
      ;; Recursive Case:  K > 0
      (else
       (let* (;; Pick random index into list
              (randy (random (length listy)))
              ;; Get corresponding element from the list
              (chosen-item (nth listy randy)))
         ;; Tail-recursive function call with updated inputs
         (choose-k-from-acc (- k 1)
                            ;; Since replacement not allowed....
                            ;; (Note: REMOVE only removes *first* occurrence
                            ;;   of CHOSEN-ITEM; so okay if LISTY contains
                            ;;   duplicates.)
                            (remove chosen-item listy)
                            ;; Update accumulator
                            (cons chosen-item acc)))))))

;;;(tester '(choose-k-from 3 '(a b c d e f g h i)))
;;;(tester '(choose-k-from 3 '(a b c d e f g h i)))
;;;(tester '(choose-k-from 3 '(a b c d e f g h i)))
;;;(tester '(choose-k-from 3 '(a b c d e f g h i)))
;;;(newline)

;;; A DECK of cards

(define list-from
  (lambda (n)
    (if (<= n 0)
        (list 0)
        (cons n (list-from (- n 1))))))

(define *deck* (list-from 51))

;;;(tester '*deck*)
;;;(newline)

;;;(tester '(choose-k-from 5 *deck*))
;;;(tester '(choose-k-from 5 *deck*))
;;;(newline)
;;;(tester '(map rank (choose-k-from 5 *deck*)))
;;;(tester '(map rank (choose-k-from 5 *deck*)))
;;;(newline)
;;;(tester '(sort (map rank (choose-k-from 5 *deck*)) <=))
;;;(tester '(sort (map rank (choose-k-from 5 *deck*)) >=))

;;; ----------------------------------------------------

;;;(problem "4: GEN-AND-TEST with 4-of-a-kind")

(define gen-poker-hand
  (lambda ()
    (choose-k-from 5 *deck*)))

(define has-four-of-a-kind?
  (lambda (cards)
    (let ((sorted-ranks (sort (map rank cards) <=)))
      ;; Should be one of:  (X X X X Y) or (X Y Y Y Y)
      (or (= (first sorted-ranks)
             (fourth sorted-ranks))
          (= (second sorted-ranks)
             (fifth sorted-ranks))))))

;;;(tester '(gen-and-test 100000 gen-poker-hand has-four-of-a-kind?))
;;;(tester '(gen-and-test 100000 gen-poker-hand has-four-of-a-kind?))
;;;(tester '(gen-and-test 100000 gen-poker-hand has-four-of-a-kind?))
;;;(tester '*prob-of-4-of-a-kind*)

;;; ==================================================

;;;(problem "5: Full house")

(define *num-ways-full-house*
  (* 13    ;; 13 choices for rank of trips 
     4     ;; 4-choose-3 ways of choosing suits for trips 
     12    ;; 12 choices for rank of pair
     6)    ;; 4-choose-2 ways of choosing suits for the pair
  )

(define *prob-full-house*
  (/ *num-ways-full-house*
     *num-5-card-hands*
     1.0))

;;;(tester '*num-ways-full-house*)
;;;(tester '*prob-full-house*)


(define *num-ways-two-pair* ;; but not a full house
  (* (n-choose-k 13 2) ;; choose the two ranks for the two pair: O-R-
     (n-choose-k 4 2)  ;; choose two cards from first rank
     (n-choose-k 4 2)  ;; choose two cards from second rank
     44                ;; choose non-matching card
     ))

(define *prob-two-pair*
  (/ *num-ways-two-pair*
     *num-5-card-hands*
     1.0))

;;;(tester '*num-ways-two-pair*)
;;;(tester '*prob-two-pair*)