Showing posts with label treasure hunt. Show all posts
Showing posts with label treasure hunt. Show all posts

Thursday 12 June 2008

Google Treasure Hunt Question 4

Question 4 has been out for a while now and it's taken me a while to blog the solution for a couple of reasons, I've not had much time to work out the solution recently, and this question seems a lot more difficult than the other three (for me at least).

Here's my question this time around:
Find the smallest number that can be expressed as
the sum of 25 consecutive prime numbers,
the sum of 99 consecutive prime numbers,
the sum of 189 consecutive prime numbers,
the sum of 467 consecutive prime numbers,
the sum of 535 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).


First of all I thought I'd write a routine (once again in Perl) to generate prime numbers. I know I'm not entering a competition to find the worlds largest primes so chose to write an optimised solution rather than a super efficient one. The difference here is computational complexity v coding complexity. I chose the simpler code but less efficient solution rather than the more complicated code but efficient solutions offered by algorithms such as the Sieve of Eratosthenes.

sub primes {
my $max = shift || 10;
my @primes = ( 2, 3, 5, 7 );
return @primes if ($max <= 9);
my $loop = 9;
while (scalar(@primes) < $max) {
my $is_prime = 1;
for (my $div = 3; $div < ($loop-1)/2; $div++) {
$is_prime = 0 if ($loop % $div == 0);
}
push (@primes,$loop) if ($is_prime);
$loop += 2;
}
return @primes;
}


Now I had a way of populating an array with prime numbers I thought about the solution a bit more carefully and decided it wasn't likely to be simple to calculate, however long the code I managed to write was. So, I decided to search around for lists of prime numbers and decided to use a list of the first million primes. I could, on reflection, just used my routine to generate 1 million primes and written them to a file instead of generating each time.

The solution I came up with is shown below. It starts by populating an array with the first million primes from the downloaded file. Then the sums of the required continuous number of primes are generated and stored in another array. At this early stage, the solution is now contained in this array (with the assumption the solution exists within the first one million primes of course) so it's just a case of searching the array to find it. In order to find the number, I numerically sort the list. Now it's a simple case of finding the first (and therefore lowest) prime in the new list that is repeated 5 times.

use strict;
use FileHandle;

sub sum_primes {
my $amount = shift;
my $start = 0;
my @sums;

while ($amount < scalar(@_)) {
my $sum = 0;
for (my $i = $start; $i < $amount; $i++) {
$sum += $_[$i];
}
push(@sums,$sum);
$start++;
$amount++;
}
return @sums;
}

sub read_primes {
my $filename = shift;
my $fh = new FileHandle;
$fh->open($filename) || die "$filename: $!\n";
my @primes;
push(@primes,split) while (<$fh>);
$fh->close();
return @primes;
}

sub is_prime {
my $num = shift;
foreach my $prime (@_) {
return 1 if ($num == $prime);
}
return 0;
}

my @primes = read_primes("1000000.txt");
my @sum_list;
push(@sum_list, sum_primes(25,@primes));
push(@sum_list, sum_primes(99,@primes));
push(@sum_list, sum_primes(189,@primes));
push(@sum_list, sum_primes(467,@primes));
push(@sum_list, sum_primes(535,@primes));
@sum_list = sort(@sum_list);
my $prev = 0;
my $same = 0;
foreach my $num (@sum_list) {
if ($num == $prev) {
$same++;
if ($same == 4) {
print "Found $num, checking... ";
if (is_prime($num,@primes)) {
print "PRIME! :-)\n";;
last;
} else {
print "not prime :-(\n";
$same = 0;
}
}
} else {
$same = 0;
}
$prev = $num;
}


This code takes a few minutes to run. I'm sure it's not the smartest solution to the problem, there must be some maths I can use to calculate a solution. Instead, this approach turns the problem into a search solution but it works pretty well and identified the correct answer of 6990493 for my question.

Friday 30 May 2008

Google Treasure Hunt Question 3

I've been keeping up with the Google treasure hunt as a bit of fun rather than seriously going after any prizes. At least one other guy at work has been joining me, Nick O'Leary has taken up the challenge too. Question 3 was recently released, and while I thought it might possibly present the greatest challenge yet on first inspection, it turned out to be really rather trivial.

So question 3 is all about IP routing, and tracing a packet route around the network. I was expecting some hardness built in around working out subnet masks, but there was none of that at all, just a simple route to follow resulting in an 11 node path. The question then:

Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host G with a destination of 201.89.136.112. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)



You are then shown a routing table and must trace your way through it from the start node to the end node recording the path taken along the way. This is a solution that is quickly manually traceable since no node should be visited twice (unless Google have given you some really badly designed network).

Having said about the simplicity of this one, I managed to get it wrong the first time around by starting at the wrong node. Reminds me of maths teachers constantly saying "Always Read the Question!". Once I screwed my head on the right way around I correctly answered GFIHDLOPABC for my network.

Tuesday 20 May 2008

Google Treasure Hunt Question 2

After solving question 1 successfully I decided to plod on and answer question 2 as well. It was, for me at least, far less challenging than the first question.

This time, you are generated a set of files with random directories and file names that you are asked to download and process. Once I got passed the immediate suspicion of downloading a zip file (for fear of viruses) it took no time at all to whip up a solution. My question was:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_15866755520722619948.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing BCD and ending in .pdf
Sum of line 5 for all files with path or name containing mno and ending in .rtf
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)


Again, my solution was Perl based and generated a correct answer of 364264342 for my particular zip file:
#!/usr/bin/perl -w
use strict;
use File::Find;
use FileHandle;
my $total1 = 0;
my $total2 = 0;
find(\&wanted, ("/home/gwhite/GoogleTreasureHunt08_15866755520722619948"));
print $total1*$total2."\n";
sub wanted {
return if (-d $File::Find::name);
if (($File::Find::name=~m!BCD!i) && ($File::Find::name=~m!\.pdf$!i)) {
my $fh = new FileHandle;
$fh->open($File::Find::name) || die ($File::Find::name." Oops: $!\n");
while (<$fh>) {
last if ($fh->input_line_number>4);
chomp($_);
$total1+=$_ if ($fh->input_line_number==4);
}
$fh->close();
}
elsif (($File::Find::name=~m!mno!i) && ($File::Find::name=~m!\.rtf$!i)) {
my $fh = new FileHandle;
$fh->open($File::Find::name) || die ($File::Find::name." Oops: $!\n");
while (<$fh>) {
last if ($fh->input_line_number>5);
chomp($_);
$total2+=$_ if ($fh->input_line_number==5);
}
$fh->close();
}
}

Monday 19 May 2008

Google Treasure Hunt

I've just discovered today (rather late I know) that Google have released a treasure hunt which is quite interesting. It's not what you might think. Given the name, I would have guessed it involved using the google search engine to find things on the Internet. However, it's actually a problem solving challenge where they pose questions and you submit your answer. I think question 2 is due out today (they obfuscate when the next question will be released), nobody seems to know how many questions there are, exactly how long this will go on for, etc. But there is a prize for "the first person to answer all the questions correctly" whatever that means.

A word of warning, don't read the rest of this if you want to work out the answer yourself!!!

My question number 1:
Google Treasure Hunt Q1
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";