# [racket] Missionaries and cannibals

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Tue Nov 30 09:08:54 EST 2010 Previous message: [racket] Missionaries and cannibals Next message: [racket] Missionaries and cannibals Messages sorted by: [date] [thread] [subject] [author]

```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)?
>
> 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
>
>

```

 Posted on the users mailing list. Previous message: [racket] Missionaries and cannibals Next message: [racket] Missionaries and cannibals Messages sorted by: [date] [thread] [subject] [author]