FiveThirtyEight Jailbreak Riddle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem\n",
    "One hundred prisoners are put into 100 completely isolated cells, numbered 1 to 100. Once they are in their cells, they cannot communicate with each other in any way. They are taken by the warden one at a time, but in no particular order, to a special room, Cell 0, in which there are two levers. As the prisoners enter the room, each lever is either up or down, but the levers’ starting positions are unknown. When in the room, a prisoner must flip exactly one of the levers. At any point, any prisoner may declare to the warden that all of the prisoners have been to the room. (The warden will take prisoners to the room indefinitely until someone makes a guess.) If the prisoner is correct, they are all released. If not, they are all executed.\n",
    "\n",
    "Knowing these rules, what strategy can the prisoners devise beforehand that will guarantee their release? How many trips to Cell 0 will it take on average before they are released?\n",
    "\n",
    "\n",
    "# Solution\n",
    "\n",
    "## Overview\n",
    "\n",
    "Designate one prisoner (Prisoner #100) as the one who will count how many times all other prisoners have visited Cell 0.\n",
    "\n",
    "Designate one lever (`left_lever`) as the one that will indicate a prisoner has visited the cell. The other lever (`right_lever`) is basically useless, and is only toggled because the prisoners are required to toggle something every time they enter the cell. (Incidentally, it seems that this problem would be conceptually simpler if there was only one toggle, and prisoners were *not* required to toggle anything when they visit Cell 0.)\n",
    "\n",
    "Prisoners 1-99 will each \"record\" the fact that they visited the cell by toggling `left_lever` from the down to up position. If `left_lever` is already toggled up when they enter the cell, then their visit isn't \"recorded\" and they must wait to try again (and in the meantime just toggle `right_lever`). Once they have successfully toggled `left_lever` once, they no longer attempt to do so and always toggle `right_lever`.\n",
    "\n",
    "Prisoner 100 will be the one who tallies the count of other prisoners' visits (in his or her head) by counting every time s/he enters the cell and sees `left_lever` is toggled up. If it is up, s/he will reset it to down. Otherwise, s/he too will just toggle `right_lever`.\n",
    "\n",
    "Therefore, Prisoner 100 waits until s/he had counted 99 \"visits\" and then asks to be released.\n",
    "\n",
    "Except...\n",
    "\n",
    "## What about those unknown initial conditions?\n",
    "Unfortunately, the fact that the initial conditions are unknown is a bit of a curve ball - what if `left_lever` starts out toggled up and Prisoner 100 mistakenly counts that as a visit from a fellow prisoner? \n",
    "\n",
    "To address this, we can modify our solution so that each prisoner is required to have two \"recorded\" visits, i.e. they must toggle `left_lever` from the down to up position exactly twice. Then, instead of counting up only 99 visits, Prisoner 100 looks for 198 visits. \n",
    "\n",
    "Why does this work? If every prisoner has to have two \"recorded\" visits to Cell 0, then `left_lever` might be toggled to the up position 198 or 199 times, depending on its initial state:\n",
    "\n",
    "```\n",
    "99 prisoners * 2 visits + 1 if the lever started in the up position = 199 toggles\n",
    "```\n",
    "\n",
    "Prisoner 100 can (and should!) safely call it at 198 toggles, because even if only 98 prisoners have visited the cell twice and the toggle started out up, the 99th prisoner must have visited at least once:\n",
    "\n",
    "```\n",
    "98 prisoners * 2 visits + 1 toggle from initial conidtions + 1 visit from 99th prisoner = 198 toggles\n",
    "```\n",
    "\n",
    "If the toggle started down, then there will only be 198 toggles total, and Prisoner 100 would wait forever without seeing the 199th up toggle.\n",
    "\n",
    "\n",
    "## Algorithm\n",
    "\n",
    " - For prisoners 1-99, if they visit the cell and the `left_lever` is down, toggle it to up. Otherwise toggle `right_lever`. Only toggle `left_lever` up twice, afterwards always just toggle `right_lever`.\n",
    " - For prisoner 100, if `left_lever` is up, count that as a 'visit' for another prisoner, and toggle it to down. Otherwise toggle `right_lever`. After s/he has counted 198 'visits', demand to be released!\n",
    " \n",
    "### Addendum / side note on lever orientation\n",
    "There would have to be some prearranged agreement on how to distinguish the two levers and their two positions. I've assumed that the levers are left and right of each other and that they toggle up and down. The prisoners would want to make arragements for various orientations of the levers. \n",
    "\n",
    "# Probability\n",
    "I could try to dredge up college statistics to figure out the answer, or I could do what I do best and write a program for that simulates it, run multiple trials, and finds the average number of iterations.\n",
    "\n",
    "Based on this program, it looks like the average number of iterations is somewhere around 20,500. (Try running it for yourself below!)\n",
    "\n",
    "If it takes only 1 minute per iteration, and the warden works around the clock, it will take on average ~14 days for the prisoners to be released\n",
    "\n",
    "```\n",
    "(20500 iterations) * (1 minute/iteration) / (60 minutes/hour * 24 hours/day) = 14 days\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "import random\n",
    "\n",
    "class PrisonersChallenge():\n",
    "    def __init__(self):\n",
    "        self.prisoners = range(1,101)\n",
    "\n",
    "        # Levers can start in either up (True) or down (False) positions.\n",
    "        lever_options = (True, False)\n",
    "        self.left_lever = random.choice(lever_options)\n",
    "        self.right_lever = random.choice(lever_options)\n",
    "\n",
    "        # Stores the number of times each prisoner (1-99) has a \"recorded\" visit to the cell\n",
    "        # and prisoner 100's count of others' visits\n",
    "        self.visit_count = defaultdict(lambda: 0)\n",
    "\n",
    "        # How many iterations did it take for prisoners to be released?\n",
    "        self.iterations = 0\n",
    "\n",
    "    def run_iteration(self):\n",
    "        self.iterations += 1\n",
    "\n",
    "        prisoner = random.choice(self.prisoners)\n",
    "        release_prisoners = False\n",
    "\n",
    "        if prisoner == 100:\n",
    "            # If left_lever is toggled up, count it as a visit and reset it\n",
    "            if self.left_lever:\n",
    "                self.visit_count[prisoner] += 1\n",
    "                self.left_lever = not self.left_lever\n",
    "\n",
    "            else:\n",
    "                self.right_lever = not self.right_lever\n",
    "\n",
    "            # If 198 visits have been counted, ask to be released!\n",
    "            if self.visit_count[prisoner] >= 198:\n",
    "                release_prisoners = True\n",
    "\n",
    "        else:\n",
    "            # If left_lever isn't already toggled up, and this prisoner hasn't already had 2 visits recorded, toggle it up\n",
    "            if (not self.left_lever) and self.visit_count[prisoner] < 2:\n",
    "                self.left_lever = not self.left_lever\n",
    "                self.visit_count[prisoner] += 1\n",
    "            else:\n",
    "                self.right_lever = not self.right_lever\n",
    "\n",
    "        return release_prisoners"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_trial():\n",
    "    '''\n",
    "    Run a single trial of the Prisoner's Challenge\n",
    "    \n",
    "    @return: how many iterations it took\n",
    "    '''\n",
    "    release_prisoners = False\n",
    "    challenge = PrisonersChallenge()\n",
    "\n",
    "    while(not release_prisoners):\n",
    "        release_prisoners = challenge.run_iteration()\n",
    "    \n",
    "    return challenge.iterations\n",
    "\n",
    "def run_trials(number_of_trials):\n",
    "    '''\n",
    "    Run multiple trial of the Prisoner's Challenge, and record how many iterations it took\n",
    "    \n",
    "    @return: a list of the iteration count for each trial\n",
    "    '''\n",
    "    trials = []\n",
    "    for i in range(number_of_trials):\n",
    "        iteration_count = run_trial()\n",
    "        trials.append(iteration_count)\n",
    "    \n",
    "    return trials"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average # iterations: 20476\n"
     ]
    }
   ],
   "source": [
    "NUMBER_OF_TRIALS = 100000\n",
    "\n",
    "trials = run_trials(NUMBER_OF_TRIALS)\n",
    "\n",
    "print \"Average # iterations:\", sum(trials)/len(trials)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZUAAAEKCAYAAADaa8itAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHlVJREFUeJzt3X+UHWWd5/H3hyDIIWKCYG9McDpocAbImCEtMDPqdkQx\ngDtBVzE5HEkEiQg4o5NxDOoRDyxzosjqogxulAxwZIlRYMhoMMRIi7tnQn4AkoBgmhiWxJiMBMGg\nG2387h/1NFSa2903N8/tujf5vM6559b91lNV37q5N9+ueuo+pYjAzMwsh4OqTsDMzPYfLipmZpaN\ni4qZmWXjomJmZtm4qJiZWTYuKmZmlo2LipmZZeOiYmZm2biomJlZNgdXncBIO+qoo6Kzs7PqNHju\nuec4/PDDq06jYc6/Ws6/Wu2cf6O5r1u37lcRcfRw7Q64otLZ2cnatWurToOenh66u7urTqNhzr9a\nzr9a7Zx/o7lLeqKedj79ZWZm2biomJlZNi4qZmaWjYuKmZll46JiZmbZNK2oSFokaYekDaXYtyQ9\nmB6bJT2Y4p2Sflea97XSMlMlrZfUK+laSUrxIyWtkLQxPY9t1r6YmVl9mnmkciMwvRyIiPdHxJSI\nmALcBtxemv14/7yIuKgUvx64EJiUHv3rnA+sjIhJwMr02szMKtS0ohIR9wI7a81LRxvnALcOtQ5J\n44AjImJVFPc9vhk4O82eAdyUpm8qxc3MrCJV/fjxLcD2iNhYik2U9ADwLPCZiPgxMB7YUmqzJcUA\nOiJiW5r+JdAx2MYkzQXmAnR0dNDT05NlJ/bFrl27WiKPRjn/ajn/arVz/s3OvaqiMos9j1K2Aa+N\niKckTQX+VdIJ9a4sIkJSDDF/IbAQoKurK1rhl7Dt/Itc2L/z75z/vYbXu3nBWQ0vuzf25/e/HbRz\n/s3OfcSLiqSDgfcAU/tjEbEb2J2m10l6HDgO2ApMKC0+IcUAtksaFxHb0mmyHSORv5mZDa6KI5W3\nA49GxAuntSQdDeyMiOclHUvRIb8pInZKelbSqcB9wHnAV9JiS4HZwIL0fOdI7oS1tuGONuZN7mPO\nPhyRmFltzbyk+Fbg34E3SNoi6YI0ayYv7aB/K/BQusT4O8BFEdHfyX8x8A2gF3gcuCvFFwDvkLSR\nolAtaNa+mJlZfZp2pBIRswaJz6kRu43iEuNa7dcCJ9aIPwWctm9ZmplZTv5FvZmZZeOiYmZm2bio\nmJlZNi4qZmaWjYuKmZll46JiZmbZuKiYmVk2LipmZpaNi4qZmWXjomJmZtm4qJiZWTYuKmZmlo2L\nipmZZeOiYmZm2biomJlZNi4qZmaWjYuKmZll46JiZmbZuKiYmVk2LipmZpZN04qKpEWSdkjaUIp9\nTtJWSQ+mx5mleZdJ6pX0mKR3luLTU6xX0vxSfKKk+1L8W5IOada+mJlZfZp5pHIjML1G/EsRMSU9\nlgFIOh6YCZyQlvlnSaMkjQKuA84AjgdmpbYAn0/rej3wNHBBE/fFzMzq0LSiEhH3AjvrbD4DWBwR\nuyPi50AvcHJ69EbEpoj4PbAYmCFJwNuA76TlbwLOzroDZma21w6uYJuXSjoPWAvMi4ingfHAqlKb\nLSkG8OSA+CnAq4BfR0RfjfZmlemc/72Gl9284KyMmZhVY6SLyvXAlUCk52uA85u9UUlzgbkAHR0d\n9PT0NHuTw9q1a1dL5NGoVs9/3uS+Ied3HDZ8m5G2N+9nq7//w3H+1Wl27iNaVCJie/+0pK8D300v\ntwLHlJpOSDEGiT8FjJF0cDpaKbevtd2FwEKArq6u6O7u3rcdyaCnp4dWyKNRrZ7/nGGOGOZN7uOa\n9VUcqA9u87nddbdt9fd/OM6/Os3OfUQvKZY0rvTy3UD/lWFLgZmSDpU0EZgErAbWAJPSlV6HUHTm\nL42IAO4B3puWnw3cORL7YGZmg2van2qSbgW6gaMkbQEuB7olTaE4/bUZ+DBARDwsaQnwCNAHXBIR\nz6f1XAosB0YBiyLi4bSJTwKLJf034AHghmbti5mZ1adpRSUiZtUID/off0RcBVxVI74MWFYjvoni\n6jAzM2sR/kW9mZll46JiZmbZuKiYmVk2LipmZpaNi4qZmWXjomJmZtm4qJiZWTYuKmZmlo2LipmZ\nZeOiYmZm2biomJlZNi4qZmaWjYuKmZll01p3KTJL9uW2vGZWHR+pmJlZNi4qZmaWjYuKmZll46Ji\nZmbZuKiYmVk2LipmZpaNi4qZmWXTtKIiaZGkHZI2lGJXS3pU0kOS7pA0JsU7Jf1O0oPp8bXSMlMl\nrZfUK+laSUrxIyWtkLQxPY9t1r6YmVl9mnmkciMwfUBsBXBiRPw58DPgstK8xyNiSnpcVIpfD1wI\nTEqP/nXOB1ZGxCRgZXptZmYValpRiYh7gZ0DYndHRF96uQqYMNQ6JI0DjoiIVRERwM3A2Wn2DOCm\nNH1TKW5mZhWpsk/lfOCu0uuJkh6Q9CNJb0mx8cCWUpstKQbQERHb0vQvgY6mZmtmZsNScQDQpJVL\nncB3I+LEAfFPA13AeyIiJB0KjI6IpyRNBf4VOAE4DlgQEW9Py70F+GREvEvSryNiTGmdT0dEzX4V\nSXOBuQAdHR1TFy9enHtX99quXbsYPXp01Wk0rNn5r9/6TNPWDdBxGGz/XVM3sdcmj39l3W39+alW\nO+ffaO7Tpk1bFxFdw7Ub8QElJc0B3gWclk5pERG7gd1pep2kxykKylb2PEU2IcUAtksaFxHb0mmy\nHYNtMyIWAgsBurq6oru7O+s+NaKnp4dWyKNRzc5/TpMHlJw3uY9r1rfWeKqbz+2uu60/P9Vq5/yb\nnfuInv6SNB34R+BvIuK3pfjRkkal6WMpOuQ3pdNbz0o6NV31dR5wZ1psKTA7Tc8uxc3MrCJN+1NN\n0q1AN3CUpC3A5RRXex0KrEhXBq9KV3q9FbhC0h+APwIXRUR/J//FFFeSHUbRB9PfD7MAWCLpAuAJ\n4Jxm7YuZmdWnaUUlImbVCN8wSNvbgNsGmbcWOLFG/CngtH3J0czM8vIv6s3MLBsXFTMzy8ZFxczM\nsnFRMTOzbFxUzMwsGxcVMzPLxkXFzMyycVExM7NsXFTMzCwbFxUzM8vGRcXMzLJxUTEzs2xcVMzM\nLBsXFTMzy8ZFxczMsnFRMTOzbFxUzMwsGxcVMzPLxkXFzMyycVExM7NsDq46ATMrdM7/Xt1t503u\nY06p/eYFZzUjJbO9VteRiqS/ridWo80iSTskbSjFjpS0QtLG9Dw2xSXpWkm9kh6SdFJpmdmp/UZJ\ns0vxqZLWp2WulaR69sfMzJqj3tNfX6kzNtCNwPQBsfnAyoiYBKxMrwHOACalx1zgeiiKEHA5cApw\nMnB5fyFKbS4sLTdwW2ZmNoKGPP0l6S+BvwKOlvT3pVlHAKOGW3lE3Cupc0B4BtCdpm8CeoBPpvjN\nERHAKkljJI1LbVdExM6U0wpguqQe4IiIWJXiNwNnA3cNl5eZmTXHcH0qhwCjU7tXlOLPAu9tcJsd\nEbEtTf8S6EjT44EnS+22pNhQ8S014i8haS7F0Q8dHR309PQ0mHo+u3btaok8GtXs/OdN7mvaugE6\nDmv+NpppYP7t9lny5786zc59yKISET8CfiTpxoh4IvfGIyIkRe711tjOQmAhQFdXV3R3dzd7k8Pq\n6emhFfJoVLPzn7MXndaNmDe5j2vWt+91KgPz33xud3XJNMCf/+o0O/d6v1WHSloIdJaXiYi3NbDN\n7ZLGRcS2dHprR4pvBY4ptZuQYlt58XRZf7wnxSfUaG9mZhWpt6P+28ADwGeAT5QejVgK9F/BNRu4\nsxQ/L10FdirwTDpNthw4XdLY1EF/OrA8zXtW0qnpqq/zSusyM7MK1Huk0hcR1+/tyiXdSnGUcZSk\nLRRXcS0Alki6AHgCOCc1XwacCfQCvwU+CBAROyVdCaxJ7a7o77QHLqa4wuwwig56d9KbmVWo3qLy\nb5IuBu4AdvcHS/+51xQRswaZdVqNtgFcMsh6FgGLasTXAicOlYOZmY2ceotK/+mq8imvAI7Nm46Z\nmbWzuopKRExsdiJmZtb+6ioqks6rFY+Im/OmY2Zm7aze019vKk2/nKJP5H7ARcXMzF5Q7+mvj5Zf\nSxoDLG5KRmZm1rYavZ/Kc4D7WczMbA/19qn8G8XVXlAMJPlnwJJmJWVmZu2p3j6VL5am+4AnImLL\nYI3NzOzAVNfprzSw5KMUIxWPBX7fzKTMzKw91Xvnx3OA1cD7KIZVuU9So0Pfm5nZfqre01+fBt4U\nETsAJB0N/AD4TrMSMzOz9lNvUTmov6AkT9H4lWN2gOhs8j1RzKz11FtUvi9pOXBrev1+ilGFzczM\nXjDcPepfT3H7309Ieg/w5jTr34Fbmp2cmZm1l+GOVL4MXAYQEbcDtwNImpzm/ZemZmdmZm1luH6R\njohYPzCYYp1NycjMzNrWcEVlzBDzDsuZiJmZtb/hispaSRcODEr6ELCuOSmZmVm7Gq5P5WPAHZLO\n5cUi0gUcAry7mYmZmVn7GbKoRMR24K8kTePFe8F/LyJ+2PTMzMys7dR7P5V7gHtybFDSG4BvlULH\nAp+l6L+5EPiPFP9URCxLy1wGXAA8D/xtRCxP8enA/6AYOfkbEbEgR45mZtaYen/8mE1EPAZMAZA0\nCtgK3AF8EPhSRJRHREbS8cBM4ATgNcAPJB2XZl8HvAPYAqyRtDQiHhmRHTEzs5cY8aIywGnA4xHx\nhKTB2swAFkfEbuDnknqBk9O83ojYBCBpcWrromJmVpGqx++ayYtDvwBcKukhSYskjU2x8cCTpTZb\nUmywuJmZVUQRMXyrZmxYOgT4BXBCRGyX1AH8iuIOk1cC4yLifElfBVZFxDfTcjcAd6XVTI+ID6X4\nB4BTIuLSGtuaC8wF6OjomLp48eIm793wdu3axejRo6tOo2H15L9+6zMjlM3e6zgMtv+u6iwaNzD/\nyeNfWV0yDTgQPv+tqtHcp02bti4iuoZrV+XprzOA+9MVZv1XmgEg6evAd9PLrcAxpeUmpBhDxPcQ\nEQuBhQBdXV3R3d2dIf1909PTQyvk0ah68p/TwqMUz5vcxzXrqz7727iB+W8+t7u6ZBpwIHz+W1Wz\nc6/y9NcsSqe+JI0rzXs3sCFNLwVmSjpU0kRgEsUNw9YAkyRNTEc9M1NbMzOrSCV/qkk6nOKqrQ+X\nwl+QNIXi9Nfm/nkR8bCkJRQd8H3AJRHxfFrPpcByikuKF0XEwyO2E2Zm9hKVFJWIeA541YDYB4Zo\nfxVwVY34MnxfFzOzllH11V9mZrYfcVExM7NsXFTMzCwbFxUzM8vGRcXMzLJxUTEzs2xcVMzMLBsX\nFTMzy8ZFxczMsnFRMTOzbNp3mFYze0HnPo4IvXnBWZkysQOdj1TMzCwbFxUzM8vGRcXMzLJxUTEz\ns2xcVMzMLBsXFTMzy8ZFxczMsnFRMTOzbFxUzMwsGxcVMzPLprKiImmzpPWSHpS0NsWOlLRC0sb0\nPDbFJelaSb2SHpJ0Umk9s1P7jZJmV7U/ZmZW/ZHKtIiYEhFd6fV8YGVETAJWptcAZwCT0mMucD0U\nRQi4HDgFOBm4vL8QmZnZyKu6qAw0A7gpTd8EnF2K3xyFVcAYSeOAdwIrImJnRDwNrACmj3TSZmZW\nqLKoBHC3pHWS5qZYR0RsS9O/BDrS9HjgydKyW1JssLiZmVWgyqHv3xwRWyW9Glgh6dHyzIgISZFj\nQ6lozQXo6Oigp6cnx2r3ya5du1oij0bVk/+8yX0jk0wDOg5r7fyGkzv/kf4sHgif/1bV7NwrKyoR\nsTU975B0B0WfyHZJ4yJiWzq9tSM13wocU1p8QoptBboHxHtqbGshsBCgq6sruru7BzYZcT09PbRC\nHo2qJ/85+3iPj2aaN7mPa9a37+2Ecue/+dzubOuqx4Hw+W9Vzc69ktNfkg6X9Ir+aeB0YAOwFOi/\ngms2cGeaXgqcl64COxV4Jp0mWw6cLmls6qA/PcXMzKwCVf2p1gHcIak/h/8VEd+XtAZYIukC4Ang\nnNR+GXAm0Av8FvggQETslHQlsCa1uyIido7cbpiZWVklRSUiNgFvrBF/CjitRjyASwZZ1yJgUe4c\nzcxs77XaJcVmZtbGXFTMzCwbFxUzM8vGRcXMzLJp3wv1bUR0DvJbk3mT+1r6dyhmVg0fqZiZWTYu\nKmZmlo2LipmZZeOiYmZm2biomJlZNi4qZmaWjYuKmZll46JiZmbZuKiYmVk2LipmZpaNi4qZmWXj\nomJmZtm4qJiZWTYepdjMBh2Nuh6bF5yVMRNrdz5SMTOzbFxUzMwsmxEvKpKOkXSPpEckPSzp71L8\nc5K2SnowPc4sLXOZpF5Jj0l6Zyk+PcV6Jc0f6X0xM7M9VdGn0gfMi4j7Jb0CWCdpRZr3pYj4Yrmx\npOOBmcAJwGuAH0g6Ls2+DngHsAVYI2lpRDwyInthZmYvMeJFJSK2AdvS9G8k/RQYP8QiM4DFEbEb\n+LmkXuDkNK83IjYBSFqc2rqomJlVRBFR3calTuBe4ETg74E5wLPAWoqjmaclfRVYFRHfTMvcANyV\nVjE9Ij6U4h8ATomIS2tsZy4wF6Cjo2Pq4sWLm7hX9dm1axejR4+uOo1hrd/6TM14x2Gw/XcjnExG\nzj+fyeNfudfLtMvnfzDtnH+juU+bNm1dRHQN166yS4oljQZuAz4WEc9Kuh64Eoj0fA1wfo5tRcRC\nYCFAV1dXdHd351jtPunp6aEV8hjOnEEuNZ03uY9r1rfvFenOP5/N53bv9TLt8vkfTDvn3+zcK/lU\nSnoZRUG5JSJuB4iI7aX5Xwe+m15uBY4pLT4hxRgibmZmFaji6i8BNwA/jYj/XoqPKzV7N7AhTS8F\nZko6VNJEYBKwGlgDTJI0UdIhFJ35S0diH8zMrLYqjlT+GvgAsF7Sgyn2KWCWpCkUp782Ax8GiIiH\nJS2h6IDvAy6JiOcBJF0KLAdGAYsi4uGR3BEzM9tTFVd//W9ANWYtG2KZq4CrasSXDbWcmZmNLP+i\n3szMsnFRMTOzbFxUzMwsGxcVMzPLxkXFzMyyaY2f5FpT7csNmMzM9oaPVMzMLBsXFTMzy8anv8xs\nnzRyenXe5D7mzP+e72+/H/KRipmZZeOiYmZm2biomJlZNi4qZmaWjYuKmZll46JiZmbZuKiYmVk2\nLipmZpaNi4qZmWXjX9SbWWX2ZbBT/xq/NbmotAGPMmxm7aLtT39Jmi7pMUm9kuZXnY+Z2YGsrYuK\npFHAdcAZwPHALEnHV5uVmdmBq91Pf50M9EbEJgBJi4EZwCOVZlXDwFNY/aO0mllj9vW0sPtkmqPd\ni8p44MnS6y3AKRXlYmZtZF+K0o3TD8+Yyf5FEVF1Dg2T9F5gekR8KL3+AHBKRFw6oN1cYG56+Qbg\nsRFNtLajgF9VncQ+cP7Vcv7Vauf8G839TyLi6OEatfuRylbgmNLrCSm2h4hYCCwcqaTqIWltRHRV\nnUejnH+1nH+12jn/Zufe1h31wBpgkqSJkg4BZgJLK87JzOyA1dZHKhHRJ+lSYDkwClgUEQ9XnJaZ\n2QGrrYsKQEQsA5ZVnUcDWup0XAOcf7Wcf7XaOf+m5t7WHfVmZtZa2r1PxczMWoiLyj6QtEjSDkkb\nBsQ/KulRSQ9L+kIpflkaTuYxSe8sxWsONZMuQLgvxb+VLkZoav6SpkhaJelBSWslnZziknRtyuUh\nSSeVlpktaWN6zC7Fp0pan5a5VpIy53+MpHskPZLe679L8SMlrUj5rJA0thX3YYj8r06fn4ck3SFp\nTGmZlvkMDZZ/af48SSHpqPS6Ld7/NK+lv8NDfHaq//5GhB8NPoC3AicBG0qxacAPgEPT61en5+OB\nnwCHAhOBxykuLhiVpo8FDkltjk/LLAFmpumvAR8ZgfzvBs5I02cCPaXpuwABpwL3pfiRwKb0PDZN\nj03zVqe2SsuekTn/ccBJafoVwM/S+/wFYH6Kzwc+34r7MET+pwMHp/jnS/m31GdosPzT62MoLqB5\nAjiqzd7/lv8OD5F75d9fH6nsg4i4F9g5IPwRYEFE7E5tdqT4DGBxROyOiJ8DvRTDzLww1ExE/B5Y\nDMxIfxW8DfhOWv4m4OwRyD+AI9L0K4FflPK/OQqrgDGSxgHvBFZExM6IeBpYAUxP846IiFVRfEJv\nbkL+2yLi/jT9G+CnFKMszKB4v2DP962l9mGw/CPi7ojoS81WUfz+qj//lvkMDfH+A3wJ+EeKz1O/\ntnj/aYPv8BC5V/79dVHJ7zjgLemQ90eS3pTitYaUGT9E/FXAr0v/ufTHm+1jwNWSngS+CFyW4nub\n//g0PTDeFJI6gb8A7gM6ImJbmvVLoCNNt+w+DMi/7HyKvxIZJs9KP0Pl/CXNALZGxE8GNGuX97+t\nvsMDcq/8++uikt/BFIeSpwKfAJbkPA88Aj4CfDwijgE+DtxQcT7DkjQauA34WEQ8W56X/spq6Usc\nB8tf0qeBPuCWqnKrRzl/inw/BXy20qT2Qo33v22+wzVyr/z766KS3xbg9nSYuRr4I8VYO4MNKTNY\n/CmKQ9SDB8SbbTZwe5r+NsWhPUPkOVR8Qo14VpJeRvGluiUi+vPeng7fSc/9py9abh8GyR9Jc4B3\nAeemwthI/k3/DNXI/3UU/Q0/kbQ5bfN+Sf+pgfyrev/b4js8SO7Vf3/r6XjxY8gOs0727Oi+CLgi\nTR9HcWgp4AT27OTbRNHBd3CansiLnXwnpOW/zZ6dfBePQP4/BbrT9GnAujR9Fnt29K2OFzv6fk7R\nyTc2TR8ZtTv6zsycuyjO9X55QPxq9uyo/0Ir7sMQ+U+nuH3D0QPiLfUZGiz/AW0282JHfbu8/y3/\nHR4i98q/v9m+4AfiA7gV2Ab8geKvmwvSh+qbwAbgfuBtpfafprhK5DFKV1JQXJnxszTv06X4sekf\ntjd9OA8dgfzfDKxLX4z7gKmlD/F1Kcf1QFdpPeenHHuBD5biXel9eBz4KunHthnzfzPFqa2HgAfT\n40yKc9krgY0UV/Ec2Yr7MET+vRT/kfXHvtaKn6HB8h/QZjMvFpV2ef9b/js8RO6Vf3/9i3ozM8vG\nfSpmZpaNi4qZmWXjomJmZtm4qJiZWTYuKmZmlo2LirW9NBLuNaXX/yDpc5nWfaOk9+ZY1zDbeZ+k\nn0q6Z0D8NZK+k6anSDoz4zbHSLq41rbMGuWiYvuD3cB7lIZYbxWlX1LX4wLgwoiYVg5GxC8ior+o\nTaH4LUKuHMYALxSVAdsya4iLiu0P+ihukfrxgTMGHmlI2pWeu9NggXdK2iRpgaRzJa1O95B4XWk1\nb0/3pviZpHel5UepuO/JmnR/ig+X1vtjSUspfhU/MJ9Zaf0bJH0+xT5L8aO1GyRdPaB9Z2p7CHAF\n8P50r4z3SzpcxT1xVkt6IA3kiKQ5kpZK+iGwUtJoSSsl3Z+2PSOtfgHwurS+q/u3ldbxckn/kto/\nIGlaad23S/q+ivtvfKH0ftyYcl0v6SX/FnZgaPt71Jsl1wEPqXRDpTq8EfgziuH/NwHfiIiTVdzw\n6KMUAyRCMZTNyRTjWt0j6fXAecAzEfEmSYcC/0fS3an9ScCJUQyP/gJJr6G4P8pU4GngbklnR8QV\nkt4G/ENErK2VaET8PhWfroi4NK3vn4AfRsT5Km7ktVrSD0o5/HlE7ExHK++OiGfT0dyqVPTmpzyn\npPV1ljZ5SbHZmCzpT1Oux6V5UyhGxd0NPCbpK8CrKYbtPzGtawx2QPKRiu0Xohih9Wbgb/disTVR\n3JdiN8VQFP1FYT1FIem3JCL+GBEbKYrPn1LcSOs8SQ9SDIfxKmBSar96YEFJ3kRx06T/iGI49Fso\nbpTWqNOB+SmHHuDlwGvTvBUR0X+vHAH/JOkhimFrxvPi7QAG82aKoUqIiEcpbrbVX1RWRsQzEfH/\nKI7G/oTifTlW0lckTQeerbFOOwD4SMX2J1+mGKvpX0qxPtIfT5IOohjXqd/u0vQfS6//yJ7fjYFj\nGQXFf9QfjYjl5RmSuoHnGkt/rwn4rxHx2IAcThmQw7nA0RTjQP0hjR788n3Ybvl9e57iLpVPS3oj\nxU2fLgLOoRhTyg4wPlKx/Ub6y3wJRad3v80Up5sA/gZ4WQOrfp+kg1I/y7EUgwkuBz6Shh9H0nGS\nDh9mPauB/yzpKEmjgFnAj/Yij99Q3Dq233Lgo1Jxrw9JfzHIcq8EdqSCMo3iyKLW+sp+TFGMSKe9\nXkux3zWl02oHRcRtwGcoTr/ZAchFxfY311Dc+6Lf1yn+I/8J8Jc0dhTxfykKwl3ARem0zzcoTv3c\nnzq3/yfDHPlHcTfK+cA9FKPIrouIO/cij3uA4/s76oErKYrkQ5IeTq9ruQXokrSeoi/o0ZTPUxR9\nQRsGXiAA/DNwUFrmW8CcdJpwMOOBnnQq7pu8eMdBO8B4lGIzM8vGRypmZpaNi4qZmWXjomJmZtm4\nqJiZWTYuKmZmlo2LipmZZeOiYmZm2biomJlZNv8fNwQDAWvFlO4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1047195d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "plt.hist(trials, bins=20)\n",
    "plt.xlabel('Number of iterations')\n",
    "plt.ylabel('Count')\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "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": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}