- Assigned
- Wednesday, Oct 31, 2018
- Due
- Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
- Summary
- In this laboratory, you will explore the
`random`

procedure, its use in simulating simple games, and its use in making “unpredictable” texts.

a. Make sure that you have the latest version of the `csc151`

package.

b. Copy the code from the reading into your definitions pane. You should
include `roll-a-die`

, `roll-dice`

, `random-elt`

, and the various
procedures for generating sentences.

Write a recursive procedure, `(count-odd-rolls n)`

that counts the number of odd numbers that come up when rolling `n`

six-sided dice.

```
> (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 `tally-seven-eleven`

.

a. Write a zero-parameter procedure, `(heads?)`

that simulates the
flipping of a coin. The `heads?`

procedure should return `#t`

(which represents “the coin came up heads”) half the time and `#f`

(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]
...))))
```

c. Use `count-heads`

to explore the distribution `heads?`

gives by
counting the number of heads you get in 100 flips, 1,000 flips, and
10,000 flips.

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
from `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
sentences.

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
use `(random 101)`

and then pick which color depending on
its value.

```
> (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 `tally-all`

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 ```
(select-from-distribution
m&m-colors)
```

a few times.

c. Explain, in your own words, how `select-from-distribution`

works.

d. There’s no check to ensure that `remaining`

is nonempty. Why
doesn’t the code need such a check?

The `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
the tally.

```
> (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
dice `n`

times. However, you will find that `tally-seven-eleven`

does
somewhere between `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.