►C211/  H211:   Introduction to Computer Science
▼Problem sets
►Problem set 6:   Unions and recursion
On this page:
1 Processing shows
2 Charting jobs
3 Calder mobiles
4 Challenge:   abstract painting
8.6.0.14
    contents  ← prev  up  next → 

Problem set 6: Unions and recursion

This assignment is due on Wednesday, October 5 at 11:59pm. Submit it using Handin as assignment ps6. Corrections can be presented until Friday, October 28.

This problem set builds on the skills that we introduced in Lectures 2−9 and 11−12. To encourage you to review those lectures, your grade on this assignment will be capped by your grade on those lectures at the time you submit (or correct) this assignment. You can resubmit lecture exercises at any time.

Remember to follow the design recipe whenever you design or write a function. In particular, every type mentioned in a signature must be introduced by a data definition, except for these well-known types: Number, Image, String, Color, Boolean, KeyEvent, MouseEvent, Anything.

If you think you need a long, complex function, you are likely overthinking it. Make sure you are grasping the material throughout the course. Do not start problem sets the day they are due.

1 Processing shows

Here are the data and structure definitions for a Show:
; A Show is one of:
; - (make-movie String Number Number)
; - (make-sitcom String Number Number)
(define-struct movie (title year minutes))
(define-struct sitcom (series season episode))
Here are some examples of a Show:
(define show1 (make-movie "One Cut of the Dead" 2017 97))
(define show2 (make-sitcom "Rick and Morty" 2 6))
(define show3 (make-movie "Welt am Draht" 1973 205))
(define show4 (make-sitcom "Futurama" 4 15))
You can use these example shows in your examples and tests. You can also watch them to gain appreciation for recursion.

Exercise 1. Write the template for a function that processes a Show. Make it look like a function called process-show, and do not put it in a comment.

Exercise 2. Design a function called show-minutes that computes how many minutes a given Show lasts. A sitcom lasts 20 minutes.

Exercise 3. Design a function called show-name that produces a string that names a given Show, like "One Cut of the Dead (2017)" or "Rick and Morty S2E6".

2 Charting jobs

Exercise 4. Develop a data definition Job that is either an entry or a promotion. Your data definition should look like this:
; A Job is one of:
; - FILL IN THIS BLANK
; - FILL IN THIS BLANK
To support this data definition, define a structure entry and a structure promotion:

  • An entry structure represents the first job that someone gets when they begin a career. It should contain the initial salary.

  • A promotion structure represents a later job that someone switches into after they begin a career. It should contain the raise (the difference between the old salary and the new salary) and should also contain the old job. The old job may be either an entry or a promotion.

Exercise 5. Define three examples of Jobs.

Exercise 6. Write the template process-job for your data definition Job.

Exercise 7. Design a function salary that accepts a Job and returns its salary, which is the initial salary of the entry plus all the raises of the promotions.

Exercise 8. Design a function pay-cut? that accepts a Job and determines whether it contains a negative raise at any point in time. Your function should return a Boolean. (A negative initial salary is not a pay cut.)

Exercise 9. Design a function promote that takes a Job and a raise amount, and returns the new Job that someone with the given Job would have after getting the given promotion.

Exercise 10. Design a function chart that takes a Job and draws a vertical bar chart that shows the history of Jobs that lead from the oldest (the leftmost bar, representing the entry) to the latest (the rightmost bar). For example, the vertical bar chart to the side depicts a Job that consists of an entry (like all Jobs) and four promotions.

The beside/align function will be very useful here. Look up its documentation and pay attention to what it produces when its first input is "bottom". You will also need the salary function you designed in Exercise 7. Scale the bars so that they fit comfortably on your screen for the example Jobs you defined in Exercise 5.

Hint: use the table method, like this:

3 Calder mobiles

Sheet metal, paint, metal rods, and steel wire

Calder mobiles are a kind of sculpture that can be represented using a self-referential data definition. Above is Les Mouettes (The Seagulls), 1965. Here are some ways to learn about Calder mobiles:

Typically, each rod in a mobile has two sub-mobiles hanging off of it. Let’s represent such a mobile using this data definition:
; A Mobile is one of:
; - (make-leaf Number)
; - (make-rod Mobile Number Number Mobile)
(define-struct leaf [weight])
(define-struct rod [lm ld rd rm])
In the field names of rod, the letters l r m d stand for left, right, mobile, and distance, respectively.

Exercise 11. Define three examples of Mobiles as constants, a leaf and two rods. Call them mobile1, mobile2, mobile3.

