Re: small puzzle programming
- To: mathgroup at smc.vnet.net
- Subject: [mg53869] Re: [mg53857] small puzzle programming
- From: DrBob <drbob at bigfoot.com>
- Date: Tue, 1 Feb 2005 04:08:19 -0500 (EST)
- References: <200501300818.DAA08849@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
SURELY there's a less involved solution, but here's a way to do it, anyway:
The shepherd's choices at each step are to transport the wolf, sheep, or grass -- or else take the boat alone.
The state vector will consist of three lists: a history of moves already made and the objects on each bank (including the shepherd). Numerical values are given to the symbols in order to order them a certain way. The values could be very different, so long as (a) they are four distinct values, and (b) the shepherd's value is greater than the others.
{wolf, sheep, grass, shepherd} = Range@4;
initial = {{}, {wolf, sheep, grass, shepherd}, {}};
The "interpret" function will translate a final solution into English (more or less). This may make more sense later.
interpret = TableForm@Transpose@{PadRight[{}, Length@#, {"->
", "<-"}], #} /. Thread[Range@4 -> {"with the wolf", "with the sheep
", "with the grass", "alone"}] &;
Empty sets, singletons, sets that include the shepherd, and the {wolf, grass} combination are compatible. All others are incompatible. (As it happens, sets that include the shepherd will never be tested, so that rule could be omitted.)
Clear@compatible
Attributes[compatible] = {Orderless};
compatible[shepherd, ___] = True;
compatible[wolf, grass] = True;
compatible[_] = True;
compatible[] = True;
compatible[__] = False;
The "next" function chooses the first legal move it finds, since the shepherd actually has NO CHOICE how to do this (aside from cycling). Available choices are determined by the objects on the bank where the shepherd stands.
But the order of those choices is important. When moving forward, going alone is the last choice examined. When moving backward, going alone is the first choice a shepherd should think of.
If he stands on the left bank, each object on that bank is examined in order. An object is disqualified if (a) it was transported in the previous move, or (b) taking that object will leave behind an incompatible combination. (The opposite bank is guaranteed compatible, because the shepherd will be there.)
The FIRST rule listed must be the one that says, "If everybody is on the far bank, STOP."
Clear@next
next[done : {_, {}, _}] := done
next@{history_List, left_List, right_List} /; MemberQ[left, shepherd] :=
Module[{result},
Catch@Scan[
((history == {} ||
history[[-1]] â? #) && (result = {Complement[left, {#, shepherd}], Union[
right, {#, shepherd}]};
compatible @@ result[[1]]) &&
Throw@Prepend[result, Append[history, #]]) &,
left]
]
Code for backward moves is symmetric with that for forward moves except that (a) choices are considered in reverse order, and (b) "history" is known to be non-empty.
next@{history_List, left_List, right_List} /; MemberQ[right, shepherd] :=
Module[{result},
Catch@Scan[
(history[[-1]] â? # &&
(result = {Union[left, {#, shepherd}],
Complement[right, {#, shepherd}]};
compatible @@ result[[-1]]) && Throw@Prepend[result, Append[
history, #]]) &,
Reverse@right]
]
interpret@First@FixedPoint[next, initial]
TableForm[
{{"->", "with the sheep"},
{"<-", "alone"},
{"->", "with the wolf"},
{"<-", "with the sheep"},
{"->", "with the grass"},
{"<-", "alone"},
{"->", "with the sheep"}}]
If the shepherd had real choices, this would be (I think) a good bit harder.
Somebody will probably prove me wrong.
Bobby
On Sun, 30 Jan 2005 03:18:21 -0500 (EST), zak <chocolatez at gmail.com> wrote:
> how to code the following puzzle in mathematica programming language:
> the shepherd who want to cross a river aboard a boat taking with him
> one of the following items (wolf,sheep,grass) one per time,
> lst ={S,w,g,p} may describe the group on one side of the river
> lst2={} may describe the the current state of the other side of the river.
> the pairs {{w,p} ,{p,g}} are not allowed
> of course the solution is:
> ((S,p),(S,w),(S,p),(S,g),(S,p))
>
> but how to code this or may be other ideas.
>
> zak
>
>
>
>
--
DrBob at bigfoot.com
www.eclecticdreams.net