;;; =========================== ;;; CMPU-145, Spring 2013 ;;; Lab 9 Solutions ;;; April 22, 2013 ;;; =========================== (load "asmt5-helper.txt") (header "Lab 9" "Solutions!!") ;;; ==================================================================== (problem "1: Pascal's Triangle") ;;; ==================================================================== ;;; PAIRWISE-ADD ;;; ------------------------------------ ;;; INPUTS: LISTY, LISTYZ, two lists of numbers (same length) ;;; OUTPUT: A list containing the pairwise sums of the numbers from ;;; the two input lists. For example: ;;; (pairwise-add '(10 20 30) '(1000 2000 3000)) ==> (1010 2020 3030) (define pairwise-add (lambda (listy listz) (map + listy listz))) ;;; GET-PASCAL-ROW ;;; ------------------------------------- ;;; INPUT: N, a non-negative integer ;;; OUTPUT: A list containing the entries from the Nth row of pascal's triangle (define get-pascal-row (lambda (n) (cond ;; Base Case: n = 0 ((<= n 0) '(1)) ;; Recursive Case: (#t (let* (;; PREV-ROW -- the previous row of pascal's triangle (prev-row (get-pascal-row (- n 1))) ;; PREV-ROW-PLUS -- same as PREV-ROW, except with a 0 cons'd ;; onto the front (prev-row-plus (cons 0 prev-row))) ;; Example: If PREV-ROW = (1 3 3 1) ;; Then PREV-ROW-PLUS = (0 1 3 3 1) ;; Pairwise Adding PREV-ROW-PLUS and the REVERSE of PREV-ROW-PLUS ;; yields: (0 1 3 3 1) ;; + (1 3 3 1 0) ;; ---------------- ;; (1 4 6 4 1) <--- the desired next row!! (pairwise-add prev-row-plus (reverse prev-row-plus))))))) (tester '(get-pascal-row 0)) (tester '(get-pascal-row 1)) (tester '(get-pascal-row 2)) (tester '(get-pascal-row 3)) (tester '(get-pascal-row 4)) ;;; PRINT-PASCAL ;;; -------------------------------------- ;;; INPUT: N, a non-negative integer ;;; OUTPUT: None ;;; SIDE EFFECT: Prints out the first N rows of pascal's triangle, ;;; one row per line in the interactions window. (define print-pascal (lambda (n) (newline) (dotimes (i n) (printf "~A~%" (get-pascal-row i))))) (newline) (tester '(print-pascal 5)) (newline) (tester '(print-pascal 10)) ;;; ===================================================================== (problem "2A: Powerball: Match 2 plus the PowerBall") ;;; ===================================================================== ;;; In powerball, pick 5 numbers from {1,2,3,...,59}, plus a powerball ;;; chosen from {1,2,3,...,35}. ;;; Easiest if you assume that the winning card is known in advance; ;;; For example, suppose winner is: (1 2 3 4 5; 20). ;;; Number of ways of matching 3 of the first 5, plus the powerball... ;;; *NUM-WAYS-MATCH-3-W-PB* -- number of tickets that have exactly 2 matches ;;; among the first five numbers, plus the powerball matching (define *num-ways-match-2-w-pb* (* (n-choose-k 5 2) ;; pick two numbers of first five to match (n-choose-k 54 3) ;; pick three *non-matching* numbers ;; (there are 59-5 non-matching numbers) 1 ;; only one way to match the winning powerball! )) ;;; *NUM-POWERBALL-TIX* -- the number of distinct powerball tickets (define *num-powerball-tix* (* (n-choose-k 59 5) ;; pick 5 numbers out of 59 35 ;; pick the powerball )) ;;; *PROB-MATCH-2-W-PB* -- the probability that a randomly generated ;;; powerball ticket will have exactly 2 matches with the DRAW ticket ;;; plus matching the powerball. (define *prob-match-2-w-pb* (/ *num-ways-match-2-w-pb* *num-powerball-tix* 1.0)) (tester '*num-ways-match-2-w-pb*) (tester '*num-powerball-tix*) (tester '*prob-match-2-w-pb*) ;;; ===================================================================== (problem "2B: Estimating powerball 2-matches-w-pb using GEN-AND-TEST") ;;; ===================================================================== ;;; LIST-FROM ;;; ----------------------------------- ;;; INPUTS: START and STOP, non-negative integers ;;; OUTPUT: A list of the form, (START, START+1, START+2, ..., STOP) ;;; Example: (list-from 1 5) ==> (1 2 3 4 5) (define list-from (lambda (start stop) (cond ;; Base Case: START > STOP ((> start stop) ;; Just return the empty list ()) ;; Recursive Case: START <= STOP (#t ;; Then START is the first number in the output (cons start ;; And recursive function call generates the rest of the list (list-from (+ 1 start) stop)))))) (define *pb-nums-59* (list-from 1 59)) ;;; GEN-RAND-PB-TICKET ;;; --------------------------------------- ;;; INPUTS: None ;;; OUTPUT: A list of six numbers: the first five are chosen ;;; from (1,2,3,...,59) (no replacement); the last one is chosen ;;; from (1,2,3,...,35) (define gen-rand-pb-ticket (lambda () ;; Note how we CONS the powerball onto the FRONT of the list, ;; and then REVERSE it to place the powerball at the end!! (reverse (cons ;; Pick the powerball (from 1 to 35) (+ 1 (random 35)) ;; Pick the five numbers from 1 to 59 (rand-choose-k 5 *pb-nums-59*))))) ;;; NUM-MATCHES ;;; --------------------------------- ;;; INPUTS: LISTY, LISTZ, two lists ;;; OUTPUT: The number of elements of LISTY that also appear in LISTZ ;;; (same as the number of elements in the intersection of the two lists) (define num-matches (lambda (listy listz) (cond ;; Base Case: LISTY is empty ((null? listy) ;; So no matches 0) ;; Recursive Case 1: We found a match! ((member (first listy) listz) ;; So add 1 to the recursive function call on the rest of LISTY (+ 1 (num-matches (rest listy) listz))) ;; Recursive Case 2: We did not find a match! (#t ;; So just focus on the REST of listy (num-matches (rest listy) listz))))) ;;; MATCHES-2-W-PB? ;;; ----------------------------------------- ;;; INPUT: TICKET, a list of 6 numbers, where the first five belong ;;; to {1,2,...,59} and the 6th belongs to {1,2,...,35}. ;;; OUTPUT: #t if exactly TWO of the first five numbers belong ;;; to (1,2,3,4,5) (i.e., the first five numbers of the ;;; DRAW TICKET *and* the 6th number is equal to 20 ;;; (i.e., the powerball on the DRAW TICKET). (define matches-2-w-pb? (lambda (ticket) (let* (;; The powerball is the 6th element of the ticket (pb (sixth ticket)) ;; The first five numbers are OTHERS (others (rest (reverse ticket)))) (and (= pb 20) (= 2 (num-matches others '(1 2 3 4 5))))))) (tester '(gen-and-test 1000000 gen-rand-pb-ticket matches-2-w-pb?)) (tester '(gen-and-test 1000000 gen-rand-pb-ticket matches-2-w-pb?))