<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">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.<br><br>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?<br><br>I re-did the entire data representation and all the helper functions up to mc-solvable a few moments ago. Initial state was:<br>'((0 0)'right(3 3)), with the new representation, I changed it to:<br>(make-state(make-group 0 0)'right(make-group 3 3)).<br><br>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.<br><br>My idea is to change the function which generates
 possible moves from some input state.<br>I changed the structure representation to<br>(define-struct state(left bp right history))<br>where left and right are groups, bp is a symbol, and history is a list of states<br><br>so initial should look like<br>(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.<br><br>(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.<br><br>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.<br><br>(possible-m initial)=(list<br>&nbsp;(make-state<br>&nbsp; (make-group 2 0)<br>&nbsp; 'left<br>&nbsp; (make-group 1 3)<br>&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp;
 (make-group 1 1)<br>&nbsp; 'left<br>&nbsp; (make-group 2 2)<br>&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 0 2)<br>&nbsp; 'left<br>&nbsp; (make-group 3 1)<br>&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 1 0)<br>&nbsp; 'left<br>&nbsp; (make-group 2 3)<br>&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 0 1)<br>&nbsp; 'left<br>&nbsp; (make-group 3 2)<br>&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty))))<br><br>if I take one of those and apply possible-m I get<br><br>&nbsp;(possible-m(make-state<br>
&nbsp; (make-group 2 0)<br>
&nbsp; 'left<br>
&nbsp; (make-group 1 3)<br>
&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty))))=<br><br>(list<br>&nbsp;(make-state<br>&nbsp; (make-group 0 0)<br>&nbsp; 'right<br>&nbsp; (make-group 3 3)<br>&nbsp; (list<br>&nbsp;&nbsp; (make-state<br>&nbsp;&nbsp;&nbsp; (make-group 2 0)<br>&nbsp;&nbsp;&nbsp; 'left<br>&nbsp;&nbsp;&nbsp; (make-group 1 3)<br>&nbsp;&nbsp;&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;&nbsp; (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 1 -1)<br>&nbsp; 'right<br>&nbsp; (make-group 2 4)<br>&nbsp; (list<br>&nbsp;&nbsp; (make-state<br>&nbsp;&nbsp;&nbsp; (make-group 2 0)<br>&nbsp;&nbsp;&nbsp; 'left<br>&nbsp;&nbsp;&nbsp; (make-group 1 3)<br>&nbsp;&nbsp;&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;&nbsp; (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 2
 -2)<br>&nbsp; 'right<br>&nbsp; (make-group 1 5)<br>&nbsp; (list<br>&nbsp;&nbsp; (make-state<br>&nbsp;&nbsp;&nbsp; (make-group 2 0)<br>&nbsp;&nbsp;&nbsp; 'left<br>&nbsp;&nbsp;&nbsp; (make-group 1 3)<br>&nbsp;&nbsp;&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;&nbsp; (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 1 0)<br>&nbsp; 'right<br>&nbsp; (make-group 2 3)<br>&nbsp; (list<br>&nbsp;&nbsp; (make-state<br>&nbsp;&nbsp;&nbsp; (make-group 2 0)<br>&nbsp;&nbsp;&nbsp; 'left<br>&nbsp;&nbsp;&nbsp; (make-group 1 3)<br>&nbsp;&nbsp;&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;&nbsp; (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;(make-state<br>&nbsp; (make-group 2 -1)<br>&nbsp; 'right<br>&nbsp; (make-group 1 4)<br>&nbsp; (list<br>&nbsp;&nbsp; (make-state<br>&nbsp;&nbsp;&nbsp; (make-group 2
 0)<br>&nbsp;&nbsp;&nbsp; 'left<br>&nbsp;&nbsp;&nbsp; (make-group 1 3)<br>&nbsp;&nbsp;&nbsp; (list (make-state (make-group 0 0) 'right (make-group 3 3) empty)))<br>&nbsp;&nbsp; (make-state (make-group 0 0) 'right (make-group 3 3) empty)))).<br><br>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.<br><br>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.<br><br><br>--- On <b>Tue, 11/30/10, Matthias Felleisen <i>&lt;matthias@ccs.neu.edu&gt;</i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Matthias Felleisen &lt;matthias@ccs.neu.edu&gt;<br>Subject: Re: [racket] Missionaries and cannibals<br>To: "Ken Hegeland"
 &lt;hegek87@yahoo.com&gt;<br>Cc: users@lists.racket-lang.org<br>Date: Tuesday, November 30, 2010, 2:08 PM<br><br><div class="plainMail"><br>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<br><br>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. <br><br>p.p.s. What Stephen said, too. <br><br><br><br>On Nov 29, 2010, at 10:30 PM, Ken Hegeland wrote:<br><br>&gt; 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:<br>&gt; <br>&gt; (define state1'((0 0)right(3 3)))<br>&gt; (define state2'((1 0)right(2 3)))<br>&gt; (define state3'((0 1)right(3 2)))<br>&gt; (define state4'((2 0)right(1 3)))<br>&gt; <br>&gt; (mc-solvable state1)<br>&gt; (mc-solvable state2)<br>&gt; (mc-solvable state4)<br>&gt; all three of these input states produce true in a negligible amount of time.<br>&gt; <br>&gt; but (mc-solvable state3) seems to loop and never find an answer. I believe I haven't found what exactly should produce false.<br>&gt; <br>&gt; 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?<br>&gt; <br>&gt; 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.<br>&gt; <br>&gt; Thanks for the help I will take what you said into consideration while I try to find the
 solution.<br>&gt; <br>&gt; --- On Tue, 11/30/10, Matthias Felleisen &lt;<a ymailto="mailto:matthias@ccs.neu.edu" href="/mc/compose?to=matthias@ccs.neu.edu">matthias@ccs.neu.edu</a>&gt; wrote:<br>&gt; <br>&gt; From: Matthias Felleisen &lt;<a ymailto="mailto:matthias@ccs.neu.edu" href="/mc/compose?to=matthias@ccs.neu.edu">matthias@ccs.neu.edu</a>&gt;<br>&gt; Subject: Re: [racket] Missionaries and cannibals<br>&gt; To: "Ken Hegeland" &lt;<a ymailto="mailto:hegek87@yahoo.com" href="/mc/compose?to=hegek87@yahoo.com">hegek87@yahoo.com</a>&gt;<br>&gt; Cc: <a ymailto="mailto:users@lists.racket-lang.org" href="/mc/compose?to=users@lists.racket-lang.org">users@lists.racket-lang.org</a><br>&gt; Date: Tuesday, November 30, 2010, 3:19 AM<br>&gt; <br>&gt; <br>&gt; 1. Your sketch sounds about right. The problem is probably sticking to the discipline of turning it into code. <br>&gt; <br>&gt; 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. <br>&gt; <br>&gt; Have you thought thru why the algorithm should terminate (step 7 of the gen-rec design recipe)? <br>&gt; If so, have you checked your program to make sure it adheres to your reasoning? <br>&gt; <br>&gt; 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<br>&gt; <br>&gt;&nbsp;&nbsp;&nbsp;xxx | &lt;&gt;&nbsp; &nbsp; &nbsp; &nbsp; |<br>&gt;&nbsp;&nbsp;&nbsp;ooo |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |<br>&gt; <br>&gt; to the final state: <br>&gt; <br>&gt;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;&lt;&gt;| xxx <br>&gt;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
 |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | ooo<br>&gt; <br>&gt; -- Matthias<br>&gt; <br>&gt; <br><br></div></blockquote></td></tr></table><br>