google-au.blogspot.com/2...easure-hunt.html

Thought we'd have a group effort :)

treasurehunt.appspot.com

Run the string through: www5.rptea.com/base64/base64.aspx

Welcome to the Treasure Hunt!

The contest is not open, please check back later.

Sounds like fun. It will be good to be involved from the very beginning. :)
Any idea what "1210550400" means?

1210550400 equates to May 12 at 12.

MiCCAS.net writes...

1210550400 equates to May 12 at 12.

midnight, i.e. 12am, just to clarify

MiCCAS.net writes...

1210550400 equates to May 12 at 12.

How did you figure that out? And how does 1210550400 equate to May 12th at 12?

C0RE 2 DU0 writes...

How did you figure that out?

dictionary.reference.com/search?q=epoch

www.esqsoft.com/javascri...ate-to-epoch.htm
says that 1210550400 = Mon May 12 2008 10:00:00 GMT+1000 (AUS Eastern Standard Time)

So I assume you mean by 12, that would be 00:00 GMT?

www.unixtimestamp.com/index.php

DATE: 05 / 11 / 08 @ 8:00pm

Obviously American date format so its 11/5/08.

11/5/08 would make sense but this is a Google Australia hunt. Perhaps there is another answer? A breakthrough (or time) will tell.
EDIT: Scrap that, three days is a perfectly normal time to wait, I'm just impatient.

Congratulations on solving the first clue!

Shiver me timbers - the contest's not open yet! Have you
solved the second clue from our blog post already?
Here is the second clue: 1210550400

While you're waiting, why not read about what's been happening at our Sydney office?

Great to see everyones trying and got further then me, I figured out the timestamp but just not the top one.

45 Minutes left. Are we feeling a group effort via IRC or stick with forums?

Zubby writes...

45 Minutes left. Are we feeling a group effort via IRC or stick with forums?

I think it is actually under 2 hours left.. but not as soon as 45 minutes.

While I may be wrong, I think we missed the timezone difference guys. With that added I get Monday, May 12th 2008, 10:00:00 (GMT +10). False start

Zubby writes...

False start

Damn, tomorrow at 10pm it is then lol

MiCCAS.net writes...

Damn, tomorrow at 10pm it is then lol

are you serious?
unixtime is based on seconds from 1Jan1970UTC/GMT so that makes it 10am start AEST.

LOL I was right, just started folks

NMan, technically I was right first ;)

Also looks like puzzles are shuffled and we may not get overlapping puzzles to share! Mine relates to robot movement on a grid.

Update: puzzles appear to be the same with different variables. We just need to work out the method of calculating paths.

Question

A robot is located at the top-left corner of a 55 x 35 grid (marked 'Start' in the diagram below)*.

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 diagram below)*.

img127.imageshack.us/img...robotmazeea7.png
*Image not to scale.

How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number.)

maths.. horrible, it's been years since i've done stuff like this. my grid was 66x53. I would've lost a bunch of sig figures off the back; 192 dec places for 1/2 of my equation. I hope I remembered how to do it properly.

I suspect that everyone got a differently sized grid, but the same picture. Google calculator might come in handy during treasure hunt.

Hacked up an answer in VB of all things. Quite fun.

Zubby writes...

Hacked up an answer in VB of all things. Quite fun.

I put something together in C#, but had to use a BigNumber class to avoid all sorts of overflows... The grid I had was 35x35.

Adrian writes...

The grid I had was 35x35.

Mines 42 x 51 and hence still running! Used a long so hopefully nothing will drop. I really should have used perl but VB was already open.

I think I have the formula for it, less than a second calculation in Excel. If you want to confirm your answer I'm happy to help. :)

Wally Wallitron writes...

If you want to confirm your answer I'm happy to help. :)

Same here - just whim me a grid size, and the answer, and I'll see if I get the same answer...

I give up. ;-)

Here is the video it gives you:

