Drastically shorten your training time with WalkMe's advanced online training solution that Guides your trainees to action. Forget about retraining and skyrocket knowledge retention rates.

Solved

Posted on 2007-11-27

Hi!

The problem is:

A farmer with his wolf, goat and cabbage come to the edge of a river they wish to cross. There is a boat at the river's edge. But, of course, only the farmer can row it. The boat also can carry only two things (including the rower) at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrive safely on the other side of the river.

I need source code which finds a solution to this problem in Java/C/Pascal/Basic.

Thanks

The problem is:

A farmer with his wolf, goat and cabbage come to the edge of a river they wish to cross. There is a boat at the river's edge. But, of course, only the farmer can row it. The boat also can carry only two things (including the rower) at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrive safely on the other side of the river.

I need source code which finds a solution to this problem in Java/C/Pascal/Basic.

Thanks

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

- Help others & share knowledge
- Earn cash & points
- Learn & ask questions

8 Comments

http://web.mit.edu/16.070/www/year2001/Algorithms.pdf

http://cs.nmu.edu/~jeffhorn/Classes/AI/Fall1999/hw1.html

Write a function:

bool SolveFromHere( ListA, ListB, Side)

if done, return TRUE

MakeMove(ListA, ListB, Side)

if SolveFromHere( ListA, ListB, Side )

return TRUE

else

return FALSE

ListA is the items on the near bank, ListB is the items on the far bank, side is either N or F (Near or Far).

Test for done is when everything is in ListB.

A Move is placing the first item in the current side list on the end of the other side list, or just changing sides, while testing the criteria of what can or can't be together at the same time. If the topmost call to SolveFromHere fails, permutation the order of the items and try again. I'd have to work out the details of how to record the winning moves and how to insert the switch-sides-only type moves (without endlessly cycling back and forth with no passenger, etc.), but that would become clear after I coded the first part and stepped through it.

Brute force+recursive logic should get a good grade.

step2 --> on return take wolf with

step3 -->now take cabbage and wolf

for this u must use stack

As DanRollins said your best bet in tackling this problem is to use recursion, atleast in Java and C, i am not familiar with the other two languages. The solution starts with moving the goat to the far side and then one of the other items, wolf/cabbage, but then you need to take the goat back to the starting side and you should be able to make it from there taking an item at a time. Hopefully that helps you get started. Let me know if something is unclear.

glenjr

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

Maven Project: Hibernate Dependencies Conflict | 10 | 54 | |

eclipse buid path vs tomcat lib path | 10 | 38 | |

runtime exception | 2 | 50 | |

What browser will run Java? | 7 | 128 |

The purpose of this article is to demonstrate how we can use conditional statements using Python.

Join the community of 500,000 technology professionals and ask your questions.