2 eggs problem

2-egg-problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2-Egg Problem\n",
    "You are given i eggs and a building with j floors with the following assumptions: \n",
    "    1. an egg which survives a fall can be used again\n",
    "    2. a broken egg is done\n",
    "    3. if an egg breaks or survive on a floor then all eggs would have the same result on that floor.\n",
    "    4. if an egg breaks on a floor, all eggs would break on higher floors\n",
    "    5. if an egg survives an experiment, all eggs would survive on lower floors\n",
    "    \n",
    "Goal: Determine the smallest number of egg drop experiments required, in all cases, the lowest floor an egg would crack on.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Intuition\n",
    "If $x$ is the minimum number of drops to determine the critical floor of a j-storey building and the worst case critical floor for any building is the top floor then the following holds true:\n",
    "\\begin{aligned}[t]\n",
    "x + (x - 1)+ (x - 2)+ (x - 3) + ... + 1 & \\ge j \\\\\n",
    "\\sum\\limits_{n=1}^{x}{n} \\ge j \\to \\frac{x(x+1)}{2} & \\ge j\n",
    "\\end{aligned}\n",
    "\n",
    "$\n",
    "\\text {For } j = 100, \\text { solve for x to determine the critical floor} \\\\\n",
    "\\frac{x(x+1)}{2} \\ge 100 \\to \n",
    "x^2 + x - 200 \\ge 0 \\\\\n",
    "x \\approx 13.65 \\to 14 \\text { is the critical floor. }  \n",
    "$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>table {float:left}</style>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "$$.html('<style>table {float:left}</style>')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dynamic Programming Solution i-eggs j-floors\n",
    "Let $F(i, j)$ be the minimum number of tries given i-eggs and j-floors, we can define a recurrence relationship to solve this from the bottom up: $\n",
    "F(i, j) = \\displaystyle\\min_{x = 1..j} \\bigg\\{ 1 + Max \\big\\{ F(i - 1, x), F(i, j - x) \\big\\} \\bigg\\}\n",
    "$. In other words $F(i, j)$ is the minimized value worst case drops of floors 1 through j.\n",
    "\n",
    "$$F(i, j) = \n",
    "\\begin{cases}\n",
    "0, & \\text{if i = 0} \\\\[2ex]\n",
    "j, & \\text{if i = 1} \\\\[2ex]\n",
    "1, & \\text{if j = 1} \\\\[2ex]\n",
    "\\displaystyle\\min_{x = 1..j} \\bigg\\{ 1 + Max \\big\\{ F(i - 1, x), F(i, j - x) \\big\\} \\bigg\\}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "### Analysis\n",
    "  * Runtime: $\\mathcal{O}(nk^2)$\n",
    "  * Space  : $nk$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "function eggdrop(eggs, floors) {\n",
    "    // create a 1-based eggs X floors array.\n",
    "    const M = Array.from({length: eggs + 1}, () => Array.from({length: floors+1}, () => 0))\n",
    "    \n",
    "    // establish base cases\n",
    "    for (let i=0; i<=eggs; i++) {\n",
    "        M[i][0] = 0 // 0-floors 0 drops \n",
    "        M[i][1] = 1 // 1-floor  1 drop\n",
    "    }\n",
    "    \n",
    "    for (let i=1; i<=floors; i++) {\n",
    "        M[1][i] = i // 1 egg i drops\n",
    "    }\n",
    "    \n",
    "    for (let i=2; i<=eggs; i++) {\n",
    "        for (let j=2; j<=floors; j++) {\n",
    "            M[i][j] = Infinity\n",
    "            \n",
    "            for (let x=1; x<j; x++) {\n",
    "                M[i][j] = Math.min(\n",
    "                    M[i][j],\n",
    "                    1 + Math.max(\n",
    "                        M[i - 1][x-1],\n",
    "                        M[i][j - x]\n",
    "                    )\n",
    "                )\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    return M[eggs][floors]    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "eggDrop(2, 100) = 14\n"
     ]
    }
   ],
   "source": [
    "const eggs     = 2\n",
    ",     floors   = 100\n",
    ",     solution = eggdrop(eggs, floors)\n",
    "\n",
    "console.log(`eggDrop(${eggs}, ${floors}) = ${eggdrop(eggs, floors)}`)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Javascript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "8.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}