www.youtube.com/watch?v=ZxZOpNUN3Ww

Life at Google Sydney

Google's Sydney, Australia office opened 3 years ago as a two-person sales team to help sell AdWords in the local marketplace. It expanded. The original Google Maps team set up shop alongside. The sales staff grew. Marketing and on-line support joined in. Today, the Sydney office, set in a spectacular location with harbour and city views, houses Sales, Support, Systems Operations, Engineering, and more. It is the base for Google's activities in Australia and New Zealand and helps support the whole Asia-Pacific region.

We work hard but we make time to relax, too. Lunches are catered daily, there are free snacks and drinks, massage is available on-site, and there's a pool table overlooking the city skyline. The environment is both productive and fun. Google Sydney has become one of the most sought-after job placements in the market. For a firsthand account, meet one of our Sydney Googlers.

We're always looking for great engineers, so if you're interested, we'd love to hear from you - feel free to send your resume to treasurehunt08@google.com.

MiCCAS.net writes...

Here is the video it gives you:

www.youtube.com/watch?v=ZxZOpNUN3Ww

Alright, now I'm jealous.

Clamburger writes...

Alright, now I'm jealous.

Aren't we all - but I doubt they'd employ under 18s :P

Anyone's script finished running for puzzle 1 yet?

Damn, I'm running a recursive function in C++, and it's already taking > 5 minutes. My grid size is 50 x 34 by the way. I suspect this is going to be a huge number.

A 15 x 20 grid already took a minute to calculate with the result of 818,809,200. I just can't imagine 50x34!

fizzy writes...

Anyone's script finished running for puzzle 1 yet?

I have two copies running, one perl and one VB on different machines and it has been running for almost three hours! I believe other members have worked on the problem using a mathematical approach.

Edit: Note my grid is 42x51

Zubby writes...

one perl and one VB

LOL.. good luck with those. :P

I believe other members have worked on the problem using a mathematical approach.

Hmmm.. too bad my maths ain't that good. :S

One you have the algorithm, not much crunching is required. In perl it can be solved in less than 1 second.

Wally Wallitron writes...

One you have the algorithm, not much crunching is required. In perl it can be solved in less than 1 second.

Ok, then let's compare answers. WHat do you get for a grid size of 16x16?

I get 155,117,520 for a 16*16 grid in about a second using an equation (and Google calculator).

sonome writes...

I get 155,117,520 for a 16*16 grid in about a second using an equation (and Google calculator).

Yup, someone already whimmed me where this spreadsheet is available. ;)

fizzy writes...

Anyone's script finished running for puzzle 1 yet?

Yep - I've done about 30 calculations on various grid sizes. I started with a recursive algorithm, but it was taking so long, I found a shortcut.

It seems to work fine.

A 15 x 20 grid already took a minute to calculate with the result of 818,809,200

I agree with this.

fizzy writes...

Yup, someone already whimmed me where this spreadsheet is available. ;)

Does the spreadsheet work with larger grids?
I ran out of memory using 64 bit numbers when I got up towards 20x30 grids.

Zubby writes...

I have two copies running, one perl and one VB on different machines and it has been running for almost three hours!

With a 42x51 grid, you're going to be waiting for a LONG time for an exhaustive search to complete.

For those who are theoretically-minded, this problem is going to be solved in O(n!) time... that is, depending on the 'size' of the problem -- in this case, the size of your grid -- the time taken to brute-force an answer increases... massively. With O(n!) time, when a problem of size 1 takes 1 unit (say, 1ms), a problem of size 2 takes 2x1 = 2ms to solve; size 3 = 3x2x1 = 6ms; size 4, 4x3x2x1 = 24ms, etc.

Your calculation is going to execute something like 90! times, which is 90x89x88x87....x3x2x1 = a LOT. Even if the execution time is 1 microsecond, you'll be waiting.... a long time. Like, trillions of trillions of trillions of time the age of the universe long time.

