[racket] Missionaries and cannibals

Im about to take a break from this problem for a few days and read ahead and come back. I have a few things I want to ask before that though.

In the book it said that generally an accumulator should be added after completing the function, is it not possible without one, or is it just very difficult?

I re-did the entire data representation and all the helper functions up to mc-solvable a few moments ago. Initial state was:
'((0 0)'right(3 3)), with the new representation, I changed it to:
(make-state(make-group 0 0)'right(make-group 3 3)).

I feel like I have a decent understanding of accumulators, perhaps I will re-read that section a few more times. I was thinking of adding an accumulator into the data representation as the hint suggests. When I do I have trouble though.

My idea is to change the function which generates possible moves from some input state.
I changed the structure representation to
(define-struct state(left bp right history))
where left and right are groups, bp is a symbol, and history is a list of states

so initial should look like
(make-state(make-group 0 0)'left(make-group 3 3)empty)) and I added something onto the end of the step generator to cons the input state onto the input history.

(possible-m input)=(make-state(make-group 0 1)'right(make-group 3 2)input) and so on for all the other boat loads possible.

My problem is if I take one item from the answer of (possible-m input) and use it as a new input it works as expected, except for it has the initial showing 2 times in history.

(possible-m initial)=(list
 (make-state
  (make-group 2 0)
  'left
  (make-group 1 3)
  (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 1 1)
  'left
  (make-group 2 2)
  (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 0 2)
  'left
  (make-group 3 1)
  (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 1 0)
  'left
  (make-group 2 3)
  (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 0 1)
  'left
  (make-group 3 2)
  (list (make-state (make-group 0 0) 'right (make-group 3 3) empty))))

if I take one of those and apply possible-m I get

 (possible-m(make-state

  (make-group 2 0)

  'left

  (make-group 1 3)

  (list (make-state (make-group 0 0) 'right (make-group 3 3) empty))))=

(list
 (make-state
  (make-group 0 0)
  'right
  (make-group 3 3)
  (list
   (make-state
    (make-group 2 0)
    'left
    (make-group 1 3)
    (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
   (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 1 -1)
  'right
  (make-group 2 4)
  (list
   (make-state
    (make-group 2 0)
    'left
    (make-group 1 3)
    (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
   (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 2 -2)
  'right
  (make-group 1 5)
  (list
   (make-state
    (make-group 2 0)
    'left
    (make-group 1 3)
    (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
   (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 1 0)
  'right
  (make-group 2 3)
  (list
   (make-state
    (make-group 2 0)
    'left
    (make-group 1 3)
    (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
   (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
 (make-state
  (make-group 2 -1)
  'right
  (make-group 1 4)
  (list
   (make-state
    (make-group 2 0)
    'left
    (make-group 1 3)
    (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))
   (make-state (make-group 0 0) 'right (make-group 3 3) empty)))).

Sorry about the extremely long post. I know I need to solve this myself but I can't quite figure out what I am missing.

If I can get the state with the accumulator built in to work as I want I think I can have legal also return false if input matches some item in history. This would allow me to filter out all illegal moves and previously seen moves.


--- 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/20101130/a54af87e/attachment.html>