CODEWITHSUNDEEP
pythonalgorithmoptimization
Manuel Leduc
Manuel Leduc

Reputation: 1919

Finding a number of unique paths from one corner of the board to the other without backtracking

I am stuck with a algorithm optimization.

The goal is to find how many different ways your can use to go from a point A to a point B in a chess board where :

Here is a dummy solution :

# -*- conding: utf-8 -*-
import time

def solution(n, m, x, y):
   ret = 0
   if x < n-1:
      ret += solution(n, m, x+1, y)
   if y < m-1:
      ret += solution(n, m, x, y+1)
   if x == n-1 and  y == m-1:
     ret = 1
   return ret

def wrapper(n, m):
    start = time.time()
    reponse = solution(n, m, 0, 0)
    stop = time.time()
    print "Response: %dx%d = %d\nTime : %f\n" % (n, m, reponse, stop-start)



if __name__ == "__main__":
    for i in range(10):
        wrapper(i+1,i+1)
    #wrapper(7,7)
    #wrapper(10,10)
    #wrapper(100,100)
    #wrapper(1000,1000)
    #wrapper(10000,10000) <- way too slow

While I stay with small chess boards, it works fine and results are relevant. But my goal is to find a solution for a 10000x10000 board.

Does anyboy have an idea ?

Upvotes: 0

Views: 2712

Answers (4)

Alexander
Alexander

Reputation: 23537

Dynamic Programming: O(N)

It has already mentioned that the problem has a solution by using a Triangle of Pascal, and its relation to the Binomial coefficient. Also the Catalan number's entry has a nice illustration for the n × n case.

n × n case

By making use of the aforementioned resources you can conclude that for a grid of size n × n you need to calculate C(2n - 2, n - 1). You can double-check it by rotating the grid by 45 degrees and mapping the Pascal's Triangle.

In practical terms, calculating this number directly requires to calculate, in a naive way, at most 3 different factorials which is a very expensive task. If you can pre-calculate them all then there's no discussion here and you can argue this problem has complexity O(1). If you are not interested in the pre-calculated way then you can continue reading.

You can calculate such ominous number using Dynamic Programming (DP). The trick here is to perform the operation in smaller steps which won't require you to calculate a large factorial number at all.

That is, to calculate C(n, k), you can start by placing yourself at C(n, 1) and walk to C(n, k). Let's start by defining C(n, k) in terms of C(n, k - 1).

C(n, k) = n! / k! * ( n - k )!                            ; k! = (k - 1)! * k
        = n! / (k - 1)! * k * (n - k)!                    ; (n - k)! = (n - k + 1)! / (n - k + 1)
        = n! * (n - k + 1) / (k - 1)! * k * (n - k + 1)!  ; C(n, k - 1) = n! / (k - 1)! * ( n - k + 1 )!
        = C(n, k - 1) * (n - k + 1) / k

Based on this, you can define a function to calculate C(n, k) as follows in Python:

def C(n, k):
    """
    Calculate C(n, k) using Dynamic Programming.
    C(n, k) = C(n, k - 1) * (n - k + 1) / k
    """
    C = 1
    for ki in range(1, k + 1):
        C = C * (n - ki + 1) / ki
    return C

It runs in linear time, O(N).

For the n × n case you need to calculate C(2n - 2, n - 1).

>> print "Response: %dx%d = %d" % (n, n, C(2 * n - 2, n - 1),)
Response: 10000x10000 = 5...

n × m case

For the general n × m case, you just need to calculate C(n + m - 2, m - 1).

>> print "Response: %dx%d = %d" % (n, m, C(n + m - 2, m - 1),)
Response: 10000x10000 = 5...

Last but not least, you can see a live example at Ideone here.

Timings

I ran the algorithm for the following grid sizes.

      N x N      | Response's Length |   Time
-----------------+-------------------+-----------
      1 x 1      |           1 chars |  0.000001
     10 x 10     |           5 chars |  0.000004
    100 x 100    |          59 chars |  0.000068
   1000 x 1000   |         600 chars |  0.002207
  10000 x 10000  |        6018 chars |  0.163647
 100000 x 100000 |       60203 chars | 40.853971

It seems the operations above a grid size of 100 000 x 100 000 get absurdly expensive due to the very large numbers involved. Nothing to be surprised though.

Upvotes: 2

John La Rooy
John La Rooy

Reputation: 304463

You are looking for Pascal's triangle. The wikipedia link even mentions your exact problem

Upvotes: 0

angelatlarge
angelatlarge

Reputation: 4150

You do not need an algorithm for this. Just math. Here's something to think about: when you are on the top-right square, you don't have any different options. Let's count that as zero. When you are just to the right of the top-right corner, your only choice is to go right (one option), since you are not allowed to backtrack. When you are just below the top-right corner, your only choice is to go up. Let's map that out

... 1 0
..... 1

What about the corner to the left/down from the target corner. From there, there are two paths to the corner (sum of the options to get to the neighbours): you can go up to right:

... 1 0
....2 1

Expanding the edges we expand always with ones: once you are at the top, there is only one way to get to the top-right:

...1 1 1 0
...... 2 1
........ 1
........=1

But each non-edge choice is a sum of the numbers in the north and east neighbours:

...1 1 1 0
.....3 2 1
.......3 1
........ 1

And so on. Hopefully this gets you started on a solution.

There is also different way of thinking about this. Given an NxN board, you have to make 2N moves to get from one corner to the other. N of these moves are north moves and N are east. The question is: how many different combinations of N east moves and N north moves can there be in a 2N-long string.

Upvotes: 1

Bartlomiej Lewandowski
Bartlomiej Lewandowski

Reputation: 11190

Think of it this way: since your points A and B are at the same place, you have to move the same amount of UPs and RIGHTs, but the the order will be different. So you need to find the amount of different combinations.

Upvotes: 4

Related Questions