Due: Wednesday, February 18, 2009 at 5:00 pm.
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.
HtDP: 31.3: all; 32.1: all, 32.3: all.
;; 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.
(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.
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:
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 | falsewhich, 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.
Hint: your State will need to contain more information than it did for the preceding problem.
Last modified: Fri Feb 06 15:57:49 2009