[racket] Missionaries and cannibals

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 <matthias at ccs.neu.edu> wrote:
> 
> From: Matthias Felleisen <matthias at ccs.neu.edu>
> Subject: Re: [racket] Missionaries and cannibals
> To: "Ken Hegeland" <hegek87 at yahoo.com>
> Cc: users at 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
> 
>