Don't wait up. :)

No need to code all the possibilities. Here's the formula

result = 2xy + x + y
where x = width - 1 and y = height - 1

tim writes...

No need to code all the possibilities. Here's the formula

result = 2xy + x + y
where x = width - 1 and y = height - 1

With a 3x3 grid, the possibilities are:

DDRR
DRDR
DRRD
RDDR
RDRD
RRDD

That's 6; according to your formula, it's 2x2x2 + 2 + 2 = 12.

Something's not right. :)

That works for 7x3, but not for 2x2 (answer 2, not 4) or 3x3 (answer 6, not 12).

Adrian writes...

Does the spreadsheet work with larger grids?

You basically don't need a spreadsheet. It's just an interesting algorithm that works on any dimensions. :)

If anyone wants the code, whim me and I'll gladly provide you with mine in c++. :)

The formula for this problem is as follows:

(x+y)!/(x!*y!)

x=number of columns in the grid minus 1
y=number of rows in the grid - 1

eg for a grid 16*15 x=15 y=14

so you would use 29!/(15!*14!)= 77558760

Simple really. No spreadsheet required. Just need to know factorials :)

[Edit: Oops, typo on the number]

sonome writes...

(x+y)!/(x!*y!)

Yup, that is the formula too. :)

But try using that formula to calculate 500 x 500 grid using google calculator :D

The google calculator has trouble giving the exact answer.
So heres the Haskell solution...

Prelude> let googleCalc x y = fac (x-1+y-1)`div`((fac (x-1))*(fac (y-1)))

Prelude> googleCalc 100 100
2275088307942293496618195403956888­ 5395604168260154104734000

After waking up and finding my perl/VB solvers were still running I'm cheating and taking your equation based solutions. I'm telling myself that I did figure out the answer but merely did not have the processing power to find it in time.

If you did it the naiive way then you'd need as much processing power as the number - so no, it's not really the answer :|.

It's equivalent to a very well known problem anyway. It's interesting to note that the lower grid sizes are quite a bit easier (in terms of having few enough digits to calculate using longs) than the larger ones (I had ~50x50).

I'm surprised we have to wait 24 hours from the time we submit the result to the time we can continue. Looks like I'm going to be a day behind some of you

it's not really that surprising... reduces cheating and rewards consistently understanding the questions rather than brute forcing them. You could figure out the answer with a pen and paper if you wanted to. I think a lot, if not all of the questions will like that. There'll be a mathematical or engineering solution, you just have to know the right keywords to google to find it

>:||||||||||

Grid size: 66 x 53
Your answer: 5967672566297606276262590342860600­ unique paths
Time received: 2008-05-12 00:48:57.541946 UTC

Correct answer: 5967672566297606276262590342860551­ unique paths

i knew the sig figs would get me. blargh

wornoutwords writes...

Correct answer: 5967672566297606276262590342860551­ unique paths

i knew the sig figs would get me. blargh

Cool, my code got the right answer, but now I just have to wait 9 hrs:

It is now: 2008-05-13 01:18:24.033250 UTC
Your result will be displayed at: 2008-05-13 10:07:51.672702 UTC

Tolvic writes...

It's interesting to note that the lower grid sizes are quite a bit easier (in terms of having few enough digits to calculate using longs) than the larger ones (I had ~50x50).

I think that's the whole point of the exercise. I doubt very much that any of the grid sizes asked will have an answer that isn't over the 32bit number threshold. To answer this question correctly you have to understand the permutation issues, and be aware of errors that happen when calculating large numbers.

I hope the questions get harder, because if they are all this easy it's going to really advantage the folks that have a lot of time on their hands.

They should have added some coordinates (obstacles) that you can't travel through.

Your answer was correct! Congratulations, you're part-way there.
There will more questions over the coming weeks, and the first person to answer them all correctly will win a prize, so keep trying!

