[racket] Missionaries and cannibals

Still not have solved it but I feel like I am getting close.

I developed a program that looks like this in step form
1. check if input is final, if it is return true, else
2.check if empty, if true return false(already thinking this isn't necassary
3. generate possible moves.
4. check if input has been seen in an accumulator.
5. check if possible moves is empty, if it is return false
6.else (or(recurse on first item in possible moves, and add input to the accumulator
             (recurse on rest items in possible moves.

I am able to get it to return for some state inputs where an answer can be found, but I simply cannot figure out how to produce a false.
I think that it should produce false if every item in possible moves has already been seen or is empty. How I have it set up it simply checks if its been seen and moves to the next item.

I feel close but still can't figure out a way to produce false.


--- 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, 2:08 PM


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
> 
> 




      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101201/8f0e127e/attachment.html>