# Eggs and Floors – Java

```package com.standardwisdom.puzzles;

import java.util.Scanner;

// Eggs and Floors
// Essentially Nikita Rybak's algo - I added some color commentary..
public class EggsFloors
{
public static void main(String[] args)
{
int n = 2000; // floors
int m = 40; // eggs

int[][] optNumAttempts = new int[n + 1][m + 1]; // Optimal number of attempts for each floor, egg combination
int[][] optFirstAttempt = new int[n + 1][m + 1]; // Optimal 1st attempts for each floor, egg combination

// If we have only 1 egg, then we have to take a conservative approach - one floor at a time, so max number of attempts may be i..
for (int i = 1; i <= n; ++i) {
optNumAttempts[i][1] = i;
optFirstAttempt[i][1] = 1;
}

// If we have only 1 floor, then it always take one attempt.
for (int j = 1; j <= m; ++j) {
optNumAttempts[1][j] = 1;
optFirstAttempt[1][j] = 1;
}

// Otherwise, we use the recursive formulation
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++) {
// i floors, j eggs
optNumAttempts[i][j] = Integer.MAX_VALUE;

for (int k = 1; k <= i; k++) {
// try throw first egg from k-th floor
int result = Math.max(optNumAttempts[k - 1][j - 1], optNumAttempts[i - k][j]) + 1;
if (result < optNumAttempts[i][j]) {
optNumAttempts[i][j] = result;
optFirstAttempt[i][j] = k;
}
}
}
}

System.out.println("Entering interactive mode - enter floors (<= 2000) and eggs <= 40) - comma or space separated.  Enter 0 to quit.");
while (true) {
System.out.print("Enter floors and eggs  ");
Scanner sc = new Scanner(System.in);
int currn = sc.nextInt();
if (currn <= 0) {
break;
}
int currm = sc.nextInt();
System.out.println(currn + " floors, " + currm + " eggs.  Optimal number of attempts: " + optNumAttempts[currn][currm] + "  [Try first egg at floor #: "
+ optFirstAttempt[currn][currm] + "]");
}
}
}
```