Grid size: 34 x 59
Your answer: 6623993658588396149806110 unique paths

To check your own formulas.

MiCCAS.net writes...

There will more questions over the coming weeks, and the first person to answer them all correctly will win a prize, so keep trying!

I am pretty sure there's a prize for each question?

Could somebody please explain the formula to me? It had to be something with a factorial, but why does this formula work? What is the problem called that we're calculating here?

OK, the 'correct' approach to working this out (e.g. the one that would most likely impress Google in a job interview, and don't forget that that's pretty much what this is -- an online recruitment tool) -- is:

1) If you try a brute force solution, realise quickly that it's unworkable, and why. Google like people who understand algorithmic complexity ("Big-O notation") and would realise that (a) this problem is O(n!) and (b) O(n!) complexity is about the worst there is so it's really not suitable for any sort of production solution for any problem Google are ever going to solve.

2) To actually work out WHY the answer is the formula posted, you need to work out the 'nature' of the problem. The steps you might work through COULD go something like this:

* What's the minimum number of moves the robot can make? For a 5x6 grid, clearly the best it can do is 9 (4 down, 5 across)

* What's the maximum number of moves it can make? Well, it can't go up or left, so the WORST it can do is 9. We've just eliminated one question from the solution (how many different numbers of moves are there?)

* How many different moves are there? 2, obviously -- right and down. If you realise that the description of the moves could be looked at as a 9-bit binary number (0=down, 1=right) they'd probably quite like that!

* What restrictions are there on the individual 'bits'? 4 of them must be 0 (down), but 5 of them must be 1 (right).

* Does the order matter? No. It doesn't matter if you go DDDDRRRRR or RDRDRDRDR.

* So basically, the question is 'how many different combinations of 5 'on' bits of a 9-bit binary number are there?'

* From here, you might need a bit of help if you don't remember all your high-school maths, but if you do you remember that this is basic binomial expansion -- how many ways are there of picking r items from a population of n? Or, in binomial terms, what's 9C5? Google probably wouldn't worry if you needed help with remembering the formula. I'm sure they wouldn't mind if you Googled it! :)

* In an actual interview, they wouldn't ask for the actual answer! Now you've got the idea (you need to calculate nCr) then they'd ask you to generalise your solution (if it wasn't already) to work out where those values of 'n' and 'r' come from (e.g. total moves = (width - 1) + (height - 1) for n, and either down moves (height - 1) or right moves (width - 1) for r)

Then they offer you a job and it's all the free lunch you can get!

my head just exploded....

mino writes...

Then they offer you a job and it's all the free lunch you can get!

Will it still be free lunch after Rudd's change? FBT applies on "free" lunch now :(

Of course, there's no such thing as a free lunch anyway. I don't know if that many Googlers would care if they lost all their "free" stuff but were given a 5-10% pay rise. I rekon most techies just like to work on cool stuff.

Cling Wrap writes...

Will it still be free lunch after Rudd's change? FBT applies on "free" lunch now :(

"The measure will not affect subsidised canteens that are provided to all staff and that are not part of a salary sacrifice arrangement" apparently (according to the budget docs). I just panicked because I read that what you're talking about also applies to work-supplied drinks, but I can't find anything about that in the budget stuff. Phew!

The updated post on the Official Google Blog says:

-------------------------------
Posted by Phillip Grasso, Manager, Engineering/Operations

Avast, matey! As announced on the Google Australia blog, we've launched Treasure Hunt — a puzzle contest designed to test yer problem-solving skills in computer science, networking, and low-level UNIX trivia. You'll find the first of four brainteasers at treasurehunt.appspot.com. A new puzzle will be posted every week for the next three weeks, and a few lucky gobs to submit correct answers to every question will receive a prize.

The second puzzle will be appearing soon — to be exact, 936266827 seconds before Y2K38, so keep yer eyes open. We'll also be highlighting our Mountain View mother ship, so step smartly, lads and lasses, and good luck!

