Find the maximum length of a good path in the grid

Question

This is an N * N grid. Now we need to find a good path of maximum length, where the correct path is defined as follows:

• A good way always starts with a cell marked as 0
• We are allowed to move left, right, up or down
• If the value of the ith cell is indicated by A, then the value of the next cell in the path must be A + 1.

Now, given these few conditions, I need to figure out the length of the maximum path that can be done. I also need to count paths that have the maximum length.

Example: let N = 3, and we have a 3 * 3 matrix as follows:

0 3 2 3 0 1 2 1 0 

Then the maximum length of the allowed path here is 3, and the number of such good paths is 4.

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

Answer 1

This problem is a variation. The longest path problem , however, your limitations make this problem much simpler because the graph is actually a Directional Acyclic Graph (DAG) , and therefore, the problem can be effectively solved.

Define a directed graph G=(V,E) as follows:

• V = { all cells in the matrix} (health check: | V | = N ^ 2)
• E = { (u,v) | u is adjacent to v AND value(u) + 1 = value(v) }

Note that the resulting graph from the above definition is DAG, because you cannot have any loops, as this will result in some edge e= (u,v) such as value(u) > value(v) .

Now you need to find the longest path in the DAG from any starting point. This is done using topological sorting on the graph, and then using dynamic programming:

 init: for every source in the DAG: D(v) = 0 if value(v) = 0 -infinity otherwise step: for each node v from first to last (according to topological sort) D(v) = max{D(u) + 1 | for each edge (u,v) } 

When you're done, find node v with the maximum value of D(v) , this is the length of the longest "good path".
The search for the path itself is performed by repeating the above, re-returning your steps back from the maximum D (v) until you return to the original node with a value of 0.

The complexity of this approach is O(V+E) = O(n^2)

---

Since you are looking for the number of longest paths, you can slightly modify this solution to calculate the number of paths reached for each node, as follows:

 Topological sort the nodes, let the sorted array be arr (1) For each node v from start to end of arr: if value(v) = 0: set D(v) = 1 else sum = 0 for each u such that (u,v) is an edge: (2) sum = sum + D(u) D(v) = sum 

The above will find for each node v number of "good paths" D(v) that will achieve this. All you have to do now is find the maximum value of x that the sum of node v , such that value(v) = x and D(v) > 0 and sum the number of paths reaching any node using value(v) :

 max = 0 numPaths = 0 for each node v: if value(v) == max: numPaths = numPaths + D(v) else if value(v) > max AND D(v) > 0: numPaths = D(v) max = value(v) return numPaths 

Notes: (1) - the “regular” view works here, but it will take the time O (n ^ 2logn), and the topological sort takes the time O (n ^ 2)
(2) Reminder, (u, v) is an edge if: (1) u and v are adjacent (2) value (u) + 1 = value (v)

Answer 2

You can do this with a simple search in width and width.

First find all the cells marked 0. (This is O (N ² ).) A walker is placed on each such cell. Each walker executes the number "p" initialized to 1.

Now iteration:

All walkers stand on cells with the same number k. Each walker searches for neighboring cells (left, right, up or down) marked k + 1.

If no walker sees such a cell, the search is complete. The length of the longest path is k, and the number of such paths is the sum p of all walkers.

If some walkers see such numbers, kill all walkers who do not.

Each walker moves to a good adjacent cell. If a walker sees more than one good cell, it is divided into as many walkers that there are good cells, and each one enters each. (Each “child” has the same p value that its “parent” has.) If two or more walkers meet in the same cell (i.e., if more than one path gets to this cell), they are combined into one walker whose p value is the sum of their p values.

This algorithm is O (N ² ), since no cell can be visited more than once, and the number of walkers cannot exceed the number of cells.

Answer 3

I did this with ActionScript, hope it will be readable. I think it works correctly, but I may have missed something.

 const N:int = 9; // field size const MIN_VALUE:int = 0; // start value var field:Array = []; // create field - not relevant to the task var probabilities:Array = [0,1,2,3,4,5]; for (var i:int = 0; i < N * N; i++) field.push(probabilities[int(Math.random() * probabilities.length)]);//RANGE)); print_field(); // initial chain fill. We will find any chains of adjacent 0-1 elements. var chain_list:Array = []; for (var offset:int = 0; offset < N * N - 1; offset++) { if (offset < N * N - N) { // y coordinate is not the lowest var chain:Array = find_chain(offset, offset + N, MIN_VALUE); if (chain) chain_list.push(chain); } if ((offset % N) < N - 1) { // x coordinate is not the rightmost chain = find_chain(offset, offset + 1, MIN_VALUE); if (chain) chain_list.push(chain); } } var merged_chain_list:Array = chain_list; var current_value:int = MIN_VALUE + 1; // for each found chain, scan its higher end for more attached chains // and merge them into new chain if found while(chain_list.length) { chain_list = []; for (i = 0; i < merged_chain_list.length; i++) { chain = merged_chain_list[i]; offset = chain[chain.length - 1]; if (offset < N * N - N) { var tmp:Array = find_chain(offset, offset + N, current_value); if (tmp) chain_list.push(merge_chains(chain, tmp)); } if (offset > N) { tmp = find_chain(offset, offset - N, current_value); if (tmp) chain_list.push(merge_chains(chain, tmp)); } if ((offset % N) < N - 1) { tmp = find_chain(offset, offset + 1, current_value); if (tmp) chain_list.push(merge_chains(chain, tmp)); } if (offset % N) { tmp = find_chain(offset, offset - 1, current_value); if (tmp) chain_list.push(merge_chains(chain, tmp)); } } //save the last merged result if any and try the next value if (chain_list.length) { merged_chain_list = chain_list; current_value++; } } // final merged list is a list of chains of a same maximum length print_chains(merged_chain_list); function find_chain(offset1, offset2, current_value):Array { // returns always sorted sorted from min to max var v1:int = field[offset1]; var v2:int = field[offset2]; if (v1 == current_value && v2 == current_value + 1) return [offset1, offset2]; if (v2 == current_value && v1 == current_value + 1) return [offset2, offset1]; return null; } function merge_chains(chain1:Array, chain2:Array):Array { var tmp:Array = []; for (var i:int = 0; i < chain1.length; i++) tmp.push(chain1[i]); tmp.push(chain2[1]); return tmp; } function print_field():void { for (var pos_y:int = 0; pos_y < N; pos_y++) { var offset:int = pos_y * N; var s:String = ""; for (var pos_x:int = 0; pos_x < N; pos_x++) { var v:int = field[offset++]; if (v == 0) s += "[0]"; else s += " " + v + " "; } trace(s); } } function print_chains(chain_list):void { var cl:int = chain_list.length; trace("\nchains found: " + cl); if (cl) trace("chain length: " + chain_list[0].length); for (var i:int = 0; i < cl; i++) { var chain:Array = chain_list[i]; var s:String = ""; for (var j:int = 0; j < chain.length; j++) s += chain[j] + ":" + field[chain[j]] + " "; trace(s); } } 

