Farmer duck corn wolf

[Builder_1]

A farmer with his wolf, duck and bag of corn come to the east side of a river they wish to cross. There is a boat at the river’s edge, but of course only the farmer can row. The boat can only hold two things (including the rower) at any one time. If the wolf is ever left alone with the duck, the wolf will eat it. Similarly if the duck is ever left alone with the corn, the duck will eat it. How can the farmer get across the river so that all four arrive safely on the other side? Solve this problem using Depth First Search to find the shortest solution. Write Code in C++/Java.Its my assignment im unable to do it although have made the state space

[happygeek]

You've been a member for three years, so surely you should know by now that you can't simply post a homework assignment, show no coide, show no effort, and expect someone else to do it for you. Apart from anything else it breaches the rules at DaniWeb.

provide evidence of having done some work yourself if posting questions from school or work assignments

Post your code, explain exactly where your problem is and the help you are looking for, then someone might be able to help.

[Builder_1]

#include <iostream>
#include <stdlib.h>
using namespace std;
#include<conio.h>
#include<stdio.h>

typedef struct object
{
int farmer, duck, bag_of_corn, fboat;
object * next;
}
object;
bool repeated;

typedef struct objects_array
{
int farmer , duck , bag_of_corn , fboat;
}
objects_array;
struct objects_array soltionlist[3];

//Check if the object is already in the list

void checkrepeated(bool& repeated, int w, int x, int y, int z, object * node_value)
{
while ((node_value!=NULL))
{ 
if (node_value->farmer = w && node_value->duck == x && node_value->bag_of_corn == y && node_value->fboat == z)
{
repeated = true;
} 
node_value = node_value ;
}
}

//Push objects in the open list if the farmer and duck are not on the same side of the river or if the duck and the bag of bag_of_corn are not the on same side of the river

void pushobject(object * & phead, object * closehead, int w, int x, int y, int z)
{
bool repeated = false;
if ((( (w < 2) && (x < 2) && (y < 2)))

&& (( (w == 1) || (x == 1) || (y == 1) || (w != z)) || (x != y))

&& (((w > 0) || (w == 0)) && ((x > 0) || (x == 0)) && ((y > 0) || (y == 0))) )
{
checkrepeated(repeated, w, x, y, z, phead);

if (repeated == false)

checkrepeated(repeated, w, x, y, z, closehead);

if (repeated == false)
{
object * pushobj = new object;
pushobj->farmer = w;
pushobj->duck = x;
pushobj->bag_of_corn = y;
pushobj->fboat = z;
pushobj->next = phead;
phead = pushobj;
}
}
}

//to carry accross on bring back the farmer

void carryfarmer(object * & phead, object * closehead, int f1, int g1, int gr1, int fb1)
{
if (fb1 == 1)
{
f1 = f1 - 1;
fb1 = fb1 - 1;
} 
else if (fb1 == 0)
{
f1 = f1 + 1;
fb1 = fb1 + 1;
}
pushobject(phead, closehead, f1, g1, gr1, fb1);
}

//Function to carry accross or bring back the duck

void carryduck(object * & phead, object * closehead, int f1, int g1, int gr1, int fb1)
{
if (fb1 == 1)
{
g1 = g1 - 1;
fb1 = fb1 - 1;
} 
else if (fb1 == 0)
{
g1 = g1 + 1;
fb1 = fb1 + 1;
}
pushobject(phead, closehead, f1, g1, gr1, fb1);
}

//to carry accross on bring back the bag of bag_of_corn

void carrybag_of_corn(object * & phead, object * closehead, int f1, int g1, int gr1, int fb1)
{
if (fb1 == 1)
{
gr1 = gr1 - 1;
fb1 = fb1 - 1;
} 
else if (fb1 == 0)
{
gr1 = gr1 + 1;
fb1 = fb1 + 1;
}
pushobject(phead, closehead, f1, g1, gr1, fb1);
}

