/*
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

*/

/*
 * Memoized Egg Dropper
 * By Alex Ponebshek
 * 
 * This is a program to solve the Google egg-dropping puzzle, generalized to more than 2 eggs.
 * It uses memoization for efficiency.
 * I still think it could be made more efficient by using a binary search to find the optimal drop floor.
 * 
 * It can print the full decision tree for egg dropping.
 */

public class EggDropper
{
	public static void main(String[] args)
	{
		System.out.println("Dropping eggs...");
		int eggs=3;
		int stories=100;
		
		EggDropper e=new EggDropper(eggs, stories); // Pepare the computat0r!
		System.out.println("It will take "+e.eggdrop(eggs, stories)+" drops."); // Print worst case drops
		e.eggdrop_treewalk(eggs, stories, 0, 0, false); // Print decision tree
	}
	
	//f(1,b)=b, f(a,b)=1+max(f(a-1,x), f(a, b-x-1)) where x is whatever value of x would make f(a,b) the lowest
	
	private int[][] droppages;
	
	public EggDropper(int maxeggs, int maxlevels)
	{
		droppages=new int[maxeggs-1][maxlevels-1];
	}
	
	public int eggdrop(int a, int b)
	{
		if (b==0) // No ambiguity, so no testing required
			return 0;
		
		if (b==1) // One last drop!  I'm such an idiot for missing this before.
			return 1;
		
		if (a<=1) // One egg, so exhaustive search
			return b;
		
		if (droppages[a-2][b-2] == 0) // If it's not in the table...
			droppages[a-2][b-2]=eggdrop_calc(a, b); // calculate it!
		
		return droppages[a-2][b-2];
	}
	
	private int eggdrop_calc(int a, int b)
	{
		for (int i=2; i<b; i++) // Precompute for lower floors to shake the obscenely deep recursion out ;)
			eggdrop(a, i);
		
		int follow=beatdrop(a, b, 0);
		for (int x=1; x<b; x++) // Loop to find optimal floor from which to drop this floor
		{
			follow=Math.min(follow, beatdrop(a, b, x));
		}
		
		return follow+1;
	}
	
	private int beatdrop(int a, int b, int x) // Find worst case of smash or no smash for a given drop
	{
		return Math.max(eggdrop(a-1, x), eggdrop(a, b-x-1));
	}
	
	/**
	 * Outputs a decision tree
	 * Each line is spaced out by the number of drops that already happened.
	 * A number means "drop from this floor".  
	 * 	The next line is what happens if there was no smash,
	 * 	and the following line at that tablevel is what happens if there is a smash.
	 * 
	 * n : Drop on floor n
	 * =n: Smashpoint is n
	 * ~n: Smashpoint is either n or n+1; drop at n
	 * ~n,m: Smashpoint is from n to m+1; dropscan from n to m
	 */
	public void eggdrop_treewalk(int a, int b, int prefixed, int rebase, boolean smashfun)
	{
		tabOut(prefixed);
		
		// Note to me: a is at least 1, and b is... fuck b.
		
		if (b<=0) // Not sure if this can happen, but I'm afraid to remove it >_>
		{
			System.out.println("="+rebase);
			return;
		}
		
		if (b==1)
		{
			System.out.println("~"+rebase);
			return;
		}
		
		if (a<=1)
		{
			System.out.println("~"+rebase+","+(rebase+b-1));
			return;
		}
		
		eggdrop(a, b); // Makes sure the table is filled out
		
		int follow=beatdrop(a, b, 0);
		int opx=0; // now we track optimal floor
		for (int x=1; x<b; x++)
		{
			int drop=beatdrop(a, b, x);
			if (drop<follow || (smashfun && drop==follow))
			{
				follow=drop;
				opx=x;
			}
		}
		
		System.out.println(opx+rebase);
		
		eggdrop_treewalk(a  , b-opx-1, prefixed+1, rebase+opx+1, smashfun); // If it doesn't break
		eggdrop_treewalk(a-1, opx    , prefixed+1, rebase      , smashfun); // If it does break
	}
	
	private void tabOut(int spaces)
	{
		for (;spaces>0;spaces--) System.out.print(" ");
	}
}

/*
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFJGpK3wwWAXIUwsAcRAv7KAJ47XjIYK4/iObsmuiWTZOxnMtujYwCeIe2U
3F/U5THbCw4z+DWueKd84e4=
=MUj1
-----END PGP SIGNATURE-----
*/