CSG 107: Problem Set 3

Due: Wednesday, February 4, 2009 at 500 pm.

Purpose:

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

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


Drill:

HtDP: 14.1.3, 14.1.6, 14.2.1-3, 14.4.1-3, 17.6.2, 17.6.5.


Required Problems:

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

  1. Design a program that updates an inventory represented as a binary tree:
    (define-struct inventory-item (name manufacturer in-stock))
    ;; Inventory-Item is (make-inventory-item Symbol Symbol Number)
    ;; Interpretation: in-stock represents the number of this item in stock.
    ;; Assumption: in-stock is >= 0.
    
    (define-struct inv-node (left right inventory-item))
    ;; Inventory is one of:
    ;; -- false
    ;; -- (make-inv-node Inventory Inventory Inventory-Item)
    ;; Assumption: an inventory is a binary search tree sorted by
    ;; name.
    

    Design a program (inventory-after-order name manufacturer inventory n) that takes an item name, a manufacturer name, an Inventory and a number, and produces an inventory like the original, except that the number of units in stock for this item is decremented by n. If the number of units in stock is less than n, return false instead. You may assume than n is greater than 0.

  2. Design the function forest-sum which computes the sum of the numbers in a forest. Here are the relevant data definitions:
    (define-struct tree (left right))
    ;; A Forest is one of
    ;; -- empty
    ;; -- (cons Tree Forest)
    ;; A Tree is one of
    ;; -- Number
    ;; -- (make-tree Forest Forest)
      
  3. Modify your solution to the LOSTR problem from problem set 2 to deal with nested lists:
    ;; A LOI ("list of items") is either
    ;; -- (cons Item empty)
    ;; -- (cons Item LOI)
    
    ;; An Item is either
    ;; -- a string
    ;; -- a LOI
    
    ;; A Style is one of:
    ;; -- 'solid-dot
    ;; -- 'open-dot
    

    Design a function LOI-to-image that takes a LOI and a Style and produces the corresponding image, as in Problem Set 2. A subitem should be indented, as it might be in an HTML UL. See, for example, http://www.w3schools.com/tags/tryit.asp?filename=tryhtml_lists2 (but you should produce an image with either all solid dots or all open dots, depending on the Style).

  4. Modify your Matryoshka doll simulation from the last problem set as follows:

    In the new simulation, you will manipulate multiple dolls, each with multiple individual dolls inside. As before, start with a single doll, fully assembled.

    At any state of the simulation, you may have up to 9 dolls on the stage. If you type the digit k, the outermost layer of the k-th doll on the stage (from left to right) should be lifted up. If you then type another number m, then the layer you just picked up should be dropped on the m-th doll. If the doll you are dropping is not larger than the doll you are dropping it on, the move should be rejected (flash the screen, make a noise, or something) and the piece you are moving should stay in mid-air. You may also drop a piece to the right of all the current dolls by typing the letter "n".

    The new simulation will not support the "d" and "a" commands from problem set 2, but it should support the "q" command.


Last modified: Wed Jan 14 16:05:23 EST 2009