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.

Originally Posted by bluej322

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.

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.

Originally Posted by quzah

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;

}

Originally Posted by Babkockdood

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#>
					}
				}

			
			}
		}
	}
}

Originally Posted by bluej322

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.

Originally Posted by quzah

The whole point of linked lists is to use dynamically allocated structures.

Quzah.

Could you show me an example of this?

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/

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

Originally Posted by Babkockdood

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?

Originally Posted by Adak

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.

Originally Posted by bluej322

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.

Originally Posted by Babkockdood

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.

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.

Originally Posted by bluej322

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