birthday cake problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Birthday problem:\n",
    "\n",
    "You have a baby. The doctor tells you your baby will live to be exactly 128 years old.  \n",
    "Because you are a kind parent, you intend to buy your child enough candals to last every\n",
    "birthday of their lifetime.  Because you are a thrifty parent, you intend to buy the \n",
    "fewest number of candals possible to represent every birthday your child will have.\n",
    "\n",
    "How many candals do you need to represent every birthday number between 1 and 128 in base \n",
    "10?  In base 9? 8? Which base system requires you to buy the fewest candals? \n",
    "\"\"\"\n",
    "\n",
    "DIGITS = \"0123456789ABCDEFG\"\n",
    "\n",
    "def toString(num: int, base: int) -> str:\n",
    "    \"\"\"\n",
    "    Convert |num| to a string base |base|\n",
    "    \"\"\"\n",
    "    ret = \"\"\n",
    "    while num:\n",
    "        ret = DIGITS[num % base]+ ret\n",
    "        num = num // base\n",
    "    return ret\n",
    "\n",
    "assert(toString(7, 2) == \"111\")\n",
    "assert(toString(8, 2) == \"1000\")\n",
    "assert(toString(7, 10) == \"7\")\n",
    "\n",
    "def countMaxOfDigit(ageMax: int, base: int, digit: str) -> int:\n",
    "    \"\"\"\n",
    "    Given all the birthday cake needs from 0 to |ageMax|, find\n",
    "    the most candals of type |digit| you need at any given point\n",
    "    \"\"\"\n",
    "    return max([toString(age, base).count(digit) for age in range(ageMax)])\n",
    "\n",
    "assert(countMaxOfDigit(150, 10, '0') == 2)\n",
    "\n",
    "def countTotalCandals(ageMax: int, base: int) -> int:\n",
    "    \"\"\"\n",
    "    Count the total number of candals needed to represent all ages\n",
    "    from 0 to |ageMax| in base |base|\n",
    "    \"\"\"\n",
    "    return sum([countMaxOfDigit(ageMax, base, digit) for digit in DIGITS])\n",
    "\n",
    "assert(countTotalCandals(128, 10) == 21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><th></th><th>base 2</th><th>base 3</th><th>base 4</th><th>base 5</th><th>base 6</th><th>base 7</th><th>base 8</th><th>base 9</th><th>base 10</th><th>base 11</th><th>base 12</th><th>base 13</th><th>base 14</th></tr><tr><th>age 5</th><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td></tr><tr><th>age 10</th><td>6</td><td>6</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td></tr><tr><th>age 15</th><td>6</td><td>7</td><td>6</td><td>7</td><td>8</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>14</td></tr><tr><th>age 20</th><td>8</td><td>7</td><td>8</td><td>8</td><td>8</td><td>9</td><td>10</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td></tr><tr><th>age 25</th><td>8</td><td>7</td><td>9</td><td>9</td><td>9</td><td>10</td><td>10</td><td>11</td><td>12</td><td>13</td><td>13</td><td>14</td><td>15</td></tr><tr><th>age 30</th><td>8</td><td>9</td><td>9</td><td>10</td><td>10</td><td>10</td><td>11</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>15</td></tr><tr><th>age 35</th><td>10</td><td>9</td><td>9</td><td>11</td><td>10</td><td>11</td><td>11</td><td>12</td><td>13</td><td>13</td><td>14</td><td>15</td><td>16</td></tr><tr><th>age 40</th><td>10</td><td>9</td><td>9</td><td>11</td><td>12</td><td>11</td><td>12</td><td>12</td><td>13</td><td>14</td><td>15</td><td>15</td><td>16</td></tr><tr><th>age 45</th><td>10</td><td>10</td><td>10</td><td>11</td><td>13</td><td>12</td><td>12</td><td>13</td><td>14</td><td>14</td><td>15</td><td>16</td><td>16</td></tr><tr><th>age 50</th><td>10</td><td>10</td><td>10</td><td>11</td><td>13</td><td>14</td><td>13</td><td>13</td><td>14</td><td>15</td><td>15</td><td>16</td><td>17</td></tr><tr><th>age 55</th><td>10</td><td>10</td><td>10</td><td>11</td><td>13</td><td>14</td><td>14</td><td>14</td><td>14</td><td>15</td><td>16</td><td>16</td><td>17</td></tr><tr><th>age 60</th><td>10</td><td>10</td><td>10</td><td>11</td><td>13</td><td>15</td><td>14</td><td>14</td><td>15</td><td>15</td><td>16</td><td>17</td><td>17</td></tr><tr><th>age 65</th><td>12</td><td>10</td><td>12</td><td>12</td><td>13</td><td>15</td><td>16</td><td>15</td><td>15</td><td>16</td><td>16</td><td>17</td><td>18</td></tr><tr><th>age 70</th><td>12</td><td>10</td><td>12</td><td>12</td><td>13</td><td>15</td><td>16</td><td>15</td><td>16</td><td>16</td><td>17</td><td>17</td><td>18</td></tr><tr><th>age 75</th><td>12</td><td>10</td><td>12</td><td>12</td><td>13</td><td>15</td><td>17</td><td>16</td><td>16</td><td>17</td><td>17</td><td>18</td><td>18</td></tr><tr><th>age 80</th><td>12</td><td>10</td><td>12</td><td>12</td><td>13</td><td>15</td><td>17</td><td>16</td><td>17</td><td>17</td><td>18</td><td>18</td><td>19</td></tr><tr><th>age 85</th><td>12</td><td>12</td><td>12</td><td>12</td><td>13</td><td>15</td><td>17</td><td>18</td><td>17</td><td>18</td><td>18</td><td>19</td><td>19</td></tr><tr><th>age 90</th><td>12</td><td>12</td><td>13</td><td>12</td><td>14</td><td>15</td><td>17</td><td>18</td><td>18</td><td>18</td><td>18</td><td>19</td><td>19</td></tr><tr><th>age 95</th><td>12</td><td>12</td><td>13</td><td>13</td><td>14</td><td>15</td><td>17</td><td>19</td><td>18</td><td>18</td><td>19</td><td>19</td><td>20</td></tr><tr><th>age 100</th><td>12</td><td>12</td><td>13</td><td>13</td><td>14</td><td>15</td><td>17</td><td>19</td><td>19</td><td>19</td><td>19</td><td>20</td><td>20</td></tr><tr><th>age 105</th><td>12</td><td>12</td><td>13</td><td>13</td><td>14</td><td>15</td><td>17</td><td>19</td><td>20</td><td>19</td><td>20</td><td>20</td><td>20</td></tr><tr><th>age 110</th><td>12</td><td>12</td><td>13</td><td>13</td><td>14</td><td>15</td><td>17</td><td>19</td><td>20</td><td>20</td><td>20</td><td>20</td><td>21</td></tr><tr><th>age 115</th><td>12</td><td>12</td><td>13</td><td>13</td><td>14</td><td>16</td><td>17</td><td>19</td><td>21</td><td>20</td><td>20</td><td>21</td><td>21</td></tr><tr><th>age 120</th><td>12</td><td>12</td><td>13</td><td>13</td><td>14</td><td>16</td><td>17</td><td>19</td><td>21</td><td>20</td><td>21</td><td>21</td><td>21</td></tr><tr><th>age 125</th><td>12</td><td>13</td><td>13</td><td>14</td><td>14</td><td>16</td><td>17</td><td>19</td><td>21</td><td>22</td><td>21</td><td>21</td><td>22</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.display import HTML, display\n",
    "\n",
    "def renderBirthdayMatrix(maxAgeMax: int, maxBase: int):\n",
    "    rows = []\n",
    "    \n",
    "    firstRow = [\"<th></th>\"]\n",
    "    for base in range(2, maxBase):\n",
    "        firstRow.append(\"<th>base %s</th>\" % (base,))\n",
    "    rows.append(''.join(firstRow))\n",
    "    \n",
    "    for ageMax in range(5, maxAgeMax, 5):\n",
    "        row = [\"<th>age %s</th>\" % (ageMax,)]\n",
    "        for base in range(2, maxBase):\n",
    "            row.append(\"<td>%d</td>\" % (countTotalCandals(ageMax, base),))\n",
    "        rows.append(''.join(row))\n",
    "    \n",
    "    rows = [\"<tr>%s</tr>\" % (row) for row in rows]\n",
    "    \n",
    "    \n",
    "    return HTML(\"<table>%s</table>\" % (''.join(rows)))\n",
    "\n",
    "display(renderBirthdayMatrix(128, 15))"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}