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] + "]");
        }
    }
}

Leave a Reply