void popobject(object * & ophead, object * & clhead, int& w, int& x, int& y, int& z)
{
object * clcurrent = new object;
clcurrent->farmer = ophead->farmer;
clcurrent->duck = ophead->duck;
clcurrent->bag_of_corn = ophead->bag_of_corn;
clcurrent->fboat = ophead->fboat;
w = ophead->farmer;
x = ophead->duck;
y = ophead->bag_of_corn;
z = ophead->fboat;
clcurrent->next = clhead;
clhead = clcurrent;
ophead = ophead->next ;
}

void solve (object * & openhead, object * & closehead, int& w, int& x, int& y, int& z, int& count)
{ 
count = 5;
for (int i=1; i<=count; i++)
{
carryfarmer(openhead, closehead, w, x, y, z);
carryduck(openhead, closehead, w, x, y, z);
carrybag_of_corn(openhead, closehead, w, x, y, z);
popobject(openhead, closehead, w, x, y, z);
}
}

int main()
{
int w, x, y, z, count, i;
object * openhead = NULL;
object * closehead = NULL;
object * tmphead = NULL;
w = 1;
x = 1;
y = 1;
z = 1;
pushobject(openhead, closehead, w, x, y, z);
popobject(openhead, closehead, w, x, y, z);
solve (openhead, closehead, w, x, y, z, count);
cout << " \n"<< " \n";
i=0;

//Put the close list in an array

while (closehead != NULL)
{ 
soltionlist[i].farmer = closehead->farmer;
soltionlist[i].duck = closehead->duck;
soltionlist[i].bag_of_corn = closehead->bag_of_corn;
soltionlist[i].fboat = closehead->fboat;
closehead = closehead->next ;
i=i++;
}
cout<< " \n";

//Print the solution
//char a = getchar();


for (i = count; i >= 0; i--)
{
if (soltionlist[i].fboat == 0)
{
cout << "Carry ";
if (soltionlist[i].farmer != 0)
cout << soltionlist[i].farmer << " farmer ";
if (soltionlist[i].duck != 0)
cout << soltionlist[i].duck << " duck ";
if (soltionlist[i].bag_of_corn !=0 )
cout << soltionlist[i].bag_of_corn << " bag_of_corn ";
if (((soltionlist[i].farmer == 0 ) && (soltionlist[i].duck == 0 )&& (soltionlist[i].bag_of_corn == 0)))
cout << " no object ";
cout << "across ";
} //if 
else if (soltionlist[i].fboat == 1)
{
cout << "Bring ";
if ((soltionlist[i].farmer - soltionlist[i+1].farmer) != 0)
cout << soltionlist[i].farmer - soltionlist[i+1].farmer << " farmer ";
if ((soltionlist[i].duck - soltionlist[i+1].duck) != 0)
cout << soltionlist[i].duck - soltionlist[i+1].duck << " duck ";
if ((soltionlist[i].bag_of_corn - soltionlist[i+1].bag_of_corn) !=0 )
cout<< soltionlist[i].bag_of_corn - soltionlist[i+1].bag_of_corn << " bag_of_corn ";
cout << "back ";
} //else if 
cout << "\n"; 
} //for
char a = getchar();
cout <<"Mission accomplished! Everyone has safely crossed the river! \n";
system("PAUSE");
_getche();
return 0;

}

// Ok this is the problem that im getting pdb error ; have tried many things like system(pause) , _getche etc but no use

[AssertNull]

My head hurts just looking at this. I can't follow code like this. You need to format/indent. You also need to decide whether you are programming in C or C++. You're using iostream, so it must be C++. So you want to include cstdlib and cstdio, not stdlib.h and stdio.h. No need to use typedef struct either. Plain old struct will do.

I see lots of comments like "else if" and "for" and comments that match the function names closely, but I do not see the comments that I should see. For example, I see variables like w, x, y, and z, but I don't know what they represent. I also see values like 0, 1, or 2, but what do those values represent? I'm guessing it is something like chicken = 0 if it's on one side of the river, 1 if it's on the other side of the river, and 2 if it's in the boat. But that's just a guess. It's be easier to read if you had some named constants or an enumerated type or something.

I see that you're implementing a stack. If you don't need to write your own, then use C++'s stack.

http://www.cplusplus.com/reference/stack/stack/

