Homework Eight

Mutating Structures

Comp210

Due: 98.Nov.04 (Wed.)

You don't need to write templates if you don't want, but (as always) every function must have a contract, and (if it's not obvious from the name) a short description of what it does. A large component of the grade is based not so much on correctness, as on having a clearly organized, well thought out, straightforward solution. If you notice yourself repeating similar chunks of code, abstract over it!
  1. (3pts) Write collect using make-lists-fun, where collect (as seen in lecture) takes in a list and a criterion, and returns a list of all elements meeting that criterion.

    Recall that make-lists-fun (seen in lecture and similar to lab 8's fold) is the last list-processing function you'll ever need:

    ;; make-lists-fun:  
    ;; Based on the generalized template for lists,
    ;; where you pass in the base-case answer and
    ;; the rule to combine the first element with the
    ;; result of the recursive call,
    ;; and you are given back the corresponding list-processing-function.
    ;;
    ;; If you are wondering, the contract of the function which is returned is
    ;;    answer-fun: list-of-alpha --> beta
    ;; and so therefore we must have the contract 
    ;;    make-lists-fun: beta, (alpha, beta --> beta) 
    ;;                    --> (list-of-alpha --> beta)
    ;;
    (define make-lists-fun
      (lambda (base combine)
        (local [(define answer-fun
                  (lambda (lyst)
                     (if (empty? lyst)
                         base
                         (combine (first lyst)
                                  (answer-fun (rest lyst))))))]
               answer-fun)))
    

  2. You have a job as chief programmer for J-mart, and their inventory database.
    1. (0pt) An inventory record contains the name of an item, a price, a color, and how many are in stock. The placeholder total-inventory is a list of these inventory records, representing all items for sale. Define this placeholder with a list of several records.
    2. (1pts) Write a function select-by-color, which takes in a color, and returns a list of all inventory records in total-inventory for items of that color. (What previous function is the most appropriate for this?)
    3. (2pts) Write a function blue-light! which takes a list of inventory records and a discount-rate (e.g. 10%), and changes the price by the given discount-rate, but doesn't return anything. (You should use make-list-fun, or use map (not for the list it returns, but rather for its side-effect of calling a ``!'' function on the things in a list).)
    4. (2pts) Since it is spring, J-mart is having a white sale: All items with the color white are being reduced by 10%. Model this by first getting a list of white items, and then discounting the items in that list. The placeholder total-inventory is still the same list, but (manually) check to ensure that the correct elements in the list have been modified (mutated).

  3. (2pts) In this problem, you will implement (the infrastructure for) a simple maze navigation game. The maze is a collection of caves. Each cave has a name, and may contain one item, e.g., a bag of coins, a loaf of bread, a compass, a picture of president Gillis, etc. It also has a number of exits, each of which leads into a tunnel that connects to other caves or leads out of the maze altogether. All tunnels are one-way. If you want a two-way connection between two caves, use two one-way tunnels. In general, the connections between caves are arbitrary and may include tunnels from a cave to itself, several tunnels for connecting the same two rooms, etc.

    Note: For this homework, you only need to turn in Task 1 this week; you may turn in Tasks 2 and 3 either with this homework or with the next homework.

    Task 1 Define the function create-cave, which creates caves from a name (symbol), and an item (symbol) . Define the function connect-caves, which accepts two caves, c1 and c2, and a label lbl (symbol) and enters the pair (list lbl c2) as an exit into the exit list for cave c1. Finally, define the functions cave-name, cave-item, and cave-exits, which return the appropriate properties of a cave. Caves labeled 'Exit will serves as exits from the maze. You can test your functions with a small example cave. If you make extensive test cases and want to let other people use them, put a copy in your home directory and post to the newsgroup!

    As the player walks through the maze, she can collect two items. When the player enters a cave, she may pick up the item, if one of the pockets is empty or exchange one of the two items for the item in the cave. Once the player is happy with the state of the items, she moves on by choosing one of the exits out of the cave. The game is over when the player exits the maze.

    Task 2 Define the function create-player, which accepts a cave and creates a player who is in that cave and with nothing (empty) in their pockets. You will also need the functions player-left-pocket, player-right-pocket, and player-current-cave. Then define the function swap-items, which accepts a player, a cave (if you like), and one of the symbols 'left, 'right. It swaps the item (or empty) in the indicated pocket with the item in the cave. Swap-items has no (useful) return value.

    The walk is simulated with a simple generative recursive program. It prints a question and reads a typed response from the keyboard. The response is one of a pre-determined number of symbols: 'show-pockets, 'show-exits, 'swap-left, 'swap-right and 'leave. In the latter case, the program asks one more question which must be answered with a number. It then selects the exit from the current cave with this number and moves the player to this next cave.

    Task 3 Implement the dialogue. You may use the following functions:

    1. read, which takes no argument and returns the symbol it reads from the input (keyboard);
    2. printf, which takes a string and prints it to the current line in the evaluation window of DrScheme;
    3. newline, which takes no argument and ends the current line.
    For simplicity, you should implement each command as a one-symbol command.

    Here is a sample dialogue:

    You entered the cave LovettHall.  It contains water. 
    What would you like to do next? swap-left
    You just put down shoes and picked up water.
    What would you like to do next? swap-right
    You just put down bread and picked up shoes.
    What would you like to do next? show-pockets
    You own water in the left and shoes in the right pocket.
    What would you like to do next? leave
    There are 5 exits. Which one would you like to take? 3
    ...
    
    (A better dialogue might list the names of the five exits.)
    The first line could be produced with
        (printf "You entered the cave ~s.  It contains ~s.~n" 'LovettHall 'water)
    

    End of Problem This problem is open-ended and flexible. The design of the dialogue is up to you. You are in control of how you output descriptions of items, caves, or connections, if you choose to do so. It may be a simple text-based dialogue as above. It is acceptable to implement the minimum described above, but don't feel constrained by this standard; if you implement more, tell us. Be creative!