Homework 3

Due Date Friday, Septebmer 27 at 6pm

Purpose To design small programs and practice using enumerated data.

Graded Exercises

Exercise 1 Your friend Loki has written a function that takes four positive integers as parameters and determines if the first parameter, plus a single randomly generated number, that is less than the second parameter, results in a sum that is (i) even, (ii) larger than the third parameter, and (iii) smaller than the fourth parameter. Loki’s logic, however, is a bit off.

; loki : PosInt PosInt PosInt PosInt -> Boolean

; Determines if the base, plus a random number in a bound, is even and within a threshold

(define (loki base random-upper too-small too-big)

(and (even? (+ base (random random-upper)))

(> (+ base (random random-upper)) too-small)

(< (+ base (random random-upper)) too-big)))

• Leave a comment explaining why Loki’s code isn’t correct. For extra credit, provide a test that should work, given the problem description, but doesn’t (note: given that the function uses randomness, it is ok if we would need to run your test multiple times).

• Design a corrected loki function. Hint: this might involve a helper function.

Exercise 2 Consider the following structure and data definition:

; A Fish is a (make-fish String String NonNegNumber)

(define-struct fish [species color weight])

; and represents a fish's species, color, and weight in grams

• Define some examples of Fish.

• Design the template for functions that consume a Fish.

• List all of the signatures of all of the functions that are defined by this structure and data definition.

  Note: one could write the technically correct signature for make-fish as follows

  ; make-fish : Any Any Any -> (make-fish Any Any Any)

  This does describe a proper data type in both the inputs and output. However, as discussed in class, just because we could write something like (make-fish #false 42 "bark") doesn’t mean we should. Instead, we should think of the signature of make-fish in so far as it relates to the data type of Fish.

Exercise 3 Your goal is to approximate the value of pi (π) using a sampling approach, meaning we make use of many randomly generated numbers. The basic idea is as follows:

• Independently generate two numbers in the range [0, 1]

• Determine if these numbers, interpreted as (x,y), lie in quadrant 1 of a unit circle; that is, the distance from the point to the origin (0,0) is less than or equal to 1.

• Add this to your samples: keep track of how many samples have been taken in total, as well as how many lay in quadrant 1.

• To approximate pi, multiply the proportion of in-quadrant samples (in-quadrant / total) by 4.

• Rinse and repeat for as many samples as you wish (more samples will tend towards a more accurate approximation).

By the end of this problem you will design a program to allow the user to perform this process via key presses, visually illustrating the current approximation. (Note: this is quite an inefficient approximation method, but makes for good practice with this week’s content.)

• Design data for PiSamples, the data you will need to keep track of the number of samples collected, as well as how many were in quadrant 1. Remember to follow all the steps of the data design recipe.

• Design the function samples->approximation that converts the sampling data from (a) and computes the associated approximation. For example, if two samples have been collected and one was within the quadrant, the pi approximation would be 4*(1/2) = 2. Note that you should produce a reasonable response if the number of samples gathered is 0.

• Design the function add-sample that incorporates a new sample, supplied simply as whether or not it was in quadrant 1, into the data from (a). For example, if we started with two samples that had been collected, with one having been in the quadrant, and a new sample is collected that is also in the quadrant, the new sample data would reflect that three samples had been collected in total, two of which were in the quadrant.

• Design the function rand-0-1 that takes as input a positive integer n and produces a number in the range [0, 1]. To do so, first produce a random integer in the range [0, n], then divide that number by n. (Note: larger values of n will get closer and closer to a uniform sample in [0, 1]).

• Design the function sample-in-quadrant? which determines if a supplied position (x,y) is within a distance of 1 from the origin (0, 0).

• Design the function approximate-pi which allows the user to press a key to generate a new sample in the process of approximating pi. If no samples have been collected, the program should display text telling the user to press a key. Otherwise, it should display text about how many have been collected and the resulting approximation.

Exercise 4 Consider the following data definitions for a shell game:

; A CoinOrEmpty is one of:

; - "quarter"

; - "penny"

; - "empty"

(define-struct sg [left middle right])

; An SG (ShellGame) is a (make-sg CoinOrEmpty CoinOrEmpty CoinOrEmpty)

; and represents three cups/shells in a shell game, and what is under them

; A Guess is one of:

; - "left"

; - "middle"

; - "right"

• Provide examples and templates for the above data definitions.

• Design the function shuffle-right which moves all shell contents to the right. The rightmost contents should loop back to the left shell.

• Design the function winnings which returns the monetary value (in cents) of a Guess’d shell in a ShellGame.

• Design the function non-empty which returns the number of shells that are non-empty in a given ShellGame.

Exercise 5 A coat hanger on the back of an office door has two hooks (left and right) and a weight limit (how many pounds it can support on the hooks). Each hook has an individual weight limit (how much that one hook can support, in pounds) and a garment, which has a weight (in pounds) and color.

• Design data to support the above description. In your examples, you must describe a coat hanger of capacity 20 pounds, which has a 12-pound-limited left hook holding an 8-pound black jacket and a 14-pound-limited right hook holding a 13-pound red backpack. You must also provide at least one other example of your choosing.

• Design the function well-supported? that determines if the hanger garments are within both the individual hook limits as well as the total hanger limit.

• Design the function summary that produces a textual summary of a hanger, including its limit, hook limits, and garments (color and weight), and whether or not the hanger supports the garments (be sure to re-use functions you have written previously).

Exercise 6 Design the function thinking that visually animates a thinking face. As time passes, the pupils of both eyes should move between a left position, a middle position, and a right position (all looking up). When the user presses any key on the keyboard, the mouth should swap between two positions (smile and frown).