Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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.

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

Marshal

Posts: 56533

172

Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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 ?

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 ?

posted 2 years ago

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.

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

ok . thanks

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

posted 2 years ago

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) )

"Il y a peu de choses qui me soient impossibles..."

Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

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

posted 2 years ago

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.

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.

"Il y a peu de choses qui me soient impossibles..."

posted 2 years ago

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.

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.

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 matrixfor 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

posted 2 years ago

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

...

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

...

Piet Souris

Master Rancher

Posts: 2042

75

posted 2 years ago

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

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

It is sorta covered in the JavaRanch Style Guide. |