Exercise 12. Write the template process-mobile for a function that processes a Mobile.

Exercise 13. Design a function weight that takes a Mobile as input and computes its total weight. For simplicity, assume that the connection between the two sub-mobiles of a rod adds no weight.

Hint: you will write several functions that process a Mobile in this assignment, so it’s useful to write a separate template now and re-use it for all of the functions.

Exercise 14. Design a function average-leaf-weight that takes a Mobile as input and computes its leaves’ average weight. You’ll need a helper function that also takes a Mobile as input.

Exercise 15. Design a function all-balanced? that takes a Mobile as input and returns a Boolean indicating whether it is balanced everywhere. Use the following helper function to compute and compare torques, after providing its missing examples as tests.
; balanced? : Mobile -> Boolean
; determines whether the given mobile is balanced at the top
(define (balanced? m)
  (cond [(leaf? m) true]
        [(rod? m) (= (* (rod-ld m) (weight (rod-lm m)))
                     (* (rod-rd m) (weight (rod-rm m))))]))

Exercise 16. Design a function lighten that takes a Mobile as input and returns a new Mobile that is like the given one except everything weighs half as much as the given one. (So, your all-balanced? function should produce the same result for the given and returned mobiles.)

Exercise 17. Design a function enlarge that takes a Number and Mobile as inputs and returns a new Mobile that is like the given one except all the distances are that many times as long as the given one. (So, your weight, average-leaf-weight, and all-balanced? functions should produce the same results for the given and returned mobiles.)

Exercise 18. Design a function all-balanced-mobile that takes a positive integer as input and returns a Mobile that has exactly that many leaves (with positive weights) and satisfies all-balanced?.

Hint 1: Here is a data definition for positive integers:
; A PositiveInteger is one of:
; - 1
; - (+ PositiveInteger 1)
And here is the template for a function that processes a positive integer:
; process-positive-integer : PositiveInteger -> ...
(define (process-positive-integer n)
  (cond [(= n 1) ...]
        [else (... (process-positive-integer (- n 1)))]))

Hint 2: If you already have a Mobile that satisfies all-balanced?, then one way to make a Mobile that has exactly one more leaf and also satisfies all-balanced? is to balance the existing mobile against a new leaf whose weight is the total weight of the entire existing mobile. So this helper function is useful (but if you use it, provide its missing examples as tests):
; counterbalance : Mobile -> Mobile
; adds a leaf to a given mobile in a balanced? way
(define (counterbalance m)
  (make-rod m 20 20 (make-leaf (weight m))))

Hint 3: Study the excerpt below from The Ghost (maquette), 1964.

Painted sheet metal, metal rods, and steel wire

Help other students by answering this ungraded question: what did you have to learn to finish this problem set that we didn’t teach? Post your answer to Discord in the #ps6 channel, or put it as a comment at the bottom of your Handin submission.

4 Challenge: abstract painting

Here are the data and structure definitions for a Painting:
; A Painting is one of:
; - (make-solid String)
; - (make-hsplit Painting Painting)
; - (make-vsplit Painting Painting)
(define-struct solid [color])
(define-struct hsplit [top bottom])
(define-struct vsplit [left right])
Every Painting can be drawn as a rectangle of any size. A solid Painting is drawn as a rectangle filled entirely with the given color. An hsplit Painting is divided into two rectangles of equal size, one on the top and one on the bottom. A vsplit Painting is also divided into two rectangles of equal size, but one on the left and one on the right. So h stands for “horizontal” and v stands for “vertical”.

After you have defined several example Paintings, finish designing the following function so that you may visualize them:

; draw-painting : Painting Number Number -> Image
; draws the given painting with the given width and height
; (define (draw-painting p w h) ...)

In this challenge, you will design an interactive big-bang program that allows you to view a Painting and update the colors by clicking. For example, when I click on the rightmost rectangle of this picture

,

I see

.

To get started, we suggest that you design a program which turns any rectangle you click on to a particular color (e.g. "black"). This should be done with a function update which takes a Painting, a width, a height, an x-coordinate and a y-coordinate. The latter two inputs are understood as the point inside the rectangle whose color you would change. Note that the functions draw-painting and update do not have the required signatures to be used directly by big-bang; so you will have design two corresponding functions which call them as helpers using a width and a height that you pick.

Once you have this working, define an enumeration which contains a selection of colors (your palette) and a function next-color which can be used to cycle the color of a rectangle by repeated clicking.

    contents  ← prev  up  next →