;;; =========================
;;;  CMPU-145, Spring 2013
;;;  Lab 7 Solutions
;;; =========================

(load "asmt-helper.txt")

(header "Lab 7" "Solutions!!")

;;; ========================
(problem "0:  power")
;;; ========================

;;;  POWER-ACC
;;; ---------------------------
;;;  INPUTS:  X, any number
;;;           N, a non-negative integer
;;;           ACC, a multiplicative accumulator
;;;  OUTPUT:  The value, X^N * ACC.  
;;;           Notice that if ACC = 1, then it returns the value of X^N.

(define power-acc
  (lambda (x n acc)
    (cond
      ;; Base Case:  N <= 0
      ((<= n 0)
       ;; Return the accumulator
       acc)
      ;; Recursive Case:  N > 0
      (#t
       ;; Tail-recursive function call with updated inputs
       (power-acc x 
                  (- n 1) 
                  (* acc x))))))

;;;  POWER
;;; ---------------------------
;;;  INPUTS:  X, any number
;;;           N, a non-negative integer
;;;  OUTPUT:  The value, X^N (i.e., X to the Nth power)

(define power
  (lambda (x n)
    ;; Just call helper function with properly initialized accumulator
    (power-acc x n 1)))


(tester '(power 3 4))
(tester '(power 10 3))
(tester '(power 2 10))
(tester '(power 2 20))


;;; ============================
(problem "1:  permutations")
;;; ============================

;;;  PERMY-ACC
;;; -------------------------------------------------
;;;  INPUTS:  N, K, non-negative integers with K <= N
;;;           ACC, a multiplicative accumulator
;;;  OUTPUT:  The value:  N*(N-1)*...*(N-K+1)*ACC = Perm(N,K)*ACC
;;;  Note:  If called with ACC=1, the output value is Perm(N,K).

(define permy-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
       (permy-acc (- n 1) 
                  (- k 1) 
                  (* acc n))))))

;;;  PERMY
;;;-------------------------------------
;;;  INPUTS:  N, K, non-negative integers with K <= N
;;;  OUTPUT:  The value:  N*(N-1)*...*(N-K+1) = Perm(N,K)

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


(tester '(permy 5 2))
(tester '(permy 4 2))
(tester '(permy 10 1))
(tester '(permy 10 3))
(tester '(permy 5 5))


;;; =============================
(problem "2:  combinations")
;;; =============================

;;;  N-CHOOSE-K-ACC
;;; ----------------------------
;;;  INPUTS:  N, K, non-negative integers with K <= N
;;;           ACC, a multiplicative accumulator
;;;  OUTPUT:  The value, "N choose K" * ACC
;;;  Note:  If ACC=1, then the output is exactly "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)))))))

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

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


(tester '(n-choose-k 4 2))
(tester '(n-choose-k 5 3))
(tester '(n-choose-k 10 2))
(tester '(n-choose-k 8 8))


;;; =====================================================
(problem "3:  Randomly choose one item from a list")
;;; =====================================================

;;;  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)))))

(tester '(rand-choose-one '(a b c d)))
(tester '(rand-choose-one '(a b c d)))
(tester '(rand-choose-one '(a b c d)))
(tester '(rand-choose-one '(a b c d)))
(tester '(rand-choose-one '(a b c d)))
(tester '(rand-choose-one '(a b c d)))