4 ms·
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
by psykotic 14y ago
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.
- jonsen 14y agoYou have to go down and pick up the unbroken egg.
- psykotic 14y agoGood 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.
- psykotic 14y agoI 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 https://gist.github.com/3157191 Let me know if this is what you had in mind.
- shasta 14y agoCan you see if the egg is broken without going down? I guess you're assuming so.