Member Avatar for 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!

  • 4 Contributors
  • 11 Replies
  • 189 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by Chainsaw
Member Avatar for 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. ;)

Member Avatar for 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.

Member Avatar for Chainsaw

We don't do your homework for you.


HA HA HA HA HA :-)

(Sorry, I couldn't resist)

Member Avatar for 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? ;)

Member Avatar for 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.

// DANI HOROWITZ
	// NOVEMBER 2004

/***************************************************************************/
/***************************************************************************/

//		CSC 155 Project 2 Dynamic Programming 
//			Assigned 11/02/2004
//			  Due : 11/16/2004
//
//	This file contains the description of the following two problems
//
//	1) Shortest path on a rectangular grid
//	2) Partitioning a set of elements S into two subsets A and B such that the 
//	   sum total of the value associated with the elements of A and that of 
//	   B are equal						(Extra Credit) 
//
// Problem 1:
//
// Shortest path on a rectangular grid
//
// You are given a rectangular grid consisting of mn points (i.e. m points on the 
// x-axis and n points on the y-axis. Let the co-ordinates of these mn grid points 
// be (1,1),(1,2),(1,3),..., (1,n), (2,1), (2,2), ..., (2,n), ... (m,1), ...(m,n).  
// You are told that every grid point (i,j) is connected only to the four adjacent 
// grid points (i-1,j), (i,j-1), (i+1, j) and (i, j+1). Each link that connects 
// a grid point (i,j) with its neighbor is associated with a link distance.
// The link distance between the grid point (i,j) and the grid point to its right 
// (i, j+1) is stored in a 2-dimensional array Right[i,j] and the link distance 
// between the grid point (i,j) and the grid point above it (i+1,j) is stored in 
// a 2-dimensional array Above[i,j].

// You are told that to begin with you are at grid point (1,1) and your objective 
// is to reach the grid point (m,n) by choosing the shortest path. In addition, 
// you are told at any grid point (i,j) you are allowed to either move to the grid 
// point (i, j+1) immediately to your right or the grid point (i+1, j) one 
// immediately above you.

// Write a dynamic program to determine the shortest path from grid point (1,1) to
// grid point (m, n). 

// You need to write a program to solve the above problem using dynamic 
// programming techniques discussed in class.
//
// int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy, 
// 				   int Right[][], int Above[][])
//
// Given the grid points with co-ordinates (startx, starty) and (endx, endy),
// the above function returns an array containing the shortest path from 
// (startx, starty) to (endx, endy) 
//
// Problem 2:
//
// Partitioning a set of elements S into two subsets A and B such that the 
// sum total of the value associated with the elements of A and that of 
// B are equal						(Extra Credit) 

// You are given an integer array S of n elements, you need to partition the 
// elements in S into two arrays A and B such that the sum of the elements in A 
// equals the sum of the elements in B
//
// You need to write a program to solve the above problem using dynamic 
// programming techniques discussed in class.
//
// void		Partition(int *S, int *A, int *B)
//
// Example : suppose the array S contains the items {20, 15, 35, 45, 55, 30}
// then the program partitions the elements in S into two arrays 
// A = {20, 15, 35, 30} and B = {45, 55}. If the set S cannot be partitioned 
// into two equal sub-arrays set both A and B to empty arrays.
// 
#include <iostream.h>
int	*Rectangular_Shortest_Path(int , int , int , int , int[][6], int[][6]);
void	Partition(int *S, int *A, int *B);

int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy, 
				   int r[][6], int a[][6])
{
	// I could find no easy way to dynamically create a 2D array in C++
	int distance[10][10];			// keep track of distances to get to each point
	int path[10][10];				// keep track of the best paths

	/***************************************************************************/
	/***************************************************************************/

	int size = (endx-startx)+(endy-starty);		// size of our shortest path array
	int* shortest_path = new int[size];			// it will take 8 steps to get from (0,0)->(5,5)
	cout << "It will take " << size << " steps" << endl;

	/***************************************************************************/
	/***************************************************************************/

	// populate our starting place
	distance[startx][starty] = 0;

	// populate bottom distance row
	for (int 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;
	}

	// populate leftmost distance row
	for (int y=starty+1; y<=endy; y++)
	{
		distance[startx][y] = distance[startx][y-1] + a[startx][y-1];
		cout << "We went up to get to (" << startx << "," << y << ") in " << distance[startx][y] << " units" << endl;
	}

	/***************************************************************************/
	/***************************************************************************/

	cout << endl;
	for (int y=starty+1; y<=endy; y++)	// go down each column
	{
		for (int 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 = endx;
	y = endy;
	int n=0;
	cout << endl << "Working backwards ..." << endl;
	// now that we have all of the smaller problems solved to calculate the optimal weight to get to every point on the grid,
	// let's figure out how to get from (5,5)->(1,1)

	while (x >= startx && y >= starty)	// loop so long as both coordinates are >= 1
	{
		if (x > startx && y > starty)
		{
			// we are not working in the first row or first column,
			// which means that we have an opportunity of going left or down, whichever is best

			if ((distance[x-1][y]+r[x-1][y]) < (distance[x][y-1]+a[x][y-1]))
			{
				cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				x--;	// move one unit left
			}
			else
			{
				cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				y--;	// move one unit down
			}
		}
		else
		{
			if (x == startx)	// we are somewhere in the left column
			{
				// we don't have a choice, we can only move down
				cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				y--;
			}
			else				// we are somewhere in the bottom row
			{
				// we don't have a choice, we can only move left
				cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
				x--;
			}
		}
		shortest_path[n] = path[x][y];		// populate our shortest path array
		n++;
	}

	cout << endl;

	/***************************************************************************/
	/***************************************************************************/

	return shortest_path;	// return the shortest path BACKWARDS!

	}

void	Partition(int *S, int *A, int *B)
{
	// please fill in your code here and remove the statement "return"
	return;
}


void	main()
{

	int	Right[6][6]; 	// entry Right[i][j] contains the link distance  
				// between grid point (i,j) to (i+1, j);
	int	Above[6][6]; 	// entry Above[i][j] contains the link distance  
				// between grid point (i,j) to (i, j+1);

	int	*shortest_path; // the array for storing the shortest path 

	int	S[10];		// set of items you would like to partition 
	int	A[10];		// the first half of the partition
	int	B[10];		// the second half of the partition


	//
	// read the inputs for the 2-dimensional arrays Right and Above 
	//

	for (int i=1; i< 6; i++)
	{
		for (int j=1; j < 6; j++)
		{
	cout << "Please enter the link distance : Right[" << i << "," << j << "]\n";
			cin  >> Right[i][j];
	cout << "Please enter the link distance : Above[" << i << "," << j << "]\n";
			cin  >> Above[i][j];
		}
		
	}
	shortest_path = Rectangular_Shortest_Path(1,1,5,5, Right, Above);

	/*
	//
	// read the inputs for the set S 
	//
	for (int i=1; i< 10; i++)
	{
		cout << "Please enter the " << i << "th item in S\n";
		cin  >> S[i];

	}
	Partition(S, A, B);
	*/
}
Member Avatar for 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 ];

Member Avatar for 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?

Member Avatar for 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.

Member Avatar for 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. :-)

Member Avatar for 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]

Member Avatar for 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....

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.