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 java code samples which finds a solution to this problem.
I tried it a few weeks ago, both in Java and in LISP. My advice would be, stick to LISP. If you have a breadth search function in LISP, the solution is really easy. I gave up in Java after about two hours because I couldn't seem to get it to work properly.
The choice of programming language is pretty much irrelevant. First you need a mental model of how to solve the problem. Break that model down into smaller and smaller and smaller chunks until it's straightforward to translate the chunks into a program.
This type of problem, where the solution involves a series of steps, seems to be modelable as a series of "states". What defines each state? How do you transition from one state to the next? How do you identify invalid states? As Campbell suggested, you would then start at your initial state and search for the ending state (avoiding invalid states, of course), keeping track of the states and/or state transitions along the way.
I agree with Ryan M. The language doesn't really matter for this problem. I would add one other item to what Ryan suggested. In addition to avoiding invalid states, in may be worth thinking about what to do if you come back to a state you've already visited.
How I see this problem in terms of java language is make two arrays represting both sides of river. One array lets say "arroneside" will have values Goat,Cabbage,Fox standing to cross river .Other array will have values of animals who have crossed the river.Make a function which picks value from arroneside one by one and apply all conditions to it.if it can be transferred then move it to arrotherside.With each transfer you can get the array values printed. This problem is easy to solve by hand but in terms of coding it is tricky!
What about when the boat is crossing the river? At that point there are two groups of animals on the shores, and there may be an animal in the boat. So you may need to include this in your state. Also, what direction is the boat traveling? This last bit can be derived from the number of previous boat trips that have been made (if you have that info somewhere) - if the number of trips is even, the boat is traveling from the starting shore to the target shore. If the number is odd, the boat is traveling from target back to the start.
You can consider what happens when the farmer is on a shore, and what happens when he's crossing the river. Do you need to consider all of these? If a problem occors, will it (first) occur when the farmer is on a shore, or when he's on the river?
I think it helps to work through the problem as a human several times to get a good sense of which parts of the problem are important, and which can be ignored.
Also, when you make classes representing the state, don't forget to give them good toString() methods. Then when you wite code to search through all the possible states, you can print out the states as you go, to see what your program is doing, and compare that with what you want it to be doing. This is very useful for debugging - as well as for presenting your final solution(s). [ November 30, 2007: Message edited by: Jim Yingst ]
"I'm not back." - Bill Harding, Twister
Joined: Oct 13, 2005
No, Jim Yingst, you don't need to consider what happens while the farmer is crossing the river, nor what the boat is doing; you simply assume the boat is wherever the farmer is. What I actually got was 16 possible states numbered from 0 to f, where the most significant bit (3rd bit = 8) represents the farmer, the 2nd bit = 4 is the wolf, the 1st bit = 2 is the goose and the 0-th bit (least significant bit =1) represents the grain cabbage or whatever.
So, f means all four are on this side of the river, 0 means all four have crossed, 1 means the cabbage is alone on this side of the river, 2 means the goose is alone this side of the river, etc. You could consider that this implies the complement of the number is on the other side of the river, so 0 implies f on the other side. You would then have an invariant that thisSide + thatSide == 0xf. There are three prohibited states this side of the river, 3, 6, 7, where the goose would eat the cabbage or the wold would eat the goat or both. That implies that there are three prohibited states on the other side, 8 9 and c. We know that 8+7 or 9+6 or c+3 all add up to 0xf. That leaves a total of 10 permitted states. Each permitted state can be followed by 1 2 or 3 permitted successor states.
The rules are that the farmer must cross on every occasion, alone or accompanied by one item. This is equivalent to a bitwise XOR by 8 9 a or c; if you have thisSide and thatSide variables then the same operation must be applied to both sides to maintain the class invariant. Also you delete any of the six prohibited states from the results. You can get the states back into English with a bitwise AND:
You then end up with a tree, starting with f, and then you do a search of the tree until you find a 0 in it. It ought to take exactly 7 operations, of which the first isto reach 0.
**************************************************************************** In LISP it reads something like this, assuming your breadth-search algorithm and the -> operator have already been supplied:The abbreviations (obviously) mean farmer wolf goose cabbage and RIVER; those before R are on this side, and those after R are on that side. The defun bit creates a Legal Move Generator (LMG). **************************************************************************** With the LISP utilities we have been supplied, it works, but it always seems to give me the same answer. I think there are 4 possible solutions, but the first operation is always that the farmer takes the goose across, and the fourth is always bringing the goose back.
Minor spelling corrections and what lmg means[/edit] [ November 30, 2007: Message edited by: Campbell Ritchie ]
Joined: Jan 30, 2000
[Campbell Ritchie]: No, Jim Yingst, you don't need to consider what happens while the farmer is crossing the river, nor what the boat is doing; you simply assume the boat is wherever the farmer is.
There's more than one way to do this, Campbell. Several different possible models can include some things and ignore others. I was just asking questions to get the original poster to think about what what needs to go into the model. I've already got a working Java solution along the lines I suggested, which ignores the states where the farmer is on the shore, and considers only what happens on the boat. I am glad to see the Lisp version though.
Joined: Jan 30, 2000
[Campbell]: I think there are 4 possible solutions, but the first operation is always that the farmer takes the goose across, and the fourth is always bringing the goose back.
Hm, I found two solutions, the ones I expected. I put in a prohibition against repeating previous states, as otherwise you can get infinite loops. Here they are - each line is a step in the solution, showing the animals on each shore, and the boat in the middle travelling back and forth. The farmer is not represented.
For simplicity these can be represented just by what gets put in the boat on each trip (where - indicates nothing but the farmer):
G, -, W, G, C, -, G
G, -, C, G, W, -, G
What are the other two solutions you're thinking of? [ November 30, 2007: Message edited by: Jim Yingst ]
Joined: Feb 18, 2005
One thing about this particular problem is that the tree of possible valid (non-repeated) states doesn't branch away from the two solutions. For the first move, taking either the wolf or the cabbage across leads to an invalid state. For the return trip, taking the goat back leads to a previously seen state. Now the farmer has the choice of taking either the wolf or the cabbage. As is turns out, either choice works -- let's say he takes the wolf. For the return trip, taking the wolf back leads to a repeated state. Taking nothing back leads to an invalid state. The only possibility left is taking the goat. Similar resoning leads directly to the solution(s). At no point does the farmer have to look farther ahead than the end of upcoming boat trip to make the right decision at any point.
We could add a twist to this problem: Each boat trip takes 4 minutes. The farmer knows that there is a group of hungry amoral vegetarian pacifists on the trail a mere 15 minutes behind him. If the farmer leaves the cabbage ungarded on the original side of the river, after the 15 minute mark, the HAVPs, the farmer believes, will eat his cabbage. In contrast, the wolf and/or the goat would be safe from consumption. Also, the farmer could defend his use of the boat from the HAVPs.
How does that affect the algorithm?
How about this one: That night, four people want to cross this same river, but this time over a bridge. The bridge is only strong enough for two people at a time. Two people walking together, can walk only as fast as the slower of the pair. Lastly, the bridge has holes and loose boards, so one or two people need a flashlight to cross. They have only one flashlight. The flashlight cannot be thrown across the river -- someone has to carry it.
The four people can cross at different speeds:
Campbell can cross in 10 minutes.
Preeti can corss in 5 minutes.
Jim can cross in 2 minutes.
Ryan can cross in 1 minute. (Of course I mean Mr. DeJana is the fastest walker. How vain do you think I am? )
One strategy would be for the fastest walker, Ryan, to hold onto the flashlight and act as a ferry for the three other people:
Can you find a strategy that takes only 17 minutes? The tricky part here is that the tree of valid states is quite branchy compared to the Cabbage/Goat/Wolf problem. You can't identify an invalid state until you get to the 17 minute mark and someone isn't on the right side of the river yet.
Also, each one of our travelers has a balance and three coins, one of which may be heavier or lighter than the rest... Oh wait, wrong problem. [ December 03, 2007: Message edited by: Ryan McGuire ]
Actually for your flashlight problem, i would probably transform this to a 'shortest path' or min-max rather then the state transform.
Joined: Oct 13, 2005
I may have been mistaken about 4 solutions; when I think about the problem I seem only to be able to produce two. Of course you can always make the thing more complicated by adding vegetarians, lamps, etc.
The wolf / cabbage / goat problem is a 3 disc towers of hanoi problem.
That is to say there's probably an elegant recursive solution to it.
Edit - my mistake, it's not tower of hanoi, but it has some similarities.
[ December 07, 2007: Message edited by: Jeremy Botha ] [ December 07, 2007: Message edited by: Jeremy Botha ]
McFinnigan? Never heard of him. Nobody here but us chickens...<br /> <br />SCJP for Java 1.4<br />SCJD for Java 5.0
Joined: Feb 16, 2005
base state : you have to move the goat first, it's the only legal first move.
For every subsequent move: select an object O to ferry from A to B. - if O is an unsafe choice, terminate this branch and return to the level above - if O can be removed from A leaving a safe combination behind, move it to B - if B is now an unsafe configuration, select an object other than O and bring it back to A. - repeat / recurse / do a little dance
If I recall correctly, one way to solve it goes like this: Construct a graph where each node is a state of the problem and the arcs the valid transitions. The path from the initial configuration (all on one side) to the final (all in the other side) will be the solution. (that Operations Research course I took long ago totally ruined this kind of problems for me )