2020_10&11_CandyCollectors.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "import pandas as pd\n",
    "import itertools\n",
    "import requests\n",
    "from bs4 import BeautifulSoup\n",
    "import sympy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Puzzle\n",
      "~~~~~~\n",
      "Five children went trick-or-treating together and decided to randomly split their candy haul at the end of the night.  As it turned out, they got a total of 25 pieces of candy, 5 copies each of 5 different types (they live in a small town).  They distribute the candies by choosing an ordering of the 25 uniformly at random from all shufflings, and then giving the first 5 to the first child, the second 5 to the second, and so on.What is the probability that each child has one type of candy that they have strictly more of than every other trick-or-treater?  Give your (exact!) answer in a lowest terms fraction.November update:correct solutions to this puzzle have come in more slowly than others, so we are going to keep it up for an extra month and will have a new puzzle on the site in early December.\n"
     ]
    }
   ],
   "source": [
    "print(\"Puzzle\")\n",
    "print(\"~~~~~~\")\n",
    "url='https://www.janestreet.com/puzzles/candy-collectors/'\n",
    "res = requests.get(url)\n",
    "soup = BeautifulSoup(res.content, 'html.parser')\n",
    "x =[text for text in soup.body.stripped_strings]\n",
    "print(\"\".join(x[7:11]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "<b>Generating Function :</b>\n",
    "<br>\n",
    "<br>\n",
    "$\\begin{align}\n",
    "f_1(a,b,c,d,e) &= \\frac{a^5}{5!}+\\frac{a^4}{4!}(b+c+d+e)+\\\\\n",
    "&\\quad\\frac{a^3}{3!}\\left(\\frac{b^2}{2!}+\\frac{c^2}{2!}+\\frac{d^2}{2!}+\\frac{e^2}{2!}+bc+bd+be+cd+ce+de\\right)\n",
    "\\\\&\\quad\\frac{a^2}{2!}(bcd+bce+bde+cde)\n",
    "\\end{align}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Answer is\n",
      "~~~~~~~~~\n",
      "318,281,087 / 8,016,470,462\n"
     ]
    }
   ],
   "source": [
    "# Here's the solution using generating functions as per stackexchange\n",
    "# Don't think this is the easiest way or the way that is described above\n",
    "# https://math.stackexchange.com/questions/3934750/how-to-solve-this-candy-collectors-puzzle\n",
    "# and the book referred to https://www2.math.upenn.edu/~wilf/DownldGF.html\n",
    "\n",
    "def f(a,b,c,d,e) :\n",
    "    return (a**5/math.factorial(5) \n",
    "            + a**4/math.factorial(4)*(b + c + d + e) \n",
    "            + a**3/math.factorial(3)*((b**2+c**2+d**2+e**2)/math.factorial(2)+ b* c + b *d + b* e + c* d + c* e + d *e)\n",
    "            + a**2/math.factorial(2)*(b* c* d + b* c* e + b* d* e + c* d *e))\n",
    "            \n",
    "\n",
    "from sympy.abc import a,b,c,d,e\n",
    "EGF = sympy.Poly(f(a,b,c,d,e)*f(b,c,d,e,a)*f(c,d,e,a,b)*f(d,e,a,b,c)*f(e,a,b,c,d))\n",
    "coeff = EGF.coeff_monomial((a*b*c*d*e)**5) \n",
    "\n",
    "num = int(coeff * math.factorial(5)**6)\n",
    "denom = int(math.factorial(25)/(math.factorial(5)**5))\n",
    "gcd= math.gcd(num,denom)\n",
    "\n",
    "print(\"Answer is\")\n",
    "print(\"~~~~~~~~~\")\n",
    "print(\"{:,.0f} / {:,.0f}\".format(num/gcd,denom/gcd))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Solution\n",
      "~~~~~~\n",
      "The probability that every child would have strictly more of a candy than each other trick-or-treater was precisely 318281087/8016470462 , which comes to just under 4%.  The most straightforward way to compute this was to assign a particular candy to each child and compute the probability of that (writing some code certainly helped here) and then multiplying the result by 120 to account for the disjoint other assignments of candy to trick-or-treater.\n"
     ]
    }
   ],
   "source": [
    "print(\"\")\n",
    "print(\"Solution\")\n",
    "print(\"~~~~~~\")\n",
    "url='https://www.janestreet.com/puzzles/solutions/october-2020-solution/'\n",
    "res = requests.get(url)\n",
    "soup = BeautifulSoup(res.content, 'html.parser')\n",
    "x =[text for text in soup.body.stripped_strings]\n",
    "print(\" \".join(x[7:10]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}