;;; ===============================
;;;  CMPU-145, Spring 2013
;;;  Asmt. 5 Solutions!
;;; ===============================

(load "asmt5-helper.txt")

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

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

(problem "1:  Generate all permutations of a given set (list)")

;;;  GEN-ALL-PERMS
;;; -------------------------
;;;  INPUT:  LISTY, a list of stuff (with no duplicates)
;;;  OUTPUT:  A list of all the permutations of LISTY, where each
;;;           permutation of LISTY contains *all* of the elements of 
;;;           LISTY, but possibly in a different order.

(define gen-all-perms
  (lambda (listy)
    (cond
      ;; Base Case:  LISTY is empty
      ((null? listy)
       ;; There is only one permutation of the empty list:  ()
       ;; So return a list containing that one permutation:
       '(()))
      (#t
       ;; The APPLY APPEND trick!
       ;; The following concatenates the lists of permutations returned
       ;; by the OUTER MAP.
       (apply append
              ;; The OUTER MAP returns a list of elements, each of which
              ;; is a list of permutations of listy generated by the INNER MAP.
              ;; Thus, the OUTER MAP returns a LIST OF LISTS of permutations.
              (map (lambda (item)
                     ;; The INNER MAP returns a list of elements, each of which
                     ;; is obtained by consing ITEM onto a permutation of 
                     ;; (rest listy).  Thus, the INNER MAP returns a list of
                     ;; permutations of LISTY, each of which has ITEM as its
                     ;; first element.
                     (map (lambda (perm-resty)
                            (cons item perm-resty))
                          (gen-all-perms (remove item listy))))
                   listy))))))

(tester '(gen-all-perms '(1 2)))
(tester '(gen-all-perms '(a b c)))
(tester '(length (gen-all-perms '(1 2 3 4 5 6 7))))
(tester '(* 7 6 5 4 3 2 1))

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

(problem "2:  Generate all possible ways of choosing k items from a given list")

;;;  GEN-ALL-WAYS-OF-CHOOSING-K-ITEMS
;;; --------------------------------------------------------
;;;  INPUTS:  LISTY, a list of stuff (usually no repeats)
;;;           K, a non-negative integer (assume that K <= (length listy))
;;;  OUTPUT:  A list of K randomly chosen items from LISTY (order doesn't
;;;            matter; repetition not allowed).

(define gen-all-ways-of-choosing-k-items
  (lambda (listy k)
    (cond
      ;; Base Case:  K = 0
      ((<= k 0)
       ;; There's only one way of choosing 0 items from a list: ()
       ;; So, return a list containing that one way:
       '(()))
      ;; Base Case 2:  LISTY is EMPTY, but K > 0
      ((null? listy)
       ;; There are no ways of choosing K > 0 items out of the empty list
       ())
      ;; Recursive Case:  LISTY has at least one element, K > 0
      (#t
       (append 
        ;; All ways of choosing k items that include the first of listy
        (map (lambda (resty-choosy)
               (cons (first listy) resty-choosy))
             (gen-all-ways-of-choosing-k-items (rest listy) (- k 1)))
        ;; All ways of choosing k items that do not include first listy
        (gen-all-ways-of-choosing-k-items (rest listy) k))))))

(tester '(gen-all-ways-of-choosing-k-items '(1 2 3 4) 2))
(newline)
(tester '(gen-all-ways-of-choosing-k-items '(A B C) 2))
(newline)
(tester '(gen-all-ways-of-choosing-k-items '(1 2 3 4 5 6) 3))
(newline)
(tester '(length (gen-all-ways-of-choosing-k-items '(1 2 3 4 5 6 7 8 9 10) 4)))
(newline)
(tester '(/ (* 10 9 8 7) (* 4 3 2 1))) ;; (i.e., 10 choose 4)
                      
                    
;;;  3.  POKER HAND WITH A FLUSH (i.e., all five cards in same suit)
;;; ====================================================================

(problem "3:  Poker hand with a flush!")

;;;  *NUM-FLUSHES*  --  the number of ways of getting a FLUSH in five cards

(define *num-flushes*
  (* 4                 ;; chooose suit
     (n-choose-k 13 5) ;; pick 5 cards from that suit
     ))

(tester '*num-flushes*)

;;;  *PROB-FLUSH*  -- the probability of getting dealt a 5-card flush

(define *prob-flush*
  (/ *num-flushes*
     *num-5-card-hands*
     1.0))

(tester '*prob-flush*)

;;;  HAS-FLUSH?
;;; -----------------------------------------
;;;  INPUT:  HAND, a list of 5 "cards" (each card being a number from 0 to 51)
;;;  OUTPUT:  #t, if all five cards belong to the same suit

(define has-flush?
  (lambda (hand)
    ;; Here we use the GET-HISTY function to return a histogram
    ;; of the suits in the hand.  For a flush, the histogram should
    ;; consist of one 5 and three 0s.
    (let* ((suits (map suit hand))
           (suit-histy (get-histy suits))
           (no-zeroes-suit-histy (remove-all 0 suit-histy)))
      ;; If we remove all the 0s from the histogram, then for a flush
      ;; we should be left with (5).
      (equal? no-zeroes-suit-histy
              '(5)))))

;;;  ALT-HAS-FLUSH?
;;; ---------------------------------------
;;;  Alternative implementation

(define alt-has-flush?
  (lambda (hand)
    ;; The built-in = function can take any number of inputs
    (apply = (map suit hand))))

(newline)
(tester '(gen-and-test 100000 rand-poker-hand has-flush?))
(tester '(gen-and-test 100000 rand-poker-hand has-flush?))
(newline)
(tester '(gen-and-test 100000 rand-poker-hand alt-has-flush?))
(tester '(gen-and-test 100000 rand-poker-hand alt-has-flush?))


;;;  4.  BRIDGE HAND WITH 5-4-2-2 DISTRIBUTION OF SUITS
;;; =============================================================

(problem "4:  Bridge hand with 5-4-2-2- distribution of suits")

;;;  *NUM-HANDS-WITH-5-4-2-2* -- number of 13-card hands with 5/4/2/2 
;;;       distribution of suits

(define *num-hands-with-5-4-2-2*
  (* 4 ;; 4 choices for the suit that will have 5 cards
     3 ;; 3 choices for the suit that will have 4 cards
     ;; the remaining suits will have pairs... (no choice)
     (n-choose-k 13 5) ;; pick 5 cards for first suit
     (n-choose-k 13 4) ;; pick 4 cards for second suit
     (n-choose-k 13 2) ;; pick 2 cards for each remaining suit
     (n-choose-k 13 2)
     ))

(tester '*num-hands-with-5-4-2-2*)

;;;  *NUM-13-CARD-HANDS*  --  number of distinct 13-card hands

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

(tester '*num-13-card-hands*)

;;;  *PROB-5-4-2-2-DISTN* -- probability of getting dealt a 13-card 
;;;     hand with a 5/4/2/2 distribution of suits

(define *prob-5-4-2-2-distn*
  (/ *num-hands-with-5-4-2-2*
     *num-13-card-hands*
     1.0))

(tester '*prob-5-4-2-2-distn*)

;;;  GEN-BRIDGE-HAND
;;; ----------------------------------------
;;;  INPUT:  None
;;;  OUTPUT:  A list of 13 cards (suits only) generated randomly

(define gen-bridge-hand
  (lambda ()
    (rand-choose-k 13 *deck*)))

;;;  IS-5-4-2-2-DISTN?
;;; -------------------------------------
;;;  INPUTS:  CARDS, a list of "cards" (each card a number from 0 to 51)
;;;  OUTPUT:  #t if the list of cards contains 5 cards from one suit,
;;;              4 from another, and 2 of each of the remaining suits

(define is-5-4-2-2-distn?
  (lambda (cards)
    ;; Use GET-HISTY to get a histogram of the suits in the hand
    (let* ((suits (map suit cards))
           (suit-histy (get-histy suits))
           (sorted-suit-histy (sort suit-histy <=)))
      ;; The sorted histogram should equal (2 2 4 5)
      (equal? '(2 2 4 5)
              sorted-suit-histy))))

(newline)
(tester '(gen-and-test 100000 gen-bridge-hand is-5-4-2-2-distn?))