<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Still not have solved it but I feel like I am getting close.<br><br>I developed a program that looks like this in step form<br>1. check if input is final, if it is return true, else<br>2.check if empty, if true return false(already thinking this isn't necassary<br>3. generate possible moves.<br>4. check if input has been seen in an accumulator.<br>5. check if possible moves is empty, if it is return false<br>6.else (or(recurse on first item in possible moves, and add input to the accumulator<br> (recurse on rest items in possible moves.<br><br>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.<br>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.<br><br>I feel close but still can't figure out a way to produce false.<br><br><br>--- On <b>Tue, 11/30/10, Matthias Felleisen <i><firstname.lastname@example.org></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Matthias Felleisen <email@example.com><br>Subject: Re: [racket] Missionaries and cannibals<br>To: "Ken Hegeland" <firstname.lastname@example.org><br>Cc: email@example.com<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>> 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>> <br>> (define state1'((0 0)right(3 3)))<br>> (define state2'((1 0)right(2 3)))<br>> (define state3'((0 1)right(3 2)))<br>> (define state4'((2 0)right(1 3)))<br>> <br>> (mc-solvable state1)<br>> (mc-solvable state2)<br>> (mc-solvable state4)<br>> all three of these input states produce true in a negligible amount of time.<br>> <br>> but (mc-solvable state3) seems to loop and never find
an answer. I believe I haven't found what exactly should produce false.<br>> <br>> 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>> <br>> 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>> <br>> Thanks for the help I will take what you said into consideration while I try to find the solution.<br>> <br>> --- On Tue, 11/30/10, Matthias Felleisen <<a ymailto="mailto:firstname.lastname@example.org" href="/email@example.com">firstname.lastname@example.org</a>> wrote:<br>> <br>> From: Matthias Felleisen <<a ymailto="mailto:email@example.com" href="/firstname.lastname@example.org">email@example.com</a>><br>> Subject: Re: [racket] Missionaries and cannibals<br>> To: "Ken Hegeland" <<a ymailto="mailto:firstname.lastname@example.org"
href="/email@example.com">firstname.lastname@example.org</a>><br>> Cc: <a ymailto="mailto:email@example.com" href="/firstname.lastname@example.org">email@example.com</a><br>> Date: Tuesday, November 30, 2010, 3:19 AM<br>> <br>> <br>> 1. Your sketch sounds about right. The problem is probably sticking to the discipline of turning it into code. <br>> <br>> 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>> <br>> Have you thought thru why the algorithm should terminate (step 7 of the gen-rec design recipe)? <br>> If so, have you checked your program to make sure it adheres to your reasoning? <br>> <br>> 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>> <br>> xxx | <> |<br>> ooo | |<br>> <br>> to the final state: <br>> <br>> | <>| xxx <br>> | | ooo<br>> <br>> -- Matthias<br>> <br>> <br><br></div></blockquote></td></tr></table><br>