In case ye missed out on the first week's puzzle, it's still available, so 'tis not too late! ARR! (Can you tell we can hardly wait to Talk Like a Pirate?)
----------------------------------­ ----

By my calculation that is Mon, 19 May 2008 17:07:00 GMT which in EST is Mon, 20 May 2008 3:07:00.

odeee writes...

The second puzzle will be appearing soon — to be exact, 936266827 seconds before Y2K38, so keep yer eyes open. We'll also be highlighting our Mountain View mother ship, so step smartly, lads and lasses, and good luck!

?Date.Parse("1/01/2038 00:00").Subtract(new TimeSpan(0,0,936266827))
#5/1/2008 1:52:53 PM#

What am I doing wrong?

Y2K38 isn't just January 1st, 2038; it refers to the January 19th of that year at 03:14:07 -- this is the 'Unix equivalent' of the Y2K bug, when Unix timestamps (stored as a number of seconds since 1/1/1970, in a signed 32-bit integer) will roll over into negative numbers.

mino writes...

Y2K38 isn't just January 1st, 2038

Thanks - I live in a windoze world...

odeee writes...

By my calculation that is Mon, 19 May 2008 17:07:00 GMT which in EST is Mon, 20 May 2008 3:07:00.

Makes sense to me (now!)

a new question is live

Nman writes...

a new question is live

Is there a catch to this? It all seems too easy. I've solved mine using PHP!

fizzy writes...

Is there a catch to this? It all seems too easy. I've solved mine using PHP!

Jep, the catch is that if you used bash, you would be quicker.. no other catch than for now the task is to use the tools that enable you to be the fastest.

I still expect that the last, or last two questions, are so hard that not a lot of people can solve them.

Tomy_MMX writes...

Jep, the catch is that if you used bash, you would be quicker.. no other catch than for now the task is to use the tools that enable you to be the fastest.

I don't think there's a noticable speed in processing. Mine executed and gave the results almost instantly. The only reason I used PHP is because I already have a similar script I've written in PHP for some other previous projects. All I had to do was to make very little modification to it, and viola.. the answers!

Didn't mean the speed of execution.. I meant if you start from scratch then this is one line of bash code using find, sed itd.. I doubt it is less than 15 lines in php..

Good question. Taking me a little longer than expected but that makes it even better.

Tomy_MMX writes...

Didn't mean the speed of execution.. I meant if you start from scratch then this is one line of bash code using find, sed itd.. I doubt it is less than 15 lines in php..

Yeah, true..that can be solved using a line of bash command.

My php code has a little bit more than 15 line of codes, but that includes global variables that holds the generic settings. I'd say if I left that out, it'd be less than 10 lines of code. :)

fizzy writes...

Is there a catch to this? It all seems too easy. I've solved mine using PHP!

Yeah it seemed very easy, I wish I could have made for the 3am launch. I am sure most people solved it very fast.

Edit:
We'll have to wait and see if it really was that easy =p

Cling Wrap writes...

Edit:
We'll have to wait and see if it really was that easy =p

It was!

First attempt:

Your question: 2 sums from 9301143502524598045.zip: line 4 in *bar*.rtf, line 5 in *aaa*.pdf
Your answer: 2295986550
Time received: 2008-05-19 19:26:33.985534 UTC

Correct answer: 2295986550
Your answer was: Correct

Second attempt:

Your question: 2 sums from 18363718271017021787.zip: line 4 in *stu*.xml, line 3 in *abc*.pdf
Your answer: 4504259290
Time received: 2008-05-19 19:34:53.006146 UTC

Correct answer: 4504259290
Your answer was: Correct

Made only one attempt.. but faster:)

Your question: 2 sums from 7514763831725892664.zip: line 5 in *HIJ*.xml, line 4 in *foo*.xml
Your answer: 518516378
Time received: 2008-05-19 18:02:24.802315 UTC

