/*
-----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-----
*/