1
$\begingroup$

I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.

I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.

The algorithm I wrote is a bottom-up one, as follows:

JUMP(x, y)
1.  M[x-1,y+1] ← 1 
2.  for i=0 to x+1
        M[i,y+1] ← 0
3.  for i=0 to y+1
        M[x+1,i] ← 0
4.  for j=0 to y-1
        for i=j+1 to x
            M[i,j] ← 0

5.  for j=y to 0
        for i=j to 0
            M[i,j] ← M[i+1,j] + M[i,j+1]

6.  return M[i,j]

Please advise on this.

$\endgroup$
  • 1
    $\begingroup$ Printing all paths is often a bad idea (w.r.t. resources) but here's a hint: after filling the table, retrace the steps you've taken. $\endgroup$ – Raphael Jan 14 '15 at 17:40
  • $\begingroup$ The number of paths is given by the Catalan numbers. $\endgroup$ – Yuval Filmus Jan 14 '15 at 20:58
  • $\begingroup$ @YuvalFilmus I know how to get the number of paths (both via a top-down approach as well as a bottom-up one), and that's covered pretty nicely online. The problem is when trying to print out all the paths that get you from point A to point B, which I can't seem to be able to wrap my head around on. $\endgroup$ – The_Ben Jan 14 '15 at 22:57
  • $\begingroup$ @Raphael Retracing one paths back is pretty simple as well, as you can just save a general pi array of size n*n and trace your way "back" from (n,n) to (0,0) using it. However, printing all the paths from (0,0) to (n,n) is the hard part here. $\endgroup$ – The_Ben Jan 14 '15 at 22:59
  • 1
    $\begingroup$ @The_Ben The technique for printing one path can be extended to print all paths. Note that using DP for this task is unnecessary; its power lies in not examining all solutions. Just do DFS with backtracking or something similar. $\endgroup$ – Raphael Jan 15 '15 at 8:01
5
$\begingroup$

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call.

$f(i,j) = \begin{cases} \emptyset & if\ \ {i>j}\\ \emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\ \{(n,n)\} & if \ \ i = n \wedge j = n\\ \bigcup_{p\,\in\, f(i+1,j)\,\cup\,f(i,j+1) } \ \ \{(i,j)\}\cup p & \text{otherwise} \end{cases}$

By example, two of all paths from $f(0,0)$ when $n=4$ are:

blue path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}}

red path = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4, 4}}

enter image description here

So, although programming is not in the scope of this site, I think is good to see a implementation for a memoization version of the above algorithm. asdf

from functools import wraps

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def f(i, j):
    global n
    if i > j:
        return []
    if not (0 <= i <= n and 0 <= j <= n):
        return []
    if i == n and j == n:
        return [[(n,n)]]
    alls = []
    for path in f(i, j+1)+f(i+1, j):
        if len(path) > 0:
            alls += [[(i,j)] + path] 
    return alls

n = 4
for path in f(0,0):
    print path
$\endgroup$
  • $\begingroup$ Thank you very much. This seems to be a good solution, but what is the time complexity of it? Isn't it O(2^(n*n))? Seems a bit high when doing this recursively. Also, do you know of any bottom-up approach to solve this (rather than top-down like you did above, with memoization). $\endgroup$ – The_Ben Jan 14 '15 at 22:54
  • $\begingroup$ You seem to be right about complexity, btw generate all paths is usually expensive for graphs, like in this case, your lattice. And, for a bottom-up approach, may be you can do a Breath First Search in the lattice asserting all conditions about monotonic paths. $\endgroup$ – jonaprieto Jan 14 '15 at 23:12
0
$\begingroup$

In the case of an $x$ by $y$ grid (assuming we start at the bottom-left and travel toward the upper-right), you can notice that every possible path will always contain $x$ steps toward the right and $y$ steps upward. You could encode every possible path with a binary string of length $x+y$ where $0$ encodes "right" and $1$ encodes "up", and there are exactly $x$ $0$'s and exactly $y$ $1$'s in the string.

To solve the problem, you could follow this procedure:

  • take a binary string of length $x+y$, starting with all $0$'s
  • check if the string has $y$ bits equal to $1$
  • if so, print the path the string represents, with $0$ = "right" and $1$ = "up"
  • incrememt the binary string by $1$ and repeat


In pseudocode:

x = 7; //the grid is x by y in size
y = 9; 
N = x+y; //length of the binary string

for i from 0 to (2^N)-1:
  if NumberOfOnes(i,N) == y:
    PrintPath(i,N);      

To check if the least-significant bit is a 1, we can just take i mod 2 and check if the result is a 1. We can check bit j in the same way just by bit-shifting j bits to to the right and repeating the processes.

function NumberOfOnes(i,N)
  ones = 0;
  zeroes = 0;
  bit = 0;
  for j from N-1 to 0
    temp = i >> j;     //ensures we read the string from left-to-right
    if (temp mod 2) == 1
     ones++
    else
     zeros++
    if zeros > ones  // this protects us from moving below the diagonal
     ones = -1;
     break;
  return ones

To print the string we use a similar process to find the 1's and let 0 mean "right" and 1 mean "up". We also need to read the string left-to-right.

function PrintPath(i,N)
  path_string = [empty]
  for j from N-1 to 0
    temp = i >> j          //ensures we read the string left-to-right
    if (temp mod 2) == 1
      path_string += 'up, '
    else
      path_string += 'right, '

  print(path_string)

This involves checking $2^{x+y}$ binary numbers and performing $x+y$ bit-shifts on each one.

Also for counting the paths, you can notice that the number of acceptable binary strings is just ${x + y \choose y}/2$ since we have $x+y$ binary digits and need to choose $y$ of them to be $1$, and divide by $2$ to ignore paths below the diagonal.

$\endgroup$
  • $\begingroup$ For $x=y=3$ this will print (simplifying a bit) URRURU, but that wouldn't be allowed, since the OP stated that no paths can be below the main diagonal. $\endgroup$ – Rick Decker Jan 15 '15 at 19:48
  • $\begingroup$ @RickDecker--good point. I added some extra code NumberOfOnes() to ignore these cases and some code in PrintPath() to read the string in the proper direction. $\endgroup$ – eigenchris Jan 15 '15 at 19:51
  • $\begingroup$ @eigenchris This seems like it would work, but kind of "runs around the whole idea", doesn't it? I mean, you're solving an equivalent problem, but not the same problem. I need to use dynamic programming here, which your suggested solution isn't written by (this is an interview question). $\endgroup$ – The_Ben Jan 16 '15 at 18:57
  • $\begingroup$ @The_Ben I didn't realize you were constrained to use dynamic programming. It's true that my solution is very specific to this problem and doesn't follow any sort of general bottom-up or top-down approach you would use to tackle algorithm problems in general, so it's not very instructional in that sense. However my solution has $O(2^{2n})$ complexity so I thought it would be worth mentioning. $\endgroup$ – eigenchris Jan 16 '15 at 19:32
  • $\begingroup$ @The_Ben As Raphael has pointed out, DP represents a scheme to intelligently reuse interim results in an optimization setting. There is nothing to optimize here as you are requested - in sloppy phrasing - to enumerate the complete search space. So you might have been asked a trick question. $\endgroup$ – collapsar Jan 16 '15 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.