Output Example:

  1 2 1 3 2 2 3 2 4 4 3 1 2 2 2 [0][0] 1 [0][0] 1 2 4 [0] 3 3 1 [0][0] 5 4 1 1 [0][0] 1 2 2 3 4 3 2 [0] 1 5 4 [0] 3 [0] 3 1 4 3 1 1 2 2 3 5 3 3 3 2 3 4 2 1 2 4 4 4 5 4 2 1 2 2 3 4 5 [0] chains found: 2 chain length: 5 23:0 32:1 41:2 40:3 39:4 33:0 32:1 41:2 40:3 39:4 

Answer 4

I implemented it in my own Lisp dialect, so the source code will not help you with this :-) ...

EDIT: A version of Python has also been added.

anyway the idea is this:

• write the function paths(i, j) --> (maxlen, number) , which returns the maximum length of paths starting with (i, j) and how many of them are present.
• this function is recursive and looks at neighbors (i, j) with a value of M[i][j]+1 calls paths(ni, nj) to get the result for real neighbors
• if the maximum length for the neighbor is greater than the current maximum length, you set a new maximum maximum length and reset the counter
• if the maximum length matches the current, add a counter to the total
• If the maximum length is less, just ignore the result of the neighbor
• cache the calculation result for the cell (this is very important!). In my version, the code is divided into two mutually recursive functions: paths , which first checks the cache and calls compute-paths otherwise; compute-paths calls paths when processing neighbors. Caching a recursive call is roughly equivalent to an explicit approach to dynamic programming, but sometimes it is easier to implement.

To calculate the final result, you basically do the same calculations, but add the result for all 0 cells instead of looking at the neighbors.

Please note that the number of different paths can become huge, and therefore listing all of them is not a viable option, and / DP caching is mandatory: for example, for the matrix N=20 with values M[i][j] = i+j there 35 345 263 800 maximum length paths 38.

This algorithm is O (N ^ 2) in time (each cell is visited no more than once) and requires O (N ^ 2) space for cache and for recursion. Of course, you cannot expect to get anything better than this, given that the input consists of N ^ 2 digits, and you need to at least read them to calculate the answer.

 (defun good-paths (matrix) (let** ((N (length matrix)) (cache (make-array (list NN))) (#'compute-paths (ij) (let ((res (list 0 1)) (count (1+ (aref matrix ij)))) (dolist ((ii jj) (list (list (1+ i) j) (list (1- i) j) (list i (1+ j)) (list i (1- j)))) (when (and (< -1 ii N) (< -1 jj N) (= (aref matrix ii jj) count)) (let (((maxlen num) (paths ii jj))) (incf maxlen) (cond ((< (first res) maxlen) (setf res (list maxlen num))) ((= (first res) maxlen) (incf (second res) num)))))) res)) (#'paths (ij) (first (or (aref cache ij) (setf (aref cache ij) (list (compute-paths ij)))))) (res (list 0 0))) (dotimes (i N) (dotimes (j N) (when (= (aref matrix ij) 0) (let (((maxlen num) (paths ij))) (cond ((< (first res) maxlen) (setf res (list maxlen num))) ((= (first res) maxlen) (incf (second res) num))))))) res)) 

Edit

Below is the transliteration above in Python, it should be much easier to understand if you have never seen Lisp before ...

 def good_paths(matrix): N = len(matrix) cache = [[None]*N for i in xrange(N)] # an NxN matrix of None def compute_paths(i, j): maxlen, num = 0, 1 count = 1 + matrix[i][j] for (ii, jj) in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)): if 0 <= ii < N and 0 <= jj < N and matrix[ii][jj] == count: nh_maxlen, nh_num = paths(ii, jj) nh_maxlen += 1 if maxlen < nh_maxlen: maxlen = nh_maxlen num = nh_num elif maxlen == nh_maxlen: num += nh_num return maxlen, num def paths(i, j): res = cache[i][j] if res is None: res = cache[i][j] = compute_paths(i, j) return res maxlen, num = 0, 0 for i in xrange(N): for j in xrange(N): if matrix[i][j] == 0: c_maxlen, c_num = paths(i, j) if maxlen < c_maxlen: maxlen = c_maxlen num = c_num elif maxlen == c_maxlen: num += c_num return maxlen, num