Need help with recursion and arrays

[Dani]

Hey everyone. I actually have a homework assignment that is due Tuesday afternoon that I've been struggling all weekend with. The assignment is located at: http://cs.hofstra.edu./~cscsxd/hofstra/teaching/cs155-04/course_info/project/Recursion.cpp

As you can see, the function we have to write is:

int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy, 
				   int r[][6], int a[][6])
{
	// please fill in your code here and remove the statement return -1;
	// return -1;
}

I understand the algorithm to use in the sense that I can explain it on paper. But I am confused how to actually translate it into code given the professor's function prototype. What exactly are we returning as a pointer to an integer? Are we making changes to the two arrays that are passed in with each iteration?

From what I see, we are doing ...

Initially pass in 1,1 to start and 5,5 to end with both arrays
Try going to 1,2 and to 2,1, and decide which is better
After picking the one that is better, recursively go back to 1,1->1,2->1,3 or 2,2 ... and the same for the other coordinate ...

Oh wait, I'm screwed up again. Maybe I don't understand this at all :( It would be fantastic if someone could give me a hand with this, because I'm very confused. Thanks!

[Narue]

>What exactly are we returning as a pointer to an integer?
The shortest path, basically an array of x,y pairs.

>Are we making changes to the two arrays that are passed in with each iteration?
No, those arrays simply tell you what the distance between two points is.

>Try going to 1,2 and to 2,1, and decide which is better
Or you could walk each path in turn and collect the total distances. Then simply choose the shortest path from that collection. I'll leave it up to you to figure out if that's a good solution or not. ;)

[Dani]

Hey there Narue. I spoke to my professor and it appears the reason I was stumped was because I misread the question!! It turns out we don't have to use recursion afterall! I have also opted to solve the problem in a similar way as you described (collecting distances one row at a time.) I'm working on the problem right now, and I'll have something that I can show here in about an hour.

[Chainsaw]

We don't do your homework for you.

HA HA HA HA HA :-)

(Sorry, I couldn't resist)

[jwenting]

Muaha. Dani didn't ask for anyone to do her homework, only for hints to get started :)

Anyway, it's now almost 6 hours later and still nothing to show? ;)

[Dani]

Sorry, I have just been so busy I haven't had a chance to update this thread. I'm attaching what I have so far. It works up until the point where it populates the array that the function returns. In other words, it correctly computes the shortest path and prints it out as it goes. But then it screws up filling the data it computed into the array. At this point I'm just looking for some help finishing it up :) I'm pretty sure it's just a one-line typo somewhere in my last loop. If you run the file you should see what I'm talking about. Unfortunately, for some reason, I can get the thing to compile on my Windows machine in VS.NET but not by using gcc on my mac :( I think it's just some quirk.

[Chainsaw]

I see a couple of things, though I can't claim to understand what is being attempted (heck, back in 1977 when I took CS classes, rectangles only had 3 sides! What we would have GIVEN for a 4-sided rectangle! You kids today... )

1) shortest_path is allocated at 8 ints (0.7) but you use 9 positions; n ends up as 9 (so 0..8 are filled in). Not exactly sure why, but....

2) you don't compute paths indexes 0 or 1 (0,0 0,1 1,0 1,1), yet you reference them when building shortest_path! Because you decrement the x or y value before fetching it to fill in shortest_path, you decrement x or y down to 0.

I moved setting shortest_path to the TOP of the while loop, and that seemed to help, but you still have to fix the setting of paths[] so it fills in the first entry (1,n and n,1)

(oh, and VC++ bitches about declaring x more than once)

(note: at some point you'll want to delete [] shortest_path in main())

(note: in cases where you use a simple 2 dimension array like this and don't want to add the complexity of a class or ugly macros, pick some size that is "larger than you'll ever need" (you picked 10 that might be fine), and then add asserts to make sure you don't blow the size. Here's an example:

static const int kArraySize = 10; // Naru would complain about static being deprecated, but heck this is my example code! :=)

assert( (endx < kArraySize) && (endy < kArraySize) ); // if this fires, kArraySize may need to be bumpped up!

int distance[ kArraySize ][ kArraySize ];

[Dani]

Hey there Chainsaw. Thanks for the comments. As for deleting shortest_path in main ... the professor actually wrote that part. It was only our job to fill in the actual function. Also, since this program was mainly just to make sure we understood the algorithm, I'm not concerning myself with the technicalities of dynamically generating the array. But, yes, I used a size of [10][10] because that is larger than I ever plan on needing.

I'm actually confused what you mean where you say that I'm never computing the path indexes?

[Chainsaw]

Here's a snippet of your code:

for (y=starty+1; y<=endy; y++)	// go down each column
	{
		for (x=startx+1; x<=endx; x++)	// go across each row
		{
			int distance_up = distance[x][y-1] + a[x][y-1];			// calculate weight to get to (x,y) from coordinate below it
			int distance_right = distance[x-1][y] + r[x-1][y];		// calculate weight to get to (x,y) from coordinate to left of it
			if (distance_up < distance_right)	// it's better to move up
			{
				distance[x][y] = distance_up;		// populate our distance array
				path[x][y] = 1;						// populate our path array
				cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
			else								// it's better to move right
			{
				distance[x][y] = distance_right;	// populate our distance array
				path[x][y] = 0;						// populate our path array
				cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
		}
	}

x and y both go from 2..5 They skip 1! So path[1][y] and [x][1] values (10 total) are all random.

[Chainsaw]

And I wasn't advocating more complicated arrays, but you had this comment in the code:

// I could find no easy way to dynamically create a 2D array in C++

So I couldn't resist opening my big mouth about it. :-)

[Dani]

Ahh! But if you look above that loop, you will realize that the first row and the first column of the matrix are populated each in their own individual loops, therefore taking care of [1][y] and [x][1]

[Chainsaw]

true for distance[][] but not path[][].

Or am I smoking too much crack again?

for (x=startx+1; x<=endx; x++)
	{
		distance[x][starty] = distance[x-1][starty] + r[x-1][starty];
		cout << "We went right to get to (" << x << "," << starty << ") in " << distance[x][starty] << " units" << endl;
	}

path[x][starty] is set to, er, well, see, it's like this....