Due: Wednesday, March 11, 2009 at 5:00 pm.
The goal of this problem set is to help you recognize when generative recursion and accumulators may be helpful and to use them when they are. Note: not all problems in this set use generative recursion or accumulators!
As always, you must follow the design recipe. You must annotate each function with the design strategy that you used:
HtDP: 26.2.1, 26.3 (all), 27.2.3-5, 28.2 (all)
;; find-root2 : (Number -> Number) Number Number[>0] -> Number ;; (find-root f lo delta) ;; assumes: f monotone, f(lo) <= 0 <= f(lo+delta) ;; returns: z such that there is a root of f in [z, z+TOLERANCE)
value-of : DiffExp -> Numberthat finds the value of a DiffExp. For example:
(value-of (make-diffexp (make-diffexp 2 4) (make-diffexp 3 5))) = (- (value-of (make-diffexp 2 4)) (value-of (make-diffexp 3 5))) = (- (- (value-of 2) (value-of 4)) (- (value-of 3) (value-of 5))) = (- (- 2 4) (- 3 5)) = (- -2 -2) = 0To make it easier to write your test cases, you may use your function decode from last week. However in ISL, there is no way to give a list structure directly to Scheme and get its value.
Design a function
solution : State (State -> Boolean) -> Listof(Move) | false (solution state winning-state?) returns a list of moves that transforms the given state into a winning state, or false if there is none.Remember that Move is the data representation of moves, which you designed last week.
Hint: the states of the pitchers correspond to the nodes of a graph, and the moves correspond to the edges. This graph is probably too big to construct, but you can still easily write something corresponding to the neighbors function.
For examples of this problem where there is a solution, verify that the sequence your program finds really is a solution by testing it using your function simulate from last week.
Last modified: Tue Feb 24 12:24:10 2009