Thread: C fastest path problem

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    37

    C fastest path problem

    Hi, my current C project is a program that looks at a text file with a matrix inside. The format of the matrix is like so:
    1,2,5,6
    5,6,7,8
    1,8,7,9
    1,1,3,2:
    The matrix can be comprised of ANY set of numbers so long as the matrix is size n x n.
    The program has to be able to find a path from the top-left of the matrix to the bottom-right of the matrix that costs the least sum; in this case of the example matrix above the solution is: 1,5,1,1,1,3,2
    So, i need a way for the program to go through every possible path and store the data so as not to retrace the paths already taken.
    The solution i've come up with requires me to be able to store arbitrary amounts of data because 'n' in the n x n matrix is variable.
    If i haven't made it clear already, i can't use something like "path[i]" because there is not a set amount of paths. Someone suggested linked lists but i don't see how i can create a linked list of any desired size.
    This may not have been a very clear explanation, i can clarify if anyone has questions.
    Last edited by bluej322; 02-28-2011 at 06:03 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by bluej322 View Post
    Someone suggested linked lists but i don't see how i can create a linked list of any desired size.
    Then you have no understanding of linked lists.

    Also, all you have to do is know N and you can simply use dynamic allocation to allocate N*N elements of whatever you want.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Third Eye Babkockdood's Avatar
    Join Date
    Apr 2010
    Posts
    352
    You could find the number of columns in the matrix by finding how many integers there are in each line, then you could find the number of rows in the matrix by simply counting the lines (or count how many lines begin with an integer, if you want to be safe). Then create a two-dimensional array with each number you found.

    And you can just use fscanf to get the array's elements.
    Quote Originally Posted by The Jargon File
    Microsoft Windows - A thirty-two bit extension and graphical shell to a sixteen-bit patch to an eight-bit operating system originally coded for a four-bit microprocessor which was written by a two-bit company that can't stand one bit of competition.

  4. #4
    Registered User
    Join Date
    Jan 2011
    Posts
    37
    Quote Originally Posted by quzah View Post
    Then you have no understanding of linked lists.

    Also, all you have to do is know N and you can simply use dynamic allocation to allocate N*N elements of whatever you want.


    Quzah.
    You're right, I've used linked lists once but I didn't see the dynamic capabilities. In fact, the measly code below is all i have done with linked lists. What i don't understand is how i can declare multiple structs if like in the example i have to declare n1, n2, and n3.

    Code:
    #include <stdio.h>
    
    struct list {
    	int value;
    	struct list *next;
    };
    
    main()
    {
    	struct list n1, n2, n3;
    	int i;
    	
    	n1.value = 100;
    	n2.value = 200;
    	n3.value = 300;
    	n1.next = &n2;
    	n2.next = &n3;
    	n3.next = NULL;
    
    }

  5. #5
    Registered User
    Join Date
    Jan 2011
    Posts
    37
    Quote Originally Posted by Babkockdood View Post
    You could find the number of columns in the matrix by finding how many integers there are in each line, then you could find the number of rows in the matrix by simply counting the lines (or count how many lines begin with an integer, if you want to be safe). Then create a two-dimensional array with each number you found.

    And you can just use fscanf to get the array's elements.
    I did just that.
    The code below isn't complete, i realized that the path algorithm would only detect shortest routes adjacent to the current position, thus failing in the first example matrix in my original post.

    Code:
    #include <stdio.h>
    #include <ctype.h>
    #include <string.h>
    
    int main() {
    	
    	FILE *file = fopen("/Users/bluej322/desktop/sequence.txt","r");
    	
    	char val=getc(file);
    	char line[40];
    	char tmpNum[10];
    	int totalLength = 0;
    	int currentRow = 1;
    	int x = 0;
    	int y = 0;
    	int rowCount = 1;
    	int colCount = 1;
    	int row;
    	int col;
    	int endQue=0;
    	int endNumber=0;
    	int lastDirect=1; //1=up,2=right,3=down,4=left
    
    	
    	while (val!=EOF) {
    		printf("%c",val);
    		line[totalLength]=val;
    		++totalLength;
    		val=getc(file);
    		
    	}
    	
    	if (val=EOF) {
    		line[totalLength]=':';
    		printf("\n");
    	}
    	
    	fclose(file);
    	printf("File Closed\n");
    
    	
    	//row/col count
    	x=0;
    	while (line[x]!='\n') {
    		if (line[x]==',') {
    			++colCount;
    		}
    		++x;
    	}
    	col=colCount;
    	
    	for (x=0;x<totalLength;++x) {
    		if (line[x]=='\n') {
    			++rowCount;
    		}
    	}
    	row=rowCount;
    
    	int matrix[row][col];
    	int path[totalLength];
    	int index=0;
    	
    	printf("Rows: %d\nColumns: %d\n",rowCount,colCount);
    	
    	//proto4
    
    	
    	
    	for (x=0,y=0,row=0,col=0;x<totalLength;++x) {
    		if (isdigit(line[x])) {	
    			tmpNum[y]=line[x];
    			++y;
    			if (line[x+1]=='\n' || line[x+1]==':') {
    				tmpNum[y]='\0';
    				printf("- %s\n",tmpNum);
    				matrix[row][col]=atoi(tmpNum);
    				printf("Matrix[%d][%d]: %d\n",row,col,matrix[row][col]);
    				++col;
    				y=0;
    				if (line[x+1]==':') {
    					endNumber=matrix[row][col];
    				}
    			}
    		}else if (line[x]=='\n') {
    			++row;
    			printf("++ROW\n");
    			col=0;
    			y=0;
    		}else {
    			tmpNum[y]='\0';
    			printf("- %s\n",tmpNum);
    			matrix[row][col]=atoi(tmpNum);
    			printf("Matrix[%d][%d]: %d\n",row,col,matrix[row][col]);
    			printf("++COL\n");
    			++col;
    			y=0;
    		}
    		
    	}
    	
    	printf("\n");
    
    
    	for (x=0;x<rowCount;++x) {
    		for (y=0;y<colCount;++y) {
    			printf(" %d ",matrix[x][y]);
    		}
    		printf("\n");
    	}
    	
    	
    	//path algorithm
    	x=0;
    	y=0;
    	
    	
    	while (endQue==0) {
    		if (x==row && y==col) {
    			path[index]=matrix[x][y];
    			endQue=1;
    			//top-left
    		}else if (y-1<0 && x-1<0) {
    			if (matrix[x+1][y]<matrix[x][y+1]) {
    				printf("down\n");
    				path[index]=matrix[x][y];
    				++x;
    				++index;
    				lastDirect=3;
    			}else{
    				printf("right\n");
    				path[index]=matrix[x][y];
    				++y;
    				++index;
    				lastDirect=2;
    			}
    			//left side, space up and down
    		}else if (y-1<0 && (x+1)<=rowCount-1 && (x-1)>=0) {   
    			if (matrix[x+1][y]<matrix[x-1][y]) {
    				if (matrix[x+1][y]<matrix[x][y+1] && lastDirect!=1) {
    					printf("down\n");
    				}else {
    					printf("right\n");
    					path[index]=matrix[x][y];
    					++y;
    					++index;
    					lastDirect=2;
    				}
    
    			}else if (matrix[x-1][y]<matrix[x+1][y]) {
    				if (matrix[x-1][y]<matrix[x][y+1] && lastDirect!=3) {
    					printf("up\n");
    					path[index]=matrix[x][y];
    					--x;
    					++index;
    					lastDirect=1;
    					
    				}else{
    					printf("right\n");
    					path[index]=matrix[x][y];
    					++y;
    					++index;
    					lastDirect=2;
    				}
    			}
    
    			//right side, space up and down
    		}else if (y+1>colCount-1 && x-1>=0 && x+1<=rowCount-1) {
    			if (matrix[x+1][y]<matrix[x-1][y]) {
    				if (matrix[x+1][y]<matrix[x][y-1] && lastDirect!=1) {
    					printf("down\n");
    					path[index]=matrix[x][y];
    					++x;
    					++index;
    					lastDirect=3;
    					
    				}else{
    					printf("left\n");
    					path[index]=matrix[x][y];
    					--y;
    					++index;
    					lastDirect=4;
    					
    				}
    			}else if (matrix[x-1][y]<matrix[x+1][y]) {
    				if (matrix[x-1][y]<matrix[x][y-1] && lastDirect!=3) {
    					printf("up\n");
    				}else {
    					printf("left\n");
    					path[index]=matrix[x][y];
    					--y;
    					++index;
    					lastDirect=4;
    				}
    			}
    			//middle
    		}else if (x+1<=rowCount-1 && x-1>=0 && y+1<=colCount-1 && y-1>=0) {
    			if (matrix[x-1][y]<matrix[x+1][y]) {
    				if (matrix[x-1][y]<matrix[x][y-1]) {
    					if (matrix[x-1][y]<matrix[x][y+1] && lastDirect!=3) {
    						printf("up\n");
    					}else {
    						printf("right\n");
    					}
    
    				}else if (matrix[x][y-1]<matrix[x-1][y]) {
    					if (matrix[x][y-1]<matrix[x][y+1] && lastDirect!=2) {
    						printf("left");
    					}else {
    						printf("right\n");
    					}
    				}
    
    			}else if (matrix[x+1][y]<matrix[x-1][y]) {
    					if (matrix[x+1][y]<matrix[x][y-1]) {
    						<#statements#>
    					}else if (matrix[x+1][y]<matrix[x][y+1]) {
    						<#statements#>
    					}
    				}
    
    			
    			}
    		}
    	}
    }

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by bluej322 View Post
    You're right, I've used linked lists once but I didn't see the dynamic capabilities.
    The whole point of linked lists is to use dynamically allocated structures.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Jan 2011
    Posts
    37
    Quote Originally Posted by quzah View Post
    The whole point of linked lists is to use dynamically allocated structures.

    Quzah.
    Could you show me an example of this?

  8. #8
    Third Eye Babkockdood's Avatar
    Join Date
    Apr 2010
    Posts
    352
    I highly recommend appropriate code spacing, lol.

    Try using one loop to get the first dimension of the array, and use a second loop to get the second dimension. Use fseek in between these loops to reset the file stream to the beginning of the file, it sounds like that's your problem.

    EDIT: Sorry, here's a link for fseek.
    http://www.manpagez.com/man/3/fseek/
    Last edited by Babkockdood; 02-28-2011 at 05:49 PM.
    Quote Originally Posted by The Jargon File
    Microsoft Windows - A thirty-two bit extension and graphical shell to a sixteen-bit patch to an eight-bit operating system originally coded for a four-bit microprocessor which was written by a two-bit company that can't stand one bit of competition.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You extend your linked list with another node, as needed, BUT linked lists are not for you, my "I don't see how I can create a linked list of any desired size", friend.

    I would suggest an array - a big array. They're much faster to program right, and easier to debug. A good sized upper limit could be n * n, divided by some factor, no?

    DFS maybe, with a cost variable as it goes along?
    http://en.wikipedia.org/wiki/Depth-first_search
    Last edited by Adak; 02-28-2011 at 05:55 PM.

  10. #10
    Registered User
    Join Date
    Jan 2011
    Posts
    37
    Quote Originally Posted by Babkockdood View Post
    I highly recommend appropriate code spacing, lol.

    Try using one loop to get the first dimension of the array, and use a second loop to get the second dimension. Use fseek in between these loops to reset the file stream to the beginning of the file, it sounds like that's your problem.
    Haha, i know, i really should.
    I can put the data in a multidimensional array without a problem. The issue is calculating all paths and storing the data. Maybe i misunderstood what you're saying?

  11. #11
    Registered User
    Join Date
    Jan 2011
    Posts
    37
    Quote Originally Posted by Adak View Post
    You extend your linked list with another node, as needed, BUT linked lists are not for you, my "I don't see how I can create a linked list of any desired size", friend.

    I would suggest an array - a big array. They're much faster to program right, and easier to debug. A good sized upper limit could be n * n, divided by some factor, no?

    Is this related to Dijikstra's program for graphs?
    I am using an array, a multidimensional array. Yes, it is related but I'm not sure that it's identical.

  12. #12
    Third Eye Babkockdood's Avatar
    Join Date
    Apr 2010
    Posts
    352
    Quote Originally Posted by bluej322 View Post
    Haha, i know, i really should.
    I can put the data in a multidimensional array without a problem. The issue is calculating all paths and storing the data. Maybe i misunderstood what you're saying?
    I believe I misunderstood what you're saying.

    Are you trying to find the shortest possible path of obtaining the elements? I think I can write a program like this in much less lines. Maybe you're program's worrying too much about the fastest way to obtain data - it could be using that time to actually obtain the data. I'll write my own version and post it.
    Quote Originally Posted by The Jargon File
    Microsoft Windows - A thirty-two bit extension and graphical shell to a sixteen-bit patch to an eight-bit operating system originally coded for a four-bit microprocessor which was written by a two-bit company that can't stand one bit of competition.

  13. #13
    Registered User
    Join Date
    Jan 2011
    Posts
    37
    Quote Originally Posted by Babkockdood View Post
    I believe I misunderstood what you're saying.

    Are you trying to find the shortest possible path of obtaining the elements? I think I can write a program like this in much less lines. Maybe you're program's worrying too much about the fastest way to obtain data - it could be using that time to actually obtain the data. I'll write my own version and post it.
    Oh, I'm sorry. I neglected to say that it has to go from the top left to the bottom right position of the matrix.

  14. #14
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    The best way to tackle this is working backwards. I recommend the 2-d array method you're using. Each element should contain the cost of traversing that square (the data from the input file) and the total cheapest cost from that node to the goal.

    Work this backwards, starting from the goal. To explain, I will pretend that every square has a cost of 1. You would build a grid like the following:
    Code:
    S x 4 3 2
    9 x 5 x 1
    8 x 6 x G
    7 6 5 x 1
    6 5 4 3 2
    Where S is the start, G is the goal and x means the square is untraversable (just to make the example more interesing.

    Basically you calculate the cost to the goal for every square in your grid, by expanding recursively from the goal to it's neighbors, then their neighbors, etc. Always record the lowest cost for each square (e.g. the red square above would have a cost of 7 if coming from the top, or 5 if coming from the bottom). Once you fill in the whole grid, you then start at the S and move to whichever neighbor has the lowest cost to goal. Here are a couple solutions for the previous example, with the quickest path marked by a dot (there are actually 3 solutions with equal cost):
    Code:
    S x 4 3 2     or     S x 4 3 2
    . x 5 x 1            . x 5 x 1
    . x 6 x G            . x 6 x G
    . . . x .            . 6 5 x .
    6 5 . . .            . . . . .
    Now, in your code, all you have to do is create a similar grid, but instead of using 1 as the cost for each square, use the costs as specified in the input file.
    Last edited by anduril462; 02-28-2011 at 07:08 PM. Reason: Clarified a bit

  15. #15
    Third Eye Babkockdood's Avatar
    Join Date
    Apr 2010
    Posts
    352
    Quote Originally Posted by bluej322 View Post
    Oh, I'm sorry. I neglected to say that it has to go from the top left to the bottom right position of the matrix.
    Damn, that sounds tough.

    Look into isdigit and fgetc if you haven't already.
    isdigit(3): char classification routines - Linux man page
    man page fgetc section 3
    Quote Originally Posted by The Jargon File
    Microsoft Windows - A thirty-two bit extension and graphical shell to a sixteen-bit patch to an eight-bit operating system originally coded for a four-bit microprocessor which was written by a two-bit company that can't stand one bit of competition.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem building Quake source
    By Silvercord in forum Game Programming
    Replies: 16
    Last Post: 07-11-2010, 09:13 AM
  2. Can't figure out what keeps hanging up my program
    By shays in forum C Programming
    Replies: 7
    Last Post: 11-12-2007, 02:59 PM
  3. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 05:32 PM
  4. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 05:20 AM
  5. linked list recursive function spaghetti
    By ... in forum C++ Programming
    Replies: 4
    Last Post: 09-02-2003, 02:53 PM