Correct answer: 518516378
Your answer was: Correct

Actually my only problem was that I almost forgot about the time when the question goes live, so it was almost an hour until I checked what it was:)

P.S.
It's a pity that you don't get to see how many correct answers there were before yours.. that would be an interesting information:)

Tomy_MMX writes...

Actually my only problem was that I almost forgot about the time when the question goes live, so it was almost an hour until I checked what it was:)

I wonder if they count time from when the question goes live, or when your personal question is generated?

Another correct answer (however I did solve it in a dirty way). I'm enjoying this alot and I wonder what the prizes will be!

Adrian writes...

I wonder if they count time from when the question goes live, or when your personal question is generated?

I am pretty sure that it is the time when the question goes live.. since once you have the answer how to solve it it is very easy to solve an other one with an other e-mail account in practically no time. That is the reason why I both times submitted only one answer, since I don't see the reason to do it more often.

How did ya's do it?

MiCCAS.net writes...

How did ya's do it?

Edit: Removed so people aren't tempted to copy. I don't want to spoil the fun

It's a tough one isnt it ClingWrap. I've been getting Whirls asking the same thing.

I enjoy the aspect of working as a team towards something (and everyone can contribute) and I'm happy to share all code and concept behind each puzzle but I would be heartbroken if something I shared caused me to be ranked "behind" the copier. I have infact gained a 'better way' of solving a puzzle from another Whirlpooler saving me alot of time and hassle.

Perhaps we should expect to be asked questions when we brag about getting correct answers and if someone Whirls us with a legitimate understanding of the problem and a partial solution we can help.

It is a little bit of a shame that we can't share answers freely without spoiling the benefit of the challenge for others. I would love to see an excellent bash script answer to the second challenge. I answered it myself using what I think is a kludgy bash script, so it would be good to compare it to a master's answer.

murrayh writes...

It is a little bit of a shame that we can't share answers freely without spoiling the benefit of the challenge for others. I would love to see an excellent bash script answer to the second challenge. I answered it myself using what I think is a kludgy bash script, so it would be good to compare it to a master's answer.

How about we do this when the third one has launched? There is always after the comp is over too.

MiCCAS.net writes...

How about we do this when the third one has launched? There is always after the comp is over too.

I personally think lagging two weeks behind Google is appropriate, so next week we could all share Question 1 answers. And for the special case of the last question, 2 weeks after its released (assuming its solved quickly).

Edit:
Though, clues on the next question start time are always nice :)

Cling Wrap writes...

Though, clues on the next question start time are always nice :)

Tuesday, May 27 at 10 a.m. PDT, according to googleblog.blogspot.com/...hunt-week-3.html

That's 3AM Wednesday AEST by my calculations.

Stupid Americans, stealing our treasure hunt and putting all the questions at ridiculous times.

(That blog post also includes more details about the prizes, by the way.)

This week's puzzle is set to be released on Tuesday, May 27 at 10 a.m. PDT.
I agree with the time conversion.
It is also nice to know that there will be multiple prizes.

mino writes...

Stupid Americans, stealing our treasure hunt and putting all the questions at ridiculous times.

(That blog post also includes more details about the prizes, by the way.)

Also from the post:
time is defined as the time between the question's release and the submission of the correct answer

so it seems you will need to be awake at 2 am to have any chance of a prize!

Adrian writes...

so it seems you will need to be awake at 2 am to have any chance of a prize!

Unless they actually start putting out hard questions

I might actually be able to do tonight's if I don't fall asleep. I have a suspicion it's going to be a networking problem.

This questions are too easy.. but once again I was late for the start.. don't know why they don't make it harder!

I enjoyed this one. I did expect to be tricked with an unusual mask at some point but a nice logic problem.

Would be a good lab for someone doing cisco certification to set up and implement EIGRP on!

