Google Treasurehunt

You know about Google Treasure Hunt ?

As a programmer (java, C etc.) I've got amazing tools available in my working computer. This would be unfare, and not fun to go that fight using all those weapons.

That the reason why, I've decided to play this game, using nothing but my personal laptop (running ubuntu), and the net... and the skills I can't leave at the office.

Let's try it.

The first question is/was to get the number of path from the topleft point of a n,m grid to the bottomright. Beeing allowed to move right or down, only.

This is a so easy "mathematical" exercice, that I've made a mistake at the first time ;-)

First the math : one can code a single path like that ( rddrrrddr), where 'r' represent 'right' and 'd' 'down'.

1. First, notice that, as the grid is n width, there is N-1 'r' (on a 2-width grid there is only one step right to do) (this was my silly mistake, ugly trees).It's the same for the height.
   
2. second notice that the whole path is always (n-1)+(m-1) moves length.
   

Well, sorry for non math aware readers, but the number of such path is well known to be the number of combinations. i.e (n-1) choose (n-1+m-1). (means that you choose where to put the 'r' somewhere in the whole path, all others moves are 'd'.

Haha, got you, google, too easy !

Mine was a 60x35 grid so there was 34 'r' to choose among (60+35-2)=93

let's try it on google calc : 93 choose 34 , and ... damit :

93 choose 34 = 2.82526868 × 10²⁵

but they wanted an exact integer.... Come on, google, next time try to provide a game that does not defeat your own tools!

well, let's think a little : the number is huge but not so much,I need what we call biginteger in Java, or arbitrary precision arithmetic. A glance at google results, a fast jump to GNU related tools, and here I'am, at gmplib :

there is an online tool, too cool. But they do not have the choose function. It doesn't matter, this is a nuclear weapon to kill an ant : choose function (as given in wikipedia) gives
(59+34)!/(59!*34!) :28252686811008134325892860

nice shot ! got the right answer.

And what about you ?