CS 5010 F '09 Pair Programming The Recipes The Style Subversion Assignments Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12

### Problem Set 3 Due date: 10/07

Purpose:

The goal of this problem set is to help you design functions that deal with arbitrarily large data, especially trees, forests of trees and trees of forests, and forests of forests.

#### Drill:

HtDP: 14.1.4, 14.1.6, 14.2.1, 14.2.2, 14.2.3, 14.2.4, 17.6.4, 17.6.6, 17.7.1, 17.7.2, 17.7.3, 17.7.4

#### Required Problems:

Note: You must use DrScheme's HtDP Intermediate Student Language.

1. Economists use "choice trees" to record how decisions are made in so-called binary situations:

``````    (define-struct choice (left right))
;; An ChoiceTree is one of:
;; -- Number
;; -- (make-choice ChoiceTree ChoiceTree)
``````
The weight of a `ChoiceTree` is the sum of its numbers.

For the analysis of `ChoiceTree`s we need two functions:

1. `balanced?`, which determines whether a `ChoiceTree` is balanced.

Definition: A balanced choice tree contains only instances of `choice` structures whose two subtrees have the same weight.

2. `decide`, which consumes an `ChoiceTree` and a list of `Directions`s to find a final decision---a leaf---in the tree.

Definition: A `Direction` is one of: `"left"` or `"right"`.

Naturally, `decide` works just like a person who is given a list of directions in a city. When, however, the function exhausts the list and hasn't discovered a leaf yet, it signals an error. Similarly, it is also an error if the function reaches a leaf and there are some directions left.

2. Design the function `sumF`, which adds up all the numbers that occur in a forest. Here are the relevant data definitions:
``````    ;; A Forest is one of:
;;  -- empty
;;  -- (cons Tree Forest)
;; A Tree is one of:
;;  -- Number
;;  -- (cons Forest (cons Number (cons Forest empty)))
``````
3. Design a program that renders an `Expr` as an image:
``````     (define-struct pls (x in?))
(define-struct mul (x in?))
;; Expr is one of:
;; -- Number
;; -- (make-pls (cons Expr 1LON) Boolean)
;; -- (make-mul (cons Expr 1LON) Boolean)
;; 1LON is one of:
;; -- (cons Expr empty)
;; -- (cons Expr 1LON)
;; interp. a pls struct represents an addition expression
;; with at least two sub-expressions; a mul represents a
;; multiplication; the boolean flag indicates whether it
;; represents an infix or a prefix expression.
``````
The rendering program consumes an `Expr` and produces an image. It ignores the boolean flags and instead renders all expressions as prefix expressions.

Here are two examples:
 ``````(make-pls (list 1 3 2) true) `````` ``````(make-mul (list (make-pls (list 1 3 2) true) (make-mul (list 1 3 2) true)) false)`````` Hint: This problem is related to problems 1.3 and 2.3.

Domain knowledge: The rendering places only the first sub-expression of an addition or multiplication on the same line as the operator. All others are on separate lines below the first line, always indented by five pixels -- relative to the beginning of the inner-most sub-expression. The closing parentheses of an expression appears on its last line.

4. Mini Project: Design a Space Invader program.

The player is in control of a ``tank'' (render as a small rectangle) that must defend earth (the bottom of the canvas) from a UFO (``flying saucer'') that descends from the top of the canvas to the bottom. In order to stop the UFO from landing, the player may fire missiles (triangles, smaller than the ``tank'') -- as many as desired. To fire a missile, the player hits the space bar and, in response, a missile emerges from the tank. If the UFO collides with any of the fired missile, the player wins; otherwise the UFO lands and the player and ``earth'' is lost.

Here are some details concerning the movement of the three game objects. First, the tank moves a constant velocity along the bottom of the canvas. The player may use the left arrow key and the right arrow key to change directions. Second, the UFO descends at a constant speed but makes small random jumps to the left or right---without ever disappearing from the canvas. Third, once fired a missile ascends along a straight vertical line at a constant speed at least twice as fast as the UFO descends. Finally, the UFO and the missile ``collide'' if their reference points are close enough---for whatever you think ``close enough'' should mean.

BSL and ISL come with the function

``````
;; random : NaturalNumber -> NaturalNumber
;; (random n) produces a number in [0,n)
(define (random n)
;; magic happens here
...)
``````
Use this function to move the UFO randomly, but remember to always keep the UFO inside the canvas's boundaries. -- To test functions that employ `random`, create a main function that calls an auxiliary function. The auxiliary function should not use `random` and should perform all computations. Instead the main function should call the auxiliary function on random numbers. That way you can still test the auxiliary function where all the real computation happens.

 last updated on Wed Dec 2 17:58:10 EST 2009 generated with PLT Scheme