# puzzle questions

A man (M), wolf (W), goat (G) and cabbage (C) are on the left bank of a river. There is a boat large enough to carry
the man and only one of the other three. The man wishes to ferry everyone to the right river bank, and the man can
ferry each across, one at a time.
However, if the man leaves the wolf and goat unattended on either shore, the goat is history. Similarly the goat and
cabbage cannot be left unattended by the man.

How can the man bring all those animals to the other river bank safely using the shortest way possible?
###### Who is Participating?

Commented:
>MW|MGC
Thats does not look correct ... man cant be in two places at one time

MWGC|0 -> WC|MG -> MWC|G -> C|MWG -> MGC|W -> G|MWC -> MG|WC -> 0|MWGC
0

Commented:
Hello kuntilanak,

man take goat
comes back
takes wolf
brings goat back
take cabbage
comes back
takes goat

Regards,

sunnycoder
0

Author Commented:
hey it's you again, thanks for helping since you're quite familiar with dfa/nfa.. I want to practice and put this into a transition diagram.

The start state is labeled MWGC | 0

0 = empty set

and input set will be soemthing like:

g (rows across with the goat), c (rows accross with the cabbage)

example when given an input gm

MWGC|0 -> WC|MG -> MWC|G

Any hints?

0

Commented:
>example when given an input gm
>MWGC|0 -> WC|MG -> MWC|G
>Any hints?
You drew first three states correctly ... translate rest of the steps into your state diagram
0

Commented:
MWGC|0 -> WC|MG -> MWC|G -> W|MCG -> MW|MGC -> 0|MWCG
0

Author Commented:
so there's 6 states in this problem, and I just draw 6 circles with arrows connecting to each (input) other?
0

Author Commented:
oh and I just realized that ozo's solution has a shorter path :)
0

Desktop SupportCommented:
Actually, there is an easier solution. Just use a tranquilizer gun on both the goat and the wolf, then take them over one at a time...faster too.
0

Author Commented:
haha..yea, that's a killers solution.. oh and if I were asked to draw a transition diagram of this situation.. what would it be like?
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.