CSG 107: Problem Set 5

Due: Wednesday, February 18, 2009 at 5:00 pm.

Purpose:

The goal of this problem set is to help you recognize when accumulators may be helpful and to use them when they are. Note: not all problems in this set use accumulators!

As always, you must follow the design recipe. If you are using the structure strategy, be sure to say which argument you are doing it. If you are using an accumulator, please tell us which argument is the accumulator and state the invariant that describes what the accumulator represents.

Drill:

HtDP: 31.3: all; 32.1: all, 32.3: all.

Required Problems:

1. Extend your solution to the LOI problem from Homework 3 by adding an additional Style, as follows:

   ;; A Style is one of:
   ;; -- 'solid-dot
   ;; -- 'open-dot
   ;; -- 'numbered
   

   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 or OL. For the numbered style, subitems should be indented and numbered. For example, your output might be an image that looks like

   1. An item
   2. Another item
     1. A subitem of 2
     2. Another subitem of 2
       1. A sub-subitem of 2.2
       2. Another sub-subitem of 2.2
       3. And yet a third one (of 2.2)
     3. Again a subitem of 2
       1. And again a sub-subitem 2.3
       2. Another one (of 2.3)
     4. One more subitem (of 2)
   3. And another item
   4. One final item
   

   The exact indentation doesn't matter, but it should be the same as for the solid-dot and open-dot styles.

2. Pieces of information may be represented in different ways. For example, (cons 3 (cons 5 empty)), (list 3 5), and '(3 5) all represent the same list. In class, we discussed difference expressions, which had the following structure and data definition:

   (define-struct diffexp (exp1 exp2))
   ;; A DiffExp is either
   ;; -- a Number
   ;; -- (make-diffexp DiffExp DiffExp)
   

   This is a machine-friendly representation. A more human-friendly representation of this information might use lists. For example:

     '(- 3 5)             corresponds to (make-diffexp 3 5)
     '(- 2 (- 3 5))       corresponds to (make-diffexp 2 (make-diffexp 3 5))
     '(- (- 2 4) (- 3 5)) corresponds to (make-diffexp  
                                           (make-diffexp 2 4)
                                           (make-diffexp 3 5))
     '(- 3)               does not correspond to anything
     '(+ 3 5)             does not correspond to anything
     '(- (+ 3 5) 5)       does not correspond to anything
     '((1))               does not correspond to anything
     '((- 2 3) (- 1 0))   does not correspond to anything
   

   Design a function decode that converts from the representation on the left to the representation on the right.

   Here are the relevant data definitions and the contract:

   ;; An AtomicSymbol is either
   ;; -- '-
   ;; -- a Number
   
   ;; An (SexpOf X) is either
   ;; -- an X
   ;; -- a (listof (SexpOf X))
   
   ;; decode : (SexpOf AtomicSymbol) -> DiffExp | false
   ;; (decode s) returns the DiffExp corresponding to s, or false if s 
   ;; does not correspond to anything.
   

3. There is a series of classic puzzles about pouring from one pitcher to another. Here are two examples that I got from the web.

   Here we have an eight-quart pitcher filled with juice, an empty five-quart pitcher, and an empty three-quart pitcher. The pitchers are unmarked, and your task is to divide the eight quarts of juice so that both the five-quart pitcher and the eight-quart pitcher are each holding exactly four quarts.

   On the counter we have a 10-quart pitcher full of milk, an empty seven-quart pitcher, and an empty three-quart pitcher. The pitchers are unmarked, and your task is to divide the 10 quarts of milk so that both the 10-quart pitcher and the seven-quart pitcher are each holding exactly five quarts.

   The permissible moves in the game are:

   • Pour the liquid from one pitcher to another until the first pitcher is empty, or the second pitcher is full, whichever comes first.
   • Empty the contents of a pitcher down the drain.

   Design a data representation called State that is capable of handling any such puzzle. Your states should handle any number of pitchers, each of any capacity.

   Also, design a representation for the moves of the game.

   Then design a function

   simulate : State (listof Move) -> State | false  
   

   which, given a state and a list of moves, gives the state resulting from executing those moves (in the order they occur in the list), or else returns false if any of the moves are illegal in the state in which it is to be executed.

4. Add to your representation above an "undo" move, which undoes the last move. You should have unlimited undo: that is, having done some sequence of moves, you should be able to undo them all by repeatedly doing an "undo", eventually getting back to the starting state.

   Hint: your State will need to contain more information than it did for the preceding problem.