If you do need to write your own, well, pass your functions an "object" and a stack. That's 2 parameters to a function. I'm seeing a whole bunch of functions with four integers passed to them, which I'm guessing is an "object"? Hard to tell since the variable names aren't descriptive and there aren't comments describing these variables.

All in all, pick either C or C++ and go with that consistently, then (assuming C++) use some more descriptive names, use some enumerated types/named constants for your states instead of 0, 1, and 2, get rid of the extremely obvious comments like "for" and "else if", and make some comments on the less obvious stuff. And indent, indent, INDENT! The code is unreadable as-is. You wouldn't NEED the "for" and "else if" comments if you indented because it would be obvious.

[AssertNull]

There is a boat at the river's edge, but of course only the farmer can row.

I forgot to comment on this. The boat is always where the farmer is, correct? So it seems to me that you can get rid of all code keeping track of the boat, like the variable fboat. And what happened to the wolf in this problem?

[Gribouillis]

@AssertNull running

astyle --style=allman --align-pointer=middle --max-code-length=79 farmer.cpp

does a pretty good job on formatting Builder_1's code

[AssertNull]

Good to know. I've never tried that program. NetBeans has a nice little formatter that I use. Formats quite well. And quickly. Far faster than it took me to write those sentences complaining about the OP not formatting his code...

But I still think it's worth writing those sentences because the OP can't read/debug his own code if it's formatted the way he has it (i.e. not formatted at all).

Is the OP even still around to read this? It's actually an interesting problem. I know the answer, but I never thought of writing a computer program to solve it. It's fairly trivial with only three items, but you could add a whole bunch of things that couldn't be together without supervision (Lions and hyenas, snakes and mongooses, Crips and Bloods, Donald Trump and Hillary Clinton, etc.). I'm gonna give this a try.

[Builder_1]

Thanks everyone for your time and help.

[Gribouillis]

I posted a solution in python for this problem Click Here. The algorithm could perhaps give you some ideas to compare with your code.

[AssertNull]

I posted a solution in python for this problem Click Here. The algorithm could perhaps give you some ideas to compare with your code.

I have a C++ implementation of the problem that works now. I'm commenting/prettying it up, then I will post it. One thing I'm not sure of yet is whether my implementation guarantees that the solution found is a solution that involves the fewest number of trips across the river. This is one of those problems (I think), that is actually much faster to figure out WITHOUT a computer program than with a computer program after you stick in all the comments so that other people can understand your algorithm, testing it, etc.

Re-reading the OP's problem, I noticed that I did not actually use a "depth first search". I figured out what the possibilities were for each river crossing, checked to make sure the resulting state was legal and that I hadn't been in that state before, added that new state to the vector, rinse and repeat till I was in my success state. The only "searching" I did was to iterate through my vector to make sure I hadn't been in this state before. Hence I used a vector instead of a stack.

Will post program soon.

[Gribouillis]

I drew the following graph, which shows that there are only two routes of equal length. The starting point is the green dot fdwc (farmer, duck, wolf, corn) and the final point is the red dot, labelled 0. The arrows are possible transitions. I removed the yellow states from the graph because they are not acceptable states. For example fw (farmer wolf) is not acceptable because the other bank of the river would contain duck and corn and no farmer. Some of those yellow states could be reached in principle, but the corresponding edges were removed.

[Gribouillis]

Here is the graph with all states allowed. Note that an undirected graph can be drawn, because every move is reversible.

[AssertNull]

Very nice, very useful graphs. May I ask what software you used to create this? I am guessing Microsoft PowerPoint of Microsoft Visio or Dia? I've been meaning to learn how to use one of these programs to make graphs like this. Still using pencil and paper in 2016!

[Gribouillis]

I simply used the <igraph> library with a few lines of python. This library can also be called from C or R.

[AssertNull]

I simply used the <igraph> library with a few lines of python. This library can also be called from C or R.

Wow. I'll have to check that out. Thanks.

I added my C++ implementation to your code snippet.

https://www.daniweb.com/programming/software-development/code/504761/farmer-crossing-river-with-wolf-duck-bag-of-corn