Find out how many possible (unique) paths you can take to get from the top left of a NxN grid to the bottom right.

The program will receive either 1 integer (or 2 for -20 points bonus) as input for the gridsize.
Input has to be anywhere in the range of 1..2000.
Output will be a string containing the number of possible paths in either decimal or hex format.


You can only move in 2 directions, right and down.


This example will show the possible paths in a 2x2 grid so you can see what correct paths are. Possible paths
I gave each line a different color, the output for a 2x2 grid will be 6.

This will be a big number

Indeed, it will be a big number, huge, enormous, gigantic or any other word you can come up with. Just to keep the fun in the challenge you are not allowed to use any plugins, libraries, native functions or any other thing I forgot to name that allows you to handle integers that would exceed an int64. So come up for a creative way to handle this.


As said before you cant use anything simular to BigInteger in C# for example.
Write an algorithm to solve this problem rather than a built-in function that would destroy the challenge.


This is codegolf so obviously the score is based on the length of your code.


  • Y U NO SQR() - The program accepts non square grids ex. [4,3], [100,20] etc. Reward: -20 points + invisible baby panda
  • Need for Speed! - The size of the grid will not result in a significant difference in the runtime where 1 second is considered significant. Reward: -20 points + Invisible bamboo for the baby panda (you dont want him to starve right?)
  • IT'S OVER NINE THOUSAANNNNDD - The program accepts gridsizes over 9000 Reward: -20 points + Invisible unicorn costume (baby panda size) Coz asians love cosplay


You can assume the following:

  • The input will never be a negative integer.
  • The input will always be >0 and never >2000.
  • You will always start at [0,0] and move to [N,N]

These baby pandas are sad and lonely, I cant take care of them all by myself so I need your help. Get on with it and claim your own baby panda while theyre still fresh ^.^ (instant delivery guaranteed.)

