CSG 107: Problem Set 2

Due: Wednesday, January 28, 2009 at 500pm

Purpose:

The goal of this problem set is to help you design functions that deal with arbitrarily large data.

Remember that you must follow the design recipe. Your deliverables include the data analysis, contract and purpose header, template, code, and tests. (Remember that there is no deliverable corresponding to the template.)

Your template should be delivered in a form like that in the book. For example, if your function consumes a structure, then you should deliver a template like that in Section 6.5 of HtDP.


Drill:

HtDP: 9.5.3, 9.5.7, 9.5.8 (produce an image), 10.1.5, 10.2.1, 10.2.3


Required Problems:

Note 1: You may use DrScheme's HtDP Beginning Student Language to solve the problems, or you may switch to the Intermediate Student Language if you prefer.

  1. Design a program that updates an inventory:
    (define-struct inventory-item (name manufacturer quantity))
    ;; Inventory-Item is (make-inventory-item Symbol Symbol Number)
    
    ;; List-of-Inventory-Item is one of:
    ;; -- empty
    ;; -- (cons Inventory-Item List-of-Inventory-Item)
    

    Design a program remove-manufacturer that takes a List-of-Inventory-Item and a manufacturer and produces a new List-of-Inventory-Item like the original, except that all the items by that manufacturer have been removed.

  2. Modify your solution to the enum3 problem from problem set 1 to deal with lists of unbounded length, rather than of length 3:
    ;; A LOStr ("list of strings") is either
    ;; -- empty
    ;; -- (cons String LOStr)
    
    ;; A Style is one of:
    ;; -- 'solid-dot
    ;; -- 'open-dot
    

    Design a function LOStr-to-image that takes a LOStr and a Style and produces the corresponding image, as in PS1.

    Note that the catalog of styles is much smaller than the one in PS1. We'll learn how to deal with the others later on. (If you want to impress us, figure out how to do the 'number now.)

  3. A matryoshka doll, also called a stacking doll, is a set of individual dolls of decreasing sizes placed one inside the other. Here is a picture, from Wikipedia:

    seven matryoshka dolls

    Here is a representation of that idea, with each invidual doll represented as a symbol:

    (define-struct doll (outermost inner-doll))
    
    ;; A Doll is one of:
    ;; -- (make-doll Symbol empty)
    ;; -- (make-doll Symbol Doll)
    

    Design the following functions:

    1. assemble, which takes a nonempty list of symbols and produces the corresponding Doll.
    2. disassemble, which takes a Doll and produces a list of dolls, each consisting of exactly one of the indvidual dolls that made up the original.
    3. doll<?, which takes two Symbols and a Doll and produces true if and only if the first Symbol occurs inside the second one in the doll.

  4. Using the World package, create an animation of Matryoshka dolls. Get an image of a set of Matryoshka dolls from the web (be sure to credit your source!) and use it as the basis for your animation. Your dolls will use these images instead of the symbols used in the preceding problem.

    Your animation should start with the doll fully assembled. When you push the "d" ("disassemble") key, the top layer of the doll should come off and stand next to the doll. You should be able to do this as many times as there are individual dolls in the doll, resulting in all the individual dolls standing in a row.

    When you push the "a" ("assemble") key, the smallest available individual doll should go back on the main doll. So "d" followed by "a" should leave the world unchanged. "a" on a fully-assembled doll should have no effect.

    Unlike the functions assemble and disassemble from the preceding problem, these actions work one layer at a time.

    When you push the "q" ("quit") button, the entire animation should quit.

    Write a function start that takes one argument, ignores it, and starts the animation. This way you can test your "q" event without re-running your system.

    For extra respect, make the assemble and disassemble actions move the pieces in a continuous way, rather than just jumping to the next state of the world. (You, too, can produce an episode of South Park).


Last modified: Mon Jan 12 14:53:29 EST 2009