;;; ============================= ;;; CMPU-145, Spring 2013 ;;; "asmt5-helper.txt" ;;; ============================= ;;; Defines a bunch of the functions we use for counting different kinds ;;; of poker or bridge hands, computing combinations, GEN-AND-TEST, etc. (load "asmt-helper.txt") ;;; N-CHOOSE-K ;;; ======================================================== ;;; 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))) ;;; NUMBER OF 5-CARD POKER HANDS ;;; ---------------------------------------------- (define *num-5-card-hands* (n-choose-k 52 5)) ;;; 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)))) ;;; A simple representation of cards -- seen previously ;;; --------------------------------------------------------------- ;;; A card is a number from 0 to 51 ;;; Its rank is a number from 1 to 13 (J = 11, Q = 12, K = 13) ;;; Its suit is a number from 0 to 3 (0 = Clubs, 1 = Diamonds, 2 = Hearts, 3 = Spades) (define *deck* '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51)) ;;; The RANK of a card is a number from 1 to 13, where 11=Jack, 12=Queen, 13=King ;;; ------------------------------------------------------------------------------ (define rank (lambda (card) (+ 1 (remainder card 13)))) ;;; The SUIT of a card is a number from 0 to 3, where 0=Clubs, 1=Diamonds, etc. ;;; ----------------------------------------------------------------------------- (define suit (lambda (card) (quotient card 13))) ;;; RAND-CHOOSE-ONE ;;; ------------------------------------- ;;; INPUT: LISTY, a list of items (usually with no repeats) ;;; OUTPUT: A randomly chosen item from that list (define rand-choose-one (lambda (listy) (nth listy (random (length listy))))) ;;; RAND-CHOOSE-K ;;; ---------------------------------- ;;; INPUTS: K, a non-negative integer ;;; LISTY, a list of at least K items ;;; OUTPUT: A list of K items chosen randomly from LISTY where ;;; order doesn't matter and repetition NOT allowed. (define rand-choose-k (lambda (k listy) (cond ;; Base Case: K <= 0 ((<= k 0) ;; A list of 0 items ()) ;; Error Case: K > 0 but LISTY is empty :o ((null? listy) ;; Just return a symbol signifying that an error happened 'error) ;; Recursive Case: K > 0 and LISTY non-empty (#t ;; Pick one item from LISTY (let ((rndy (rand-choose-one listy))) ;; And then cons it onto the front of (cons rndy ;; a list of (k-1) items chosen from (rand-choose-k (- k 1) ;; the remaining items in listy (remove rndy listy)))))))) ;;; RAND-POKER-HAND ;;; ----------------------------------- ;;; INPUTS: None ;;; OUTPUT: A list of 5 randomly chosen cards from *DECK* ;;; Note: This function is called like this: (rand-poker-hand) (define rand-poker-hand (lambda () (rand-choose-k 5 *deck*))) ;;; GET-HISTY-ACC! ;;; -------------------------------------------------- ;;; INPUTS: LISTY, a list of non-negative integers ;;; VECKY, a vector of accumulators (the Nth slot in the vector ;;; is used to keep track of the number of occurrences ;;; of the number N in LISTY) ;;; OUTPUT: The vector of accumulators, updated to reflect the contents ;;; of listy (for each N in LISTY, the Nth slot of VECKY is ;;; incremented by the number of times N occurs in LISTY). (define get-histy-acc! (lambda (listy vecky) ;; Note: VECKY is a vector of accumulators (i.e., a histogram) (cond ;; Base Case: LISTY is empty ((null? listy) ;; Return the vector of accumulators vecky) ;; Recursive Case: LISTY is non-empty (#t ;; Increment the counter in the appropriate slot of the vector VECKY ;; Notice how VECTOR-SET! and VECTOR-REF are used together! (vector-set! vecky (first listy) (1+ (vector-ref vecky (first listy)))) ;; Tail-recursive function call to look through the rest of the list (get-histy-acc! (rest listy) vecky))))) ;;; GET-HISTY ;;; ------------------------------------------ ;;; INPUT: LISTY, a list of non-negative integers ;;; OUTPUT: A histogram, in list form, where the Nth slot of the list ;;; specifies the number of times N appeared in LISTY. ;;; Example: (get-histy '(1 1 2 1 5 3)) ==> (0 3 1 1 0 1) (define get-histy (lambda (listy) ;; VECTOR->LIST is a built-in function that converts a vector into a list ;; MAKE-VECTOR is used to create a vector of a specified length ;; MAX is a built-in function (vector->list (get-histy-acc! listy (make-vector (1+ (apply max listy))))))) ;;; REMOVE-ALL: removes all occurrences of ITEM from LISTY ;;; ------------------------------------------ ;;; INPUTS: ITEM, anything ;;; LISTY, a list of stuff ;;; OUTPUT: A list just like LISTY except that it doesn't contain any ;;; occurrences of ITEM (define remove-all (lambda (item listy) (cond ;; Base Case: LISTY is empty ((null? listy) ()) ;; Recursive Case 1: ITEM = (FIRST LISTY) ((equal? item (first listy)) ;; Ignore (FIRST LISTY) and do recursive function call on (REST LISTY) (remove-all item (rest listy))) ;; Recursive Case 2: ITEM != (FIRST LISTY) (#t ;; Keep (FIRST LISTY), consing it onto the list returned by the ;; recursive function call (cons (first listy) (remove-all item (rest listy)))))))