Published by Dimitris Kougioumtzis · Updated
Track the maximum number of floors distinguishable with each egg count and number of drops.
Track floors distinguishable with a fixed move count: broken-egg coverage below plus surviving-egg coverage above plus the tested floor.
When to use Egg dropping (moves formulation)
Reformulating a minimax problem into coverage growth.
Choosing an alternative
Floor-based DP minimizes moves directly instead.
Worked example: input and state changes
Example input
2,10
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0 ], "active": [] }Step 2: After 1 drops, 1 eggs distinguish 1 floors.
State at this checkpoint
{ "values": [ 0, 1, 1 ], "active": [ 1 ] }Step 5: After 3 drops, 2 eggs distinguish 6 floors.
State at this checkpoint
{ "values": [ 0, 2, 6 ], "active": [ 2 ] }Step 7: After 4 drops, 2 eggs distinguish 10 floors.
State at this checkpoint
{ "values": [ 0, 3, 10 ], "active": [ 2 ] }Step 9: Minimum worst-case drops = 4.
State at this checkpoint
{ "values": [ 0, 4, 10 ], "active": [], "result": 4 }
Expected final state
Minimum worst-case drops = 4.
Complexity and input bounds
Family: Dynamic programming. Time complexity: O(eggs × moves).
Space complexity: O(eggs) coverage counts.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
eggs,floors; 1–6 eggs and 0–50 floors.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Update egg states backward so a new move is not reused in the same pass.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 | // 1–6 eggs, 0–50 floors. Returns minimum number of drops in the worst case. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(eggs, floors) { let dp = Array(256).fill(0); let moves = 0; while (dp[eggs] < floors) { moves++; for (let e = eggs; e >= 1; e--) { dp[e] = dp[e] + dp[e - 1] + 1; } } return moves; } |
Source
Foundational dynamic-programming paper. It establishes the general method, not the first publication or exact recurrence of this particular teaching example.
- The theory of dynamic programming
Richard Bellman (1954). Foundational method paper.