Happy coding :D

  • 9
    \$\begingroup\$ This is just computing choose(2*N,N), right? Or, for rectangular grids, choose(M+N,N) = (M+N)!/(M!*N!). Any language with the binomial function as a built-in will trivialize it, or even factorial, as long as it also handle big numbers. \$\endgroup\$
    – xnor
    Commented May 23, 2014 at 10:32
  • 1
    \$\begingroup\$ Banning built-in functions helps. Do you have to calculate the actual paths, or just their number? I can imagine lots of ways of computing binomials/factorial that have nothing to do with paths. Regarding integer types exceeding an int64 disallowed, I don't see how one would write a solution in a language like Python whose native integer type allows huge numbers. \$\endgroup\$
    – xnor
    Commented May 23, 2014 at 10:41
  • 2
    \$\begingroup\$ Hmm. For N=2000, the number will already have thousands of digits. The challenge here seems to be to build a giant calculator. Once you have that, solving the stated task should be relatively trivial. \$\endgroup\$ Commented May 23, 2014 at 11:17
  • 1
    \$\begingroup\$ To make it a little easier, can we output the answer in hex? It means we could work in binary (a string of int64's for example) and not have additional challenge of converting to decimal just to output, which is not very relevant to the stated problem. \$\endgroup\$ Commented May 23, 2014 at 11:24
  • 1
    \$\begingroup\$ code-golf should have clear output formats defined, VTC as too broad. \$\endgroup\$
    – user80551
    Commented May 23, 2014 at 13:26

4 Answers 4


GolfScript (62 - 40 = 22 points)


This program takes two inputs in the form w h from stdin and outputs the result to stdout. The largest intermediate value is w+h; although GolfScript has native big integers, this uses an array of single decimal digits for the calculations.

Bonuses claimed: non-square grids and grid sizes over 9000.

Online demo


# Stack: 'w h'
# Stack: w h
# Stack: [[1] [0] ... [0]] w+h  (where the array contains h [0]s)
# Loop w+h times:
    # Stack: nth row of Pascal's triangle. Put [0] on the stack underneath it.
    # Update to get the (n+1)th row.
        # Stack: [prev] [curr]
        # We need the 0 for the carry in
        # Stack: [curr] 0 [prev] [curr]
        # Group digits of prev and curr
        # Simple addition
            # Stack: [curr] carry-in [a b]
            # Although if the zip was of two arrays of different length,
            # it might just be [a] instead of [a b]
            # Stack: [curr] carry-out=(carry-in+a+b)/10 digit=(carry-in+a+b)%10
        # Stack: [curr] carry-out [sum]
        # We want to append the carry-out to the sum iff it's not 0
        # Stack: [curr] [sum]
    # Stack: ... [last of previous row] [next row]
# Stack: garbage [[1] ... [result in little-endian]]
# Stack: [result in big-endian]
  • \$\begingroup\$ How long does it take to run 9000x9000? I tried running 30x30 on the link you provided and it got aborted after 5 seconds without completing. \$\endgroup\$
    – MT0
    Commented May 28, 2014 at 17:52
  • \$\begingroup\$ Cool... Just wondering, can you do a factorial based algorithm and still beat me? (I will be golfing my C program hard this weekend.) \$\endgroup\$ Commented May 28, 2014 at 23:17
  • \$\begingroup\$ @MT0, more than 12 hours. \$\endgroup\$ Commented May 29, 2014 at 6:49
  • \$\begingroup\$ @steveverrill, under 100 chars, so less than 60 points with the bonuses. Does 800C400 in under 2 minutes with a highest intermediate value of 7915. \$\endgroup\$ Commented May 29, 2014 at 15:01

Javascript, 318 - 20 = 298

N=prompt(),Z=6e3,D=N*2,O=Array(D),W=Array(D);function p(n){while(n.length<Z)n="0"+n;return n}function a(a,b){r="",c=0,i=Z;while(i-->0){v=a[i]- -b[i]+c,r=(v%10)+r,c=~~(v/10)}return r}O[0]=p("1");for(x=1;x<=D;x++){for(y=0;y<=x;y++)if(x==1||y==0||y==x)W[y]=p("1");else W[y]=a(O[y-1],O[y]);O=W;W=Array(D)}console.log(O[N])

It's simple add only big number and pascal's triangle.

You can run this at your browser's console, but I don't recommend. You'd better run it from command line using Node.js. If you run this with Node.js, you need to modify N=prompt() to N=YOUR_NUMBER.

It took about an hour to calculate N=2000 using Node.js (with Z=2e3). I don't know how long will it take with Z=6e3.

Since 18000C9000 is less than 6000 decimal digits, this can calculate more than N=9000. And of course digit limit can be extended.

Output (N=2000, Z=2e3, 80 columns per row)

( 9 more zero rows)

JavaScript (ECMAScript 6 & Typed Arrays) - Score: 269 - 20 = 249

g=(a,b)=>b?g(b,a%b):a;f=x=>{for(r=[i=0];i<x;)r[i]=++i+x;for(i in r){k=+i+1;for(j in r){r[j]/=d=g(k,r[j]);k/=d}}return r.reduce((x,y)=>{y+='';z=Int8Array(x[l='length']+y[l]);for(a=x[l];a--;)for(b=y[l];b--;){d=z[p=a+b+1]+x[a]*y[b];z[p]=d%10;z[p-1]+=d/10|0}return z},'1')}


  • 269 Characters
  • Can handle large grid sizes (above 9,000) for bonus -20 points (and does the calculation for 10,000x10,000 grid in hundreds of seconds rather than in hours).


Run f(x) where x is the grid size.


A Typed Array (of Int8) where each array element contains a digit of the answer (or wrap the output in [...result].join('') to convert it to a string.)


Unlike the other answers, this does not rely on calculating Pascal's Triangle.

Instead it calculates C(n,k) = n!/(k!(n-k)!) and, for a n-by-n grid then the answer is C(2n,n) = (2n)!/(n!n!) however, (2n)!/n! can be simplified to the product of the numbers (n+1)...(2n) and then the division by n! can be done by cancelling common factors from those numbers before calculating the product.


is a function to calculate the greatest common divisor of two numbers.

  for(i in r){
    for(j in r){
  return r.reduce((x,y)=>{..},'1')

The first for-loop creates an array r of the numbers (x+1)...(2x). The second for-loop goes through the numbers 1...x and then (in the nested for-loop) finds common divisors with values in r and cancels them. The return value then reduces r and multiplies all the values together.

The function called by reduce is:

  return z

Which creates a Typed Array to store each digit of the number and then performs long multiplication to calculate the result.

ECMAScript 5 Version:

(Chrome Friendly and a few additional modifications for performance - such as preventing multiplication by 1)

function M(x,y){var r=new Uint8Array(x[l]+y[l]);for(a=x[l];a--;)for(b=y[l];b--;){d=r[p=a+b+1]+x[a]*y[b];r[p]=d%10;r[p-1]+=d/10|0}return r}
function g(a,b){return b?g(b,a%b):a;}
function f(x){for(r=[i=0];i<x;)r[i]=++i+x;for(i in r){k=+i+1;for(j in r){r[j]/=d=g(k,r[j]);k/=d}}return r.reduce(function(p,c){return c<2?p:M(p,c+'')},new Uint8Array([1]))}


20x20 Grid:

time=new Date();result=f(20);console.log("Time Taken: " + (new Date()-time)/1e3 + " seconds");[...result].join('').replace(/^0+/,'');
"Time Taken: 0.001 seconds"

10,000x10,000 Grid:

time=new Date();result=f(10000);console.log("Time Taken: " + (new Date()-time)/1e3 + " seconds");[...result].join('').replace(/^0+/,'');
"Time Taken: 219.353 seconds"

C, 201-20-20=161

Completely refactored since rev 0. Bonuses claimed: non-square and over 9000.

#define B i%w][j] 
char a[22000][5999];n,m,i,j,w=21669,c;main(){scanf("%d%d",&n,&m);


Calculating a number like 4000!/(2000!)^2 using multiplication and division seemed rather complicated to me. Instead I went for an approach based on iterating through the rows of Pascal's triangle, using only addition.

Here's an example using an int32 type, just to show the algorithm clearly:

int a[999],n,m,i,w=997;
  scanf("%d %d",&n,&m);

Where n+m is the number of rows of Pascal's triangle (counting the 1 at the top as row zero.) At the end of the program, a[] contains rows x and x-1 of Pascal's triangle, the even row in the even cells, and the odd row in the odd cells.

It's important that w is an odd number, so that on each pass through the array it alternates between writing to the odd and even cells. Also, it is important to ensure that the 1 used to initialise the array is not overwritten on the first pass. This requires that w/2 be even. I will explain this later.

This program will give the right answer, up to about n=m=16, after which the integer type overflows.

Ungolfed code

This works in the same way, but uses an array of char to store the decimal digits (in big endian format.) In order to minimise the code needed to print the answer, the calculations are performed using the ASCII values (add 48 to each value.)

Note that the value of w is enough to hold rows 9000 and 8999 the same time (a total of 9001+9000=18001 big numbers.) We actually get as far as row 18000 of Pascal's triangle, so by that stage there will not be enough space in the array to hold all 9001+9000 big numbers, and some wrapping around will occur. But this does not affect the central cell of row 9000, which is the only cell we are interested in.

Besides adding whitespace, I have explicitly spelt out the #define and ungolfed w/4 to the correct value of 5417. This value is chosen because 18000C9000 has 5417 digits.

char a[22000][5999];
  for(a[w/2][5417]=1;i<w*(n+m);i+=2)                       //Initialise array with a 1 in least significant bit of the middle cell of [a]. Loop through the numbers of each row of Pascal's triangle.
    for(j=5418;j--;a[1+i%w][j]-=c*10)                      //Loop through the digits of each number. The code to subtract 10 from the digit if carry flag `c` is executed after the following line.
      c=(a[1+i%w][j]=(a[i%w][j]+a[2+i%w][j]+c)%48+48)>57;  //Update the cell with a digit that is the sum of the ones to the left and right, taking into account the carry, and using mod 48 arithmetic in order to store the number as its ASCII code. The return value of the assigment to a[1+i%w][j] is compared with ASCII 57 (`9`) and if it is greater the carry flag `c` is set.


My first program took about an hour to print 4000C2000. This one can handle more digits and a higher number of rows to comply with the over 9000 rule. Consequently it takes about 15 hours to print 4000C2000 and would take several days to print 18000C9000.

For 2000x2000 it prints the following (formatted to 80 columns for clarity.) This can be verified to be correct here: http://www.wolframalpha.com/input/?i=4000C2000

First 50 rows of 80 zeros (total 4000) omitted

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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