my 1st one had a bit of a gotcha. The default went to the destination but the x.x.x.0/24 one (that the destination matched) went somewhere else. I didn't know if i'd chosen correctly so I did another one and this one was more straightforward. The paths that I chose both took the same amount of hops so I think I was right the 1st time too.

This was the hardest for me so far, i have no idea about networking

wornoutwords writes...

I didn't know if i'd chosen correctly so I did another one and this one was more straightforward.

The default route is also known as the 'route of last resort'. Routers check for matches in their routing table (eg the static routes mentioned in googles challenge) and if they don't find a match, they jump on the default train.

Did I miss something, or was this really easy?
It took me 5 minutes and a piece of paper... The only slightly tricky bit was knowing what a /24 mask did, and the default route.

Adrian writes...

Did I miss something, or was this really easy?
It took me 5 minutes and a piece of paper... The only slightly tricky bit was knowing what a /24 mask did, and the default route.

I thought this as well... I know nothing about routing, but it was pretty easy to logically deduce what the default route was for and what a /24 mask would do. I figure I must have missed some "trick" to the question - I guess I'll find out when I get my results.

Your question: F -> 131.125.181.103
Your answer: FJIEDCONMAP
Time received: 2008-05-27 18:44:22.791888 UTC

Correct answer: FJIEDCONMAP
Your answer was: Correct

Seams it really was that easy. Wonder if the last one will be harder...

Your question: N -> 206.66.58.210
Your answer: NBMAPLCDKHI
Time received: 2008-05-27 17:25:36.373142 UTC

Correct answer: NBMAPLCDKHI
Your answer was: Correct

Probably still too late to get a prize.

Do you have to be the first answer to get prizes, or one of the first however many?

Theres always gonna be someone getting the question the second it comes out. Pretty tough.

Wally Wallitron writes...

Probably still too late to get a prize.

I still hope that the last (or was it last two) question will be so hard that not a lot of people get the correct answer.. if not, this was all a big scam to get more good engineers to send a CV to google, since the email is posted with every question:)

Tomy_MMX writes...

big scam to get more good engineers to send a CV to google

I was a little disappointed at so much of the hunt being dedicated to US content. They have fantastic buildings here in Australia as well as some interesting regular events (Women in IT etc).
I applied and I don't think scam is the right word to use here. Recruitment drive? Pre-Interview testing?

I was correct on this one but I would have been too slow because I had to look up how routing works, as I have an Engineering background rather than computer science and hadn't come across it (although I had a vague idea). And if you actually knew how routing worked it would have taken about 30 seconds, 10 if you'd had a lot of coffee.

I know how routing works, and at 3am it took me about 10mins. I set my alarm for 3, but didn't actually rise from the grave till quarter past. I got half way through the puzzle before I actually woke up and realised I was doing it wrong. :)

It's a fairly good technique for interviewing people that want an operations role where solving problems in the middle of the night, while half asleep are par for the course. Hopefully the next one is at a reasonable hour though, either that or the prize is something better than a Google t-shirt.

From googleblog.blogspot.com

The fourth and final puzzle will be released at 1212448500.
By my calculation:
GMT: Mon, 02 Jun 2008 23:15:00 GMT
Your timezone: Tuesday, 3 June 2008 9:15:00 AM

Game on!

Toughest one yet for me as I have little love for math.

Zubby writes...

Toughest one yet for me as I have little love for math.

The fact it used prime numbers is fairly irrelevant, so I don't think it had much to do with Math at all. I would love a real Math question :)

I made that one a lot harder for myself than it needed to be... I could have got the answer about half an hour before I did but I chased around thinking I'd screwed something up when I hadn't! D'oh.

mino writes...

thinking I'd screwed something up

Yeah I did the same, well I wasted about 10 minutes. Hopefully I didn't make any stupid mistakes :) We'll see...

Edit:
Waking up late didn't help either :)

