Seems that the Google guys are getting softy. The last two questions of the Google Treasure Hunt 2008 were easily solved.
The Question #1 is about paths. We have a robot that can move down or right, in a n x m grid. So how many possible paths exists, from the top left to the top right?
It gets solved just searching in Google for “grid path right down” from there you will get the equation that you must run on any language that has Big Integer implementations, since involves the calculations factorial.
Example of our solution for the first puzzle in Java:
[code lang=”java”]
BigInteger dividend = factorial( (rows-1)+(columns-1) );
BigInteger divisor = factorial(rows-1).multiply(factorial(columns -1));
System.out.println(dividend.divide(divisor));
[/code]
The Question #2 seems to be even easier. It involves to transverse a directory tree, filtering the files that verifies 2 conditions based on the path string and the extension string (like .txt or .xml). Then reading some specific line. All files are text files this simplifies then things even more. Nothing hard to any programmer.
Snippet of our solution for the second puzzle in PHP:
[code lang=”php”]
// Setting where’s the Google Treasure Hunt Directory
$dirbase = ‘GoogleTreasureHunt08_11336769377172459175’;
// Creating and loading the directory Tree
$tree = new Mytree($dirbase);
$tree->load();
// Getting the leaf Files
$leafs = $tree->get_leafs();
// Filtering to files that satisfies the conditions
$cond1 = array_filter ($leafs, filter_bycond1);
$cond2 = array_filter ($leafs, filter_bycond2);
// Doing the sums at the right line number
$sum1 = array_reduce($cond1, create_function(‘$v, $node’,
‘$v = ($v == null) ? 0 : $v;’.
‘$v += (int)read_line($node->data, 5);’.
‘return $v;’));
$sum2 = array_reduce($cond2, create_function(‘$v, $node’,
‘$v = ($v == null) ? 0 : $v;’.
‘$v += (int)read_line($node->data, 5);’.
‘return $v;’));
echo $sum1, ‘
‘;
echo $sum2, ‘
‘;
// Obtaining result
echo $sum1 * $sum2;
[/code]
So as you see, there’s no complication at all. I would expect some challenge when Google uses the “Puzzle” word. Maybe they aren’t what they were? I don’t know, but I will be expecting some real challenge to solve :).
Robot solution: GTH Q1 Java solution
File transeversing solutino: GTH Q2 PHP solution