A word of warning, don't read the rest of this if you want to work out the answer yourself!!!
My question number 1:
A robot is located at the top-left corner of a 65 x 61 grid (marked 'Start' in the diagram above)*.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the not to scale diagram below).
How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number.)
The problem here is the vast number of different routes that can be taken, which would overflow 32 bit computers for numbers this size. My (correct) answer was 1426507627253102510231886503468838531 which I calculated using the formula (x+y-2)! / ((x-1)! (y-1)!)
A few simple lines of Perl later and I had the answer:
#!/usr/bin/perl -w
use strict;
use Math::BigInt;
# change these to match your X & Y grid size
my $xgrid = 61;
my $ygrid = 65;
my $x = Math::BigInt->new($xgrid-1)->bfac();
my $y = Math::BigInt->new($ygrid-1)->bfac();
my $z = Math::BigInt->new($xgrid+$ygrid-2)->bfac();
print $z->bdiv($x->bmul($y))."\n";
No comments:
Post a Comment