Purpose:

The goal of this problem set is to help you design functions that deal with arbitrarily large data, especially tree-shaped data.

---

Drill:

HtDP: 9.5.4, 9.5.6, 10.1.7, 10.2.2, 10.2.3, 12.4 (large!)

---

Required Problems:

Note: You may use DrScheme's HtDP Beginning Student Language to solve the problems or, if you are comfortable with using Intermediate Student Language, you are welcome to switch.

1. Design a program that updates an attribute list:

   
       (define-struct attribute (key value))
       ;; LOA is one of: 
       ;;  -- (cons Attribute empty)
       ;;  -- (cons Attribute LOA)
       ;; Attribute is (make-attribute String Number)
   

   The update program is given an LOA and a String s. For each attribute on the list for which s is string<=? than the attribute's key, the attribute's value is increased by 1.

   Hint: The design guideline suggests the use of two distinct functions when applied to the data definition. Why?

2. In some countries there is a tradition of wrapping gifts in several boxes of distinct colors. Here is a data representation of this idea:

   
       (define-struct china (below layer))
       ;; A Gift is one of: 
       ;;  -- Image 
       ;;  -- (make-china Gift ColorSymbol)
       ;; interp.: A data representation of a nested series of gift boxes. 
   
       ;; LOS is one of: 
       ;;  -- (cons Image empty)
       ;;  -- (cons ColorSymbol LOS) 
   

   Imagine you are writing a script for a robot that is supposed to wrap or unwrap such gifts.

   Design the function unwrap, which maps a Gift to an LOS.

   Design the function wrap, which maps a LOS to an Gift.

   Design the function image, which maps a Gift to an Image. Each layer draws an appropriately colored box around the box inside, adding 5 pixels in each dimension. Here is my favorite gift:

   

3. Design a program that renders an "Enum" as an image:

   
       (define-struct ul (list nested?))
       ;; Enum is one of: 
       ;; -- (make-ul LOI Boolean)
       ;; LOI is one of: 
       ;; -- (cons String empty) 
       ;; -- (cons String LOI)
       ;; interp. an enum contains a list of items; the second 
       ;; fields specifies  whether the enumeration uses the 
       ;; "plain" or the "nested" style of bullets. 
   

   The rendering program consumes an enum, which specifies both the items and the nesting style of the enumeration.

   Here are two examples:

          

   Hint 1: The design guideline suggests the use of two distinct functions when applied to the data definition. Why? Hint 2: This problem is related to problem 1.3. Do try to reuse the images (bullets) and image composition functions you designed for that problem but do start from scratch for the rest. Otherwise you will spent a long time on this problem.

   Domain knowledge: The rendering inserts exactly one "string space" between the "enumeration anchor" (i.e., bullet or circle) and the text of the item.

4. Project: The purpose of this exercise is to design a program that simulate the movement of a ball in a square box that is open at the top. The ball moves on a straight line at constant speed, unless it hits one of the three walls (or two corners), in which case it bounces perfectly. When the ball leaves through the top, the simulation is over. Assume: The ball has an initial velocity that moves it on non-horizontal lines.

   Constraint: Designing a proper solution for this problem requires a design technique that you do not yet know. Your solution will therefore use a function move-ball, which computes the ball's next location and velocity for a one-tick interval. If during this tick the ball hits an obstacle, the function "moves" the ball to the obstacle and "changes" its speed appropriately. Otherwise it "moves" the ball as far as possible.

   

   Hint 1: This problem demands a systematic approach to the design of examples and tests. If you follow this advice the problem is labor-intensive but reasonably straightforward.

   Hint 2: You are designing a "World" program so keep in mind to start with a data definition of the world; to add global and especially visual constants; and to then design two functions: one for creating an image from the world and one for computing what happens to a world during one tick.