;; CMPU 145, Spring, 2019
;; Probability helper functions
;; Also contains asmt-helper functions
;; N-CHOOSE-K
;; ----------
;; INPUTS: N, K, non-negative integers with K <= N
;; OUTPUT: The value "N choose K", i.e., the number of
;; combinations (without repetition) of N elements from a
;; set of N elements: n!/(k!(n-k)!)
(define n-choose-k
(lambda (n k)
(if (< k 1)
;; Base Case: K has hit bottom
;; So return 1 (the multiplicative identity)
1
;; Recursive Case: There's more to do...
;; Multiply (N/K) by whatever the recursive function
;; call returns
(* (/ n k)
(n-choose-k (- n 1) (- k 1))))))
;;;
;; REMOVE-FIRST -- a helper for CHOOSE-K-FROM
;; ------------------------------------------
;; INPUTS: ITEM, input-list
;; OUTPUT: A list just like input-list except that the first occurrence
;; of ITEM is not included.
(define remove-first
(lambda (item input-list)
(cond
;; Base Case: input-list is empty
((null? input-list)
;; We're done
'())
;; Base Case 2: We found the first occurrence of ITEM
((eq? item (first input-list))
;; So just return the rest of input-list
(rest input-list))
;; Recursive Case: Keep (FIRST input-list) and let the
;; recursive function call look for ITEM in (REST input-list)
(else
(cons (first input-list)
(remove-first item (rest input-list)))))))
;; CHOOSE-K-FROM
;; -------------
;; INPUTS: K, a non-negative integer
;; input-list, a list of at least K items
;; OUTPUT: A list of k items drawn from input-list
(define choose-k-from
(lambda (k input-list)
(cond
;; If K = 0, we're done
((<= k 0)
'())
;; Otherwise...
(else
;; Use the built-in RANDOM function to select a random
;; number from 0 to (length input-list) minus 1. Then use
;; the built-in LIST-REF function to fetch the indicated
;; item from input-list.
(let* ((rnd (random (length input-list)))
(item (list-ref input-list rnd)))
;; Cons that selected ITEM onto the list returned by
;; the recursive function call
(cons item
(choose-k-from (- k 1)
;; Use REMOVE-FIRST because we are
;; selecting WITH NO REPLACEMENT!!
(remove-first item input-list))))))))
;; CHOOSE-ONE-FROM
;; ---------------
;; INPUT: A list
;; OUTPUT: A randomly selected item from that list
(define choose-one-from
(lambda (input-list)
(first (choose-k-from 1 input-list))))
;;;
;; rank-and-suit->card
;; -------------------
;; INPUTS: rank (number from 0 to 12) and suit (number from 0 to 3)
;; OUTPUT: corresponding card (number from 0 to 51)
(define rank-and-suit->card
(lambda (r s)
(+ (* 13 s) r)))
;; card->suit-num
;; --------------
;; INPUT: Card (number from 0 to 51)
;; OUTPUT: Suit (number from 0 to 3)
(define card->suit-num
(lambda (c)
(quotient c 13)))
;; A vector of short names for the various suits
(define *suit-strings* '("C" "D" "H" "S"))
;; suit-num->suit-str
;; ------------------
;; INPUT: Suit (number from 0 to 3)
;; OUTPUT: Suit string (one of the *suit-strings*)
(define suit-num->suit-str
(lambda (sn)
(list-ref *suit-strings* sn)))
;; card->suit-str
;; --------------
;; INPUT: Card (number from 0 to 51)
;; OUTPUT: Suit string for that card
(define card->suit-str
(lambda (c)
(suit-num->suit-str (card->suit-num c))))
;; card->rank-num
;; --------------
;; INPUT: Card (number from 0 to 51)
;; OUTPUT: Rank Num (number from 0 to 12)
(define card->rank-num
(lambda (c)
(remainder c 13)))
;; A list of names for the various ranks of a card
(define *rank-strings*
'("A" "2" "3" "4" "5" "6" "7" "8" "9" "10" "J" "Q" "K"))
;; rank-num->rank-str
;; ------------------
;; INPUT: rank num (a number from 0 to 12)
;; OUTPUT: corresponding rank string (one of *rank-strings*)
(define rank-num->rank-str
(lambda (rn)
(list-ref *rank-strings* rn)))
;; card->rank-str
;; --------------
;; INPUT: Card (number from 0 to 51)
;; OUTPUT: rank string for that card
(define card->rank-str
(lambda (c)
(rank-num->rank-str (card->rank-num c))))
;; card->string
;; ------------
;; INPUT: card (number from 0 to 51)
;; OUTPUT: string containing rank and suit of that card
(define card->string
(lambda (c)
(string-append (card->rank-str c)
(card->suit-str c))))
;; Lists containing the possible rank and suit numbers
(define *rank-nums* '(0 1 2 3 4 5 6 7 8 9 10 11 12))
(define *suit-nums* '(0 1 2 3))
;;;
;;; new additions, 4/23.
;;;
;; 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 [print #f])
;; COUNT is a counter variable
(let ((count 0))
;; FOR executes its body N times
(for ((i n))
;; Use (GEN) to generate a random instance;
;; Use TEST to determine whether that instance has the
;; desired property
(let* ((rnd (gen))
(result (test rnd)))
(when print
(printf "[~A: ~A] " rnd result))
(when result
;; If it does, then destructively increment the counter!
(set! count (+ count 1)))))
;; After the for loop finishes, return the fraction of the
;; trials that satisfied the TEST.
(/ count n 1.0))))
;;;;
;;(problem "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
;; Generate a full DECK of cards as a list of numeric IDs
(define list-from
(lambda (n)
(if (<= n 0)
(list 0)
(cons n (list-from (- n 1))))))
(define *deck* (list-from 51))
;; RANK
;; ----
;; INPUT: CARD, an integer between 0 and 51 inclusive
;; OUTPUT: The "rank" of that card (an integer between 1 and 13, inclusive)
;; This adjusts the output of card->rank-num to make it match the "real" numbers
;; for cards but without producing names like "A", "J", "Q", and "K" used by
;; card->rank-str
(define rank
(lambda (card)
(+ 1 (card->rank-num card))))
;;;;
;; HEADER
;; ------
;; INPUTS:
;; - ASMT-STRING, a string representing the particular assignment
;; (e.g., "asmt 0")
;; - NAME-STRING, a string representing your name
;; OUTPUT: none
;; SIDE EFFECT:
;; Prints out a nice header for your assignment in the Interactions Window
(define header
(lambda (asmt-string name-string)
(printf "=======================================~%")
(printf " CMPU 145, Spring 2019~%")
(printf " ~A~%" asmt-string)
(printf " ~A~%" name-string)
(printf "=======================================~%~%")))
;; PROBLEM
;; -------
;; INPUT: PROBLEM-STRING, a string giving some info about the problem
;; (e.g., "(1) FACTORIAL")
;; OUTPUT: none
;; SIDE EFFECT: Prints out a nice header for a problem within an assignment
(define problem
(lambda (problem-string)
(printf "~%------------------------~%")
(printf " ~A~%" problem-string)
(printf "------------------------~%~%")))
;; TESTER
;; ------
;; INPUT: DATUM, a scheme datum
;; OUTPUT: The result of evaluating that datum
;; SIDE EFFECT: Prints out the DATUM before evaluation, followed by
;; an arrow...
;; Racket has made namespaces more complicated, so the `eval` below doesn't
;; work without this code.
(define-namespace-anchor *anc*)
(define *ns* (namespace-anchor->namespace *anc*))
(define tester
(lambda (datum)
(printf "~A ==> " datum)
(eval datum *ns*)))