Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

"Wolf, Goat, Cabbage problem"s solution code in Java

Posted on 2007-11-27
8
Medium Priority
?
3,527 Views
Last Modified: 2010-05-19
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
0
Comment
Question by:ozguny
[X]
Welcome to Experts Exchange

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

Assisted Solution

by:contactkarthi
contactkarthi earned 200 total points
ID: 20360120
0
 
LVL 49

Accepted Solution

by:
DanRollins earned 800 total points
ID: 20361650
I don't know Java, but I can describe the way I'd solve this:

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.
0
 
LVL 37

Expert Comment

by:samtran0331
ID: 20362873
...I vaguely remember doing this exact problem in school...it was an exercise in understanding stacks....
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 4

Expert Comment

by:jindalankush
ID: 20364705
step1--> take wolf and goat
step2 --> on return take wolf with
step3 -->now  take cabbage  and wolf

for this u must use stack
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 20370772
Can only take 1 item at a time (rower plus 1 item)

mlmcc
0
 
LVL 3

Assisted Solution

by:glenjr
glenjr earned 400 total points
ID: 20371623
ozguny

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  
0
 

Author Comment

by:ozguny
ID: 20372653
I should make use of trees and Breadth-first Search or Depth-first Search.
I think I understood the solution, I'll build up a tree for every probability.
4 boolean variables or an bool array for farmer, wolf, goat, cabbage which marks near bank or far bank
Thanks everyone for your help!
0

Featured Post

Ask an Anonymous Question!

Don't feel intimidated by what you don't know. Ask your question anonymously. It's easy! Learn more and upgrade.

Question has a verified solution.

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

In this post we will learn different types of Android Layout and some basics of an Android App.
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

636 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question