How to find the longest sequence in a 2d array?
up vote
0
down vote
favorite
Given a 2d grid, with the below constraints, I want to find the longest sub-sequence :
- allowed to move up, right, left, down, diagonally
- difference between the current value and the next value should be greater than or equal to 3 (i.e absolute difference).
- visited cells should not be repeated
- grid could be maximum 10 x 10
- not allowed to do 4 -> 9 in the below example
Example:
824
061
379
The length of the longest path for the above input is 8, with the sequence 9,1,6,2,8,0,7,3
I tired to approach using multiple for loops, but it would be highly inefficient. I want to know how do I approach using Dynamic Programming. Any help would be appreciated.
algorithm recursion data-structures dynamic-programming
New contributor
|
show 9 more comments
up vote
0
down vote
favorite
Given a 2d grid, with the below constraints, I want to find the longest sub-sequence :
- allowed to move up, right, left, down, diagonally
- difference between the current value and the next value should be greater than or equal to 3 (i.e absolute difference).
- visited cells should not be repeated
- grid could be maximum 10 x 10
- not allowed to do 4 -> 9 in the below example
Example:
824
061
379
The length of the longest path for the above input is 8, with the sequence 9,1,6,2,8,0,7,3
I tired to approach using multiple for loops, but it would be highly inefficient. I want to know how do I approach using Dynamic Programming. Any help would be appreciated.
algorithm recursion data-structures dynamic-programming
New contributor
if you want to use dynamic programming you need to define a recurrence relation with base case first. that shouldn't be very hard since you already got a feeling that the same subproblems are called multiple times
– mangusta
Nov 21 at 3:46
Pham, I've edited the question. It's actually greater than or equal to 3.
– Ramesh
Nov 21 at 3:56
2
This looks like a variation of the en.wikipedia.org/wiki/Longest_path_problem to me. So there might be no efficient solution.
– SaiBot
Nov 21 at 7:05
Why not do a depth first search instead of dynamic programming?
– vivek_23
Nov 21 at 7:11
apparently I think it cannot be solved by means of dynamic programming, because all subproblems are distinct from each other. for example, we would like to find sequences starting with2
and7
. at first glance it seems that going one step down for2
and one step up for7
will call the same subproblem i.e.start with 6
, but it is actually not the same subproblem because if we go from2
, then2
is visited so we can't pick2
anymore, and if we go from7
then7
is visited and we can't pick7
anymore
– mangusta
Nov 21 at 7:15
|
show 9 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given a 2d grid, with the below constraints, I want to find the longest sub-sequence :
- allowed to move up, right, left, down, diagonally
- difference between the current value and the next value should be greater than or equal to 3 (i.e absolute difference).
- visited cells should not be repeated
- grid could be maximum 10 x 10
- not allowed to do 4 -> 9 in the below example
Example:
824
061
379
The length of the longest path for the above input is 8, with the sequence 9,1,6,2,8,0,7,3
I tired to approach using multiple for loops, but it would be highly inefficient. I want to know how do I approach using Dynamic Programming. Any help would be appreciated.
algorithm recursion data-structures dynamic-programming
New contributor
Given a 2d grid, with the below constraints, I want to find the longest sub-sequence :
- allowed to move up, right, left, down, diagonally
- difference between the current value and the next value should be greater than or equal to 3 (i.e absolute difference).
- visited cells should not be repeated
- grid could be maximum 10 x 10
- not allowed to do 4 -> 9 in the below example
Example:
824
061
379
The length of the longest path for the above input is 8, with the sequence 9,1,6,2,8,0,7,3
I tired to approach using multiple for loops, but it would be highly inefficient. I want to know how do I approach using Dynamic Programming. Any help would be appreciated.
algorithm recursion data-structures dynamic-programming
algorithm recursion data-structures dynamic-programming
New contributor
New contributor
edited Nov 21 at 3:53
New contributor
asked Nov 21 at 3:30
Ramesh
11
11
New contributor
New contributor
if you want to use dynamic programming you need to define a recurrence relation with base case first. that shouldn't be very hard since you already got a feeling that the same subproblems are called multiple times
– mangusta
Nov 21 at 3:46
Pham, I've edited the question. It's actually greater than or equal to 3.
– Ramesh
Nov 21 at 3:56
2
This looks like a variation of the en.wikipedia.org/wiki/Longest_path_problem to me. So there might be no efficient solution.
– SaiBot
Nov 21 at 7:05
Why not do a depth first search instead of dynamic programming?
– vivek_23
Nov 21 at 7:11
apparently I think it cannot be solved by means of dynamic programming, because all subproblems are distinct from each other. for example, we would like to find sequences starting with2
and7
. at first glance it seems that going one step down for2
and one step up for7
will call the same subproblem i.e.start with 6
, but it is actually not the same subproblem because if we go from2
, then2
is visited so we can't pick2
anymore, and if we go from7
then7
is visited and we can't pick7
anymore
– mangusta
Nov 21 at 7:15
|
show 9 more comments
if you want to use dynamic programming you need to define a recurrence relation with base case first. that shouldn't be very hard since you already got a feeling that the same subproblems are called multiple times
– mangusta
Nov 21 at 3:46
Pham, I've edited the question. It's actually greater than or equal to 3.
– Ramesh
Nov 21 at 3:56
2
This looks like a variation of the en.wikipedia.org/wiki/Longest_path_problem to me. So there might be no efficient solution.
– SaiBot
Nov 21 at 7:05
Why not do a depth first search instead of dynamic programming?
– vivek_23
Nov 21 at 7:11
apparently I think it cannot be solved by means of dynamic programming, because all subproblems are distinct from each other. for example, we would like to find sequences starting with2
and7
. at first glance it seems that going one step down for2
and one step up for7
will call the same subproblem i.e.start with 6
, but it is actually not the same subproblem because if we go from2
, then2
is visited so we can't pick2
anymore, and if we go from7
then7
is visited and we can't pick7
anymore
– mangusta
Nov 21 at 7:15
if you want to use dynamic programming you need to define a recurrence relation with base case first. that shouldn't be very hard since you already got a feeling that the same subproblems are called multiple times
– mangusta
Nov 21 at 3:46
if you want to use dynamic programming you need to define a recurrence relation with base case first. that shouldn't be very hard since you already got a feeling that the same subproblems are called multiple times
– mangusta
Nov 21 at 3:46
Pham, I've edited the question. It's actually greater than or equal to 3.
– Ramesh
Nov 21 at 3:56
Pham, I've edited the question. It's actually greater than or equal to 3.
– Ramesh
Nov 21 at 3:56
2
2
This looks like a variation of the en.wikipedia.org/wiki/Longest_path_problem to me. So there might be no efficient solution.
– SaiBot
Nov 21 at 7:05
This looks like a variation of the en.wikipedia.org/wiki/Longest_path_problem to me. So there might be no efficient solution.
– SaiBot
Nov 21 at 7:05
Why not do a depth first search instead of dynamic programming?
– vivek_23
Nov 21 at 7:11
Why not do a depth first search instead of dynamic programming?
– vivek_23
Nov 21 at 7:11
apparently I think it cannot be solved by means of dynamic programming, because all subproblems are distinct from each other. for example, we would like to find sequences starting with
2
and 7
. at first glance it seems that going one step down for 2
and one step up for 7
will call the same subproblem i.e. start with 6
, but it is actually not the same subproblem because if we go from 2
, then 2
is visited so we can't pick 2
anymore, and if we go from 7
then 7
is visited and we can't pick 7
anymore– mangusta
Nov 21 at 7:15
apparently I think it cannot be solved by means of dynamic programming, because all subproblems are distinct from each other. for example, we would like to find sequences starting with
2
and 7
. at first glance it seems that going one step down for 2
and one step up for 7
will call the same subproblem i.e. start with 6
, but it is actually not the same subproblem because if we go from 2
, then 2
is visited so we can't pick 2
anymore, and if we go from 7
then 7
is visited and we can't pick 7
anymore– mangusta
Nov 21 at 7:15
|
show 9 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
Just run bfs (Breadth-first search) from every possible source in the grid by following the constraints. For example, in your given sample input the number of possible source is 9. Then, save the paths in some suitable data structure. After saving the paths, check which path is longest and that's your answer.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Just run bfs (Breadth-first search) from every possible source in the grid by following the constraints. For example, in your given sample input the number of possible source is 9. Then, save the paths in some suitable data structure. After saving the paths, check which path is longest and that's your answer.
add a comment |
up vote
0
down vote
Just run bfs (Breadth-first search) from every possible source in the grid by following the constraints. For example, in your given sample input the number of possible source is 9. Then, save the paths in some suitable data structure. After saving the paths, check which path is longest and that's your answer.
add a comment |
up vote
0
down vote
up vote
0
down vote
Just run bfs (Breadth-first search) from every possible source in the grid by following the constraints. For example, in your given sample input the number of possible source is 9. Then, save the paths in some suitable data structure. After saving the paths, check which path is longest and that's your answer.
Just run bfs (Breadth-first search) from every possible source in the grid by following the constraints. For example, in your given sample input the number of possible source is 9. Then, save the paths in some suitable data structure. After saving the paths, check which path is longest and that's your answer.
answered Nov 22 at 13:39
Golam Rahman Tushar
646
646
add a comment |
add a comment |
Ramesh is a new contributor. Be nice, and check out our Code of Conduct.
Ramesh is a new contributor. Be nice, and check out our Code of Conduct.
Ramesh is a new contributor. Be nice, and check out our Code of Conduct.
Ramesh is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53404864%2fhow-to-find-the-longest-sequence-in-a-2d-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
if you want to use dynamic programming you need to define a recurrence relation with base case first. that shouldn't be very hard since you already got a feeling that the same subproblems are called multiple times
– mangusta
Nov 21 at 3:46
Pham, I've edited the question. It's actually greater than or equal to 3.
– Ramesh
Nov 21 at 3:56
2
This looks like a variation of the en.wikipedia.org/wiki/Longest_path_problem to me. So there might be no efficient solution.
– SaiBot
Nov 21 at 7:05
Why not do a depth first search instead of dynamic programming?
– vivek_23
Nov 21 at 7:11
apparently I think it cannot be solved by means of dynamic programming, because all subproblems are distinct from each other. for example, we would like to find sequences starting with
2
and7
. at first glance it seems that going one step down for2
and one step up for7
will call the same subproblem i.e.start with 6
, but it is actually not the same subproblem because if we go from2
, then2
is visited so we can't pick2
anymore, and if we go from7
then7
is visited and we can't pick7
anymore– mangusta
Nov 21 at 7:15