how to find the longest path in a matrix ?

[Dan D'amico]

Hi, I have some N*M matrix or N*N matrx , and there's a "worm" that can start from any index in the first column, or, any index in the first row. i need to choose the longest worm that satisfying this :
the index that comes after the index before him must be greater then 1. and i must use recursion, also for helper methods. no loops at all. that's it. i'm having a problem to find the longest worm in the matrix.
my idea was to create an helper array and assign to the array indexes a variable that will count the steps of the worm and finally assigns in to the helper array index. then i used findMax method to find the max value in an index. and thats will be the longest worm. i wrote a lot of code so i wont put it here. i will say that i'm close. if the longest worm is 6 i get in my output 7.
still, someone here can point me some advice about this kind of excercise ?
thanks.

[Campbell Ritchie]

Forget all about arrays. Write down on paper how you would do it without using any computing words. Once you have that algorithm you can simply convert it to code.

[Dan D'amico]

Campbell Ritchie wrote:Forget all about arrays. Write down on paper how you would do it without using any computing words. Once you have that algorithm you can simply convert it to code.

i just was about to edit this question . since no answers. and since i wanted to be more specific.
yes i wrote it now actually.

if i start from [0][0] , i need to find the shortest path to [n-1][n-1] all integers in the path must be greater than the previous one

just recursion and no loops.

i thought to start with :
1) create a variable count. to count the steps
2) method to check if i'm not out of bounds
3) check to see if the next index has a value greater then my current index.
4) if so , incerement count, and call the function recursivly with thenew index.
5) if my path ends and im not at [n-1][n-1] or if i've arrived to [n-1][n-1] put count in an helper array. then set count back to 1.

finally if all paths were found, i will create a method that find the lowest value in the helper array. and thats will be the sortest path from [0][0] to [n-1][n-1]

am i correct ? you suggest to add something or change something ?

[fred rosenberger]

variable, method, "out of bounds", index, function, array, "[0][0]"...

these are all computing/programming words.

pretend you are talking to a ten year old child. you need to give them directions on how to find this path.

for example...I would have written this:
1) create a variable count. to count the steps
like this:
1) get a piece of paper on which I will keep track of how many steps I've taken.

[Dan D'amico]

fred rosenberger wrote:variable, method, "out of bounds", index, function, array, "[0][0]"...

these are all computing/programming words.

pretend you are talking to a ten year old child. you need to give them directions on how to find this path.

for example...I would have written this:
1) create a variable count. to count the steps
like this:
1) get a piece of paper on which I will keep track of how many steps I've taken.

ok . thanks

[Stevens Miller]

I'm having a hard time understanding what the assignment is. If he starts at (0,0) and must move to (n-1,n-1), with each step indexing its dimension by one greater than the previous step, that only allows one path, doesn't it? (I'm thinking it's this: (0,0), (1,1), (2,2)... (n-1,n-1) )

[Dan D'amico]

Stevens Miller wrote:I'm having a hard time understanding what the assignment is. If he starts at (0,0) and must move to (n-1,n-1), with each step indexing its dimension by one greater than the previous step, that only allows one path, doesn't it? (I'm thinking it's this: (0,0), (1,1), (2,2)... (n-1,n-1) )

but the path must be like that : if you go your way through the path. each value must be greater than the one before him
so a vaild path in this matrix for example , will be
3 4 6 9 10
7 9 10 11 12
3 6 7 3 13
1 7 8 9 15 so the shortest pathhere will be (0,0)(1,0)(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)
so the method goal is to return 8 , which is the shortests path in this matrix

[Stevens Miller]

I'm afraid I'm really baffled now, Dan. It seemed as though your goal was to reach position (n-1, n-1). But, your example ends at (1,6), while your matrix appears to have dimensions of 4 by 5. I'm afraid I also can't make the list of coordinate pairs match your criteria, no matter where I start and which way I assign each direction.

Maybe if you listed the values in the matrix at each of the eight steps in your example's path, I'd get a better idea of what you're doing.

[Liutauras Vilda]

Dan D'amico wrote:
but the path must be like that : if you go your way through the path. each value must be greater than the one before him
so a vaild path in this matrix for example , will be
3 4 6 9 10
7 9 10 11 12
3 6 7 3 13
1 7 8 9 15 so the shortest pathhere will be (0,0)(1,0)(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)
so the method goal is to return 8 , which is the shortests path in this matrix

I do not agree with bolded parts.

Beside that, you also need to check path from 3 to 4, because 4 is also greater than 3, and you cannot make an assumption that going from 3 > 7 you'll get what you want. You need to check all possible paths. Unless there are something else in the requirements which you forgot to mention to us, or assumed as not important.

Dan D'amico wrote:...having a problem to find the longest worm in the matrix.

Do you need shortest path, or longest worm (sounds like a longest path)? Stick to a one requirement, will be easier to point you out.
If you're looking for a shortest path, i'm thinking about BFS or Dijkstra algorithm, this is what they are meant to do.

[Stefan Evans]

Most probably that longest path is meant to be:

3 - (0,0)
7 - (0,1)
9 - (1,1)
10 - (1,2)
11 - (1,3)
12 - (1,4)
13 - (2, 4)
15 - (3,4)

That shows the worm advancing either to the right, or down, each time moving to a square with a larger number than the one it came from.
Note that there is an equally long path going along the top, and then straight down


Seeing as this is applying recursion, you should actually start simple and build up.
What is your base case? And what should its answer be?

Solve it for a 1x1 matrix
Solve it for a 2x1 matrix
Solve it for a 2x2 matrix
...

[Liutauras Vilda]

There are more than one longest path:

3 -> 4 -> 6 -> 9 -> 10 (0,4) -> 12 -> 13 -> 15 = 8
3 -> 4 -> 6 -> 9 -> 10 (1,2) -> 12 -> 13 -> 15 = 8

As I mentioned, probably over here need to use special purpose algorithms.

[Piet Souris]

hi Dan,

you haven't told us anything about the (long) method you wrote about in your opening post.
However, you asked about anything that might help you.

Well, what I might do is: suppose you have a method called 'findMax'. Parameters could be
a row and a column, and a int 'length_so_far'. Now, the cell matrix(row, column) has at most
four neighbours, and of these neighbours not all can be involved, only those neighbours
having a value that is higher that that of matrix(row, column). Now, for each suitable
neighbour N, with indices Nx, Ny, you know for sure that the path you're on, and that
has its current length equal to 'length_so_far', can be extended by at least 1. So you might
like to call findMax(Nx, Ny, length_so_far + 1).

Of course, as with any recursion, there must be at least one base case, and each recursion
must bring you closer to a base case, in some sense. Suppose that you do not find any
suitable neighbour. Then what? And how does it get started?

Greetz,
Piet