Pathfinding

[Mats]

I'm trying to find vertical paths of length n through a 2D grid of numbers. Paths may connect orthogonally or diagonally. An example grid and an example possible path looks like this:

//Grid 
   0 1 2 3 4 5 6 7 

0  2 4 6 4 1 3 4 5
1  5 3 5 8 6 6 6 6
2  3 4 2 1 1 2 5 3
3  3 2 3 3 1 3 4 5 
4  3 6 1 1 5 2 5 4
5  2 5 4 2 4 5 6 2
6  6 6 1 1 5 1 4 5 
7  1 5 6 4 2 4 2 3

A example possible path of length n = 3 is running from (3,2) to (3,4) - All 1s 
Edit: An example of n = 4 is the run of 3s (1,1) (0,2) (0,3), (0,4)

What is an efficient algorithm for solving this kind of problem? I would like to solve (ideally) millions of grids, giving a list for each grid of all possible paths of length for n = 3-6.

[lsk]

What's the result you want to solve? max sum?
or you just want to know all possible paths? (that's look like no algorithm, just loop them all.)

[Mats]

All paths of n = 3, n = 4, n = 5, n = 6. The thing is, I could just look at every node and find every path, but that is very expensive! It feels like there should be some kind of way to make that substantially more efficient? I can't think how though. =/

[lsk]

In your,

//Grid 
   0 1 2 3 4 5 6 7 

0  2 4 6 4 1 3 4 5
1  5 3 5 8 6 6 6 6
2  3 4 2 1 1 2 5 3
3  3 2 3 3 1 3 4 5 
4  3 6 1 1 5 2 5 4
5  2 5 4 2 4 5 6 2
6  6 6 1 1 5 1 4 5 
7  1 5 6 4 2 4 2 3

A example possible path of length n = 3 is running from (3,2) to (3,4) - All 1s 
Another example for n = 3 is the run of 3s from (0,2) to (0,5). 

Could you please explain what you want in output and how it comes to me ?
Sorry, but maybe I'm not smart in theory to understand what you really want.

[Mats]

The output would be something like:

Total number of paths for n = 3 : 3
Total number of paths for n = 4 : 1
Total number of paths for n = 5 : 0
Total number of paths for n = 6 : 1

Where the n = 3 paths are any path you can connect through orthogonally or diagonally that traverses at least 3 vertical levels, a n = 4 path connects 4 vertical levels etc...

[cire]

How would it be possible for a result of 1 with n equal to 6, if it was previously determined that when n is 5 the result is 0?

[keskiverto]

Let me guess: each element on a "path" must have same value?

In your example, there is value 1 in (3,2) (4,3) (3,4).
However, there is also (4,2) (4,3) (3,4). Is that a separate path?

Your "run of 3s" is a n=4: (1,1) (0,2) (0,3) (0,4).

I don't see a way to know the paths without looking at each element in the grid. What you do when you look at them is the real question.

[Mats]

Your "run of 3s" is a n=4: (1,1) (0,2) (0,3) (0,4).

Nice spot! I must go back and correct that.

[joe7]

You don't have to search the whole grid every time. You can initially copy the data stored in the grid into arrays of x,y positions of each number 1, 2, 3, etc. Then, when trying to find paths of a certain number, you are limiting the search to only that certain number, ignoring the rest.

[Mats]

hmm interesting idea. This is the kind of ideas I was hoping to get from this thread. I'll try it.

[lsk]

You can use easily recursion, running from i=0 to n-1 and j=0 to m-1,
assume a new array B contain 0s size = A's.
if B[i][j] = 0 then process A[i][j], which function is checking for the same value as A[i][j] around (i,j) by recursive. And after check, you'll know how many of them around, put it on all of B[-][-] you run through.

A
   0 1 2 3 4 5 6 7 

0  2 4 6 4 1 3 4 5
1  5 3 5 8 6 6 6 6
2  3 4 2 1 1 2 5 3
3  3 2 3 3 1 3 4 5 
4  3 6 1 1 5 2 5 4
5  2 5 4 2 4 5 6 2
6  6 6 1 1 5 1 4 5 
7  1 5 6 4 2 4 2 3

B
   0 1 2 3 4 5 6 7 

0  0 0 0 0 0 0 0 0
1  0 0 0 0 0 0 0 0
2  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
6  0 0 0 0 0 0 0 0
7  0 0 0 0 0 0 0 0

A
   0 1 2 3 4 5 6 7 

0  2 4 6 4 1 3 4 5
1  5 3 5 8 6 6 6 6
2  3 4 2 1 1 2 5 3
3  3 2 3 3 1 3 4 5 
4  3 6 1 1 5 2 5 4
5  2 5 4 2 4 5 6 2
6  6 6 1 1 5 1 4 5 
7  1 5 6 4 2 4 2 3

rec(0,0)

B
   0 1 2 3 4 5 6 7 

0  1 0 0 0 0 0 0 0
1  0 0 0 0 0 0 0 0
2  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
6  0 0 0 0 0 0 0 0
7  0 0 0 0 0 0 0 0

...

A
   0 1 2 3 4 5 6 7 

0  2 4 6 4 1 3 4 5
1  5 3 5 8 6 6 6 6
2  3 4 2 1 1 2 5 3
3  3 2 3 3 1 3 4 5 
4  3 6 1 1 5 2 5 4
5  2 5 4 2 4 5 6 2
6  6 6 1 1 5 1 4 5 
7  1 5 6 4 2 4 2 3

B
   0 1 2 3 4 5 6 7 

0  1 1 1 1 1 1 1 1
1  1 1 1 1 0 0 0 0
2  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
6  0 0 0 0 0 0 0 0
7  0 0 0 0 0 0 0 0

A
   0 1 2 3 4 5 6 7 

0  2 4 6 4 1 3 4 5
1  5 3 5 8 6 6 6 6
2  3 4 2 1 1 2 5 3
3  3 2 3 3 1 3 4 5 
4  3 6 1 1 5 2 5 4
5  2 5 4 2 4 5 6 2
6  6 6 1 1 5 1 4 5 
7  1 5 6 4 2 4 2 3

rec(1,4)

B
   0 1 2 3 4 5 6 7 

0  1 1 1 1 1 1 1 1
1  1 1 1 1 4 4 4 4
2  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
6  0 0 0 0 0 0 0 0
7  0 0 0 0 0 0 0 0

...

This may takes several comparison, if you want to minimize it, save all each number's position in array before start recursive.

[keskiverto]

You can initially copy the data stored in the grid into arrays of x,y positions of each number 1, 2, 3, etc.

One variant of this:
-Reserve a vector for N*M pairs (value,count).
-Create a N*M matrix B of pointers to those pairs.
-Iterate your data matrix.

A(i,j) has value
IF any in A(i-1,j-1), A(i,j-1), A(i+1,j-1) has same value
THEN set B(i,j) to point to existing pair** and increment the count of that pair
ELSE append new pair(value,1) and set B(i,j) to point to it.

**If there are more than one existing pair, then point to the one with largest count.

Now the vector has list of paths, but it only knows value and length for each path.
Replace the count with a list of x,y pairs. Length of list is still the count, but now you know the elements of each path.

You still have a problem with the Y-shaped paths. For example, there is a path of 3 and path of 4 that both are elongated by A(i,j) (into 4 and 5). My algorithm would leave the 3 as 3 and turn the 4 into 5 (and potentially more, if lower rows continue it).