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 ChoiceTrees 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 Directionss 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.