0
\$\begingroup\$

Objective

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.

Moving

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

Example

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.

Restrictions

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.

Scoring

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

Achievements

  • 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

Assumptions

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

\$\endgroup\$
  • 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 May 23 '14 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 May 23 '14 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\$ – Level River St May 23 '14 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\$ – Level River St May 23 '14 at 11:24
  • 1
    \$\begingroup\$ code-golf should have clear output formats defined, VTC as too broad. \$\endgroup\$ – user80551 May 23 '14 at 13:26
2
\$\begingroup\$

GolfScript (62 - 40 = 22 points)

~.),{!}%1/\@+{1,\{0@2$[\]zip{{+}/.10/\10%}%\[.](<+}%}*~]-1=-1%

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

Dissection

# Stack: 'w h'
~
# Stack: w h
.),{!}%1/\@+
# 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.
    1,\
    # Update to get the (n+1)th row.
    {
        # Stack: [prev] [curr]
        # We need the 0 for the carry in
        0@2$
        # Stack: [curr] 0 [prev] [curr]
        # Group digits of prev and curr
        [\]zip
        # 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]
            {+}/.10/\10%
            # 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]]
~]-1=-1%
# Stack: [result in big-endian]
|improve this answer|||||
\$\endgroup\$
  • \$\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 May 28 '14 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\$ – Level River St May 28 '14 at 23:17
  • \$\begingroup\$ @MT0, more than 12 hours. \$\endgroup\$ – Peter Taylor May 29 '14 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\$ – Peter Taylor May 29 '14 at 15:01
2
\$\begingroup\$

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)

0000000000000000000000000000000000000000000000000000000000000000000000000000000
( 9 more zero rows)
0000000166289787503383506953953682646038155801622559738864034512798427681344501
7509252934975119859380048360611740678717585164643246798390027541570435890783832
2828226892377078626044702804227263602256126747404152452060942681410793262364057
9569330167375801484191414608801079710165776274135023159100265188426666848338060
6949793134619965230289977433552832030768157074757286534981709857589026992861252
1344100050157521073022188690505729147513821887627918618839581616172143849923927
4840048169102967953586452459212832708643054316262086765263594646961335049751537
9265409756142767025376053045249340712557306410138509625397351647538695677912837
8613359541658838021140118989221026997673523121971126420597801576122121460038197
8745550595336070934606835960371170035071541788401648588967587345651743656288974
5430127914167663913908250964969081591944874685892721789931300479950258222066061
7063988223169179908327236982684836052004811138567928905241430746884887665722611
8060986563028228292375661960412817073779119546057911790152387847927530536412500
6054662568628218914552174948097277723212342938035400224911022983417537096691344
0248688425483608677217484634416362795730488526623314570505664794028764906794828
5761750402006009891416640
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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')}

Score:

  • 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).

Input:

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

Output:

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.)

Explanation:

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.

g=(a,b)=>b?g(b,a%b):a;

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

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)=>{..},'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:

(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
}

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)

l='length'
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]))}

Tests:

20x20 Grid:

