On this page:
1 Many pairs of numbers
2 Stars and Planets
6.10.1

Assignment 5: Recursion

This assignment is due on Wednesday, 9/20 at 11:59 PM. Submit it using the handin server as assignment a5.

Important Note Whenever we say to "design a function", we mean that you need to follow the design recipe. Any other time that you write a function in this class, you also need to follow the design recipe.

1 Many pairs of numbers

Variations of the exercises in this section have been done in class. Please review the lecture code from class (available under Resources in Piazza) as you work the exercises. Sometimes your solutions will look similar to in-class solutions: this is fine.

Example Here is a sample exercise and a solution.

Sample exercise: Develop a data definition Numbers which can store arbitrarily many numbers. Define corresponding structures named no-numbers and some-numbers.

Solution:
; A Numbers is one of:
; - (make-no-numbers)
; - (make-some-numbers Number Numbers)
 
(define-struct no-numbers [])
(define-struct some-numbers [n ns])

Note: You must develop your own data definition and your own structures. You may only use built-in primitive types, not any existing structures.

Exercise 1 Develop a data definition named Pair and a structure named pair for storing a pair of numbers representing x and y coordinates.

Exercise 2 Develop a data definition Pairs which can store arbitrarily many pairs of numbers using the data definition from the previous exercise. Name the structures you define no-pairs and some-pairs.

Exercise 3 Write the templates for both data definitions you have developed.

Exercise 4 Design a function called draw-pairs, which, given a Pairs, visualizes each of the pairs as a circle with radius 10 at location (x,y) (obtained via pair-x and pair-y) on an empty scene.

In the following exercises, we will create two interactive animations with big-bang. Both will be simple paint programs which use draw-pairs from Exercise 4.

In the first version, any mouse event will paint circles on the scene, and any keyboard event will undo the most recent painting operation (if there is one). In the second version, these operations will require specific mouse events, "button-down" and "drag", and a specific key event, "z".

For big-bang, a World is always a Pairs.

Exercise 5 Design an on-mouse function for big-bang called any-paint. Given Pairs, two numbers for x and y coordinates and a MouseEvent, any-paint causes big-bang to paint a new circle on the scene. Recall that an on-mouse function returns a World: so any-paint returns a Pairs.

Design also an on-key function for big-bang called any-undo. Given Pairs and a KeyEvent, any-undo causes big-bang to remove the most recently painted circle from the scene. Recall that an on-key function returns a World: so any-undo returns a Pairs.

Finally, define a function run-any that takes a Pairs as an initial World and runs big-bang with draw-pairs, any-paint and any-undo. Recall that big-bang returns the final World: so run-any returns a Pairs.

Exercise 6 Design an on-mouse function for big-bang called paint. Given Pairs, two numbers for x and y coordinates and a MouseEvent, paint does the following. If the MouseEvent is "button-down" or "drag", paint causes big-bang to paint a new circle on the scene. If the MouseEvent is anything else, paint causes big-bang to do nothing to the scene.

Design also an on-key function for big-bang called undo. Given Pairs and a KeyEvent, undo does the following. If the key pressed is "z", undo causes big-bang to remove the most recently painted circle from the scene. If any other key is pressed, undo causes big-bang to do nothing to the scene.

Finally, define a function run that takes a Pairs as an initial World and runs big-bang with draw-pairs, paint and undo.

2 Stars and Planets

Exercise 7 Develop a data definition SolarObject that is the union of a sun and a planet, i.e., a SolarObject is one of .... To support this data definition, define a structure sun for storing a sun, and a structure planet for storing a planet.

A sun is similar to the solid doll that we discussed in class.

A planet should contain a distance to next inner planet, and should also contain the next inner most planet. Much like we defined a hollow doll in class, a planet’s inner planet is like the inner nested doll in a hollow doll. This time however, an inner planet may be either another planet, or it may be a sun.

Exercise 8 Write the template process-solar-object for your data definition SolarObject.

Exercise 9 Design a function distance-of-solar-object which accepts a SolarObject and calculates and returns the distance of the outermost solar object to the center of the solar system. For example, the distance of a sun should be zero, because a sun is located at the center of the solar system. To take another example, say we have a system of 3 objects, with a sun, planet1 with a distance of 100, and planet2 with a distance of 200; then, the distance of the system (planet2) to the center should be 300.

Exercise 10 Design a function add-to-solar-object which accepts a SolarObject and a distance, and returns a new SolarObject which has the given SolarObject plus a new planet that is the given distance away from its inner object. The given SolarObject should be the inner object of the new planet.

Exercise 11 Design a function draw-solar-object which draws a SolarObject. The sun in the SolarObject should be drawn simply as a small solid size 20 circle in the middle. Each planet in the SolarObject should be drawn as a circle with a radius that you calculate as the distance of the planet to the center of the solar system. So, a system of 3 objects, with two planets and a sun, should appear as a small solid size 20 circle in the middle, surrounded by two rings, with the radius of each ring being the planets’ distance to the center.

The overlay function will be very useful here. Remember, the overlay function stacks all of its arguments building a single image. The first argument goes on top of the second argument, and the images are all lined up on their centers. For example:

(overlay  (circle 20 "solid" "blue") (circle 30 "outline" "red"))

will produce an image where a small solid blue circle is stacked on top of a larger hollow red ring. This could be an example of drawing a SolarObject with one planet and one sun.