Seems I don't get it.. is there an easy solution.. since the almost brute force method could take a while:)

Also for anyone interested: When I visited the site at exactly 9:15:

Traceback (most recent call last):
File "/base/python_lib/versions/1/google/appengine/ext/webapp/__init__.py", line 499, in __call__
handler.get(*groups)
File "/base/data/home/apps/treasurehunt/1.80/treasurehunt.py", line 423, in get
entry.put()
File "/base/python_lib/versions/1/google/appengine/ext/db/__init__.py", line 618, in put
return datastore.Put(self._entity)
File "/base/python_lib/versions/1/google/appengine/api/datastore.py", line 162, in Put
raise _ToDatastoreError(err)
File "/base/python_lib/versions/1/google/appengine/api/datastore.py", line 1603, in _ToDatastoreError
raise datastore_errors.Error(err.error_detail)
Error

Ok.. it was fast.. my mistake:)

Struggling to even write the pseudocode for this one.

Bah... this one's got me stumped :(

sonome writes...

Bah... this one's got me stumped :(

Hmm.. it wasn't that hard. Start with the least likely number that can be found.. the one that is a sum of the highest number of primes. When you find one that is also a prime, test if you can find the other sums for this number.. if not, move to the next higher number, that could be the solution.. basically it is a brute force approach whit some knowledge about the problem.. nothing special.. my two answers are both somewhere around 8 or 9 million.

Your question: [13, 39, 237, 1409]
Your answer: 8632157
Time received: 2008-06-03 01:33:11.724825 UTC

Correct answer: 8632157
Your answer was: Correct

All the questions were too easy..
The fastest people where those who sat in front of the computer waiting for the question to appear, all others that started when they could are in no position to win,

Your question: [19, 27, 61, 765]
Your answer: 8685373
Time received: 2008-06-03 00:43:42.050603 UTC

Correct answer: 8685373
Your answer was: Correct

Tomy_MMX writes...

All the questions were too easy..
I agree, but I think they did it on purpose unfortunately.

Tomy_MMX writes...

Hmm.. it wasn't that hard. Start with the least likely number that can be found.. the one that is a sum of the highest number of primes. When you find one that is also a prime, test if you can find the other sums for this number.. if not, move to the next higher number, that could be the solution.. basically it is a brute force approach whit some knowledge about the problem.. nothing special.. my two answers are both somewhere around 8 or 9 million.

This is how I did it:

Generated a lot of prime numbers (largest number 10,000,000 I think.. can't remember). Then put those in a set (an array of numbers).

Foreach number your given say [2 3 4 5]
Generate another set that sums each consecutive numbers from the prime number array. I optimised it by taking the previous number away and adding the next number for each of the values.

Then take the interception of any one of your summed sets and the original prime number set. Then take the interception of another of your summed sets with the new set. Repeat and repeat again.

The answer to the problem is at index 0 of the resultant set. If index 0 doesn't exist your initial prime number set was not large enough.

Performance of the interception was quick because it exploited the fact the sets are all ordered lists. So a search for a number in a set was only a O(logn) operation.

My program takes approximately 4 seconds in c# (170 milliseconds with a smaller prime number list) to find the answer once the prime number list is generated. For the prime number list I generated it once and put it in a text file, it takes about 8 seconds (110 milliseconds with a smaller prime number list) to serialise. So 12 seconds all up (280 milliseconds with a smaller prime number list) or there about, but my prime number set was much bigger than it needed to be.

I think it may have even been faster to re-generate the prime number set than serialise it. And really all the optimisations were pretty much a waste because the sets you're dealing with aren't really that big, so people who optimised their code probably wasted more time doing that than just completely brute forcing it.

Edit:
The quickest way to solve the problem probably would have been to import the prime number list to a SQL database and perform the operations there. Or use linq in c#.

If anyone has a few minutes to spare I'd appreciate a hand with this purely to complete the exercise. I have taken the route of making