time=new Date();result=f(20);console.log("Time Taken: " + (new Date()-time)/1e3 + " seconds");[...result].join('').replace(/^0+/,'');
"137846528820"
"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+/,'');
"2245602662746345541551569436157863147589736965779878243620710432072380220323594045444472025293862316422309263843389696601194422592336037980842489107531389451830672280612433657530040454017679073575902237192364811070856775330598231460644117219368118763325182774686432525080213090160115673919689862107981042354851670966818948676564830140501103187863794706664465811607040131101683992056451405543094155968811920452571949507557600467174912328072850455729969720191780701452688854257603611847037827605552582859834242788236262670736603455466219593151999063650749856823166968850527296485588202270430832568539209738210376363912068348046527593712676598114275057725448074762994389716714228014972717990665655542719818865743339454183615030835830305139616518492695118602146815860665223808633176268571726593283988824607425355592984356868896869862580500515357846009974598198321288825579426658640907413002967841476067160478290202983314513163463038280660407527182823870960838051855993812507051491908668019398012912369456365762315666169554994191335426644692433453363187237190602132828961650920658565301500509193119884570874258737247485829216385618342486447844947213196238030134524983054770474053585023793978892577387526457918946588268929907828682326196633699156234581816413904872488728507925854813450176908651564852721569388770569930287248915922924411545263754812143287478042214444621065481406479398080621318844029545454028585176013489301113823710181485620874382318281857386837919920701890894625108803933176722069336461781683541422121086991647087652147284822317663570743148764774033648397327468021594942679125884694968969332204828731441754249021429349656598535609471052108614801685829269989700832755501489020128710656014006836216197987756444549633039680607736312406212588175898069500611632946947799529169692574582589750518632839394752980774225093724027495379809484034977200321903596844462615734329067608432549413707940871319890469393844963571407457377334877216772454033389084142676285806902637797488763353473466066822809210584101235225998953947938915377769021982654883558206998963272164596600775488971680387367538122344557413818621662406496247109991804531795100517797167063996878642683327979264223567699891665615713611009526299462126796985207245788716655650426218579366699329579858511381654502622302912582882684792066014962942240394597348645270782509718832951466433891090978541336254143585462500263461684042839507789587811204279710254993942025892945601695170644887563291515368274374063520835068832131167187474842828579719937909391112117195041857108857239562691726726702643007507039362605394535637097327713764222415485620341381540767233167644132826791926024203040667329421530740193677551474654993017450782648333444090222674585630983008186652924657628834644834897637100207827867875420310837070750573815531470530524180034731724332101031672890345603628559285019986137841041116709652804803139426628377299615430216027399519026044679350067886217467263524591015020531907048463208063488528312685913072745794836545662380385834140814999378490244024780995338812025730352455529676770358659547650249804283900011838368646509317431580951157376905474629063271169833948707893813039282816616907678052493544703900215285385058457677307599020083956655910704396742375774315427582021313456558410563793441233057058025144411029757612203569710672080779165668828168521289596761787397325681625660653192977888670246261911216399243662205739370770046372354374220936363897457898780405624443924814889011338090769117051737746754985734497557778663312693365179886144225951173871128084844040449803500491929332734754368318302430214497217975692931298990258323804620757034918404560366163840841072441000320675514835079247880064047869015630380157609814514040932220403437718337488877890778238494014391690425601864031323957135120027555082477063150459930701650780285384453388336077377121055338628377146981137889198842340869632742053906028770557341060336878653800814974615546968662362273290989476934259302767216729596126488039964396176141919113223267501056191536248753818366731367312406692903437617638932267581962930857165345963136810734198213936668088356741553219693881162677230424784997861243775211675433579854032330836888751373327882252412206557991081886624898878359998751193051401516964683179243936067892262188825401327072308716202362911256788799329857627698277770687149426001821663875726694661244747631721052410085430890409928740622334089217756542895671262253123936763801115074889013481254745081915197784943512915677779444963105849446755664215506395836894772469910086237687105421745977376920570771626733504599223542966841236247102370534036819088880218308209024050311536655793658337998790762606714155868286812188839118472616299802565927495745940284528240254386499939523999520596277132212186095070411570106538259855769470982656707461210562571490326926210620803834148878482972089601133163571013947112083955529981253879737966165303683790341165560024646236523972553574840278821681074979776329411205810819665855189239707931962605270727950974426698058627244400515066278396902584162744568736105207412135656010689766040282572939680172149257044340704829719879721687608258149965462252245080442931266857021277237131024139647963633885493260096879685394128359963116428519583664694934576569475325699821465842386691254697532097771873987978047504413838158748068968892215862983676173540273874534862001307752100536588688292828705851757447949714769417190412694714297744044392104416757585732254330156026932813617502416565242653469786940326257618448770059989525168485762655624921898046438254580859341751007212586827631643328947659711146404946502903000689636285194875198320579698491636549172232925641059923504741712671910317948432372246260690133335427497606680877732273639896378143626395326414086145095099723387892407262889953543012714369821734100784766656809866900137709949860411313062712660264910291639389982314499434721495889186429885229838000591785792876272266149104236799504939344487686719027471999185870696168236802471361046889013725705989453050875284762549547494087189359500841418426659486453916640"
"Time Taken: 219.353 seconds"
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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);
for(a[w/2][w/4]=1;i<w*(n+m);i+=2)for(j=5418;j--;a[1+B-=c*10)c=(a[1+B=(a[B+a[2+B+c)%48+48)>57;
printf("%s",a[w/2+n-m]);}

Algorithm

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;
main(){
  scanf("%d %d",&n,&m);
  a[w/2]=1;
  for(i=0;i<w*(n+m);i+=2)a[i%w+1]=a[i%w]+a[i%w+2];
  printf("%d",a[w/2+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];
n,m,i,j,w=21669,c;
main(){
  scanf("%d%d",&n,&m);
  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.
  printf("%s",a[w/2+n-m]);
}

Output

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
00000000000000000000000000000000000000000000000000000000000000000000000000000000          
00000000000000000000000000000000000000000000000000000000000000000000000000000000          
00000000000000000000000000000000000000000000000000000001662897875033835069539536          
82646038155801622559738864034512798427681344501750925293497511985938004836061174          
06787175851646432467983900275415704358907838322828226892377078626044702804227263          
60225612674740415245206094268141079326236405795693301673758014841914146088010797          
10165776274135023159100265188426666848338060694979313461996523028997743355283203          
07681570747572865349817098575890269928612521344100050157521073022188690505729147          
51382188762791861883958161617214384992392748400481691029679535864524592128327086          
43054316262086765263594646961335049751537926540975614276702537605304524934071255          
73064101385096253973516475386956779128378613359541658838021140118989221026997673          
52312197112642059780157612212146003819787455505953360709346068359603711700350715          
41788401648588967587345651743656288974543012791416766391390825096496908159194487          
46858927217899313004799502582220660617063988223169179908327236982684836052004811          
13856792890524143074688488766572261180609865630282282923756619604128170737791195          
46057911790152387847927530536412500605466256862821891455217494809727772321234293          
80354002249110229834175370966913440248688425483608677217484634416362795730488526          
6233145705056647940287649067948285761750402006009891416640
|improve this answer|||||
\$\endgroup\$

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.