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 <matth...@ccs.neu.edu> wrote:
From: Matthias Felleisen <matth...@ccs.neu.edu>
Subject: Re: [racket] Missionaries and cannibals
To: "Ken Hegeland" <hege...@yahoo.com>
Cc: us...@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 <matth...@ccs.neu.edu> wrote:
>
> From: Matthias Felleisen <matth...@ccs.neu.edu>
> Subject: Re: [racket] Missionaries and cannibals
> To: "Ken Hegeland" <hege...@yahoo.com>
> Cc: us...@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
>
>
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
