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