CODEWITHSUNDEEP
python
user3685412
user3685412

Reputation: 4547

Code to find number of route-combinations in a N by N grid

I have to write a code that has to count the number of different combinations where I start from the upper left of a N by N grid, and end in the lower right corner. But I can only go down and right!

So basically (if we give each of the vertices a number from 1 - (N+1)^2), how many different combinations are there from 1 - (N+1)^2. But I can only add 1 or add N+1.

An example: 2x2 Grid:

1 -- 2 -- 3
|    |    |
4 -- 5 -- 6
|    |    |
7 -- 8 -- 9

And the combinations would be:

[1-2-3-6-9]
[1-2-5-6-9]
[1-2-5-8-9]
[1-4-5-6-9]
[1-4-5-8-9]
[1-4-7-8-9]

Now, how should I write this code? Any help would be greatly appreciated!
Thanks in advance

Upvotes: 0

Views: 1079

Answers (1)

Zahand
Zahand

Reputation: 488

Ah. I see you are trying on one of the EulerProject problems? The point is to manage to figure it out yourself and learn new things along the way! You are only tricking yourself by cheating. Oh well

Anyways, consider a grid of m rows and n columns (we do not need to assume that the grid is square). Counting from the upper-left and starting at zero, denote the intersection/node in the i-th row and j-th column by N_(i,j).

Thus, the upper-left node is N_(0,0), the bottom-left is N_(m,0) and the bottom-right is N_(m,n). Clearly, the number of paths from N_(0,0) to any node along the far right or far top of the grid is only 1 (since we may only proceed down or right).

Now, consider how many paths there are to N_(1,1). We must first travel through N_(0,1) or N_(1,0). This yields only two paths to N_(1,1). We can continue this process. In order to determine the total number of paths to any node N_(i,j), we only need to sum together the total number of paths to N_(i,j−1) and N_(i−1,j). The process is understood graphically in the following diagram, where each new integer represents the number of paths to a node.

enter image description here

If we code this in python we get:

def route_num(cube_size):
    L = [1] * cube_size
    for i in range(cube_size):
        for j in range(i):
            L[j] = L[j]+L[j-1]
        L[i] = 2 * L[i - 1]
    return L[cube_size - 1]

print route_num(20) would give us 137846528820.

Source: http://code.jasonbhill.com/

Upvotes: 1

Related Questions