# Code Golf: Number of paths!

## Challenge

Consider a square matrix of order N(N rows and N columns). At each step you can move one step to the right or one step to the top. How many possibilities are to reach (N,N) from (0,0)?

## Constraints

• Assume input will be a positive integer N satisfying 1 <= N <= 125
• No special characters, only 0-9
• Output should be in a separate line for ever test-case.

Sample test Cases:

Input:

32
99
111
98
101
69
23
56
125
115


Output:

1832624140942590534
22750883079422934966181954039568885395604168260154104734000
360523470416823805932455583900004318515997845619425384417969851840
5716592448890534420436582360196242777068052430850904489000
360401018730232861668242368169788454233176683658575855546640
23623985175715118288974865541854103729000
8233430727600
390590044887157789360330532465784
91208366928185711600087718663295946582847985411225264672245111235434562752
90678241309059123546891915017615620549691253503446529088945065877600


## Good luck!

The shorter an answer is, the better!

• Without invoking any moderator superpowers, I'd like to say that I don't much like this kind of questions. The answer can be worked out in full detail on pencil and paper, which means that there is minimum room for programming cleverness: the most concise mathematical notation will win. – dmckee Mar 8 '11 at 23:42
• With all respect I choose to differ from your opinion,to me mathematics is a integral part of programming,and does mathematical cleverness is not the part of golfing? Anyways,I can probably assure that you that this problem will need programming cleverness along with mathematics precisely for languages that don't support big-integer by default :-) – Quixotic Mar 9 '11 at 0:06
• For languages not supporting arbitrary-precision numbers I think this is pretty much impossible to compete. Of course, we know that not every task is doable in a short manner without bignums, but still, if that's the only source of need for programming cleverness ... well, that does not bode too well for the task, then :-) – Joey Mar 9 '11 at 2:20
• It's certainly possible to write your own bignum code into an answer, but I don't think I have ever seen anyone actually do that for a golf question yet. – gnibbler Mar 9 '11 at 2:33
• Almost a duplicate of codegolf.stackexchange.com/questions/1209/… - but that one requires division by 2^n as well. – Peter Taylor Mar 9 '11 at 15:41

## J, 8

(!+:)~x:

• x: forces arbitrary precision
• +: doubles its argument
• ! is the binomial
• a !+: b is the binomial of a out of 2*b
• (!+:)~ b is the binomial of b out of 2*b

PARI GP

binomial(2*n,n)


Mathematica

Binomial[2n, n]

• Does that work for the input? I.e. one test case per line. – Joey Mar 9 '11 at 12:38
• @Joey, Not particularly but i can't fix it right now. don't have access to eithor software. – st0le Mar 9 '11 at 13:15
• @StOle:I am not sure but you may like to experiment here. – Quixotic Mar 9 '11 at 14:11
• @debanjan, how would i test stdin and stdout at wolframalpha? can we? – st0le Mar 10 '11 at 4:45
• w..wh..WHAT IS WITH THAT SPACE?? – CalculatorFeline Mar 11 '16 at 14:43

## C# (203 chars)

using System;using i=System.Numerics.BigInteger;class X{static void Main(){Func<i,i>f=null;f=n=>n<2?1:n*f(n-1);try{i p=i.Parse(Console.In.ReadLine());Console.WriteLine(f(2*p)/f(p)/f(p));Main();}catch{}}}


using System;
using i = System.Numerics.BigInteger;
class X
{
static void Main()
{
Func<i, i> f = null;
f = n => n < 2 ? 1 : n * f(n - 1);
try
{
Console.WriteLine(f(2 * p) / f(p) / f(p));
Main();
}
catch { }
}
}


Tricks I used:

• Using try/catch instead of an explicit end condition for the main loop

• Calling Main() recursively is slightly shorter than for(;;){...} or x:...goto x;

• Why the try/catch? Only because Parse could throw? But this isn't Java and assuming sane input this won't ever happen, right? – Joey Mar 9 '11 at 12:40
• @Joey: It’s because Parse will throw when the end of the stream is reached and Console.In.ReadLine() returns null. That’s how the infinite loop ends. – Timwi Mar 9 '11 at 22:50
• Ah, sorry then, didn't consider that – Joey Mar 9 '11 at 22:56
• Blows the call stack on input 10^10^10^10 – CalculatorFeline Mar 11 '16 at 14:42

## Ruby, 48 characters

#!ruby -n
s=1;1.upto(l=\$_.to_i){|a|s+=s*l/a};p s


Python 67 57 Characters

while 1:s=i=1;n=input();exec"s=s*(n+i)/i;i+=1;"*n;print s


## DC -- 27 character

 ?d2*[d1-d1<F*]dsFxrlFxd*/pq


Invoke it like

echo 125 | dc -e '?d2*[d1-d1<F*]dsFxrlFxd*/pq'


or

echo 23 | dc -f


The bit in the brackets is a recursive factorial, ? reads the standard input, and the rest is stack management and operations.

## PARI/GP -- 11 bytes

(2*n)!/n!^2


## Golf-Basic 84, 37 characters

lA:1_S:1_IiN:(S*(N+I)/I:I++I)N_SdS


I can't test this right now, but I think that the the : and/or the multiplying of the result of I++I and an integer result from S*(N+I)/I will cause it to return ERR:UNDEFINED`