River Crossing Problem

[notmecy]

I would really appreciate it if someone could tell me what is wrong with the following code:

#include <iostream.h>
#include <stdlib.h>

//Define the objects we are going to use
//We assume that the farmer and the boat sre one object as we don't have
//to carry the farmer, but the farmer carries other objects using the boat

typedef struct object
{
int fox, goose, grain, fboat;
object * next;
}
object;
bool repeated;

typedef struct objects_array
{
int fox , goose , grain , fboat;
}
objects_array;
struct objects_array slist[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->fox = w && node_value->goose == x && node_value->grain == y && node_value->fboat == z)
{
repeated = true;
}
node_value = node_value ;
}
}

//Push objects in the open list if the fox and goose are not on the same side of the river
//or if the goose and the bag of grain 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->fox = w;
pushobj->goose = x;
pushobj->grain = y;
pushobj->fboat = z;
pushobj->next = phead;
phead = pushobj;
}
}
}

//Function to carry accross on bring back the fox

void carryfox(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 on bring back the goose

void carrygoose(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);
}

//Function to carry accross on bring back the bag of grain

void carrygrain(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->fox = ophead->fox;
clcurrent->goose = ophead->goose;
clcurrent->grain = ophead->grain;
clcurrent->fboat = ophead->fboat;
w = ophead->fox;
x = ophead->goose;
y = ophead->grain;
z = ophead->fboat;
clcurrent->next = clhead;
clhead = clcurrent;
ophead = ophead->next ;
}

void mainproc (object * & openhead, object * & closehead, int& w, int& x, int& y, int& z, int& count)
{
count = 5;
for (int i=1; i<=count; i++)
{
carryfox(openhead, closehead, w, x, y, z);
carrygoose(openhead, closehead, w, x, y, z);
carrygrain(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);
mainproc (openhead, closehead, w, x, y, z, count);
cout << " \n"<< " \n";
i=0;

//Put the close list in an array

while (closehead != NULL)
{
slist[i].fox = closehead->fox;
slist[i].goose = closehead->goose;
slist[i].grain = closehead->grain;
slist[i].fboat = closehead->fboat;
closehead = closehead->next ;
i=i++;
}
cout << " \n";

//Print the solution

for (i = count; i >= 0; i--)
{
if (slist[i].fboat == 0)
{
cout << "Carry ";
if (slist[i].fox != 0)
cout << slist[i].fox << " fox ";
if (slist[i].goose != 0)
cout << slist[i].goose << " goose ";
if (slist[i].grain !=0 )
cout << slist[i].grain << " grain ";
if (((slist[i].fox == 0 ) && (slist[i].goose == 0 )&& (slist[i].grain == 0)))
cout << " no object ";
cout << "across ";
} //if
else if (slist[i].fboat == 1)
{
cout << "Bring ";
if ((slist[i].fox - slist[i+1].fox) != 0)
cout << slist[i].fox - slist[i+1].fox << " fox ";
if ((slist[i].goose - slist[i+1].goose) != 0)
cout << slist[i].goose - slist[i+1].goose << " goose ";
if ((slist[i].grain - slist[i+1].grain) !=0 )
cout<< slist[i].grain - slist[i+1].grain << " grain ";
cout << "back ";
} //else if
cout << "\n";
} //for
cout <<"Mission accomplished! Everyone has safely crossed the river! \n";
system("PAUSE");
return 0;

}

[jsmith]

What problems are you having? Compile problems? Link problems? Runtime problems? Be more specific.

[notmecy]

Not compile or link problems. When i execute the program it doesn't print the path i get a blank screen with a cursor. I suspet it has something to do with the constraints

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))) )

[jsmith]

Uh, good luck on that one. That if is so complicated only its programmer could ever hope to understand it (and even then...)

No offense...

[helios]

What's up with the last AND? Haven't you ever heard of the greater-than-or-equal-to (>=) operator?

Wasn't the river crossing problem one of those logistics stuff that computer scientists spend years researching to find (optimal) solutions. It could be the your program is legitimately searching for a path, but the algorithm is so sub-optimal that it'll take considerable time.

[Duthomhas]

Well, I'm having a more and more difficult time convincing myself to respond to lengthy, unformatted code, but this one is borderline interesting enough that given the evasive answers so far I'll take a gander at it.

Notmercy and jsmith are right to target things like x,y,z,g1,g2, etc. There are two sides to your functions. From main(), w,x,y, and z are state variables whose values are indeterminate. However, in your functions, they should have an explicit (i.e. determinate) meaning, and hence, specific names.

Give me a short bit to look it over properly... (I might get called to dinner momentarily).

