HW_5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "<font size=\"4\" style=\"color:red;\"> **IMPORTANT: ** When submitting this homework notebook, please modify only the cells that start with:</font>\n",
    "\n",
    "```python\n",
    "# modify this cell\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "# Different Dice\n",
    "\n",
    "\n",
    "So far we mostly considered standard 6-faced dice. The following problems explore dice with different number of faces. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "%pylab inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "## Problem 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "Suppose that a 6-sided die is rolled $n$ times. Let $X_i$ be the value of the top face at the $i$th roll,\n",
    "and let $X\\triangleq\\max_{1\\le i\\le n} X_i$ be the highest value observed. For example, if $n=3$ and the three\n",
    "rolls are 4, 1, and 4, then $X_1=4, X_2=1, X_3=4$ and $X=4$. \n",
    "\n",
    "To find the distribution of $X$, observe first that $X\\le x$ iff $X_i\\le x$ for all $1\\le i\\le n$,\n",
    "hence $P(X\\le x)=(x/6)^n$. It follows that $P(X=x)=P(X\\le x)-P(X\\le x-1)=(x/6)^n-((x-1)/6)^n$.\n",
    "For example, $P(X=1)=(1/6)^n$, and $P(X=2)=(1/3)^n-(1/6)^n$.\n",
    "\n",
    "In this problem we assume that each of the $n$ dice has a potentially different number of faces, denoted $f_i$,\n",
    "and ask you to write a function **largest_face** that determines the probability $P(x)$ that the highest top face observed is $x$. **largest_face** takes a vector $\\boldsymbol f$ of positive integers, interpreted as the number of faces of each of the dice, and a value $x$ and returns $P(x)$. For example, if $\\boldsymbol f=[2, 5, 7]$, then three dice are rolled, and $P(1)=(1/2)\\cdot(1/5)\\cdot(1/7)$ as all dice must be 1, while $P(7)=1/7$ as the third die must turn up 7.\n",
    "\n",
    "<font  style=\"color:blue\">* **Sample run** *</font>\n",
    "```python\n",
    "print largest_face([2,5,8],8)\n",
    "print largest_face([2], 1)\n",
    "largest_face( [3,4], 2)\n",
    "print largest_face([2, 5, 7, 3], 3)\n",
    "```\n",
    "\n",
    "\n",
    "<font  style=\"color:magenta\">* **Expected Output** *</font>\n",
    "```\n",
    "0.125\n",
    "0.5\n",
    "0.25\n",
    "0.180952380952\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def largest_face(f, x_max):\n",
    "    # inputs: m is a list of integers and m_max is an integer\n",
    "    # output: a variable of type 'float'\n",
    "    # Example: Here we want to get the probability of getting largest face as 2 for two dices.\n",
    "    # That should be 3 combinations out of total 36 combinations : 1,2 2,1, 2,2\n",
    "    # According to formula : P(2)= (2/6)^2 - (1/6)^2 = 3/36\n",
    "    return np.prod([x_max/float(n) for n in f if x_max <= n]) - np.prod([(x_max - 1) / float(n) for n in f if x_max <= n])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex_1",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "\n",
    "assert abs( largest_face([5],3) - 0.19999999999999996 ) < 10**-5\n",
    "assert abs( largest_face( [11,5,4], 5) - 0.16363636363636364  ) < 10**-5\n",
    "assert abs( largest_face(range(1,10), 3) - 0.011348104056437391 ) < 10**-5 \n",
    "\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "## Problem 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "Write a function **face_sum** that takes a vector $\\boldsymbol f$ that as in the previous problem represents the number of faces of each die,  and a positive integer $s$, and returns the probability that the sum of the top faces observed is $s$. For example, if $\\boldsymbol f=[3, 4, 5]$ and $s\\le 2$ or $s\\ge 13$, **face_sum** returns 0, and if $s=3$ or $s=12$, it returns $(1/3)\\cdot(1/4)\\cdot(1/5)=1/60$.\n",
    "\n",
    "Hint: The **constrained-composition** function you wrote for an earlier probelm may prove handy. \n",
    "\n",
    "<font  style=\"color:blue\"> * **Sample run** *</font>\n",
    "```python\n",
    "print face_sum([3, 4, 5], 13)\n",
    "print face_sum([2,2],3)\n",
    "print face_sum([3, 4, 5], 7)\n",
    "```\n",
    "\n",
    "\n",
    "<font  style=\"color:magenta\"> * **Expected Output** *</font>\n",
    "```\n",
    "0.0\n",
    "0.5\n",
    "0.18333333\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "### Helper Code\n",
    "\n",
    "Below is a correct implementation of **constrained_composition**. Call this function in your implementation of **face_sum**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def constrained_compositions(n, m):\n",
    "    # inputs: n is of type 'int' and m is a list of integers\n",
    "    # output: a set of tuples\n",
    "    \n",
    "    k = len(m)\n",
    "    parts = set()\n",
    "    if k == n:\n",
    "        if 1 <= min(m):\n",
    "            parts.add((1,)*n)\n",
    "    if k == 1:\n",
    "        if n <= m[0]:\n",
    "            parts.add((n,))\n",
    "    else:\n",
    "        for x in range(1, min(n-k+2,m[0]+1)):\n",
    "            for y in constrained_compositions(n-x, m[1:]):\n",
    "                parts.add((x,)+y)\n",
    "    return parts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "### exercise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def face_sum(m, s):\n",
    "    # inputs: m is list of integers and s is an integer\n",
    "    # output: a variable of type 'float'\n",
    "    # Example: Here we want to see to get the probability of largest face summing up to the number provided\n",
    "    # As for [2,2], we have (1,1),(1,2),(2,1),(2,2) as all possible combinations of largest faces\n",
    "    # For getting 3 as sum, we have its probability as 2/4 = 0.5\n",
    "    l1= len(constrained_compositions(s,m))\n",
    "    l2=1\n",
    "    for i in m:\n",
    "        l2= i*l2\n",
    "    probability= l1/l2\n",
    "    return probability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex_2",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "assert sum(abs( face_sum([2,2],2) - 0.25  )) < 10**-5\n",
    "assert sum(abs( face_sum([2,2],10) - 0.0  )) < 10**-5\n",
    "assert sum(abs( face_sum(range(1,10),20) - 0.03037092151675485  )) < 10**-5\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "locked": false,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "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.6.5"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "48px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}