programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# how to find the longest path in a matrix ?

Dan D'amico
Ranch Hand
Posts: 94
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.
thanks.

Campbell Ritchie
Marshal
Posts: 56533
172
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
Ranch Hand
Posts: 94
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.

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
lowercase baba
Bartender
Posts: 12563
49
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
Ranch Hand
Posts: 94
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
Bartender
Posts: 1445
30
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
Ranch Hand
Posts: 94
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
Bartender
Posts: 1445
30
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
Sheriff
Posts: 4917
334
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
Bartender
Posts: 1837
10
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.

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

Liutauras Vilda
Sheriff
Posts: 4917
334
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
Master Rancher
Posts: 2042
75
hi Dan,

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

 It is sorta covered in the JavaRanch Style Guide.