[edit] Oh, the problem itself is not particularly difficult, but it is NP-complete.

[edit 2] Yoinks, notmercy is the OP.

[Zaita]

My piece of advice is to use a formal coding standard. Hideously named variables are impossible to comprehend.

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml

[Duthomhas]

Hmm, I am sorry to say this, but your algorithm is irrevocably broken. You need to start over. (Really. Don't waste any more time trying to fix this.)

I will continue with the assumption that what follows is your assignment. If your professor has added or changed something, post back with the correction.

A farmer seeks to take his goods to market: a fox, a goose, and a bag of grain. To do so, he must cross a river. However, his boat is only big enough to accomodate himself and one of his goods.

His problems are these:
1. The fox cannot be left alone with the goose.
2. The goose cannot be left alone with the grain.
3. The grain cannot be left alone on the far side of the river (where there is a large flock of crows).

So, the question is: in what order should he take his goods across the river in order to preserve them?

Your first problem is with names. Everything should have an identifying name. Names like w, x, y, and z are meaningless here. Don't use them. Use names like 'fox', 'goose', 'grain', and 'fboat' instead. That's what you mean.

Likewise 'openhead' and 'closehead' are confusing terms. Why not just say 'farside_of_river' and 'nearside_of_river', or something like that? You can 1) read it, and 2) think about it very directly and clearly.

By using bad names you have really confused yourself about your assignment.

For example, you are counting stuff, instead of just checking to see whether something is present. It does not matter how many times something crosses the river. (In fact, the solution to the puzzle relies upon the realization that things may cross the river more than once.)

Next, you have type-confusion. (I don't think I made that term up, but at this point I don't really care.) It appears that your professor would like you to keep track of what objects are on which side of the river by using some form of list. Is this correct?

Currently you have an 'object' object (which really should be named something like 'locations' or 'positions' or 'items_on_near_side_of_river' or somesuch. Likewise, each element in the object should not be a counter, but simply a position report, answering the question: "am I on the near side of the river?" [or the far side, which ever you wish --just be consistent. If your object is named 'items_across_the_river' then the boolean value should be TRUE if the item is on the far side of the river, and FALSE if still on the near side. Etc.]

Your 'objects_array' duplicates that information, and has confused your algorithm. You don't need it. Sorry to be pedantic, but again: all you need is the current location of each item. When your program starts, the current location is that everything is on the starting side of the river. Hence, you can code something like:

enum position { nearside, farside };
struct positions
  {
  position fox, goose, grain, farmer_and_boat;
  positions * next;
  };

int main()
  {
  // Start out with everything on this side of the river
  positions current_positions;

  current_positions.fox             =
  current_positions.goose           =
  current_positions.grain           =
  current_positions.farmer_and_boat = nearside;
  current_positions.next            = NULL;

Now, as you determine what to send across the river next (the farmer and boat crosses every time, but only one of the other items, if any, cross with him). Each time a crossing is made, just add a copy of the current state to the end of your list:

void push_positions( positions * stack, positions current )
  {
  // Append a copy of the 'current' positions to the end of the 'stack'.
  ...
  }

positions pop_positions( positions * stack )
  {
  // Remove the last item in the 'stack' and return a copy of it.
  ...
  }

...

int main()
  {
  ...

  // Something to keep track of our efforts
  positions * position_history = new positions;
  *position_history = current_positions;

  ...
  push_positions( position_history, current_positions );

The last thing you need to consider is that this is a graph traversal exercise. Yes... the dreaded graph. It is possible (well, highly probable) that your algorithm will discover that it made a mistake at some point. When it does, it needs to back-up and start over at the next available possibility.

You must visualize this to understand it. Here we go:

NEAR SIDE FAR SIDE
1. farmer fox goose grain
2. goose grain farmer fox
Error, the goose ate the grain.
Back up and try step 2 again:
2. fox grain farmer goose
3. farmer fox grain goose
4. grain farmer fox goose
5. farmer grain fox goose
Error, the fox ate the goose.
Back up and try step 5 4 again. (We are going back two
steps because only the farmer crossed on step 5. This is a safe
assumption to add into your algorithm.)
4. fox farmer goose grain
5. farmer fox goose grain
Oh, no! The goose (and probably all them crows too) ate the grain!
We'll have to back up again.
This time, we know we have exhausted all our options at step 4, so we
will have to back up again.

Figure this backing-up stuff and you will be set. It looks tough, but once you can wrap your brain around it you will fix it easily enough.

Whew. Hope this helps.

[grcunning]

great post Duoas, if and when I have to solve this problem, I'll come back to it.

[notmecy]

Thanks for your advice Duoas