Google Treasure Hunt
Every once in a while, I search online to see if anyone is doing Perl Golf anymore. While looking around, I found some people discussing a new competition that Google is sponsering called the Google Treasure Hunt. There are four questions, one per week, and the first person to answer them all, wins a prize. Now, I’m by no means a great programmer, but I thought I’d give the questions a try.
The first question I tried, which was the current one, showed a picture of a dozen interconnected network devices and listed the routing tables of the devices. I was asked to find the path of a packet sent from a certain host to an IP address. I didn’t even need to write any software to do that. Five minutes later I had the correct solution. “Cool! I guess I’ll try one of the older problems” I thought to myself.
The next problem also went pretty quickly. I was asked to download a zip file which contained a bunch of files in a number of folders. I was asked to add the number on the fourth line of any .pdf file that had ‘aaa’ in its file name or path, then add the number on the second line of any .js file with xyz in its filename or path, then multiply these two numbers. Another easy one.
# for i in `find | grep aaa.*\.pdf`; do head -n4 $i | tail -n1; done | perl -ne '$sum += $_; END{print $sum.$/}'
# for i in `find | grep xyz.*\.js`; do head -n2 $i | tail -n1; done | perl -ne '$sum += $_; END{print $sum.$/}'
I decided to challenge myself with the third problem. It was a recursive problem, so I figured I’d learn haskell to tackle it. I got it to work, but it would take many hours to find the answer.
module Main where
rob 1 _ = 1
rob _ 1 = 1
rob n m =
if n == m then 2 * (rob n (n-1))
else (rob (n-1) m) + (rob n (m-1))
main = print $ rob 52 51
In the end I used perl and got the answer in a minute or so.
#!/usr/bin/perl
use bigint;
my @cache;
sub calc
{
my $m = shift;
my $n = shift;
($n, $m) = ($m, $n) if ($m < $n);
return $m if ($n == 2);
my $r = $cache[$m][$n];
return $r if ($r);
if ($m == $n) {
$cache[$m][$n] = 2 * calc($m, $n-1);
}
else {
$cache[$m][$n] = calc($m-1, $n) + calc($m, $n-1);
}
return $cache[$m][$n];
}
print calc (52, 51). $/
The fourth question came out early this morning, and is much tougher.
Question:
Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 43 consecutive prime numbers,
the sum of 399 consecutive prime numbers,
the sum of 999 consecutive prime numbers,
and is itself a prime number.For example, 41 is the smallest prime number that can be expressed as
the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).
It’s another one that haskell should be really good at, but I don’t know enough of it. I could use perl, but I’d have to brute-force it. I guess I finally met my match.