Friday, June 6, 2008

Google Treasure Hunt - Question 3 & 4

I grouped my solutions to questions 3 and 4 together for two reasons.
a) Life is short - I'm saving time.
b) Question 3 didn't involve me writing a program to solve it and there's not much to talk about anyway.

The competition can be found here:

Question 3
A packet is sent out from host H with a destination of Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)
They then provide you with a diagram and a routing table.

Personally I thought writing a program for this would be more labor than automation. So I pulled out the local handy spreadsheet application and pasted in the routing table. Then node by node, traced the path of the packet going through the network. My solution passed through 8 or 9 nodes to reach its destination. Waiting the 8 hours for my confirmation was more challenging than the question.

Question 4
Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 23 consecutive prime numbers,
the sum of 999 consecutive prime numbers,
the sum of 1489 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).
A funny story here: This question, if my calculations were correct, was released around 11:15pm GMT, around 01:15am in Durban ZA where I live. I couldn't wait for morning so I set my clock for 01:30am to specially get up and read the question. The funny thing about this is the next day someone said to me; 'I bet there are people that get up in the middle of the night to solve these things'. I just kept quiet.

Well I slept on it -literally- and made this Java app the next day.
To run:
java.exe GoogleQ4 40 1489 999 23 3

The first argument is the certainty factor for testing primes. The rest of the arguments are obviously the parameters from the question.
For the parameters quoted above my program gave the following output: (I haven't verified this result..)
9491851 -> computed in 141 seconds.
A further explanation of my logic:
Now I'm no mathematician so I'm not aware of any direct formula to solve this puppy; So I'll resort to a mechanism of over complicated logic. I visualized this problem as a set of 'Slide Rule Thing-a-ma-gigs' sliding over the prime number set.

The example in the image above doesn't balance but use it to visualize this process:
1) Drag the first slide to its next offset.
2) Calculate the slides new total. (All the numbers it hovers over)
3) Move to the next slide above it.
4) Drag this slide from an offset where the slides total will be smaller than the previous slides total, to somewhere where the slides total is greater. If a matching total is found then we can recurse to steps 3 and 4 for all our other slides.
5) When a similar total is found for all slides then we have our answer.

The method I have used requires a lot of array manipulation. I figure it makes sense to enter your arguments greatest to smallest as this will greatly reduce the amount of work the machine will have to do.

Other things that might help to speed up the slide rule machine:
- The use of vectors or linked lists (something not fixed array based) would probably help.
- A better algorithm to position the initial offset of each slide when recursing to that next slide. Originally I just started each slide from 2 everytime. gasp!. After a while I realized I was moving every slide 1000 odd positions before it was even close to solving the answer. Currently it starts the next slide where the previous left off.

Well thats all there is to my solution. Probably not the best, but I got the answer right first time. Whoopee.