randomprocedure, its use in simulating simple games, and its use in making “unpredictable” texts.
a. Make sure that you have the latest version of the
b. Copy the code from the reading into your definitions pane. You should
random-elt, and the various
procedures for generating sentences.
Write a recursive procedure,
that counts the number of odd numbers that come up when rolling
> (count-odd-rolls 10) 7 > (count-odd-rolls 10) 2 > (count-odd-rolls 10) 6 > (count-odd-rolls 10) 5
Please use direct recursion to implement
count-odd-rolls. Your procedure
should look something like
(define count-odd-rolls (lambda (n) (cond [(zero? n) 0] [(odd? (roll-a-die)) ...] [else ...])))
Consider the problem of rolling a pair of dice
n times and counting
the number of times that either a seven (7) or an eleven (11) comes up.
a. What is wrong with the following pair of procedures that are intended to accomplish this task?
;;; Procedure: ;;; pair-a-dice ;;; Parameters: ;;; [None] ;;; Purpose: ;;; Roll two six-sided dice and find their sum. ;;; Produces: ;;; roll, an integer ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; 2 <= roll <= 12 ;;; Across multiple calls, the various rolls have the same probabilities ;;; as we would get from rolling two dice. (define pair-a-dice (lambda () (+ (roll-a-die) (roll-a-die)))) (define tally-seven-eleven (lambda (n) (cond [(<= n 0) 0] [(or (= (pair-a-dice) 7) (= (pair-a-dice) 11)) (+ 1 (tally-seven-eleven (- n 1)))] [else (tally-seven-eleven (- n 1))])))
Hint: How many times should we roll a pair of dice to find out how
many sevens or elevens come up in
n rolls? Add an expression using
display to the
pair-a-dice procedure so that you can count how many
times it is called.
(define pair-a-dice (lambda () (display "Rolling ...") (newline) (+ (roll-a-die) (roll-a-die))))
If that isn’t enough of a hint, read the notes on this problem.
b. Write a correct version of
a. Write a zero-parameter procedure,
(heads?) that simulates the
flipping of a coin. The
heads? procedure should return
(which represents “the coin came up heads”) half the time and
(which represents “the coin came up tails”) about half the time.
> (heads?) #f > (heads?) #f > (heads?) #t > (heads?) #f > (heads?) #t
b. Write a procedure,
(count-heads n), that simulates the flipping of
n coins (using
heads? to simulate the flipping of each coin) and
returns the number of times the coin is heads. You will likely find
the following form useful.
(define count-heads (lambda (n) (let kernel ([count 0] [remaining n]) (cond [(zero? remaining) count] ...))))
count-heads to explore the distribution
heads? gives by
counting the number of heads you get in 100 flips, 1,000 flips, and
Suppose we have a list of names,
students, that represents
all of the students in a class.
(define students (list "Andi" "Brook" "Casey" "Devin" "Drew" "Dylan" "Emerson" "Frances" "Gray" "Harper" "Jamie" "Kennedy" "Morgan" "Phoenix" "Quinn" "Ryan"))
a. Write a procedure,
(random-student), that randomly selects the name
of a student from the class.
b. Write a procedure,
(random-pair), that randomly picks one student
students, then another, and then puts them together into a list.
c. What are potential problems with using
(random-pair) to select
partners from the class?
a. Using the
sentence procedure, generate about five different
b. Add a few names, verbs, adjectives, and nouns to expand the range of sentences, then generate five new sentences.
All of the procedures we’ve written so far assume that we have a uniform distribution (of dice faces, verb occurrences, or whatever). But many distributions are not uniform. Consider, for example, a bag of M&M Candies. According to Josh Madison,
I checked out M&M’s web site. According to it, each package of Milk Chocolate M&M’s should contain 24% blue, 14% brown, 16% green, 20% orange, 13% red, and 14% yellow M&M’s.
We might represent that distribution in Scheme as a list of “color + frequency” lists.
(define m&m-colors (list (list "blue" 24) (list "brown" 14) (list "green" 16) (list "orange" 20) (list "red" 13) (list "yellow" 14)))
a. You may have noted that these numbers don’t add up to 100.
Write a procedure,
(total-frequency tallies), that adds up the
second numbers in a list of the form above.
> (total-frequency m&m-colors) 101 > (total-frequency '((a 3) (b 5) (c 2) (d 8))) 18
b. Write a procedure,
(one-m&m), that “randomly” chooses an
M&M color according to the distribution above. You should
(random 101) and then pick which color depending on
> (one-m&m) "blue" > (one m&m) "orange"
c. Write a procedure,
(lots-of-m&ms n), that makes a list of
n randomly chosen M&M colors.
> (lots-of-m&ms 20) '("brown" "green" "red" "orange" "blue" "red" "blue" "blue" "yellow" "yellow" "brown" "brown" "red" "orange" "blue" "green" "blue" "red" "blue" "orange")
d. Explore the distribution you actually get using
and a large
n. For example,
> (tally-all (lots-of-m&ms 1000))
Consider the following procedure.
(define select-from-distribution (lambda (tallies) (let ([choice (random (total-frequency tallies))]) (let kernel ([selector choice] [remaining tallies]) ; (display (list 'kernel selector remaining)) (newline) (let* ([entry (car remaining)] [entry-frequency (cadr entry)]) (if (< selector entry-frequency) (car entry) (kernel (- selector entry-frequency) (cdr remaining))))))))
a. What does this procedure seem to do?
b. Uncomment the
display line and call
m&m-colors) a few times.
c. Explain, in your own words, how
d. There’s no check to ensure that
remaining is nonempty. Why
doesn’t the code need such a check?
select-from-distribution procedure selects “randomly” from
an unequally distributed set of values. One unequally distributed
set of values we’ve encountered recently is the set of tallies of
words in a book.
> (define bronte-words (file->words "/home/rebelsky/Desktop/pg1260.txt")) > (length bronte-words) 192630 > (define bronte-tallies (tally-all bronte-words)) ; Warning! This is *slow*. > (length bronte-tallies) 13828
We could poorly simulate an author by selecting words randomly according to that distribution.
> (select-from-distribution bronte-tallies) "Anybody" > (select-from-distribution bronte-tallies) "they"
Write a procedure,
(new-sentence n tallies), that generates a new
sentence of the appropriate length using the distribution given in
> (new-sentence 20 bronte-tallies) "thoughts I snoring with pleasure past no quiescence brought laugh be sake he her man in I at had to " > (new-sentence 20 bronte-tallies) "had rode want record and a raised sparkling patience introduced no been might jetty very or four that was that "
Suggest a few techniques that could be used to improve the generation of text.
If there are
n rolls that we want to count, we should only roll the
n times. However, you will find that
n and 2
n calls. Why? Because the “is it seven or
eleven” test potentially rolls the dice twice, once to see if the roll
is seven and, if not, one more time to see if the roll is eleven.