Teaching
211 F '05
 
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
Set 13
Set 14

Problem Set 8

If you run any of the functions (as opposed to just testing them), comment out the code for running the functions before you submit your solution.

N.B.: Tests are not runs. A test is when you evaluate an expression and compare it to some expected result, while a run is when you evaluate an expression without anticipating any particular result for the expression.

Due date: 11/04 @ NOON

This problem set covers abstraction and "loops".

HtDP Problems:

none

To obtain any credit, you must use Scheme loops for the final definitions of the functions on this problem set. Recall that you do not have to use loops for the first draft. Programming is like writing; editing and improving the essay is everything.

Additional Problem 1:

A set may contain elements other than symbols. Develop a parameteric data definition for sets. Instantiate it for sets of symbols and sets of tuples of symbols.

Develop polymorphic contracts for element-of, domain, range, union, and intersect from Problem Set 7(2,3).

Additional Problem 2:

Here are the definitions for domain and range:

;; Relation -> Set
;; collect all first of
;; the tuples into a set 
(define (domain r)
  (cond
    [(empty? r) empty]
    [else (add-element
	    (first (first r))
	    (domain (rest r)))]))


;; Relation -> Set
;; collect all seconds of
;; the tuples into a set 
(define (range r)
  (cond
    [(empty? r) empty]
    [else (add-element 
	    (second (first r))
	    (range (rest r)))]))

The two functions are obviously similar to each other. Create complementary tests suites for both and then abstract over them.

An ternary relation is a set that consists of tuples of length 3. Example:


'((a b 1) (a c 2) (b b 1) (a b 3))

The domain is still the set of all firsts in a ternary relation but the range is the set of all rests. That is, the range is a plain (or binary) relation.

Design the function range3 for ternary relations. Then use the abstraction from above to define it.

Problem background for the next few problems:

The remaining problems cover the use of abstraction from the perspective of a game program.

In a "space war" game, the player can fire shots at the UFO as it descends. Visually a shot is a thin, yellow rectangle. The natural data representation of a shot is a Posn; the position represents the shot's top-most point.

Problem WW1:

Here is the function shots-create, which consumes a natural number and produces a list of Shots randomly placed in a 100 x 300 grid:


;; Shot = Posn 

;; shots-create : NaturalNumber -> (Listof Shot)
;; create n random Posns 
(define (shots-create n)
  (cond 
    [(zero? n) empty]
    [else (cons (make-posn (random 100) (random 300)) 
                (shots-create (sub1 n)))]))

Turn this into a one-line definition using a "loop".

Problem WW2:

Design the function shots-move. It consumes and produces a list of Shots and produces one. Its purpose is to move each shot upwards (by 3 pixels).

Modify the function so that if a shot is moved outside of the visible scene (a 100 x 300 grid), it is removed from the resulting list.

Problem WW3:

Design the function hit?, which consumes a Rectangle and a list of shots and determines whether any of the shots is inside the Rectangle.

(define-struct rectangle (x y width height))
;; A Rectangle is: 
;; --- (make-rectangle Number Number Number Number)
;; interpretation: the first two numbers specify the 
;; northwest (upper left) corner of the rectangle, 
;; the last two its width and height. The rectangle 
;; is assumed to be parallel to the axes. 

Problem WW4:

Design the function draw, which consumes a list of shots and produces a 100 x 300 scene with those shots. If a shot is only partially visible, it isn't drawn.

Optional Problem:

Combine the above functions to create a scenery of upwards-flying shots. When all shots have disappeared, the end of time has come. (See the documentation for world.ss for an explanation of this phrase.

last updated on Sat Nov 26 15:34:41 EST 2005generated with PLT Scheme