Hacker News Reader

And the next question:

What strategy should you adopt to minimize the number of steps it takes you up and down the stairs to find the solution?

View on HN

That version seems too simple to be interesting. Let there be n floors. In the worst case you'll have to walk to the top floor from the ground floor in case the answer happens to be n-1. Therefore you can't do any better than n-1 steps in the worst case, so the obvious strategy of alternating dropping an egg and walking up one floor until you break the egg is optimal and takes n-1 steps and n-1 drops and only requires 1 egg.

You have to go down and pick up the unbroken egg.

Good point! That adds a lot of nuance. With several eggs, if you drop one egg and it doesn't break, you have the option of postponing the pick-up until later or leaving it on the ground altogether. Let me think about it.

I had a quick go at it using memoized minimax search. I assumed that picking up any dropped eggs is automatic when you're on the ground floor, but it would also be easy to model it as an action.

https://gist.github.com/3157191

Let me know if this is what you had in mind.

Can you see if the egg is broken without going down? I guess you're assuming so.

Take the elevator :)

Reply on news.ycombinator.com