Ken, you have not absorbed the design recipe for accumulators. Your function needs to exploit the knowledge in the accumulator to terminate on occasion. See graph traversal for an example -- Matthias
p.s. Work backwards in your function. Start from a state that you know will terminate in 0 steps, 1 step, 2 steps, etc. You may even wish to use the Stepper to watch it (non)terminate. p.p.s. What Stephen said, too. On Nov 29, 2010, at 10:30 PM, Ken Hegeland wrote: > I've almost managed to create mc-solvable as the book wants it. I originally > designed it to take a list of states, and I changed it to accept a list of > states, list of(listof states), or a single state. I can get it to produce > true for states that have a solution, but I am unsure how exactly to make it > create a false output. I have defined and tested the following states: > > (define state1'((0 0)right(3 3))) > (define state2'((1 0)right(2 3))) > (define state3'((0 1)right(3 2))) > (define state4'((2 0)right(1 3))) > > (mc-solvable state1) > (mc-solvable state2) > (mc-solvable state4) > all three of these input states produce true in a negligible amount of time. > > but (mc-solvable state3) seems to loop and never find an answer. I believe I > haven't found what exactly should produce false. > > It seems simple to think that if it reaches an empty list for next possible > moves, it should produce false, but will this ever occur? > > Using this code I've created what I believe will be a working mc-solution, I > simply need to be able to produce false from mc-solvable. > > Thanks for the help I will take what you said into consideration while I try > to find the solution. > > --- On Tue, 11/30/10, Matthias Felleisen <matth...@ccs.neu.edu> wrote: > > From: Matthias Felleisen <matth...@ccs.neu.edu> > Subject: Re: [racket] Missionaries and cannibals > To: "Ken Hegeland" <hege...@yahoo.com> > Cc: us...@lists.racket-lang.org > Date: Tuesday, November 30, 2010, 3:19 AM > > > 1. Your sketch sounds about right. The problem is probably sticking to the > discipline of turning it into code. > > 2. The infinite loop is troubling -- but looking at your code is the wrong > thing. The goal is to empower yourself so that you can do such things on your > own w/o help from others. > > Have you thought thru why the algorithm should terminate (step 7 of the > gen-rec design recipe)? > If so, have you checked your program to make sure it adheres to your > reasoning? > > 3. You wrote "m thinking that the goal is to define mc-solvable? and use it > in mc-solution sort of like the backtracking algorithm for finding-route." > That's about right. In a sense, the MC problem generates a graph and the > algorithm searches the graph for feasible routes from the initial state > > xxx | <> | > ooo | | > > to the final state: > > | <>| xxx > | | ooo > > -- Matthias > > _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
