labs/problem-solving.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem-solving notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: combinations of first and last names\n",
    "\n",
    "Given the following list of first and last names, write a nested Python loop to print every combination of first and last name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "first=['Xue', 'Mary', 'Robert']\n",
    "last=['Li', 'Smith', 'Dixon']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first step is to **understand** the problem, so let's figure out what the output looks like:\n",
    "\n",
    "```\n",
    "Xue Li\n",
    "Xue Smith\n",
    "Xue Dixon\n",
    "Mary Li\n",
    "Mary Smith\n",
    "Mary Dixon\n",
    "Robert Li\n",
    "Robert Smith\n",
    "Robert Dixon\n",
    "```\n",
    "\n",
    "If we were trying to do this for two arbitrary lists, we should think about the edge cases, such as when one or both of the lists are empty.  Let's assume that we fully understand the problem now.\n",
    "\n",
    "The next step is to try to **solve** the problem, which we must be able to do manually. Unless you are an experienced programmer, it's best not to think about coding at this point. I literally think about moving my fingers or data around. In this case, I use a finger on each list and then for every top pointer finger I move my finger through all of the bottom fingers:\n",
    "\n",
    "<img src=\"images/first-last.png\" width=\"200\">\n",
    "\n",
    "When you hear the \"all combinations\" operation, think of nested loops.  Moving a finger through a list also screams loop!\n",
    "\n",
    "### Exercise\n",
    "\n",
    "Write out a loop implementation and a list comprehension implementation.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "for f in first:\n",
    "    for l in last:\n",
    "        print(f+' '+l)\n",
    "</pre>\n",
    "    OR<br>\n",
    "<pre>\n",
    "[f+' '+l for f in first for l in last]\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: checking for valid parentheses\n",
    "\n",
    "Let's try to solve a problem from leetcode.com called\n",
    "[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/).  That website has lots and lots of sample problems to solve and will help you get better at programming, and is very useful when you  start practicing for interviews.  The problem description is (taken verbatim from the site):\n",
    "\n",
    "*Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.*\n",
    "\n",
    "*An input string is valid if:*\n",
    "\n",
    "1. *Open brackets must be closed by the same type of brackets.*\n",
    "2. *Open brackets must be closed in the correct order.*\n",
    "\n",
    "Per our process, we have to understand the problem and my first question involves the set of valid characters. Looking more closely at the problem description, I see that only `()[]{}` characters are allowed.\n",
    "\n",
    "### Exercise\n",
    "\n",
    "Come up with a bunch of examples that illustrate the goal of this problem.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<table>\n",
    "    <tr>\n",
    "        <th>Input</th><th>Valid</th>\n",
    "    </tr>\n",
    "    <tr><td>()</td><td>true</td></tr>\n",
    "    <tr><td>[]</td><td>true</td></tr>\n",
    "    <tr><td>{}</td><td>true</td></tr>\n",
    "    <tr><td>()[]</td><td>true</td></tr>\n",
    "    <tr><td>([])</td><td>true</td></tr>\n",
    "    <tr><td>{({})}</td><td>true</td></tr>\n",
    "    <tr><td>{)</td><td>false</td></tr>\n",
    "    <tr><td>{})</td><td>false</td></tr>\n",
    "    <tr><td>{()</td><td>false</td></tr>\n",
    "    <tr><td>(</td><td>false</td></tr>\n",
    "    </table>\n",
    "</details>\n",
    "\n",
    "<br>\n",
    "If I tried to solve this manually, I would move my finger down the list of characters and perform an operation that made sure that closing symbols come in the right order and that all groupings are closed at the end:\n",
    "\n",
    "<img src=\"images/count-parens.png\" width=\"80\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### First attempt\n",
    "\n",
    "My first thought was to increment and decrement a count for each kind of grouping:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.3 (20210619.1520)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"45pt\" height=\"58pt\"\n",
       " viewBox=\"0.00 0.00 45.00 58.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 54)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-54 41,-54 41,4 -4,4\"/>\n",
       "<!-- node140413443610232 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140413443610232</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"37,-50 0,-50 0,0 37,0 37,-50\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-34 2.5,-48 13.5,-48 13.5,-34 2.5,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;(&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"13.5\" y=\"-36.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"23.5,-34 23.5,-48 35.5,-48 35.5,-34 23.5,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"24.5\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-32 2.5,-34 35.5,-34 35.5,-32 2.5,-32\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-18 2.5,-32 13.5,-32 13.5,-18 2.5,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;[&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"13.5\" y=\"-20.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"23.5,-18 23.5,-32 35.5,-32 35.5,-18 23.5,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"24.5\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-16 2.5,-18 35.5,-18 35.5,-16 2.5,-16\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-2 2.5,-16 13.5,-16 13.5,-2 2.5,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;{&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"13.5\" y=\"-4.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"23.5,-2 23.5,-16 35.5,-16 35.5,-2 23.5,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"24.5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fb48d6e32b0>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from lolviz import *\n",
    "objviz({'(':0,'[':0,'{':0})  # a first attempt at tracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As I encountered an opening symbol, I would bump that count. As I encountered a closing symbol, I would decrement that count. After walking through the entire string, the counts should all be zero indicating nothing is still open. \n",
    "\n",
    "**Q**: This doesn't work. Why not?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, let's see what happens with a bad example: `([)`. When we get to the `)`, the counts are"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.3 (20210619.1520)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"45pt\" height=\"58pt\"\n",
       " viewBox=\"0.00 0.00 45.00 58.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 54)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-54 41,-54 41,4 -4,4\"/>\n",
       "<!-- node140413443790456 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140413443790456</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"37,-50 0,-50 0,0 37,0 37,-50\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-34 2.5,-48 13.5,-48 13.5,-34 2.5,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;(&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"13.5\" y=\"-36.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"23.5,-34 23.5,-48 35.5,-48 35.5,-34 23.5,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"24.5\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 1</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-32 2.5,-34 35.5,-34 35.5,-32 2.5,-32\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-18 2.5,-32 13.5,-32 13.5,-18 2.5,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;[&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"13.5\" y=\"-20.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"23.5,-18 23.5,-32 35.5,-32 35.5,-18 23.5,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"24.5\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 1</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-16 2.5,-18 35.5,-18 35.5,-16 2.5,-16\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-2 2.5,-16 13.5,-16 13.5,-2 2.5,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;{&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"13.5\" y=\"-4.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"23.5,-2 23.5,-16 35.5,-16 35.5,-2 23.5,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"24.5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fb48d71d898>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objviz({'(':1,'[':1,'{':0})  # a first attempt at tracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to drop the count of the `)` but how do we know that it is in the right order? We don't. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The right approach\n",
    "\n",
    "It's not just the character count that matters, but the **sequence** of open and closes. When we see a close character, the most recent opening character must be the associated grouping symbol. Because these groupings can be nested, it complicates matters. We need a way to track the opening characters we've seen before and in their order of appearance.  Since I know that the solution requires a [stack data structure](https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks) for tracking symbols, I'm going to draw it as such:\n",
    "\n",
    "<img src=\"images/stack-parens.png\" width=\"120\">\n",
    "\n",
    "At this point, we see the first closing symbol and so we compare the closing symbol with the top of the stack to see if it's the most recently opened grouping. It is, so we pop off the `(` from the stack and move to the next character with our finger.\n",
    "\n",
    "Take a look at the situation when our finger moves to the `}`. We can see that there is a clear mismatch between the closing character under the finger and what we are expecting, thanks to the stack of open grouping symbols.\n",
    " \n",
    "<img src=\"images/stack-parens-2.png\" width=\"120\">\n",
    "\n",
    "Now that we have a working process, we can think about actually implementing it.  I will play around with some code to make sure I can make it work and then worry about putting it into a nice function. This is a typical workflow for programmers. Explore then cleanup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mismatched '}' doesn't match '['; symbols={\n",
      "mismatched ']' doesn't match '{'; symbols=\n"
     ]
    }
   ],
   "source": [
    "symbols = [] # our stack of symbols\n",
    "openers = {')':'(', ']':'[', '}':'{'}\n",
    "s = \"{[()}]\"\n",
    "for c in s:\n",
    "    if c in \"([{\":\n",
    "        symbols.append(c)\n",
    "    else: # verify we have the right opening symbol\n",
    "        if len(symbols)==0:\n",
    "            print(f\"Char '{c}' doesn't have an opening char; symbols={','.join(symbols)}\")\n",
    "            continue\n",
    "        opener = symbols.pop()\n",
    "        if openers[c] != opener:\n",
    "            print(f\"mismatched '{c}' doesn't match '{opener}'; symbols={','.join(symbols)}\")\n",
    "if len(symbols)>0:\n",
    "    print(f\"Unclosed groupings: {symbols}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After trying various input strings, I added a number of messages to catch errors. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Create a clean function called `isValid` that takes a string argument and returns True or False as to whether the groupings are balanced.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "def isValid(s: str) -> bool:\n",
    "    symbols = [] # our stack of symbols\n",
    "    openers = {')':'(', ']':'[', '}':'{'}\n",
    "    for c in s:\n",
    "        if c in \"([{\":\n",
    "            symbols.append(c)\n",
    "        else: # verify we have the right opening symbol\n",
    "            if len(symbols)==0:\n",
    "                return False\n",
    "            opener = symbols.pop()\n",
    "            if openers[c] != opener:\n",
    "                return False\n",
    "    if len(symbols)>0:\n",
    "        return False\n",
    "    return True\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "We have to try the function out with a bunch of test cases to make sure it works, including some edge cases. Write out a few test cases, both valid and invalid. Run them with your function.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "isValid('')\n",
    "isValid('()')\n",
    "isValid('{()')\n",
    "isValid('(]')\n",
    "isValid('{[()]}')\n",
    "isValid('()[]{}')\n",
    "isValid('(')\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Submitting to leetcode indicates that the runtime is faster than 85% of submitted solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: determining which ad to show on a website\n",
    "\n",
    "Imagine you work for a company that has a website and you'd like to be able to show ads on the various webpages on the website.  Customers that want to purchase ads buy a certain fraction of the ad \"impressions\" (ads that appear when someone looks at a page).  For example, company X might buy 30%, company Y 60%, and company Z 10% of the ad space. Your job is to randomly show the company's ads, but in the correct proportions.\n",
    "\n",
    "To solve this problem, it helps to visualize the relationship between the companies; we might draw a bar chart on paper that looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%config InlineBackend.figure_format = 'retina'  # gets sharper images"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAT4AAAEyCAYAAABj+rxLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAABYlAAAWJQFJUiTwAAAe1ElEQVR4nO3debgcVZ3/8feHJOwmERdAtoQ944YJi4CQACKbgELQDIiCBEaUYRj8qYgsAR1BBh8QcFBRQURADWqEsAlMDIuIScAARkDDFZRNJiSghCXw/f1xqk3Tducm3advd9/6vJ7nPkVXna5zuJBPquqcOkcRgZlZmazU6QaYmQ00B5+ZlY6Dz8xKx8FnZqXj4DOz0nHwmVnpOPjMrHQcfGZWOg4+MysdB5+ZlY6Dz8xKx8FnZqUztNMN6HWSHgaGA30dbopZ2YwCno2I0Sv6RQdf64avttpqa40ZM2atTjfErEzmzZvH4sWLm/qug691fWPGjFlr9uzZnW6HWamMGzeOOXPm9DXzXT/jM7PScfCZWen0bPBJ2knSVZIel/Risb1R0t51yu4g6VpJCyQ9L2mupOMkDelE282ss3ryGZ+kk4AvAk8D1wCPA28E3gVMAK6tKrs/cBXwAvBDYAGwL3AOsCNw0AA23cy6QM8Fn6SDSKF3E3BARDxXc3xY1T8PBy4CXgEmRMSsYv/JwC3AREmTIuLKgWq/mXVeT93qSloJ+ArwPHBwbegBRMTLVR8nAm8CrqyEXlHmBeCk4uPR7WuxmXWjXrvi2wEYDUwFnpG0D/A20m3sXRHxq5ryuxbb6+ucayYpQHeQtEpEvNimNptZl+m14Num2D4JzAHeXn1Q0kxgYkT8tdi1RbF9sPZEEbGkeOvircDGwLy2tNjMuk6vBd+bi+0ngIeB9wK/BjYCvgrsAfyY1MEBMKLYLmpwvsr+kf1VLKnRCOUt+/uumXWXXgu+yvATka7sflt8vl/SB0lXduMlbV/ntrceFVuvqt4lRp0wvdNNaLu+M/fpdBNKr9eC75liO78q9ACIiMWSbgCOALYFfsXSK7oR1De82Da6Iqw+/7h6+4srwbH9fd/MukdP9eoCDxTbhQ2OV4JxtZrym9cWlDSU1FGyBJifqX1m1gN6LfhmkoJqM0kr1zn+tmLbV2xvKbZ71im7M7A6cId7dM3KpaeCLyKeJr19MQI4pfqYpN1JnRuLWDp8ZSrp7Y5JkrauKrsq8KXi44VtbraZdZlee8YHcDywHfAFSTsDd5F6dT9IekPjyIhYCBARz0o6khSAMyRdSXplbT/SUJeppCA1sxLpqSs+gIh4ihR85wAbAMeSBipPB3aKiB/XlP8ZMJ50m3wg8O/Ay6QAnRQR7tE1K5levOIjIhaQguv45Sx/O/BPs7aYWTn13BWfmVmrHHxmVjoOPjMrHQefmZWOg8/MSsfBZ2al4+Azs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrHQefmZWOg8/MSsfBZ2al4+Azs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrnaxrbkh6B3AwMAZYIyLeW+wfBWwL/CIinml8BjOz9ssWfJJOB05k6VVk9eplKwFXAMcB5+eq08ysGVludSVNAk4CfgFsBZxRfTwi5gOzSOvZmpl1VK5nfMcCfwD2j4i5wEt1yswDNstUn5lZ03IF39uBGyKiXuBVPAasnak+M7Om5Qo+Aa/2U2Zt4IVM9ZmZNS1X8D0E7NDooKQhwHuA+zPVZ2bWtFzB9yNgrKRPNzj+eWBT4PJM9ZmZNS3XcJZzgYOAsyR9iGIoi6SzgZ2ArYE7gW9lqs/MrGlZgi8iFkvaBfgacAgwpDh0POnZ32XAMRGxJEd9ZmatyDaAOSIWAYdJOh7YBngDsAi4KyL+mqseM7NWZX1lDSAiFgA35D6vmVkunqTAzEonyxWfpO8uR7FXgWdJb3BcExGP56jbzGxF5brVPYylkxKozvGo2f+ypJMi4r8z1W9mttxy3epuAkwD/o80WcEE0tRUE4CTi/0/BbYD/g14EjhT0v6Z6jczW265rvg+QBqvt1VE/KVq/wPATEmXAncDt0bEuZKuJ93yHkMKTDOzAZPriu8o4Mc1ofcPEfEo8OOiXOXzNcDYTPWbmS23XME3ijRmb1kWAqOrPvcBa2aq38xsueUKvqeB3fsp8z7Ss76KkfQflmZm2eUKvqtIkxRcJmnD6gOSNpT0A9LMzFOrDo0jzepiZjagcnVunELq3DgY+LCkv5B6btcG1iO9u3tPUQ5J6wIvA9/PVL+Z2XLLNUnBs5J2AD4LfAzYGKhc+c0HLgXOiogXivKPs4z5+8zM2innJAUvAl8EvijpdcBw4NmIeC5XHWZmOWSfpACgCDsHnpl1JU9SYGalk3NB8TWATwJ7kDo0VqlTLCJik1x1mpk1I9fsLCOB24B/Ic3AMpw0Rm9lYLWi2GOknlwzs47Kdat7Ein0jgBeX+w7h/Rmxg7AHOCPpIkLzMw6Klfw7QfMjIiLI6IyPRWR3AnsDWwJfCFTfWZmTcsVfBuQruoqXqXqGV9EPAVcB0zKVJ+ZWdNyBd/zwCtVnxcB69SUeZLU6WFm1lG5gu9R0lVfxe+AnSUNqdr3HuCJTPWZmTUtV/D9EhgvqTK9/A9JszJPl/QpST8G3g1cm6k+M7Om5RrH9z3S0JX1SVd/3wB2Jc3M/L6izO2k3l8zs47KcsUXEXMi4uhiZmUiYklEHEBaWPxfge2B8RGxMEd91SQdKimKn8kNyuwg6VpJCyQ9L2mupONqbsXNrCTa8q5uRUTMBma36/ySNgDOB/5Gg9mciwWNrgJeIN2CLwD2JY0z3BE4qF3tM7PulOWKT9J8Scf2U+ZTkubnqK84n4CLSbM6f6NBmeHARaQe5wkRcUREfIY0KeqvgImSPMTGrGRyrrkxsp8yI4GNMtUHcCzpOeLhwN8blJkIvAm4MiJmVXYW8wJWnjcenbFNZtYDBnJ2ljWBl3KcSNIY4EzgaxExcxlFdy2219c5NpM0/nAHSfUmVDCzQarpZ3y1a2sAI+vsgzTt/Iakq6+Wb3UlDSVNWf8IcGI/xbcotg/WHoiIJZIeBt5KmjF6XqttM7Pe0ErnRh8QVZ//o/hpRMDxLdRXcQrwLuA9EbG4n7Ijim2j1dwq+0f2V6mkRp00W/b3XTPrLq0E36Wk4BPwUWAuaUGhWq+QOiBujogbW6gPSduSrvK+GhG/auVclVMW21hmKTMbVJoOvog4rPLPkj4K/DQiTs/RqHqqbnEfBE5ezq9VruhGNDg+vKZcQxExrkG7ZgNjl7M9ZtYFcg1gXqmdoVdYE9icNKffC1WDlgM4tShzUbHv3OLzA8V289qTFUE6GlhChmePZtY72jqAObMXge80ODaW9NzvNlLYVW6DbwEOAfYErqj5zs7A6qR5BF/M3loz61o519xYC/g4sC1pFuZ6r4NFROzWzPmLjoxGr6RNIQXf9yLi21WHpgJfASZJOr8ylk/SqsCXijIXNtMeM+tdudbc2BKYQRosrGUUHdBOhGKh8yNJAThD0pWkV9b2Iw11mUp6jc3MSiTXAOazgTeTrq42BoYVz/1qfwZ8UoCI+BkwnjRg+UDg30mLHh0PTKqeKt/MyiHXre5OwPSI6G9AcVtExBRgyjKO305a98PMLNsVn0izLpuZdb1cwTebpa+HmZl1tVzBdzqwt6QJmc5nZtY2uZ7xbQBMA26UdAXpCnBhvYIRcWmmOs3MmpIr+C5h6Xu7hxY/tb2lKvY5+Myso3IF3+GZzmNm1nZZgi8ivpfjPGZmA2EgZ2A2M+sKWScpkPQm0tsRY4A1ImJy1f7RwL3LMXmomVlb5Zyk4AjgPGBVlnZkVCYVWJs0Y8pRNJ5hxcxsQORaXnJ34FukSUI/SM2MJxFxH3A/8IEc9ZmZtSLXFd/ngMeB8cWMKO+qU2YusH2m+szMmparc2Nr4JqIeHYZZf4MrJOpPjOzpuUKvpVpvKh3xUjSwkNmZh2VK/j6gLqL8VTZjqVrYJiZdUyu4JsG7CTpoHoHJR0OvAO4KlN9ZmZNy9W5cRYwCbhC0kSK5RwlHUOapPQA4CHg/Ez1mZk1Ldcra89IGk+agKD6qu+8YnsrcHBE9Pcc0Mys7bINYI6IR4AJkt5BGrbyBtJC3XdGxOxc9ZiZtSr7uroRMZc0Zs/MrCvlenNjNUkbSlq5wfFViuOr5qjPzKwVuXp1TyENVVmzwfE1gN8DHVmFzcysWq7g2wu4KSIW1DtY7L8JeH+m+szMmpYr+EaRJihYlgeLcmZmHZUr+IYBr/ZTJkhTVpmZdVSu4JsPjO+nzATgT5nqMzNrWq7hLD8HTpD02Yg4q/agpBOAsaQ3PEpr1AnTO92EAdF35j6dboLZMuUKvrOBQ4AzJH0IuBH4C7AesAewFfAIJQ8+M+sOOV9Z2wW4jPTWxliWrrMLcAfwkYh4Jkd9ZmatyPnK2sPAjpLGAu8mzb+3kPTK2pxc9ZiZtSpL8Em6Bbg9Ik4uQs5BZ2ZdK1ev7ruBIZnOZWbWVrmC7yFgg0znMjNrq1zB921gH0kbZjqfmVnb5OrcuBrYHbhd0leA3wBPkHp2X6OYt8/MrGNyBd98lg5f+doyykXGOs3MmpIrhC6lztWdmVk3yjWA+bAc5zEzGwi5OjfMzHpG9udtkrYExgBrRsT3c5/fzKxV2a74JG0laRZwPzAVuKTq2HhJz0vaN1d9ZmbNyrXY0ObADGALUq/udTVFZgILgIk56jMza0WuK75TgZWBbSPieNI4vn+IiAB+BWyTqT4zs6blCr7dgJ9ExLxllHkEeEum+szMmpYr+EYCf16Ouuquu2tmNpByBd9TwKb9lHkr8Gim+szMmpYr+G4B9pW0Rb2DkrYh3Q7fkKk+M7Om5Qq+M4AlwExJR1M8y5P01uLz1cBzpLU5zMw6Ktcraw9IOhC4Arig2C1gbrFdCBzgmVnMrBvkXHPjekmjgY+RZmR+A7AIuBO4OCIW5KrLzKwVWV9Zi4iFpAHMy5qaysysozxJgZmVTtbgk3SIpJslLZC0pNjeLOmQnPWYmbUi1/KSw0gTE7yf1JmxBPgr6TnfLsAESR8CJkbEyznqNDNrVq4rvs8D+wK/JgXdqhGxLrAqsCtwFykUP9dKJZLeIGmypJ9K+oOkxZIWSbpN0hGS6v77SNpB0rXFFejzkuZKOk6Sl8Q0K6FcwfdR4A/AhIj4ZUS8ChARr0bEDGACaV2Ow1qs5yDgImA7UsieC1wFvI200tuPJKn6C5L2J80OszPwU+DrpFfnzgGubLE9ZtaDcgXf+sC0iHip3sGIeBGYBqzXYj0PAvsB60fEIRHx+Yj4OLAl6XW4A4EDKoUlDScF5SukUD4iIj4DbEWaLWaipEkttsnMekyu4HsMGNZPmWFFuaZFxC0RcXXlirJq/xPAN4qPE6oOTQTeBFwZEbOqyr8AnFR8PLqVNplZ78kVfJeTrp6G1zsoaSQphH6Qqb56Kp0mS6r27Vpsr69TfibwPLCDpFXa2C4z6zK5gu90YBZwl6SDJa0vaVixPYT09sZdwBcz1fcakoaSnjPCa0OuMmnCg7XfiYglwMOknu2N29EuM+tOud7cWFxsBdRbYEjAZsALNX0PERE52nAmqYPj2oiongFmRLFd1OB7lf0j+6tA0uwGh7ZcngaaWffIFXy30qEFxSUdC3wa+D1w6Ip+vdh6MXSzEsk1O8uEHOdZUZI+RXov+HfAbnUmQqhc0Y2gvuE15RqKiHEN2jAbGNt/a82sW/Tsu7qSjiNNgXUfsEvRs1vrgWK7eZ3vDwVGkzpD5repmWbWhXoy+CR9jjQA+R5S6D3VoOgtxXbPOsd2BlYH7ijGGZpZSfRc8Ek6mdSZMZt0e/v0MopPBZ4GJknauuocqwJfKj5e2K62mll3yjofX7tJ+hhp6MwrpA6VY2t6iQH6IuISgIh4VtKRpACcIelK0sLm+5GGukwFfjgwrTezbtFTwUd6JgcwBDiuQZlfApdUPkTEzySNB75AeqVtVdJ7xccD5xWLnZtZifRU8EXEFGBKE9+7Hdg7d3vMrDf13DM+M7NWOfjMrHSautWVtGGzFXqJSTPrtGaf8fXR3Gte0UKdZmZZNBtCl/LPwTeaNCh4EWlg8RPAOqRJP0eQpoF6uMn6zMyyaSr4IuKw6s+StiDNaHwOcFpEPFt1bDhwGmnaqKOabqmZWSa5OjfOBO6NiE9Xhx6kQcQR8Z/A/UU5M7OOyhV8OwO39VPmNmB8pvrMzJqWK/hWIT3PW5Z1i3JmZh2VK/juJk0E8K56ByWNAz4MzMlUn5lZ03INLTmNtNbFnZJ+QOrBfRJYm3R7ezApZE/LVJ+ZWdNyzcB8U7E+7TdJi4Z/rOqwgGeAoyLi5hz1mZm1Ittg4oiYKuk6YH/SVOwjSGP65pAWG/97rrrMzFqR9S2KItwuL35eQ9JKwL4RMS1nnWZmK6rtr49J2giYDBxO6tkd0u46zcyWpS3BJ2kI6Zb3KOC9pI6NAG5qR31mZisia/BJ2ph0dXcYqUcX0poX3wS+ExF/ylmfmVkzWg6+YpnGD5Ku7nYhXd29BPyENNX7tIg4pdV6zMxyaTr4JG0GHEkauvJG0rCVOaT1Li6PiAWSXs3RSDOznFq54nuA9NzuKdKsLBdHxP1ZWmVm1katvrIWwLXAVIeemfWKVoLvZOBPpGEqt0v6naTPSlo3T9PMzNqj6eCLiP+KiE2AvYCfApuQ5tt7RNJ0SR/K1EYzs6xanp0lIm6IiInABsCJpKvAvYArSLfCWxWzs5iZdYVsy0tGxFMRcWZEbArsDkwFXga2Bu6SdLekT+Wqz8ysWW1ZVzcibo6IDwPrA58FHgTeCZzXjvrMzFZEW9/VjYingbOBsyVNIL3VYWZNGnXC9E43YUD0nblPW88/YGvcRsQMYMZA1Wdm1khbbnXNzLqZg8/MSsfBZ2al4+Azs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrHQefmZWOg8/MSsfBZ2al4+Azs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrHQefmZWOg8/MSsfBZ2al4+Azs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrHQefmZWOg8/MSqc0wSdpfUnflfSYpBcl9Uk6V9LrO902MxtYQzvdgIEgaRPgDuDNwDTg98C2wH8Ae0raMSL+r4NNNLMBVJYrvv8hhd6xEfGBiDghInYFzgG2AP6ro60zswE16INP0sbA+4A+4Os1h08F/g4cKmmNAW6amXXIoA8+YNdie2NEvFp9ICKeA24HVgfePdANM7POKEPwbVFsH2xw/KFiu/kAtMXMukAZOjdGFNtFDY5X9o9c1kkkzW5w6J3z5s1j3Lhx/Tbk8b80asLgMu4XpzT93TL8jvz76d/y/I7mzZsHMKqZ85ch+PqjYhtNfv+VxYsXL5ozZ05fpvbktGWx/f1AVjrnyYGsrSX+/fSvm39Ho4Bnmzl/GYKv8lfkiAbHh9eUqysi+r+k6zKVq9RebPtA8O+nf4P1d1SGZ3wPFNtGz/A2K7aNngGa2SBThuD732L7Pkmv+feV9DpgR2AxcOdAN8zMOmPQB19E/BG4kfQ84FM1h08D1gAujYi/D3DTzKxDyvCMD+CTpFfWzpO0GzAP2A7YhXSL+4UOts3MBtigv+KDf1z1bQ1cQgq8TwObAOcB2/s9XbNyUUSzozjMzHpTKa74zMyqOfjMrHQcfGZWOg4+MysdB5+ZlY6Dz8xKx8FnZqXj4BtEJE2WFJKuW0aZ6UWZTw5k27qBpJ8U/+7/uYwy20h6WdLDkoY3KjdYFasPxnL+XNLp9jbLA5gHGUnTgP2AYyLi6zXHjiYtvHRdROzdifZ1kqQ3APcCawHbRMS9NcdXB+4GNgXGR8RtA9/KzpJ0HMuelHd14HhgCPCZiDh7AJqVnYNvkJH0ZuA+0uQLYyPigWL/5qQ/1IuBt0XEE51rZedI2gO4jvQ72iYiXqw6diHwCeDLEeH3t2tIEvAjYCJwFXBQ9GiA+FZ3kImIp4AjSX8zXyZpqKShwGXFvqPKGnoAEXEDcAHwduCMyn5Je5NCbzYwpSON636nk0LvbuCjvRp64Cu+QUvSd4CPA18sdp0MXBIRh3euVd1B0qqkgBsD7A78lnQF+DqqrpJtKUmTgCuAJ0hXyn/ucJNa4uAbpIpJVn8LbFjsehR4R7GkZulJ2gr4NfBXYC6wF/DJiLiwk+3qRpK2BX5ZfJwQEb/uZHty8K3uIFUE3Omkh9BDgKMdektFxD2kq+D1SKE33aH3zyStB/wMWBWYPBhCDxx8g5ak1YDPVe06qFNt6WJnk27dAD7TyYZ0o6KX++fAusAZEfGDDjcpGwff4HUWaWnArwH3AB+XtG9HW9RlIuJVoNKru7iTbek2RQ/u94CxwDQG2SzlDr5BSNL7SOuL3Eu66juU9Af8Iklv7GTbrGecRurBnQt8pJd7cOtx8A0yktYCLgZeJv0P+2JE3Ed6nrU28I1Ots+6X9GDezLwFLBfRPytw03KzsE3+FwIvAU4KSLmVu3/KnArcKCkj3SkZdb1JG1D+ovzJeCAiPhTh5vUFh7OMohIOhS4FJgJ7FI8w6o+Ppp067IEeHuvj8XKQVIfsBEwOiL6OtuaziqGQD1A6sz4DXBtP1/pi4hL2t2udnDwDRKSNiSFmkjj9er+TS1pMnAR8Atgj8H27GZFOfiWkjQKeHgFvvLLiJjQnta0l4PPzErHz/jMrHQcfGZWOg4+MysdB5+ZlY6Dz8xKx8FnZqXj4DOz0nHwmVnpOPjMrHQcfGZWOg4+MysdB5+ZlY6Dz7KTtKWk8yXdJ2mRpJckPSZpuqQjiuUdzTrGs7NYVpJOAU4l/aV6J2let7+RZn+eAGwMzI6IrTvVRrOhnW6ADR6STiSt1fAocFC9pQglvR/49EC3zayab3Uti2ISyymktT72brT+akRcA+xZ890PSZpZ3BYvlnSvpM9LWqVOPX3Fz5qSzpH0aPGdeyR9oCgzVNKJkh6S9IKkP0o6ps65JkgKSVMkbS/ppqINz0m6QdI/XZVKeoukUyTdLumJqtv4yyWNqfd7Keq4pPjnKyU9XbRrVvEXQXX5TxTlT2nwe15H0suS7q133JaPg89yORwYBlxVLG7UUERUlnRE0peBHwJjgMuBC0izSH8ZuEHSsDqnGEaaQXpv0tKH3wc2Aa6StFtxvk8CM4BvA2sC50v6cIMmbVeUfRH4OnAdsBtwq6SdasruDJwALASuAs4h3dJPBH4j6Z0N6tgIuAsYVbT3h8DbgGmSdqkqdxnwLDBZ0pA65/k46U7tmw3qseUREf7xT8s/wM1AAJNX4DvbF995BFinav9Q4Ori2Ik13+kr9l8NrFK1f6di/wLSc8WRVcc2Ji2ec3fNuSYU3wngmJpj+xf7HwJWqtr/ZuB1df5d3kl6lnldzf5RVXWcWnNsj2L/tTX7Lyj2v79mv4D5wN+BEZ3+b97LPx1vgH8Gxw/wu+IP654r8J2Liu8cVefY5sArwPya/ZXg26TOd+YXx3atc+x/SYssDanaVwm+14Rb1fEZxfHxy/nv83PgBWBY1b5K8PVV1111/E/A0zX73loJ95r9laD8bqf/e/f6j291LRcV2xUZJjC22N5SeyAiHgT+DIyWNLLm8MKI+GOd8z1WbGfXOfYXYAiwTp1jt0bNinSFGcX2XdU7Je0j6WpJjxfP20JSAPsCqwD1Fm2/JyJeqbP/UeD11Tsi4n7SSnl7Sdqg6tBRxdZrI7fIwWe5VEJn/RX4zohi+3iD44/XlKtY1KD8EoCIqHd8SbGt98zwyQbne6K2fknHAtcAO5LC6VzgdFJv9m+LYv/UKUN6JtiozfX+HP4PKagnF/WuA+xHCtC7GpzLlpOHs1gutwG7kjoFvrOc36kE1DpAvSu4dWvKtcvaDfZXrg4XQeotJgXcE8DYiHhNYEvaPmObfkIK5CMknY47NbLyFZ/lcjFpKMuBkv5lWQWrhqncXWwn1CmzKenq8eGIWJivmXW9R1K9PwuVdlXa+UZgJHBHndBbk6W37i2LiJdJPdLrkW6hJ5M6T36Qq44yc/BZFpEW454CrAxMrzcGDkDSnqThIgDfLbYnSXpTVZkhwNmk/z+X9+qxFZuRhr9Ut3N/YDzwB+DWYvdTwPPAuCLoKmWHAV+j/rO9VnyL1MFzATAauDwinstcRyn5VteyiYgvF7eDp5LGtN0BzGLpK2s7k0JmVlH+DklnAZ8F7pM0lTRUYy/SGLfbgP8egKZfD3xV0l6k53SbAgeQemiPqHR8RMSrks4jjeO7V9I0UtDvAqxF6jnepc75mxIRj0iaTnq2B77NzcZXfJZVRJxOCq0LSJ0ChwOfAfYhPcebDLynqvzngH8lDSn5KHAs6f/Lk4DdI+KlAWj2r0m3tasAx5CC9xZg54iYWVP2ZNIrd4uBfyMF5CxgW9J4xNwqV8WzImJOG85fSp6kwEpL0gTSVdppETGlo41pQNIU0hX05IgYiNv+UvAVn1mXkvQ64BOkt1Gu6HBzBhU/4zPrMpL2IfUQ70t6Nvr/IuL5zrZqcHHwmXWfg4CPkcbxnUGaCMEy8jM+MysdP+Mzs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrHQefmZWOg8/MSsfBZ2al4+Azs9Jx8JlZ6Tj4zKx0HHxmVjoOPjMrnf8PR3K1RkNfuBIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 144x144 with 1 Axes>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 153,
       "width": 159
      },
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(2,2))\n",
    "plt.bar([\"X\",\"Y\",\"Z\"],[30,60,10])\n",
    "plt.xlabel(\"Company\")\n",
    "plt.ylabel(\"Ad percentage\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to roll some random computer dice with three sides that are biased in this way. Another way to look at this as throwing darts at the histogram on a wall and having most of the darts end up in the Y column, 30% in the X column, etc... Without altering gravity, that's hard to do. An easier way is to stretch things out so that the width of each company's region is proportional to its percentage, which then flattens out the heights of the bars:\n",
    "\n",
    "<!-- this doesn't work for some reason\n",
    "<img src=\"images/ads-regions.png\" width=\"200\">\n",
    "-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAvQAAABoCAYAAACe52QHAAAAAXNSR0IArs4c6QAAAJBlWElmTU0AKgAAAAgABgEGAAMAAAABAAIAAAESAAMAAAABAAEAAAEaAAUAAAABAAAAVgEbAAUAAAABAAAAXgEoAAMAAAABAAIAAIdpAAQAAAABAAAAZgAAAAAB9AABAAIAAAH0AAEAAgAAAAOgAQADAAAAAQABAACgAgAEAAAAAQAAAvSgAwAEAAAAAQAAAGgAAAAAEx4/KgAAAAlwSFlzAAAmcwAAJnMB82x1CgAAAgtpVFh0WE1MOmNvbS5hZG9iZS54bXAAAAAAADx4OnhtcG1ldGEgeG1sbnM6eD0iYWRvYmU6bnM6bWV0YS8iIHg6eG1wdGs9IlhNUCBDb3JlIDYuMC4wIj4KICAgPHJkZjpSREYgeG1sbnM6cmRmPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5LzAyLzIyLXJkZi1zeW50YXgtbnMjIj4KICAgICAgPHJkZjpEZXNjcmlwdGlvbiByZGY6YWJvdXQ9IiIKICAgICAgICAgICAgeG1sbnM6dGlmZj0iaHR0cDovL25zLmFkb2JlLmNvbS90aWZmLzEuMC8iPgogICAgICAgICA8dGlmZjpSZXNvbHV0aW9uVW5pdD4yPC90aWZmOlJlc29sdXRpb25Vbml0PgogICAgICAgICA8dGlmZjpPcmllbnRhdGlvbj4xPC90aWZmOk9yaWVudGF0aW9uPgogICAgICAgICA8dGlmZjpDb21wcmVzc2lvbj41PC90aWZmOkNvbXByZXNzaW9uPgogICAgICAgICA8dGlmZjpQaG90b21ldHJpY0ludGVycHJldGF0aW9uPjI8L3RpZmY6UGhvdG9tZXRyaWNJbnRlcnByZXRhdGlvbj4KICAgICAgPC9yZGY6RGVzY3JpcHRpb24+CiAgIDwvcmRmOlJERj4KPC94OnhtcG1ldGE+CtQK6igAAA6+SURBVHgB7d1ZrCRVGQDgAYZZAFFZAhoWEQXRGIwGxSCLoKhEA8aHMZKID8ZEIy6JiQrGwbhigjGC+qAmgiSEQFD0QSQ+YEzUuBFcUFAiIiKOgCzCLI7o/wPtNH3Pqdvdt7q6b/dXyZm+9ddZqr5a+kx3neo1a0wECBAgQIAAAQIECBAgQIAAAQIECBAgQIAAAQIECBAgQIAAAQIECIwgsFsv78YNa+/csH7dxt68VwIEVq/Atu07tm7dtvMQ5/Xq3YfWnAABArMs4H1m+nuntw9yTdb2Vic78/fe9Mn9evNeCRBYvQL7H3v+fdGhX+O8Xr370JoTIEBglgW8z0x/7/T2Qa7J7tNfHWtAgAABAgQIECBAgMC4Ajr048opR4AAAQIECBAgQGAGBHToZ2AnWAUCBAgQIECAAAEC4wro0I8rpxwBAgQIECBAgACBGRDQoZ+BnWAVCBAgQIAAAQIECIwroEM/rpxyBAgQIECAAAECBGZAQId+BnaCVSBAgAABAgQIECAwroAO/bhyyhEgQIAAAQIECBCYAQEd+hnYCVaBAAECBAgQIECAwLgCOvTjyilHgAABAgQIECBAYAYEdOhnYCdYBQIECBAgQIAAAQLjCujQjyunHAECBAgQIECAAIEZENChn4GdYBUIECBAgAABAgQIjCuwW6/gxg1r79ywft3G3rxXAgRWr8C27Tu2bt228xDn9erdh9acAAECsyzgfWb6e6e3D6a/JtaAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQWDiB3RZui6e7wUdH84dWVuHWiN9RWTZqeH0UOLFQ6NGI3RApX00ECBAgsFRgnwgdvzT8WOT++PfnlWUrDR8RFRxZqOTeiN1YiAsRIPC4QNM5Oymjf0fFP5hU5eqdfYFzYxX/W0m/ivieLW3CZyptZNunttSGaggQIDCPAgfFRj0UqXStzjfxF01go/NDmPxQp9TmAxHfewJtqpLAvAjkOVk6dyYdO3teAG3H6AJ7RJEfRaodZOePXuWSEi+LyM5KG1ctyS1AgAABAoMC745A7Tr901i2+2CBFc5vbmjvPSusW3EC8y4wrQ79O+cd1vY1CxwVix+JVHqz2BbxXD7ulJ/y3BypVPfdET9g3IqVI0CAwAIJ5O2oP4xUupZmrM1O9nOjvrz2l9rKD4Da/s9DVGkiMFcCOvRztTtX18bkm0Hp4p2xGyKNO7ah6VabM6NeEwECBAgMJ5AfrmyNVLpWPxjxQ4arZtlc11fa2B7x5y9bWgYCBHTo4xhY6ziYisDF0eobI51SaP3kiL090lcKy5pCeavNByoZLov4tZVlwgQIECCwVCDvad8c6cKli9Y8JWKXRDqrsGyU0KbI/OpKgU9EPL9xNREg0CzwcCz+SXOWsZbmh6vZt6pNOabGRGDNEWFQG3j1z1j2jBGMmm61+UvU87QR6pKVAAECBB4XyHFPP4tU+pQ+Y/nBzLjTvlHwrkilutt8SMK466ccgUUX+HAAlM7PjOXTrjYsOpDt3yXwjvizdrBcvSvbsn813Wpz+rKlZSBAgACBmsALY8GOSKVr9Z0Rz475ONMXolCpznyowXHjVKgMAQKtCbwuavpPpNI5uiXitUeQt7YCKlp9AtfFKpcOmIwNc9/7SyNf7ak2X159HNaYAAECMydwQaxR7Tqdt1COOr0kCtSu2xeNWpn8BAi0KvCcqC3vlCid83mbzSmRTASWCOTAqtqBs9ynP0232twW9Xp28RJuAQIECIwssC5K5G0wpTf4/BSv6T7bwcbyqTX56MtSXXnd3muwgHkCBDoTyB+p+k2k0vmZsfd2tiYaWpUCb421rh08X2rYotqtNvkGc2JDOYsIECBAYDSBvA2m9qn6TbFs7ZDVvSvy1a73pw5Zh2wECLQvkINg83bn2vl5aftNqnEeBfIpNKWD6NGIn1DY4KZbbXxlWwATIkCAwAoFPhvlS9fpjH1wiLoPijy1b2S/OkR5WQgQmJzAeVF17fw2CHZy7nNX88GxRfdUDqZ8dFl+5dubmm61ybxGXvekvBIgQKA9gY1R1S2RSm/6j0T82cs0dXml7F0R9zSyZfAsJjBBgTOi7ry7oXRub4n4YRNsW9VzKLAptql0MGXsgr7trd1qk4M1PB2hD8qfBAgQaFkgb2fMb05L1+rvNbR1WqVM1rOSx182NGkRAQJDCOSvNde+OTMIdghAWcoCV0a49EaxPeLHRGq61ebj5SpFCRAgQKBFgXyyTek6nbG3FNrJb1h/XylzVSG/EAEC3Qjkj8T9NlLtfDYItpv9MJetHBBbdXfl4Mp7uH5XWXZjxPeMZCJAgACByQrsE9XfHqnUCfh7xPeL1D99JGZKee+LeN5XbyJAoHuBHAR7TaTSuZmxy7pfJS3Om8CZsUG1A6wUz0/v88dPTAQIECDQjcDp0Uzpepyx/gGuR8b81kret0XcRIDAdARq/9HOc/gXkYxHnM5+mbtW8/FItTeLwfiH5m7rbRABAgRmX+BrsYqD1+Ocz3vsT35i9b9byXP9E8u9ECDQvcDro0mDYLt3X8gW84kH+cNSpTeL/tiPI88eCylkowkQIDBdgbxO5xNq+q/Jvb/znvmzK8v+FfFnRTIRINC9wFHR5P2Reudq/2sOgn1l96ukxXkXeG1sYP+BNvh3PiYtD0wTAQIECExHYNRbJPM6/r7prKpWCSy8QA6Czcd7D/anevPOzYU/RCYDkM+bz09yegfa4Gv+OqGJAAECBKYrcEU0P3h9rs3nt6q7T3d1tU5gIQVyEOw3I9XOzW8spIqN7kTg0w0HXu+APKeTNdEIAQIECNQEDowF/4jUuy7XXvMBBi+oVSJOgMBEBT4atdfOzRwEmz8cZyLQusDxUePOSLWDrxfP+8AObb11FRIgQIDAKAJvjsy963LtdfMoFcpLgEBrAm+Immo/CJf/GT+stZZURKBPIP+XmAOqam8Kg/HvR978KslEgAABAtMTuDaaHrw+9+Z/HcvWTW/VtExgYQWOji1/IFLvXOx/NQh2YQ+Lbjb8c5UDr/8gHPz73G5WTSsECBAgUBF4ZsQfijR4fc75/NbVRIBAtwL7RnO1H+TM89Ig2G73x0K1dlJsbe3ZqPljJfmLsKU3i4cj7ok3gWAiQIDAFAX+EG2XrtF+yXuKO0XTCymQdy40fWtmEOxCHhbdbPTe0cwfI5XeDP4U8fy58RdHyq+ISnny6QmeSR8IJgIECExJQId+SvCaJTAgsDnmS32ljBkEO4Bltl2BL0Z1pYMvB3L0/9BB09Nvzmt3ldRGgAABAiMI6NCPgCUrgQkJ5O9DNA2CPXxC7aqWwJrTGg6+SwZ8NsR8bdBsPhbt2IH8ZgkQIECgGwEd+m6ctUKgJvC8WFAbBJtPD+z/gLRWhziBsQRy0MafI5U+nb8t4nkrzuD0igjU/vd5UyzzNIVBMfMECBCYvIAO/eSNtUCgJvDUWFD7wDP7WO+vFRQn0IZADnYtdeazw35SQwMXV8plXXlbjokAAQIEuhXQoe/WW2sEegI5CPbbkUr9qYxd3svolcAkBM6ISmsH3+eXaTAHyd5eKZ9fK708kokAAQIEuhPQoe/OWksE+gU+FjO1/tQvY5lfgu3X8nerAk+P2v4aqXQA3hrxvYZo7TWV8lnnsHUM0YwsBAgQIDCEgA79EEiyEGhZ4Kyor3Ybcv4S7OEtt6c6Ak8SyGegljrz+Rz6E56Us3nm67G4VE/GBgfUNtdkKQECBAisRECHfiV6yhIYXeCYKPJgpFI/KO9WOHX0KpUgMLxA/m+ydPBl7KLhq3ks537x798ilerL/7G+6rFc/iFAgACBSQvo0E9aWP0EdgnkINhbIpX6PxkzCHaXlb8mIHBA1Hl3pNIBmKOz87GUo05vigKl+jJ2R6Q86E0ECBAgMFkBHfrJ+qqdQE8gB8F+J1Kt7/OtWJZPCZxU8uvPgbvo05UBUDoA81ab41eAc3Wl3mzr0hXUqygBAgQIDCegQz+ck1wEViqQH46W+lJdxfLDUgNtV7oXV3H5TQ0H4IUr3K6Do/x9DfXnbT4mAgQIEJicgA795GzVTKBfYP+Y6arzXmsn18G0gAIHxTbfE6l0YNwc8fUtmJxTqT/b3BLpwBbaUAUBAgQIlAV06MsuogTaFtChb1tUfUML5P1cpc58jsI+buhals94XaWdbPua5YvLQYAAAQJjCujQjwmnGIERBXToRwSTvR2Bo6OaUmc+Y59qp4n/13J4/PVQpFp7uS4mAgQIEGhfoNShfySaWdt+U2oksNACOvQLvfttPAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAAECBAgQIECAAIGZEfgfFzzKLlfOxeQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "image/png": {
       "width": 300
      }
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "Image(filename='images/ads-regions.png', width=300)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we throw darts at this overall region, X will get 30%, Y will get 60%, and Z will get 10%. \n",
    "\n",
    "So this tells us an approach: pick a uniform random number and figure out which region it falls in and report that company's ad.\n",
    "\n",
    "Now we know how to solve it; let's code it up. Obviously we have some research to do because we need to figure out how to get a random number. There are a number of ways, but let's use numpy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.40538848771386793, 0.07003793298092653, 0.2307359812043256)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "np.random.random(), np.random.random(), np.random.random()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write a function called `select` that accepts a list of company names and returns a randomly-selected company name with every call. To keep things simple, let's do it for the fixed three companies we've been talking about.  Running \n",
    "\n",
    "```python\n",
    "ads = [select(companies=[\"X\",\"Y\",\"Z\"]) for i in range(1000)]\n",
    "ads[:15]\n",
    "```\n",
    "\n",
    "Should give you something like\n",
    "\n",
    "```\n",
    "['Z', 'Y', 'Y', 'Z', 'X', 'Y', 'Y', 'X', 'X', 'X', 'Y', 'Z', 'Y', 'X', 'Y']\n",
    "```\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "def select(companies):\n",
    "    i = np.random.random() # throw a dart\n",
    "    if i>=0 and i&lt;.30:\n",
    "        return companies[0]\n",
    "    if i>=.30 and i&lt;.90:\n",
    "        return companies[1]\n",
    "    return companies[2]\n",
    "</pre>\n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "As part of our problem-solving strategy, we also need to verify things, so please create do a histogram to verify the percentages look right. The output should look something like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAGmCAIAAACManZIAAAK2mlDQ1BJQ0MgUHJvZmlsZQAASImVlwdYU1kWx+976SGhBSKd0HtvAaSE0EKRXkUlJIGEEkNCUBE7gwqOBRURLAM6KqLg6FDEhliwDYK9T5BBQV0HdbChZl9gCTOz3+5+e/Ld3F/OO/fcc+577/v+AYAczhaJ8mF1AAqEReL4sCBaalo6DTcEsICIfOyBEZsjETFiY6MAYlPzX+39HQAp5psOilz/fv2/miaXJ+EAAGUgnMWVcAoQ7kLGC45IXAQA6hDiN1tQJFJwH8JaYqRAhH9TcM4kf1Rw1gSjSRMxifFMhGkA4ElstjgHAJI94qcVc3KQPCRFD85CrkCIcCnC/hw+m4vwSYTtCwrmK3gYYWskXgQAGTkdQM/6U86cv+TPUuZns3OUPNnXhOGDBRJRPnvR/3k0/9sK8qVTe1gig8QXh8cr9kPO717e/EglC7NmxUyxgDtZk4L50vCkKeZImOlTzGUHRyrX5s+KmuJsQShLmaeIlTjFPElIwhSL58cr98oWMxlTzBZP7EtEWCbNS1L6+TyWMn8JPzFliosFybOmWJKXEDkdw1T6xdJ4Zf08YVjQ9L6hyt4LJH/qV8BSri3iJ4Yre2dP188TMqZzSlKVtXF5wSHTMUnKeFFRkHIvUX6sMp6XH6b0S4oTlGuLkIdzem2s8gxz2RGxUwwEIBqwAYemNkUAFPEWFikaYc4XLRILcvhFNAbytvFoLCHH0Z7m6uzqAoDi3Z18HN5RJ95JiHpl2reqFQC/03K5/MS0L3IjAMeskNvSN+2z2gSAmj4Al+o5UnHxpA+t+MIgd08NaAFdYATMgDVwAK7AE/iCQBACIkAMSARpYC5SKx8UADFYAErBClAOKsFGsBXUgt1gDzgADoOjoB2cBGfBRXAV9IHb4CGQgSHwEoyC92AcgiAcRIYokC5kDFlAdpArRIf8oRAoCoqH0qBMKAcSQlKoFFoFVUJVUC1UDzVCP0HHobPQZagfug8NQCPQW+gzjIJJsBZsCFvCTjAdZsCRcCI8B86BC+ESuAxeD9fADfAhuA0+C1+Fb8My+CU8hgIoFRQVZYJyQNFRTFQMKh2VjRKjlqIqUNWoBlQzqhPVg7qJkqFeoT6hsWgKmoZ2QPuiw9FJaA66EL0UvQ5diz6AbkOfR99ED6BH0d8wZIwBxg7jg2FhUjE5mAWYckw1Zh+mFXMBcxszhHmPxWKpWCusFzYcm4bNxS7GrsPuxLZgu7D92EHsGA6H08XZ4fxwMTg2rghXjtuOO4Q7g7uBG8J9xKvgjfGu+FB8Ol6IX4mvxh/En8bfwD/HjxPUCRYEH0IMgUtYRNhA2EvoJFwnDBHGiRpEK6IfMZGYS1xBrCE2Ey8QHxHfqaiomKp4q8SpCFSWq9SoHFG5pDKg8omkSbIlMUkZJClpPWk/qYt0n/SOTCZbkgPJ6eQi8npyI/kc+Qn5oypF1VGVpcpVXaZap9qmekP1tRpBzUKNoTZXrUStWu2Y2nW1V+oEdUt1pjpbfal6nfpx9bvqYxoUDReNGI0CjXUaBzUuawxr4jQtNUM0uZplmns0z2kOUlAUMwqTwqGsouylXKAMaWG1rLRYWrlalVqHtXq1RrU1td21k7UXatdpn9KWUVFUSyqLmk/dQD1KvUP9PMNwBmMGb8baGc0zbsz4oKOvE6jD06nQadG5rfNZl6Ybopunu0m3XfexHlrPVi9Ob4HeLr0Leq/0tfR99Tn6FfpH9R8YwAa2BvEGiw32GFwzGDM0MgwzFBluNzxn+MqIahRolGu0xei00YgxxdjfWGC8xfiM8QuaNo1By6fV0M7TRk0MTMJNpCb1Jr0m46ZWpkmmK01bTB+bEc3oZtlmW8y6zUbNjc2jzUvNm8wfWBAs6BZ8i20WPRYfLK0sUyxXW7ZbDlvpWLGsSqyarB5Zk60DrAutG6xv2WBt6DZ5Njtt+mxhWw9bvm2d7XU72M7TTmC3067fHmPvbS+0b7C/60ByYDgUOzQ5DDhSHaMcVzq2O752MndKd9rk1OP0zdnDOd95r/NDF02XCJeVLp0ub11tXTmuda633MhuoW7L3Drc3rjbufPcd7nf86B4RHus9uj2+Orp5Sn2bPYc8TL3yvTa4XWXrkWPpa+jX/LGeAd5L/M+6f3Jx9OnyOeoz+++Dr55vgd9h2dazeTN3Dtz0M/Uj+1X7yfzp/ln+v/gLwswCWAHNAQ8DTQL5AbuC3zOsGHkMg4xXgc5B4mDWoM+MH2YS5hdwajgsOCK4N4QzZCkkNqQJ6GmoTmhTaGjYR5hi8O6wjHhkeGbwu+yDFkcViNrNMIrYknE+UhSZEJkbeTTKNsocVRnNBwdEb05+tEsi1nCWe0xIIYVsznmcaxVbGHsiThsXGxcXdyzeJf40vieBErCvISDCe8TgxI3JD5Msk6SJnUnqyVnJDcmf0gJTqlKkaU6pS5JvZqmlyZI60jHpSen70sfmx0ye+vsoQyPjPKMO3Os5iycc3mu3tz8uafmqc1jzzuWiclMyTyY+YUdw25gj2WxsnZkjXKYnG2cl9xA7hbuCM+PV8V7nu2XXZU9nOOXszlnhB/Ar+a/EjAFtYI3ueG5u3M/5MXk7c+T56fktxTgCzILjgs1hXnC8/ON5i+c3y+yE5WLZIU+hVsLR8WR4n0SSDJH0lGkhYika1Jr6XfSgWL/4rrijwuSFxxbqLFQuPDaIttFaxc9Lwkt+XExejFncXepSemK0oEljCX1S6GlWUu7l5ktK1s2tDxs+YEVxBV5K35Z6byyauUfq1JWdZYZli0vG/wu7LumctVycfnd1b6rd69BrxGs6V3rtnb72m8V3Iorlc6V1ZVf1nHWXfne5fua7+Xrs9f3bvDcsGsjdqNw451NAZsOVGlUlVQNbo7e3LaFtqViyx9b5229XO1evXsbcZt0m6wmqqZju/n2jdu/1PJrb9cF1bXsMNixdseHndydN3YF7mrebbi7cvfnHwQ/3KsPq29rsGyo3oPdU7zn2d7kvT0/0n9s3Ke3r3Lf1/3C/bID8QfON3o1Nh40OLihCW6SNo0cyjjUdzj4cEezQ3N9C7Wl8gg4Ij3y4qfMn+4cjTzafYx+rPlni593tFJaK9qgtkVto+38dllHWkf/8Yjj3Z2+na0nHE/sP2lysu6U9qkNp4mny07Lz5ScGesSdb06m3N2sHte98NzqedunY8733sh8sKli6EXz/Uwes5c8rt08rLP5eNX6Ffar3pebbvmca31F49fWns9e9uue13v6PPu6+yf2X/6RsCNszeDb168xbp19fas2/13ku7cu5txV3aPe2/4fv79Nw+KH4w/XP4I86jisfrj6icGTxp+tfm1ReYpOzUQPHDtacLTh4OcwZe/SX77MlT2jPys+rnx88Zh1+GTI6EjfS9mvxh6KXo5/qr8Hxr/2PHa+vXPvwf+fm00dXTojfiN/O26d7rv9v/h/kf3WOzYk/cF78c/VHzU/XjgE/1Tz+eUz8/HF3zBfan5avO181vkt0fyArlcxBazJ6QAChlwdjYAb/cj2jgNAAqiy4mzJ7X1hEGT/wcmCPwnntTfE+YJQDMyKWQRswuAI8iwDARAFfmtkESJgQB2c1OOf5kk2811MhcJUZaYj3L5O0MAcJ0AfBXL5eM75fKve5Fi7wPQVTip6RWGRbR8M47MWRPX3+m0HPzNJvX+n3r8+wwUFbiDv8//BEXqGkkurdCoAAAAlmVYSWZNTQAqAAAACAAFARIAAwAAAAEAAQAAARoABQAAAAEAAABKARsABQAAAAEAAABSASgAAwAAAAEAAgAAh2kABAAAAAEAAABaAAAAAAAAAJAAAAABAAAAkAAAAAEAA5KGAAcAAAASAAAAhKACAAQAAAABAAABvqADAAQAAAABAAABpgAAAABBU0NJSQAAAFNjcmVlbnNob3RfasLyAAAACXBIWXMAABYlAAAWJQFJUiTwAAACc2lUWHRYTUw6Y29tLmFkb2JlLnhtcAAAAAAAPHg6eG1wbWV0YSB4bWxuczp4PSJhZG9iZTpuczptZXRhLyIgeDp4bXB0az0iWE1QIENvcmUgNi4wLjAiPgogICA8cmRmOlJERiB4bWxuczpyZGY9Imh0dHA6Ly93d3cudzMub3JnLzE5OTkvMDIvMjItcmRmLXN5bnRheC1ucyMiPgogICAgICA8cmRmOkRlc2NyaXB0aW9uIHJkZjphYm91dD0iIgogICAgICAgICAgICB4bWxuczpleGlmPSJodHRwOi8vbnMuYWRvYmUuY29tL2V4aWYvMS4wLyIKICAgICAgICAgICAgeG1sbnM6dGlmZj0iaHR0cDovL25zLmFkb2JlLmNvbS90aWZmLzEuMC8iPgogICAgICAgICA8ZXhpZjpVc2VyQ29tbWVudD5TY3JlZW5zaG90PC9leGlmOlVzZXJDb21tZW50PgogICAgICAgICA8ZXhpZjpQaXhlbFlEaW1lbnNpb24+NDIyPC9leGlmOlBpeGVsWURpbWVuc2lvbj4KICAgICAgICAgPGV4aWY6UGl4ZWxYRGltZW5zaW9uPjQ0NjwvZXhpZjpQaXhlbFhEaW1lbnNpb24+CiAgICAgICAgIDx0aWZmOk9yaWVudGF0aW9uPjE8L3RpZmY6T3JpZW50YXRpb24+CiAgICAgICAgIDx0aWZmOlJlc29sdXRpb25Vbml0PjI8L3RpZmY6UmVzb2x1dGlvblVuaXQ+CiAgICAgIDwvcmRmOkRlc2NyaXB0aW9uPgogICA8L3JkZjpSREY+CjwveDp4bXBtZXRhPgpvtfcpAABAAElEQVR4Ae3debSdVX0//h8yI/MY5iHBkDAECFMIU0KYCfOkgmitCsullaq1q10dQNtv16q1q1olWiuCVJQZmUMCIYRAGEKADJAJwpgwC2EG/b3qs9aT03Puveece2+Se895P3/ctc9+9t7P3u/nnPf9TPuzV/njH//4/+UKAkEgCASBZhD4RDON0zYIBIEgEAT+F4FQZ74HQSAIBIGmEQh1Ng1ZOgSBIBAEQp35DgSBIBAEmkYg1Nk0ZOkQBIJAEAh15jsQBIJAEGgagVBn05ClQxAIAkEg1JnvQBAIAkGgaQRCnU1Dlg5BIAgEgVBnvgNBIAgEgaYRCHU2DVk6BIEgEARCnfkOBIEgEASaRiDU2TRk6RAEgkAQWC0QLFcE5s6de/HFF7/xxhurr776+uuvv1yflcGDQBDoBgJ/+MMf/EJ13Gmnnb75zW+uvfbajQwS6mwEpe63efXVV2+//fYlS5Z4H1tssUX3B0rPIBAElg8CH3/88QsvvIBA9957769//euhzuUDc5OjSof60UcfeSvrrLPOlltu2WTvNA8CQWC5I+AX+tJLL73//vs4tPGHRepsHKvutFxjjTU222wzfw877LCvfe1r3RkifYJAEFieCLz99tt/93d/t2jRoo033niVVVZp8FGhzgaB6mYzb4KVc80119xkk00GDx7czVHSLQgEgeWGwFtvvcUP4Ufqp9o4dcbDvtxeSAYOAkGgdREIdbbuu83KgkAQWG4I9GmF/bnnnps9e/aDDz6o8OabbzLicrYwHe666658YZ/61KfYEEtkXn/99aeeemrSpElPP/00vzbTLx150KBB++yzz/Dhwz/5yU+WLSsLr7zyyiOPPPLwww/r6xGf+MQnjL/zzjuPHDly4MCB6623XmXjlINAEAgCBQJ9lDpZH+bNmzdx4kS8tnDhwsIA4a9r/vz5RZjkDjvsUFKn6J+pU6eOHz9e+w8//HC11VZDgk888cTjjz+OfEUe7L///jvuuGPVWxd0OW3atFtuuQVvfvDBB4wdHOLaG0TfY445BucmoqgKtHwMAkEAAn2ROnHfM888c+2111533XWvvfYayhs2bJjIHkZclOqWeZMxy0gCfIcir776al0GDBhAIB0yZAgxkyw5a9YsJIgZV1111a222go5Fm9dF0+55557rrrqqrvvvlsoLJYkohrzoYce0kvfd955h5C76aab6pvvShAIAkGgEoG+SJ007ttuu+2Xv/wl2vrc5z73xS9+cYMNNiicXwIkaeIW4GOhTSO7d99995prrqGqa//3f//3++67L5Ykny5duvSGG24YN27c9OnT77rrLhRMeS8W/9577y1YsICUiiLxptCEAw88cN1113X3xRdfFMT+ve997+abb95mm22GDh1KhTdaJWopB4Eg0OYI9EU30cyZMydMmPD73/9+9OjRY8eORW2bb765kKuNNtqI+ZIG7VKmknt5+JF+TbunpJM38SYbZdF46623xpUCKhGfMTUrX7Ze9913H1MA/j366KN33313jfVy6W6cESNGkExJrDNmzCjIuuybQhAIAkGgb1EnoZJKztr42GOPIceDDjqIR4hlk7GSp2jx4sU8OQWRlWKg9vxIbJ1YFVFiwHIfFW5FuwahvNPZDYsNi1eOOlk59ULKhx9+ODW/1MrXWmut7bbb7uCDDxbqJUo21JkfSRAIArUI9C2Fnf2RHk0YVCj0bsxI3WbfxJjIdJc/XQrlSooGRNTddtttzz33LB1HRQO6tkB0oqUx8SBfkAZol47PoMmQippZOas86cZXyQxKeSd4lkbV8qEpBIEg0OYI9DnqxJIYjfbNvnn55ZdzByFTTEcgxXrMkYyPRx111JgxY8iSSBAbkknZLt0iQupY+UY14BpiA0WCBiFmUva14QIysjENsuGGG7KcVvYieJJDPQ4vv/zyy6WsWtmmqsxs6qqq9NETC7NA7a3UBIEg0H8R+D9Es9KXQb5DVQgLzQlCQnC07+233x67Fbco8mWMJxsl4iOfiuJEoPiOtFgYQCsXUrAwHrS9HymzZrprZI+gpPOhl273shcmNZS/2jAXYNjyVmcFri2eqNq7HmSE0oZQ2yA1QSAI9EcE+hZ1ku9wDY6jgLNFCno/5JBDzjnnHM5x5EjFvuyyy0QUCSfSjGUTXeI1BIdY8SASLG2g5ctApuoRqDaEU+3p/kbzLOSIUsuWZcFQRtZRS5Mp67soUPm59WsbWIh/BrWzqm2Zmn6EwKtvvffBh/X/oTa7onXXXn29tf+PAtTsCGm/whDoc9SJ2goF2d+zzjrr5JNPRqA4zkd+G+W/+qu/uuOOOx599FFMSmasi5SOxdU9/mqwl0gArvzayRCTL7zwQpRdeys1/ReBH/7u8VnPvt7r8z9j5MAzDh7Y68NmwOWBQN+iTjxFQkSULkTJw0PeLBVq6jlhUCWvN9WbDVEQO9mQOkxOJFSSELFkFUxq1LtbtiSBEjY9i7JP/Kxq72Mpn2rZoSRb24Wl1VVbzw5b2Apqb6Wm/yLw2tL3F7/+Tq/Pf+l7H/b6mBlwOSHQt4KTMCDGxI84i1GSe6eKjzSwrUg9dpOdVKI9LQs/D34UulRrl6R0C0VCkSiM68kIumBbnGgQyj4CrSJcNRRtHc2EJt6g4Lmc3lCGDQJBoA8i0Oeok2u7IDgyJo6rhaxgPWSHDXEfBtx2221Vci5xo+O7yi6FyIlkUSTtHu1qjz0NLg6UHIpVCbC4srIX/Zq0iIvxOI98qLMSnJSDQBCAQN+iToKhzTzYCgMK6yFU1kqRvC7iitAf7sOGxNI99tgDx+FHW4aqFHDOd556/EhQxbDsAAUPEidFiHKjky6ZIzWo/DbwibOl4mIzkUXJsyrvphwEgkAQ6FvUiaTEZrJvEg+RmqQeiK98ScRAUZ9i1LEqsRGpUeqRpk2TZFWUev/99z///PMEzKIL2tWdOx4z2lYkZp6YWdyihtu0rpcdSvbLE1cJsMUtIqfgeZFGJmAmYuM7FH7LWaUQBIJAGyLQgUa8ElEgElK9OYL22msvOTimTJmCHIvcH1RvuTWlNSIPikyy61x6JHexrcb8RfZZ2ndkU6b5l+k/tJcWRN9ir1G5NLIqwrVTvkg1YucSMi3sqsjUOHa4E4FJpnYohTpL3FIIAkGgQKBvUWcxp/3224+cSLoU2smNPnnyZKk5aeJoDpkSBrHe5z//eZIpdtOFBHraaafRryWdu+iiiyTvsONIJd4UwIRw1YgcwrblW6ewi3M68sgj6ebG/+53v1smnStS1XmcuKhRo0YxC8TWWeKWQhAIAgUCfZE6iZnC3S+44AJaM+pki0SjtG86NZOlbB0uWdzLoE7URqg89dRTKe/SI2FYO47o5oRTxKelXZvkSnRZvnVd0K4cH/6yeEoOwk4q83HhVpL+4/jjj5fqmGAbQ2cJWgpBIAiUCPRF6qQgIy/x8Bw7QjgllCNRokLMaFMmkVPODnk9yjUosFqSEN1l2cSDvEN4ljpPkcfCLkJoZfuiTPDURl/yqV5im1AqY6v6HLBRC1dqgkAQKBHoi9RpcmQ9ZEehdpVz7bpAeKR0u7puVnWXGHvEn66q+nwMAkEgCHSBQN/ysHcx0dwKAkEgCPQdBEKdfeddZCZBIAj0GwRCnf3mVWWiQSAI9B0EQp19511kJkEgCPQbBEKd/eZVZaJBIAj0HQRCnX3nXWQmQSAI9BsEQp395lVlokEgCPQdBEKdfeddZCZBIAj0GwRCnf3mVWWiQSAI9B0EQp19511kJkEgCPQbBEKd/eZVZaJBIAj0HQRCnX3nXWQmQSAI9BsEQp395lVlokEgCPQdBEKdfeddZCZBIAj0GwRCnf3mVWWiQSAI9B0EQp19511kJkEgCPQbBEKd/eZVZaJBIAj0HQRCnX3nXWQmQSAI9BsEQp395lVlokEgCPQdBEKdfeddZCZBIAj0GwRCnf3mVWWiQSAI9B0EQp19511kJkEgCPQbBEKd/eZVZaJBIAj0HQRCnX3nXWQmQSAI9BsEQp395lVlokEgCPQdBEKdfeddZCZBIAj0GwRWa3ymH3zwwVtvvfXqq68uXbpUeZVVVhkyZMj666//xz/+8f3331dpqA033HDVVVd1q/Fh0zIIBIEg0O8QaII633zzzdmzZ0+ePHnevHkIdLXVVrvwwguHDRv24YcfvvLKKyox5l577fXJT37SrX4HRCYcBIJAEGgcgUY57tZbb73jjjvuvvvuN954491330WX5M1C0vQwgucNN9zw3HPPnX322SNHjtxss80an0FaBoEgEAT6HQL1bZ34ce7cubfccsvUqVMx5vDhw3fbbbeNN94Yh3700UcWTENfb7316OyLFi164IEHCKf9DoVMOAgEgSDQFAL1qfPll18eP378XXfdhShPOeWU73znO5/5zGf23HPP8jGok4lz++23X2eddR599FH20PJWCkEgCASBlkSgvsK+ePHim266yeIPP/zw888/f4MNNiBdossqODbaaCNWTo15kKpu5WMQCAJBoMUQqC91UtiffPLJLbbYYtCgQYyYa621Vi1vAoXOvvbaa7/++uuU+hbDKMsJAkEgCFQhUJ86GTE50Df50/WJT3Tavril8R/+8IeqZ+RjEAgCQaDFEOiUCivXyYEu8MhVWVlVfuedd3jeV1999S7otapLPgaBIBAE+ikC9amTGr7NNtu88MILL774YmeLxK3PPvsshxJnEY2+s2apDwJBIAi0BgL1qZNfSNy7UCTx8E888UStF4i8ybHOHsrKqeW6667bGtBkFUEgCASBzhCoT51cQ0cccQTX0PTp06+77rqZM2cuWbKEbk7StKeIt33GjBlXXnnlnDlzkOyoUaOEfHb2sNQHgSAQBFoDgfrBSQMGDBg7duykSZOExP/0pz+1EZMjiPJO/LTFaOLEiQLmCaQ87Icccsjo0aOFKLUGNFlFEAgCQaAzBOpT5xprrLHpppt+8YtfZMecMGECqRNpFtedd95J9vz444+33Xbb448/fsyYMXZndu1N6mweqQ8CQSAI9CME6lMnKqStH3jggYyYJEpmTbFKFHabi9Sr2XzzzZk4jz76aImUwpv96N1nqkEgCHQbgfrUWQy95ppr7rvvvnvvvbcI+fnz51PYbbjEm9tttx1plJUzMUndfgfpGASCQL9DoFHqLBZGzCR7Dh48eIcddqCn+4hSRSOFN/vdi8+Eg0AQ6AkCzVGnJxXsmQiknoCevkEgCPR3BOpTJ7Mm42Yj62ToJH5yK4mi72yreyPjpE0QCAJBoI8jUJ86Fy5ceOmll9ZdBt60C1PeuS233HLo0KGf+tSnZKKL16gubmkQBIJAf0SgPnXyCF1//fWVJCggqXKp5S0ip6M1+I4EM+24444C6eVF3nrrrSsbpxwEgkAQaAEE6lMnKtxpp52eeuope4cEJMk+JzUn6RJL2nn59ttv26NpfxF/UZFdyb5MsZ+PPfaYBHSFYZT/vQWQyhKCQBAIAiUC9alzjz32+OEPfzhu3DiHZ+DKY489Vop4CUFEv//+97+nzj/yyCO33Xabj/vtt99JJ50kUYhTjETL251JZxf1KaqpfF4KQSAIBIEWQKA+db722mvTpk0jRTJffvrTn6aJkyILLxAJ1D4i3HrwwQf/6le/sh1TbLxDMUmpu++++0UXXUT8FEIf6myBL0qWEASCQCUC9amTe90GdgZNm4VGjBhBfy+NmwYibLJsbrXVVvfffz+GJZkiyl133ZU9dOedd6azP/PMM5XPSzkIBIEg0AII1M+cVFAnvXvgwIHCOSt5s1g/gyYCJZOSRqdMmcL0SSYtdmcW2ZVaAKYsIQgEgSBQiUB96pTp46WXXioCNit7VpW5idTIdlycTcSJRBrFqsXHqsb5GASCQBDo1wjUp06kKcRdEninXXaxVN4hFwLVXjPyJtJEnYI9u+iVW0EgCASB/ohAfepk3OQaIng+/vjjs2bNevPNN+1eL5cqXIlBkxPJXQ6l8oAN9SRQNCqMqWycQhAIAkGgNRCo7yaid0tg/Nvf/nb8+PFkyTPPPJMDvTB6+ig+ydEa7nIl2YIp27GoT9C89957QkEJobq3BlJZRRAIAkGgRKA+dQrhFJOEH8Vv/u53v+ND5wISsEkalYCOpEm6tOOIcVNKutNOO81d296lpKOtO7p9l112KR+WQhAIAkGgNRCoT51Fljmc6JCihx566Omnn543bx6iZAAtEh4TLdGrePjDDjsMV5I9eZYIm6eccopdmPaztwZSWUUQCAJBoESgPnWyVyLHM844Q7SmbUIPPvjgc889R950QpFoJOKnqHixnHasi09CqYbWXkLP888/v3xMCkEgCASBVkKgPnUWq8WJVG854T/zmc/Yt07eZM0Uv0lt5wgqCgVvthI6WUsQCAJBoEMEGqVOncmSLl4gHvbiYs1El0U0UoejpzIIBIEg0JIINEGd5foxpqv8mEIQCAJBoN0QaII6SZqi3P0Vk+TqECnbNLmPQqwdgpPKIBAEWgaBRqmT05xjXWSSvxJ3Fr71WhSYPv/yL/9SopDaW6kJAkEgCLQMAvWpkycdb954441Tp04tDmGX4OP9998nWrpVGD3BQdi055LD3XajlkEnCwkCQSAIdIhAfeqU9f3555+/4oor8CaPkOhOMfCkTonm1ltvPSo8riSHUuHFKkk0l52XHQKdyiAQBFoJgfrUKanHVVddZfe6/ekik0aOHPkP//APM2bMOPXUU4877jhkapcRYhWrdMABB9DWBwwY0EoAZS1BIAgEgVoE6lNnka+TPm6/0FFHHeXAS/uLxCSRMW0WIoTKFY8usaesxiRT5k5hnrVPSk0QCAJBoGUQqJ85ycYhG9gd2UYZt3GojHtn6KSkU89Jo2PGjJFdyX522438bRl0spAgEASCQIcI1KdOPiKmTEk9yhxIRQy8+iJEyUdGT7swRctzJXEidfikVAaBIBAEWgaB+tSJGW0i4k8vj9aQ4EOldHOScpZAED952ImclZXl3RSCQBAIAq2EQH3qRIjESTImR1CxclZOlQsWLLCZvcQCk7rUlwxb3kohCASBINBiCNR3E/H5iEOSfxMzFovnFHKOm9j4+fPn0+IJoVjVRw4lt3xsMYyynCAQBIJAFQL1qRNL7rbbbnLNlWcT8RdJFP/www//93//t6AlHva5c+dOnDhRsOdBBx3E7ln1jHwMAkEgCLQYAvWpU/jR4YcfLvTdTiGCJ2bcc889OY6cR4QxBSSxchauIVnipfXEpC2GUZYTBIJAEKhCoD51Yszhw4dzpotPKlzqQjvFeJ588skC44mi9mLS6ImiRE4tez2o0/hMAQsXLnS0nNmLghIjVZyAVLkYe0MxOyq3u4n8a6pmYvJsCNicEbaycVnW0rBLlizR1wgMtf4TGNyK/O2sV9k9hSAQBNoTgfrUiUqo565KgAYPHvw3f/M3Dm5zyDBnEYvnwIEDcevy8BEZf8qUKePGjWMTQIhf/epXzz77bDuXKueDXu16YkNwwNycOXOwITFZQNUee+whjP/YY48lO9fyoDbmf+uttxp59uzZjvYUOYA0idUnnniiR+DcZIGqxDnlIBAECgTqU2dnSBUss/HGG6MtriHbjZYHb3JAESSvvPLKJ554wlMIhh3Oh5Pq2muvvfrqq1kScB9mJ3KqdMTxokWL9HW2UhXbGgcj33LLLTfddJOAKr322WcfayHe3nvvvfjXYXbHHHNMjqXrEPBUBoE2R6A+daISaZOczoaPHLBRiRe6dBU1JFCmT3/Hjh1rg2Zls56UDXjDDTcYmUhLtmUiqBqNHCpwyi6mm2++GUt6Ogak1ONZJ9Dd86cLP5IfkWM5f/ImI4Bet99+O1X9pJNOYoKg2tsi5Vn33Xffbbfdhovp+9ZSnJxc9dx8DAJBoJ0RqE+dZLd//dd/dfw6MiqppxYyYZ7Ii+ZL2+0t6mS1tCmeVCiS1DlxKLKWOlVSz++++26Uxwb6uc99zgTIwmZIlqSzU+Tvv//+adOmOZaunD8TJw1d+lF32Wc/+9nPOpnOAvU68MADzV9OE34wJ4COGDGCGTdqe+0bT00QaGcE6ofE05H5ggovShdI0az52bEYLuuiWVO3SH/jx493ACfiRmEFtVWN4KF4k7xJJj3kkEPwY+lBst1+2LBhJEpi48yZMxFl2ddyiJwMnY5BNnghpRZ30bRUzcyjRE6b9ynv2R9V4pZCEAgCBQL1qZNGTI11dQ0ZFdjFANp1swbv4l98TZumsB966KF0cH6eDm2pnEgkU1Sowe67786AUNlMJWOlZE5yjLKZIkHLMQdSJ2umbaN4VkxVZSyq7oTWvfbaS6U5YE8G0AannWZBIAi0CQIdK+woBg8WEBRSJPogfmKcWlzc0kY6ZB5q8l2v6LaGmjx58vTp00maxx9/PPc9/0/to9XIxMykIL0TEhQGUOVGFx5AZyc/Cj9i3LQnCiGaoYVgUn19ZAooLbbFI6yCkq4vgVezuv829GJXdRXdK/8yI6D1Rkao7JVyEAgCfRyBjqnTr53AVUy9KDA7MgtyGVWtBymgVLwmZxLuoP/2PK4Ta2PD//zP/8R0sikLIO1QVS9mUrA2KsR3/DxVxE2ElLuE7FkQ5YsvvugjekWa2JkEqhdirVoUJhW76qFWzQTRCPExLPz0pz+tGsfHIse+0WpvpSYIBIH+i0DH1Mnb8x//8R/FqlCMArMjAeqyyy6rXSpmQXaIlRN81KhRpamxtmWDNeySfOLYU1J6UZkorFIHrxqEzEtn9xchorxai4Ea9eyeZUujscziTSNj0qoBfcS/uviLl5FyoePXNktNEAgCbYtAx9RJYS91c0IldNQUPFKFFBpCMSRNUZPizynX3DVVbRr/iN3YH4VbkmEHDRp08MEH2z7fBW8aGa8VFsxiJh0+ywwRqJbG9xfXFwWVbtV2MRSq9bdoXNugtoab/itf+UptPf+VaNMupObaLqkJAkGg7yPQMXUyGgqQLGbPT8JXI+6H85rNsWpJ2AfLMAtiOtmOxX5WNWjqI2GQz0cgEbukgCFun7oybMGYXdMcokSXZUsF0zaxzpixJNmyZd1VoE5XbTMbnPjoWR5qb6UmCASB/otAx9TJoy2sp1iVeHibeUiUznE74ogjOlxqwUoFH3XYoJFKhEXk/PnPfy4bk8eJ0GwkkwixsfBNMRowLNbaJdWQoEmmZctStSdQI+vauaFaQ/lLWqS5W11tm9QEgSDQzgh0TJ0ESVeBi4DKSy65hFAp+BGPLD+wUBWrpVhLF7L79re/XWnl5MEn/Ho6Oyx/lOB2/O54Tm04YbjC9eXSIS9XzhAdszPwYqFIk+dt1x6HKvMOiVjSiy9I9FKl5q4xj7yOSJn9IdRZCWnKQSAIQKBj6qyEhqp+7rnnVtYspzKaI7eKqSyETapu5YNwXKH28vgr85XjPho93xQrgV3qJFapl2nNlfxOeESCbmFMfnbh7igSFbIwOI0OHeNNYQMMEZWhnR7ETKEv3hS6VMmqlVNKOQgEgbZFoD51ltCQCqm9/uK4srK2gLm6p7nrhb8IksTb2mH5W/jcMR15E1diNLyJZwmMbAuTJk0iQkr2ccIJJxiklBNVYlVUizd1LEVpk7RlyC3xA6JHSaMldRZ2AxsxEajoTs8Kdda+jtQEgTZHoFHqJILZpY5QqMY4hWGx1qoIStLcF77whVpvUiMoYygi5FlnnVX49Ku6yOMhYskWIIyJH4stQDLYY0kmhWuuuYY3RgQVaZGAWTiXED2zqZxyqFMbXcoxdbRJydZMgVDXX3+95CYETB01wM7CsCZMmKBgIdKClIRbdk8hCASBNkegPnUy+SGR3/3ud87YwCnshgyRZM9a6sRiKIlrvnvU6U0gL+Jkh6+EoZO67RY9nfzI9lo0IySKwxdPSjHHm7/4xS+qMidJ88HmgDqlBSlHRvE+CqjiypfjQ7wqCbTInES2FRrF3spVpYH5dE+ILp+VQhAIAq2HQH3qxJtyCF166aXIBbVRbLtQyVHnCpbR8LWw9tGjRyNBtG5XD35nxzRJpKmSq0d8KOpEuOX742TnXCJ42jcl4RPJVGMNCKq6U/PRsQwgRM5SkS/7phAEgkAQqE+dxL2LL76YQIdZZCFCUoQ4FsYOZTFE5taKh5XhkqGALi+OilJP3WZSYMEkWhZZ4pVrZ2Ut7KrCUbVHnf5DmL+0nocddliZJb62V2qCQBAIAvWpk1wmTJ3Xm1KMOuWyRI6kthWMHVokACI1mZCqIpDMhJ2Uui3Vpnnyp7PMsifQyhlPET0fUYcTVmk5UsEbXK/CxkpK1Z6erm8cRCv4LedxQaC/IFCfOhEKMyLHN0e2DUUra2E4zmUanU2Ahl606axBh/X+DZA6XR3eTWUQCAJBoEME6qfXpMMSvoQBxerXIYKpDAJBoA0RqE+d5DIec/E9NPc2BChLDgJBIAjUIlCfOlkPJc10jgUPu8xyfNC1o6QmCASBINBWCNS3dVLVuV/uvPNOPmhh5yyeIpA4WDrzsHOzrOD4pLZ6YVlsEAgCfQGB+tQpJF5aDfsRnUb513/91wcddBAfN1GU/7p2AQI/NegwEqi2cWqCQBAIAv0UgfrUKU3Rz372M1HiwstZPB0ZJP4Rb3YoWhI5RQ6FOvvptyHTDgJBoEEE6lNnMRA2FO3YxaBd5wTpomNuBYEgEAT6HQL1qdN+m/PPP7/BhVHY7cZpsHGaBYEgEAT6KQL1qZO8efTRRze4PEGgdPYGG6dZEAgCQaCfIlCfOjnT6x4Q1E8Xn2kHgSAQBLqHQH3qLMdlzZRTg6fI1kxJ59TLcVkcxltkQVZDYSd4ll1SCAJBIAi0JAJNUCfGFBIva6cTKSTLENf5pS99Sd5MvCkxnQAmNbIrdRby2ZLwZVFBIAi0JwKNUqeAJPHwIpMcCmRHJhq1QdMZmVBDnfLGX3XVVdJlnnLKKbIQyUbcnmhm1UEgCLQJAvWp0/GQDvCRJf6uu+6Su5NcKRvI0qVLpVOSLh5MNHR6OlHU0UBC5SV5C3W2ybcnywwCbYtA/T3sZEyHUzr8x8kTjvc577zzTj/9dIdPlJDR0OXKxJiC5B2RRgItb6UQBIJAEGhJBOpTp3PcrrjiCrKnAycuvPDCI444Qhpg2noVHGKY7G13pI+WVbfyMQgEgSDQYgjUp05Sp4MwpUyX51hKYIW11lqrNn063rQ7k7mTF77FMMpygkAQCAJVCNSnTgbN559/nkruHDS6eVX/8qMoJQq70KUibqmsTyEIBIEg0HoI1KdO4ZxydCLNLngTLvR0l/ikxHW23rckKwoCQaAKgfrUyXtOSaeJi+Ws6lz5UVwnRzwPu/aV9SkHgSAQBFoPgfrU6UiioUOHSjrHwy6os1Yfl9Bz0aJF7tLW2UOzh731viVZURAIAlUI1KdOWeJHjBgh5Iiz6IEHHiB74kpH9RqIR4iSTt68++67Z82apWb//ffnL6p6Rj4GgSAQBFoMgfoh8U7oPeuss5DmzJkzL7roIodtiId/5pln8OY999yjcs6cOVOnTiVyOul37NixXaf1bDH4spwgEATaE4H61CnkaPvttz/ttNNo7g899JA9RbxGhFCy5/jx40UpMXHal3nooYcK/OSI7zB7fHuCm1UHgSDQqgjUp05Oc4GcJ598chH07lxMp2MyaK699tp8R24RM51WdMYZZ+y7775de+FbFcSsKwgEgXZDoD51FohssMEG9hExZdrG/uSTT0qhREMnkNrS7pR2+ZPIpJE32+3bk/UGgbZFoFHqLHJ8yHlMrhSB9M4777B14kriJ78Q3iScti2IWXgQCALthkB96hQSz5/OsokcxWwSP11VMGnA1a5Sg3BoFTj5GASCQOshUF9ULJxC9mI6TFi5FoJiu5EQJVo853tt4Gdtl9QEgSAQBPo1AvWpUzKkSy+99Otf/7q/POmIsmrBatSPGzfuW9/61pVXXimPZ1WDfAwCQSAItBgC9amTG33KlClEThTZoQO9MIO6u3jx4vvuu4//vcUwynKCQBAIAlUI1KdO5w5J/y4CaZtttpEeqTa7hxr1XO2Sw9tTxPNe9Yx8DAJBIAi0GAL1qZMyzo7JjV7rHarEgvNd/mNb3TmUKutTDgJBIAi0HgL1qZP3XBwSv3nXrvNCGu3QGNp6qGVFQSAItDkC9alT8CZxUq74rg8dote7bDHqmmHbHO4sPwgEgdZAoD512mq51VZbSTcnPon4WbtsDiJKuoQg9Prk66zFJzVBIAi0HgL1qVPSOSmRSJT87LfddlutF0j6jxtuuIFvnbZ+wAEHdG0SbT0Es6IgEATaEIH6u4kIkkcffbRTgiUzvvzyyxcsWOBETHxKGnVsEb+QE9glnSN1SrBkn7tbbYhjlhwEgkBPEJgw47lnXl7akxE67Dt0u40OGLxFh7d6WFmfOjfddFMJ5YicEyZMkHEOh0r2QYW3b50o+vTTT0sRzxK68847a3bQQQeh1B7OKd2DQBBoNwQmPvr8PbNf7PVVnz5y4EqjThk5uYm+/OUvEz8vueQSUqf9RSq51Fk5bbsU1IlMv/CFLxBOa89n73UsMmAQCAJBYKUjUF/qNEUsScw86aSThgwZMn/+fLq5YzZYNotknYLhUacj2nHrSl9PJhAEgkAQWAEI1KdOfnOnEol4d9LG6NGjd9ttN2k+7LbkVSdvUucxpizI5NAVMN08IggEgSDQFxCoT51z587953/+52HDhh3zpwuBuvrC1DOHIBAEgsDKQqB+cJJI+NmzZ8smV5yCubImmucGgSAQBPoOAvWp0+4gNk1p4Ytkxn1n6plJEAgCQWBlIVCfOiX+2HXXXcUhMXomtcfKek95bhAIAn0KgfrUKd2cQHeh74yevENJAt+n3l8mEwSCwEpBoL6baJNNNrER87HHHnOM8EUXXSTufaeddlIphLPIllQ5bzWk1A4zIlc2SzkIBIEg0K8RqE+dssTfe++9tHURndjT+RkCOcUqOUm4ljqFK51wwgmSIvdrUDL5IBAEgkDXCNSnTqeuX3jhhSVLjh8/vrMRtZH7Y4899gh1dgZR6oNAEGgNBOpTp6D3UaNGldTZ9bJp8Y7Z6LpN7gaBIBAE+jsC9amTem5/eoPUycq55ZZb9ndQMv8gEASCQNcI1KdOVGj3etej5G4QCAJBoK0QqB+c1FZwZLFBIAgEgUYQqC91Vo7igA0OdzGedmfKOCcVSHLCV+KTchAIAm2CQKPUiSvlmpszZ46/qNOWdse9iZZHnR999JFQeYGf9hrtvvvu3EpClNoEviwzCASB9kSgPnUW+YxlALnpppuuueYavClTJ7p0+CUbqDSdGPO555778Y9/7NY3vvGNgw8+GKW2J5pZdRAIAm2CQH1bp6wfEnRefPHFV155pfJhhx3mFA0bikqAJAdxusaAAQOkCHnggQcctlHeSiEIBIEg0JII1Jc6HSN88803y3aMHMeOHSvi/dFHH3VIkfoCEamVhHNK4ml/EeG09sjMlgQuiwoCQaCdEahPnbZgOkOYg2jfffc9++yzKeMOwsSkVagxcTrojeae3HRVyORjEAgCrYdAfYWdAs4F5KBg/vQuDtLAm6yfzmRnBm09mLKiIBAEgkAlAvWps3Cgy4fEmU43r+xcWbbdSBp5wmmSyVfCknIQCAItiUCnVFiuFieKQ5Kms+tMnUycVHUuo5zvVkKXQhAIAq2KQH3qXGONNejpTg9+5ZVXOmRP0UuEzcWLF4vutGtT+1YFK+sKAkEgCBQI1KdOerpA92effVY8PJdRLXsK83z66adnzZrF0Mn/zugZcINAEAgCrY1AfQ87QfLkk0+W53jq1Kk/+clPRLwvWrRICCdhkyiKTxcsWCBW6fHHH+d8P/bYYyWQb23IsrogEASCQH3qRIWHHHLIxIkTUaeoeIIns6agTkr6gw8+OG/ePOx59913r7vuuvvss89+++2XXe35VgWBINDyCNSnTiFHwt0///nPcwFdccUVv/71r/nQqe2o80c/+hEnEvFTms7TTz/9tNNOE93ZYGbPlkc2CwwCQaCFEahPnRYvJokRs5ArZ8yY8dRTT8mfxJ8uzQcP0o477rjXXnvtvffeYj/Dmy38XcnSgkAQKBFoiDq1dmwG9tx2221tV5c8iUeId4gznZipcujQoQI/xTCV46YQBIJAEGhhBJoguyLLXLIitfC3IUsLAkGgQQTqByc1OFCaBYEgEATaB4EmpE6+dQcLz507V/S7zMfcRBR2/nTRS7T4wYMHJyypfb43WWkQaHMEGqJOPnRB77IlCUJ6+OGHxXXKCWJvOxUeXe6www7Dhw+Xx7MwhsZT1OZfqSw/CLQDAvWpE29iyf/6r/+SJd6WIaBwuPOt8wuRPe0y4jWaPHmyqPhTTjnlO9/5jj3sYc92+OpkjUGgnRGoT51SxN9zzz1TpkxBlAcccMChhx5KN994443FchZb12nxkyZNssNdM652OeS77UpC05KBFocg2b/EMsCVLwIfHXuiE+GFQJFtRUTVvjMtRU2ZCQFZ7BS6JxEPGjRIoD6hWDLm2i5qTJs0TZTW98033/RfweTZH0aOHDlw4MBsKu0QtFQGgSBQnzqXLFly6623IlDxm3ZkFpxSbhlCPThOAvnrrruOIn/HHXcMGTKk29SJiw3CLODyRB/F3iNBf12IDE2rHzFiBHarfHmmYWuTLU/Tpk1DtSgYCdrm5MKk8pLg3G222aayi7JbDz300C233GJYvXRRKdH9zJkzSdNHHnkkmhZ9VdUrH4NAEAgC9amTBEcfFw9/1FFHnX/++VXBm5iFcEesI/Rdf/31995777nnntttWJ0Qh8U87r777sO/WBjfsQyQB6VbRmr4UYH8q97upsIygCgF6l9++eXXXnstEseSOhIzyZIsDHjQ3/POO++EE04oj+rUBS+j2quuugpNO2rJEoioCBqZan///fc7pQ6Z2rOfNHrdfqHpGARaFYH61InOsOewYcO4g6p4swAFf6nHO3YT4SmU1G2wkBTGPO6444455hjpmoiZyE4lRkNk+PS73/0uzVphzz33RHbY065QOj47LNam1H/zm990EIido1jPgZ3qL7nkEmzrrhna9VTMTTx/od07Z8m69CLJ4mh3PZ3s/P3vf99flLrrrrtmd2m3X2g6BoFWRaA+dWIu29hJnXiqMxSwp7vaaFmovZ217LpetBOCI1EqbLHFFpVD+agvPz6rK6Veoibc6qEkUMyIsgmSzJoasFGahsYkUJEAGtt3P336dCRYUqdexnniiSe0lO1p//33dypyIV0SouWFkuuE+GlkltBRo0Yx7HY989wNAkGgrRCoHxLvnEvCF8kODXV2eAapkD2RfEqCK2ireyAiLxRJehUrWsmbRkNeSI3wSzZcunQpCywbqHokSIv30V3USd4sJ2AEM+e2oryTMen76LWYmBFYRfXicTr88MORbMGb7qJj/ih6ugehXaaA4kFFx/wNAkEgCECgPnXSoJELEiGjIdCSfUr48CYfC7lPzDyhb6ONNipv9W6BbIvgEKJC8df4qJNEidbRHy2euFr5UJMXD0Dxp+9bAnIv5m8hDJryjZotxV+Dyl5FJeqUW8+qLbDybspBIAgEgfoKOznuzDPPJKDxVn/ve9+Tu5Nui5JIoxgTuXDs8LQ4RpiRkXnRreUBK8rDdGKPkCCKdDxnwZLYkM9dGifmAiJklTUWybKWMlaaJ7q0ClKtNlRyfi1CNIFUZpMqfZzgiYiNj5c9rva/Re0Cx//pqq33xIULF1ZRc22z1ASBINC/EKhPnTTxQiOW1ZgIhqcYE2nH9GIEJPQSNTzwwAOIxsUxrYywShQ0Fs9Ufux2QbQQjznjI5oTmcRw6XFG45VCqQgURSLBKjVfA0RJftSYawhdmrlKNOoiw1pF6XYv5+YRBZ9qQ55thDrFOdkUUI5QFkAEwNKGUNanEASCQL9GoD51Yquvfe1r5SLFq5flsoBc0CWNWIxkWamg8uyzz+4hdRocAYlYEvxEiCP28oaTfIsHkRzdpVOjSNJiJWsXDZCpene1QYWF9o1GDYsia3lTr4JSdWTlJM82Qp3kyq222qp4YuVfzEturZ1VZZuUg0AQ6HcI1KdOpGCPULd//B0SSlMwYUb7lH73u99xeXO+n3HGGXY0NT4C4iu4r3tLaLCX+Hk209pZsaj+y7/8C6G49lZqgkAQ6L8I1KdO2rGd6Q0ySC0Q3OW1lY3XcD2xAIguwkEc3+eccw7eLAKVikHIhtRhciJxspAlqwbHm+rJj2VLEij93Yoo+x2SmqEIm+RZLYmljaydHaAwBVQ9nbXU9OKjr4IlH4NAf0egPnUSGx06tFLWKRRfWGWxSck0bGf69Kc/TQrGaOV8lNklWWDxo01HteFTaEsoEopEl/aPIlldChNnocIjUDWV/KiGoq0jTd/jKm+Vz00hCASBdkagfnDSSkRHXPpll132q1/9CuvZ3/mNb3yjSDtSOSVSoRM+UCH5jhu9Sr4rRE6iKyunkADhotpjT451QiI5FKvyMuHKyjGJnAUX8y+RcEOdleCkHASCAAT6KHVK52EPJdIkddo1dMEFF4wePRrf1b4zMUmSdOA4/Ci2tEoBJ7fKToIfxSdhWH6hggeJk7vssov4TdIlP5gGlSPzidugiYvxJnsFqq28m3IQCAJBoC9S5/PPPy/Qh7xpt6VQzc997nP2StoXhPhqXxjS5HAXhsmRLTRKXwJm0YzyjjfFnGJG3YWCEjOLW9TwAw88UC/BVbfddhtxtfC8u0vkFCpgAlhVsijOn0r7QO0EUhMEgkAbIrDMaNgXFk+/xlwkzauvvvrGG2/EXAhOpjvyZqVgiAELeyURktRpZ7qd7/ZZ2lYkBNVCGEbd0oVTXhS9YfGmQPpyjXoh3AkTJojHRJ2C+ZGpSg2QqXFkGGElIJnqFeoscUshCASBAoG+RZ14E/chTengWC2p2CRHH0tpsZg0jiMwChctfOuMmGPHjqWb33zzzTIekRNRnkrbzynjpFEavcZCrMq3zuIpVt+2UZYBm9l/8IMfFKnnyJ5FL4q/FEp6sa7G1lnilkIQCAIFAn2LOrlrhNzTl7luENaCBQsUaoU+Wjw2lJcTdVoGYkWXPOwMmiRWYUz2hqoUEEqWxKpjxoyRG6nSVOquvvbmY2E7RyUHQaD6Fm4lNW5JfCfbSO3T89UJAkEgCPQt6sRobJcSFePBLt4NmbHK7kkIFe9pu72LfZOkSWhl35T7g2LuKpTxqjFtSRLYxFnESKoX4ya+NpQJEEj1NZmqLvkYBIJAEIBA36JOBCeXu6sb7+ZPMembkC6b6kuAPf5PV1O90jgIBIE2R6Avetjb/JVk+UEgCPR9BEKdff8dZYZBIAj0OQQ6UNg5tXlLuj3TBJB3G7p0DAJBoL8g0AF1SmrZtZemi7Xx84jmERHZRZvcCgJBIAj0dwQ6oM5f/OIXc+fO7d7CRFN+9atfLZNpdm+Q9AoCQSAI9HEEOqBOEY7yblTFgQsRt8FRyDp9XGyQS8CjMEzyqYuOL0zSJbLyrLPO6uNrzvSCQBAIAj1EoAPqdK6kSPKqcW1PFPlo2yJ+lILTTkcJ3Kj2ItglGXJIkSTE4iidiElhr+qbj0EgCASBFkOgA+o89dRTKzeMEzZt6fnhD38odNzBvGLFhZ3bmSMovchr6dQgyTJs4FEjJHM5HevWYrhnOUEgCPRrBDqgTmnWKpdErnSaG5Vc8jcHDcm1YY8Nd1DRxqZvxCp/+6WXXirTsC3hVWnfKodKOQgEgSDQGgjUj+uUxk0eI5ZN6YVGjRpVdeok0ycxU/52O8oJoTfccINNkK0BTVYRBIJAEOgMgfrUSZaU99eGRSnWOxtFPVsnjV6y4Uplv4v2uRUEgkAQ6L8I1KdOeTR4gfjWy2TAHa5WM1ZRLbtu1mHfVAaBIBAE+hcC9amTSs6r7vgKTnbkWLvRiBkUY0q0LmOmgyuym6h/fQMy2yAQBLqBQH3qlM1IDnaeIkmIuYwYNKseI66zyHfpr5Z4tqpBPgaBIBAEWgyBDjzsVSsUiiTK/cc//nFxyA9nERe80HcbhwphU7yno9LlCWYMdRgGq2jVCPkYBIJAEGgxBOpTJyo84ogj8KNDflwLFy4sPEJ0c/o7f7qQeNIoeVMzLnjOohbDKMsJAkEgCFQhUJ86Rb/bk07wVLjuuuvYNB2AwRfE6GmzJssmDiWZnnjiic6tdOBP1QPyMQgEgSDQegjUp85izQ6GtMnypJNOopiTQAmbfO7MmpR0dClOHnvmOIrW+35kRUEgCHSIQKPUKd+H0HcuI/o4GnVimmgkOy/V2LS+xRZbaCCikzpvZ1HlAWodPjWVQSAIBIF+jUCj1GmRNl/iRDKmq1xzEfX53HPPLVmyhCKPOm3WdH562SCFIBAEgkDrIdAEdXa4eE52dHnHHXfceuutthKJ8TzkkENCnR1ilcogEARaBoHuUCcHkZQfc+bMmTFjxmOPPea0dAHzpE5i6dChQ6nwLYNOFhIEgkAQ6BCBJqhTSqQiQaesnSRN1CnRnIxzQuLZNwthE3V2vdW9w0mkMggEgSDQvxCoT53ikJAjv5B9lg7euOeee8TGo04edvXFXqPjjjtuzJgxQ4YMSZ7j/vX6M9sgEAS6h0Ad6qSbU8YFJE2cONHfefPm4VDiJ4qUZW769OlikkaPHn3OOefIG5/T3Lr3DtIrCASBfodAx9RZZIafNWsWMZNWXmjoPEJkTCGcu+yyi7M0sKeEIPJ4crs7bENgfL9bfCYcBIJAEOgeAh1Tp6D3CRMmPPTQQwyaot9tV7cdc4899kCacsUPGzaMsElbHzdunGye3XtwegWBIBAE+i8CHVPnnXfe+a1vfcuqnO9mFyYX0DHHHLPrrrsOGDCgXCrqLMspBIEgEATaCoGuks7Zou7wywMPPPDQQw8lb8YF1FbfjCw2CASBLhDoWOoUYORIYSZOoiXXkIBN+4VEINnGTlVn8WTi7GLQ3AoCQSAItDYCHTPg4MGDHSksxRz2lOFYQBKRk8JOcz/ggAO23XZbh7th1Zyl0dpfjqwuCASBzhDomDpFaFLV7UbnYb/vvvtQp5PdpkyZgka5jMS9i0ziNXrjjTdkAOls6NQHgSAQBFoVgY6pU4Smi2gprZyE8FhSDDzNffbs2cjUXnXpjfnf/SWNOm2YOq8lVm1VmLKuIBAEgkAlAh1TZ9lCijnXbrvtJqjT0UMPP/ww8VPoErpEoMLjuZJsY7/++uu1ocjLPudKjGcJYLOFWc+89uqbvRm6sNqqqwzdbqMNP7lmszNJ+yAQBLpAoA51lj3FvSNHlxrBnrT4m2++edq0abJ++OvCm6Ll7ciUK97OorJjCk0hcPld8+6Z/WJTXbpuvO5aq/+/z+2/18BQZ9c45W4QaA6BRqmzclRmUKLofvvtZzfR448/ThR1vfLKK/feey9plHYf6qyEK+UgEARaD4HuUCebpkt4vKPcRCyJmR8+fHixX5PjiArfejBlRUEgCASBSgS6Q51lfzZNvOmip8vaKX0n8TOR8yU+KQSBINCqCPSIOitBIX6SQw877LAc7lYJS8pBIAi0JAK9Rp0CPF050K0lvyVZVBAIAlUIdLWHvappPgaBIBAEgkCBQKgz34QgEASCQNMIhDqbhiwdgkAQCAKhznwHgkAQCAJNIxDqbBqydAgCQSAIhDrzHQgCQSAINI1AqLNpyNIhCASBIBDqzHcgCASBINA0AqHOpiFLhyAQBIJAqDPfgSAQBIJA0wiEOpuGLB2CQBAIAqHOfAeCQBAIAk0jEOpsGrJ0CAJBIAiEOvMdCAJBIAg0jUCos2nI0iEIBIEgEOrMdyAIBIEg0DQCoc6mIUuHIBAEgkCoM9+BIBAEgkDTCIQ6m4YsHYJAEAgCoc58B4JAEAgCTSMQ6mwasnQIAkEgCIQ68x0IAkEgCDSNQKizacjSIQgEgSAQ6sx3IAgEgSDQNAKhzqYhS4cgEASCQKgz34EgEASCQNMIhDqbhiwdgkAQCAKhznwHgkAQCAJNIxDqbBqydAgCQSAIhDrzHQgCQSAINI1AqLNpyNIhCASBIBDqzHcgCASBINA0AqHOpiFLhyAQBIJAqDPfgSAQBIJA0wiEOpuGLB2CQBAIAqu1OQR/+MMf3n333eeee+7ll19eunTphx9+uPrqq6+zzjqbbrrp1ltvvd56633iE/nv0ubfkSw/CHSAQFtT5x//+Ed0uXDhwquuumry5MkKb7/99ic/+cntttvugAMOOO2003bbbbcNNtigA9hSFQSCQHsj0NbU+fvf/37q1Kk//OEPkeZaa621++67b7TRRq+99tpLL710/fXXz50797Of/eyJJ56ITNv7S5LVB4EgUI1AW1PnY489dvvtt0+bNm3gwIEjR44cPnw4GfONN96YPXv2+PHjH3/88bvuumubbbY58MADV1utrYGq/tbkcxBoewTalBGo6h999NGkSZPuuOOOVVZZ5fjjjy/U8+L7MH/+fJLmr371q/vvv58cuvfee6+77rpt/1UJAEEgCCxDoE19IHiTX+jJJ5984YUXttxyy4MOOmjnnXcuUeEgwqTkTe6jBx98kAH0448/Lu+mEASCQBBoU+rkVcebbJprr702E+cWW2yx5pprlt8Gdk98SovnasewCxYsePPNN8u7KQSBIBAE2pQ633///aeeegoh0sQHDRqEIiu/ClR4TLrVVlsxfSLZRYsWccRXNkg5CASBNkegTW2d4jcXL178zjvvkDpRZKXIWXwhsKfQTnGdb731FqVey66/KB/86aptoyNl3+W+oWobVNV88N7bH33wblVlTz5+9IkP33576VtvLZOpezJa+hYIfPDeO737moph33vn7Ua+JC35Fnr9m1+g9P679SEtArr9SEV5N45tm1JnEQnP4kk3x56rrrpqFWSo06011lhDS/SnZVWDqo888jfeeGNVpY9sAiwD3ooGr776am2Dqpppc19a/Hodmq7q0vXH1Vf9xA+eunHT9dfqulnuNoXAvXMWv/Lme011aaTxb57ccMbNGzbSsvXa9Po3v4Doutnrz5+4cddwEaQeeeQRBLr55ps3zp5tSp2gLP7JoMjOAo/sI3K3bNk1+iTThx56qLYNFxM5AjUvWbLk4Ycfrm1Q1nh/4kzffOeDVVdfsxcjSa1g/pwli1ZrU8tMCW9vFWgP7Dy/f/uD1dbozddUTO/lZ5a8vaRNf5LvvPPBWh81IfTVfaGiaLypuYv/8NL8tddff/0utgWiAi21rztmZYM2fU8gKJgRXoCrRKQs+/9ToIn4usC9aL/JJpsMHjy47FsWmEo33HBDmzvp/gplfW1BKP7zzz+P4bYbsOUuu+xS2yA1fQEBaoR/k5SUvKa+8Dq6mANNkSzpZ/Xxx2vssMMOlMvOGvulb7bZZuQkP+FaBbSzXm1KnagQlORNvFmYI6sAQppcSSTBomVdQI866iiR81WD+OitFNRsnK4HEZ//7W9/W5exY8eed955tUOlpi8gYPvZhRdemNfUF95F13OggF900UWPPvqoUJl/+Id/EEXTRfviR8pAV+Ux7qJLm1InMRCUYLJ3iL+IFlaFEepkmqRrazlgwIC6gPLUu6oGaeojWcazdKFcCI1qqm8arzAEqBd5TSsM7Z48CHX62XpZhCQ/9l7/TbWpCYxLffvtt6dEs0WKUqpyoONNZPriiy+ygHAWyQbSQ1rsyTcgfYNAEOiDCLQpdSLEIUOGMHCQK2fMmMEgUulDp6cTOUXC89vYiPmpT30q+ZP64Hc3UwoCKxGBNqVOYjzeZBUW1Em6vOeee+bNjanjewAAGJJJREFUm1e+Bvsvr7nmGn+33Xbb/fbbj7+7rpuo7JtCEAgC7YBAm9o6edPo7AcffDCH6RVXXHHLLbewjMicxM5ISZ81a9att95Kix89evSxxx5LRC2ilNrhC5E1BoEg0AgCbUqdBTS4EmNybT/77LM33XSTLHN2ENm0LkgIpUoIcuihh44YMaJwCzSCZtoEgSDQJgi0NXWyYMqZxGcqsbH8cjj0vffeI2NyxslwfNJJJ+211169GJ3eJl+pLDMItAMCqxRR3+2w1A7XWMR1yhIvNoiqzkFExuRPF5C044474taugzE7HLN7lRxT9913n76eu+uuu3ZvkPRa3ggIZSu2jeU1LW+oezg+x6+MkX5WrHD77rtvFyHx3XtQu1Nn91BLryAQBNocgTb1sLf5W8/yg0AQ6CECoc4eApjuQSAItCMCoc52fOtZcxAIAj1EINTZQwDTPQgEgXZEINTZjm89aw4CQaCHCIQ6ewhgugeBINCOCIQ62/GtZ81BIAj0EIFQZw8BTPcgEATaEYFQZzu+9aw5CASBHiLQ1nvYe4hdD7s7QXPOnDkOL2pkHCnyJBjdf//96+arb2S0tGkcgXvvvVdeGJt0bebzCuzQre0r9YGUr/Jv2fa3zTbbOG1l4403TqLCWqCWX42kkXJQ+OsFHXLIITvttFPts6SRnDRpki3X3tGwYcOcANaTbdahzlqEV1DN5MmTpWtywkdnzyvOR5JuWYPdd9/9jDPO8L5DnZ3BtZzqn3jiid/+9rfY87TTTjvzzDPLAzbKxxVnsUgf86Mf/cjbPPzww2XbcoRfqLOEaAUUnDg7ceLEa6+91ukPfiNEDWdAVD63yJF28cUXP/3005JJaiCFeaizEqJ+U3YMnLfbhdTpkA//RckyzoaTwmDrrbfu7NzjfrPmfjhRCbRIlPSDK6+8kkQzaNAgCbAr1yHNxMyZM//pn/7Jb/KII4740pe+JPNW3lQlRCugfMABB2BPL8I5buPHjyf1jxkzpvK5Tse8/fbb/d1tt938ezvssMN6mEwyUmclvCu0TAGUErTyYI+qxxNLfQ8INbLZ00EkZu717C9VT8zHWgRkz/KzJG/+z//8z1133YUWv/jFL5JWyuzX5E2/Scm39txzTwlevSxZtGvHSc1yRcD/KvjTDCTbnTZtGql/jz328Nchl35itIEJEybcfffdhBX5JBm+esib1hLqXK4vtKvBGVxcHbYo5E0nf7gcjnTMMccwnzkTtcPGqVyuCPhNDh06lOzp35iU2CQav0lZAekBxRlWfpP+yfkpekf+w5F3lut8MnhnCNAGaOJMK3feeac34jURPP2rY/Kiy+NN2sOoUaNUdmgJ7WzYzurjYe8MmZVWTz33T/KGG27wm5Ss3u+WyMN8ttIm1PYPZt8k0Rx99NEKCPTyyy/navCaHKdKAXSw1aJFi7wm1Mkk3fZorTQACJgMnZ/97GcZMR1z+/Of/5wq4Jgc//Auu+wyNmt3P//5zzO59IpaEKlzpb3pzh7sZynnMYM31WPvvfe+4IILyJuxnXUG14qpl/361FNPlefYgQJCI2h8fqjc7pdccsn8+fP5ar0mh07HNbRiXkdnT+Eg4kplNnn99deffPJJfoK5c+f6Hc2ePZurQD0rGXWhs+5N1a/6j//4j011SOPligCdgkHt17/+NXGGxsGrTlv3svObXK6w1x2ccZPhjN3ZC3rggQe055Tw4xQj4VBVAikrW7zqdWFc3g38TPgDCJVsKZL5I1D+PbzpwLHjjz+elZMluide9cr5R+qsRGNllv0s2bMdxnnHHXcwzWyxxRZHHnmk32Rv/ZNcmWtriWf7yTlZ2o+QX4ha4E0RRemDbCnMZ3T5llhlKyyC4Mnk5XdE5HzrrbccL0Yt4FLfZ599enF5sXX2Ipg9Gsr/yVdeeYUCSB/0n/PLX/6yc4w78yP16Enp3F0EHJhKVf+zP/szL4iezpTGX+Q/HErt7pDp1/sIsKUwaJ511lmbb745k7T/al4Za3WvmDjL6YY6SyhWZsHpcgzb//7v/04Z5KJFmkLPdthhh+jpK/Ot1DxbQBKT2cknn8ys6fdJISh0wFiia6BamRV+TazSnOxkT8qcvV7Ez2JrSS9OK9TZi2B2fygiDP3iqquusueBJds/TB7bqOrdB3S59fRSxFQTP1Enp4TjppWX29MycHcQoA0wqjgOk/W5kD+mTp0qWt422e4M10mfUGcnwKyoav8V33//fVtr7fYTReFNUwC5hrLhckW9gaafQ/Zk93QpCOeMZtA0gsuzA5FzypQpNikQOUkhNpLYczljxgy5CMQn+bn11sPjJuotJLs5jtjAW2+91ZtesGAB3hTCyZ7dzbHSLQi0NwK2NVPgCCIc6+LeTzjhBPEPNhf94Ac/ELjCrSfwltfIv72e4xSps+cYdn8EGsT06dN/85vfCLS2a+jP//zP8aaX3f0R0zMItCsC5E0x0VINCEuy4fIzn/kMlzqLinBOngM79EijgsnESPQKQqHOXoGxO4N4l6zXt912my1i/IBiXM4991z/KnvlX2J3JpQ+QaA/IyCKU9452/BsVRCfdPrpp9uFSca0o4Q3j0rHIIZYqXccRz1faKiz5xh2cwTZA+12GDduHJ39uOOOO++88yTm6d34iW7OLN2CQD9EwC6SX/7ylzbFihWjqu+4445FuhzOIr8vRk8KOzHF/mbs2fP1xdbZcwybHoGMSeS87rrrmDhZZzCmoE4eQGTa2Vi+BILkpdoNt3YGUerbGQE7FCQT8CPya2L1kuyqdN/x5q211lryAZJGf/azn9HzRJjJFUKpd6vboIU6uw1d9zsyyghCYr32ppVd9orJ9NHFiMJ6WW0oHaHOLlDKrTZEwM+HAi6jlUBOEgkBc+TIkTJ9VEFhW7PQzocfftj2WamVRObKotST1HOhziqEV8RHUqcNfF45HnTZK4ZDu34w35FwJd+Mrpvl7opBgAVNHk8xnkWI0op5aJ7SIQI0NlZOvGlTiZxJ55xzjm2XtS1p6wJy+Y5kVBKlROHDsD2hzlV6MdCpdrqp6RABmHvf1HOk2WGD2krvmH6R9OO1yKyUGgY1785LsVOWLaXUDVfKZNr8oX5Nkj8888wzxBGKOWXc3w7fiB8dwdN2Z138mogjHTZrEM9QZ4NApVkQCAJBYBkC8bAvwyKlIBAEgkCDCIQ6GwQqzYJAEAgCyxAIdS7DIqUgEASCQIMIhDobBCrNgkAQCALLEAh1LsMipSAQBIJAgwiEOhsEKs2CQBAIAssQCHUuwyKlIBAEgkCDCIQ6GwQqzYJAEAgCyxAIdS7DIqUgEASCQIMIhDobBCrNgkAQCALLEAh1LsMipSAQBIJAgwiEOhsEKs2CQBAIAssQCHUuwyKlIBAEgkCDCIQ6GwQqzYJAEAgCyxAIdS7DIqUgEASCQIMIhDobBCrNgkAQCALLEMgBG8uwSGmlIPDaa6/Nnz//8ccflzb/jTfecM6do0ekXt94441lxXdkwuDBgx1plzOWV8rbyUM7QyDU2RkyqV/uCDih0HkyDzzwwIwZMxxs58gKpzY5pND5B4hytdVWcwSQkwudZ+d4WGccLvcJ5QFBoGEEQp0NQ5WGvYqA82Tw5m9/+9vf/OY3L774olPSSJdkzM0339xRd86QIYrOmzfvwQcfvPfee0888cRQZ6/Cn8F6ikCos6cIpn/3ELjvvvtuuOGGX//612TMsWPHnnXWWXjTYVvOSiN40tnff//9V1991emv999/PzLt3lPSKwgsJwRCncsJ2AzbKQJo8e23377nnnsch+30eaSJOg866CBnzVcZNJ03qZLO7ozDcjiHbj/99NNk0meffZZwSsd3d9NNN3X0NrmV0Fp1zOGNN964YMECB/8ec8wxTp11kKzzLPEyg4BeDpgdOHDgRhttZBy3XIY1vTXWWGPAgAHY3LXhhhuWT3fsojk7ilb3oUOHssYSjYnPLLbFOYvm7Mhv9cy1Za/i+GjTdi1ZsmTp0qWFSbeY+aBBg5x/6ymVy3dwNMvv1VdfrdK6zJNNY+HChZ5OYGfK8Ig999zTAZDKxYPMfM6cOf4naeyWdZUTKAqOhHz55Zevuuoqr8Dkjz766KoG+dg4AqHOxrFKy95BAG3hMrLk3Llz+X9OOeWUww47jFOodnTCpt//DjvsUN7CJvpiLoo8HkFACAuL6Y5fDj/88AMPPFB7cmvZBXWOHz8eS+Ky559/3nONgBzRB7YaNWoU4tYXJWnmLh7EyO6izv333/+0005DQ07xLgZEnehv3LhxCPqoo47CX4899hjCJSDjdFTo6UccccTo0aN33nnnddZZp+iFs1544YU77rjD+KwTqNM4GNDM/W9Atabhn8dmm21WngyOOpHsj3/8Yw9yV5nhYtasWbpbtY442gTQH3IvHgQcsHzve98zgS984Qu11KnBo48++m//9m+Wc+aZZ4Y6yy9JNwqhzm6Ali49QoA7aOrUqVgMc7FgohhCXxcjVspieIrQRM1HjkiK+whbkSJJZEjBhWK+/vWvY5bKAdEravvJT36Cj9xCiLgMRU6fPp306q5xbr75ZgxotGHDhmkzc+ZMzO5xWIYddvfdd68cUBkN4cEnn3yS3LfTTjsZEzka4e677+b4wow4FyMXvbCqWxMnTiSiWu+OO+5oWM/Fgx7E2jthwoTvf//7I0aMIDVXPQjLs1rceuutBGdHhx966KGY10qxpPkDB29iT71Ir3vvvbePxjQxom6VAE4snTJligGHDx/O+Vb1oHxsCoH/8w1rqmcaB4HuIYBH6JU0XJS0zz77+FspJHY2JiLAtnR8JILaPv3pT5O50BZ2QCU47vLLL0cNd911FyIjxlZq2eRcl8YnnXQSjiOBoi2j4ZHLLrvslltuERqlwemnn456iIHGFClFCCX0oUJkV0udixcvNg1y7pFHHjlkyBCERRjEtvjx2muvJepS+b/1rW8VS8PIaPQv/uIvULbx3SqkS11wNyFa++uvv55cbLQqBPwz0B65lwImcRU5Wukvf/nLyZMnW1dBnYR03GrtiBVHa8MOoG85oP8WkyZNKrR1onRZn0I3EAh1dgO0dOkRAkQ/0ha5rDBQopVGhvODR7go8pVXXiGrjhkzBkcU9kQ8SPEnBhLfSFv0YlJVJXXqi8KIk7rgoEKMJfqxEuJHXUwJZxHoyGIFqdF2SWfXXHPNM888Q6qtnSH+MnP2U2NS24sGzLK6kwcp9URCRgACdUGUCK64W6rkRZfiQcRw7dG6tVT9I/Eg8uZxxx1HbS8fpKAlARzzuoqhMD5Iaev/a1J9+mnCL8G8pE64MXG49PVQ5ojaRaWmcQSym6hxrNKydxBAZCI6sZVfNRtlFZV09gwMIvwTI5BSWSfJU6UfBtegAzIjjZWMxgHFJlA1DgUZ++y6666l+o+PtNeR8GhMYixCKSeDVUlwpDnSKOeSOdcOSLw9+OCDjVDeYqwkzfHSeAq5lRDqP4S7SM0EUC3ZGSObHnNqcWlJScdxpGCTr32QmZjnscceW/kgxEeMRZTmhqDLCWBq/1Tc9XQydfH04q7JuAptvZJSy74pNIVApM6m4ErjlYYATkEHTJYYk1+lyq1EVyXWoQw8SJXGSgU1F9NFiIjSXfxVuQCMRjjFaMbEklV3jYmb9KVWE2mxkvZld7d00aasKQqG4rymMjMj8EdhvVL+JR6SBFlIGRbYKwyLSQmPWqI/NOdCbaZaKXhaKY+QdVU9yMRwLh2cAaS8ZS1o0QRIlyykzK9GK5xIPO+8TMq4FemXXVLoHgLV76N7o6RXEGgcAXIWSQoXECSJn/420hfFENbQREGCBR2UHXENGdYtzIWJsBKrYqmrepb2aK6S+/QtepmPBpixFDmLYTUuupghIjaB8nEKBkRq+lZWKhuE7GkaeBDhFqtTZm247bbbKOboTBuXETzCHFyWZs7Fg6oGNBROr5q5NsX0zAr/ll1UYk+mCZYNrjNGAMQtbMvg2BxB+wdDKDbDsksK3UMg1Nk93NKr+whgDQIg9kQoLIk04gbHIniiCUSDE2upxCAY0KVQtCyH1VgXHcuasvC/vLXKKgUNlZVloXgKejJgFXW6ZSH6lo2Lghr17lb2olbzHXHiI1NGA9YG1oAy/p+xlckVe1pd8aDKYa2o/B9Q9axyelX1TL1Ik32DK4lJl2OKcOoppoRVt9tuO+BXdcnHZhEIdTaLWNr3FAFiETWWeRGPEI6YIBsZEZvoiJWQi46Fn7qqI23XpbJoWXW3dz+SQwuyqxrW9ApLLoG0kCsRFjsDjxMzAi/53/7t35q8GZb8KGxg2rRptQJs1ciNf2QGdSFcQq4YAO4pfn9zQJqHHHIIMbbxodKyMwSW2W46a5H6INC7CJC2/ID9nsliYmuE0aDCLh6BjFwkLJIatZruyWanb2UXRMbHQiGl87IA0tw7k9Qqe/WkjImYMmtFZtMTwml6JDtmRzylDdLUnoIvzsnCKdHqsacLY6JgTnxL6Ml8Kvv6B8PlZXeAkRkK+IsIvOwYKgXee2hl45S7h0Cos3u4pVf3EfDTxSA0Ry5jnh/R4JwnyKXSZleMzl4pjMlduieKIUlhTxSAcGn6hRmxaIl8EYRKZkExmNi5UGa7P8t6PYmWXDG0YDMv25qbGABGRjZZ9kTCNYokXRb6O/FTuVK6VOM/h6jSgvTLcXpY8BT2TSzpWaCDsBhP/3VQJ+IubBo9fES6R2HPd2BFI+D37GdM8MQXfM2CE0lqBDFEg1VL+x0mxUpiJEWM03AF/Qi61IaHWhA75kUERTg9DiUASsLEoscNIv4RdS7vVZmzyWMlc2C7NG0TNgHTI+jxL/Fim22hlZuPC7/rIr6y8JJpT9JkjhR1j2pr/3P0ZAkoktRJ+mb0NA6Hvjgq/3tMrCfDpm+JQKizhCKFFYqATYckMqql3UE20jz00EN+2OgGS6qkaWIZYh0hTjMbhxAu/dfecLFHCOtHP/qR+E1RSrhAS+5jZlOMjCBsii/jgZbfkni6XFdeeSUZE3WibP8JWBKEBLG3nnrqqaZR8KY5mNgJJ5wgVh/pm61pIzUiKpIlKXOXqaHm9+JsmVlNyWYtMUkiRo2MSfnWe/ERbT5UqLPNvwArbfm4g69ZEgoERJ1k7KO64hG8iXGIYGRJBXyKVuieJkom5Tt2Cy+Q7/AOGiLuEQA1pqfbZWRTkAEL0XW5ro3h0sQ8iBGTZEc6RvdIUD1+5/uyO7OcACq3B5SmTCYVl45krcU/Awss9i/5D0FwLtv3vGBibBe2JxnZ49h/IQmZno+cEQoEQp35Jqw0BAiY9j4S2QhuDJrYUEo07MMphBzZCnmEKeYuMeHFLImlWIDFk0sa4SIFjYuWiIxgRYuv4k2UwS6pTW1EDldScZeAVosCFdvcqNLakG1LEbJoiZhQ/8iRI4mZjzzyCKOt0QTJqxRzruB/QzmmoazUBCxE48LHRdM3MvOCkantmJSCb5DiQT5qb9sowoWDj+Vo5QQYMZCySVbdKj76JyQySQMX8ZPMXjmlDruksnEE/vcwg8Zbp2UQ6HUEfAPJjC4kSKIsvpDoAwO6EIdLoXxu2V6Xwj6oMWZxIQt/y5ZFgUzK3WSEIlSo8q6hMKO7etUSq/lwjnuKYQmJBaOxVKLsCy64QM25555r96eOxeSN7CmGQn/+Fu0rH6eZZ/lbrlGzQspm9FSvYyVHWx3d3zjaqK8cStn0LE0bd9k0qu76yFIsuckVV1zhv9FXvvIVmfb9y6ltlpruIRCps3u4pVevIVBQg99/gyM22x6tdMgsHmeoLu7iNWzb9ay0waFdtynvFv8Gyo+VBbcqPxZlRExcra0vajya5NvZXcRKthUxKkSBKYMgzN7aWePUdwOBDl5YN0ZJlyAQBPoCAsRkRg9WV6YMfieuM0Ix6hSr1Pg/p76wkL4/h1Bn339HmWEQaBQBVl0udZ4opMmN5iMPm7R4TAGNDpF2jSEQ6mwMp7QKAv0BAfZN53C46OnkTfEGPPt8Tf1h7v1sjqHOfvbCMt2ViwDrJ1f1eeedxzrJ9d+4oXPFTJsznYxphlxD7KRc9mI5ufJXzNPb6inxsLfV685ig0AQ6B0ElsV89M54GSUIBIEg0AYIhDrb4CVniUEgCPQ2AqHO3kY04wWBINAGCIQ62+AlZ4lBIAj0NgKhzt5GNOMFgSDQBgiEOtvgJWeJQSAI9DYCoc7eRjTjBYEg0AYIhDrb4CVniUEgCPQ2AqHO3kY04wWBINAGCIQ62+AlZ4lBIAj0NgKhzt5GNOMFgSDQBgiEOtvgJWeJQSAI9DYCoc7eRjTjBYEg0AYIhDrb4CVniUEgCPQ2AqHO3kY04wWBINAGCIQ62+AlZ4lBIAj0NgL/P14AdQANOUXcAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 9,
     "metadata": {
      "image/png": {
       "width": 200
      }
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# WHY THE HELL DOESN'T THIS WORK:\n",
    "# <img src=\"images/ads-histo.tiff\" width=\"200\">\n",
    "from IPython.display import Image\n",
    "Image(filename='images/ads-histo.png', width=200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "plt.figure(figsize=(2,2))\n",
    "plt.hist(ads)\n",
    "plt.xlabel(\"Company\")\n",
    "plt.ylabel(\"Ad percentage\")\n",
    "plt.show()\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: computing histograms\n",
    "\n",
    "In the previous exercise, we used the histogram functionality of the plotting library to compute the number of X, Y, and Z company values in the `ads` list. Now, let's figure out a way to efficiently keep a count for the company names in the list, without relying on built-in functionality.  To make it more interesting, we're opening up to more than just the three companies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "companies=[\"Google\",\"Apple\",\"FaceBook\",\"HP\",\"SAP\"]\n",
    "n = len(companies)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subproblem: arrays as indexes into numpy arrays\n",
    "\n",
    "As a subexercise, how would we get a uniform random sample of 5000 company names from this list? To get you familiar with the vector-based approach of numpy, let's ask for a list of integer indexes into the companies list of size 5000. The index values should be integers and in the range `[0,n)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3, 1, 3, 4, 1, 3, 2, 3, 0, 3, 0, 0, 4, 3, 4, 1, 3, 2, 2, 4, 4, 0,\n",
       "       2, 4, 2, 0, 1, 3, 3, 1, 4, 0, 1, 4, 4, 0, 4, 4, 2, 2, 0, 4, 1, 1,\n",
       "       1, 4, 0, 2, 1, 2])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "idxs = np.random.randint(low=0,high=n,size=5000)\n",
    "idxs[0:50]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's also convert the list of companies to a numpy array, which then allows us to use a list of integers as an index:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['HP', 'Apple', 'HP', 'SAP', 'Apple', 'HP', 'FaceBook', 'HP',\n",
       "       'Google', 'HP', 'Google', 'Google', 'SAP', 'HP', 'SAP'],\n",
       "      dtype='<U8')"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "companies = np.array(companies)\n",
    "names = companies[idxs]\n",
    "names[0:15]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could also do this with a list comprehension in pure Python, but it's a good idea to get familiar with numpy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counting occurrences\n",
    "\n",
    "Ok, now we have a list of companies and would like to count the number of occurrences of each. If we wanted to use numpy, we could do the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array(['Apple', 'FaceBook', 'Google', 'HP', 'SAP'], dtype='<U8'),\n",
       " array([ 978, 1018, 1013,  984, 1007]))"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.unique(names, return_counts=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead, we want to implement this ourselves.   We are given a list of company names with multiple occurrences of each.  To solve this, we don't think about code and think about how we would do this by hand. The first thing I would do is to create a table with a company name and a count to the right, something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.3 (20210619.1520)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"91pt\" height=\"90pt\"\n",
       " viewBox=\"0.00 0.00 91.00 90.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 86)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-86 87,-86 87,4 -4,4\"/>\n",
       "<!-- node140413448279600 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140413448279600</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"83,-82 0,-82 0,0 83,0 83,-82\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-66 2.5,-80 59.5,-80 59.5,-66 2.5,-66\"/>\n",
       "<text text-anchor=\"start\" x=\"16.5\" y=\"-70.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;Google&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"59.5\" y=\"-68.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69.5,-66 69.5,-80 81.5,-80 81.5,-66 69.5,-66\"/>\n",
       "<text text-anchor=\"start\" x=\"70.5\" y=\"-70.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-64 2.5,-66 81.5,-66 81.5,-64 2.5,-64\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-50 2.5,-64 59.5,-64 59.5,-50 2.5,-50\"/>\n",
       "<text text-anchor=\"start\" x=\"23.5\" y=\"-54.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;Apple&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"59.5\" y=\"-52.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69.5,-50 69.5,-64 81.5,-64 81.5,-50 69.5,-50\"/>\n",
       "<text text-anchor=\"start\" x=\"70.5\" y=\"-54.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-48 2.5,-50 81.5,-50 81.5,-48 2.5,-48\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-34 2.5,-48 59.5,-48 59.5,-34 2.5,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"2.5\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;FaceBook&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"59.5\" y=\"-36.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69.5,-34 69.5,-48 81.5,-48 81.5,-34 69.5,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"70.5\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-32 2.5,-34 81.5,-34 81.5,-32 2.5,-32\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-18 2.5,-32 59.5,-32 59.5,-18 2.5,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"36.5\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;HP&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"59.5\" y=\"-20.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69.5,-18 69.5,-32 81.5,-32 81.5,-18 69.5,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"70.5\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-16 2.5,-18 81.5,-18 81.5,-16 2.5,-16\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2.5,-2 2.5,-16 59.5,-16 59.5,-2 2.5,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"29.5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;SAP&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"59.5\" y=\"-4.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69.5,-2 69.5,-16 81.5,-16 81.5,-2 69.5,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"70.5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> 0</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fb48db53160>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from lolviz import *\n",
    "objviz({c:0 for c in companies})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, I would move my finger down the list of company names and bump the count in my table for the company pointed to by my finger:\n",
    "\n",
    "<img src=\"images/companies.png\" width=\"400\">\n",
    "\n",
    "After walking the companies, we'd see something like:\n",
    "\n",
    "<img src=\"images/count-companies.png\" width=\"130\">\n",
    "\n",
    "We would expect the numbers to be roughly the same, which they are. If we increase the sample size to 10,000, the counts would be even closer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "That sounds like a good approach and therefore we can code this up.  Every time I think of moving my finger down a list, I think of a `for`-loop of some kind.   When I think of a table mapping company name to account, I think of a dictionary.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "counts = {c:0 for c in companies}\n",
    "for name in names:\n",
    "    counts[name] += 1\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(int,\n",
       "            {'HP': 984,\n",
       "             'Apple': 978,\n",
       "             'SAP': 1007,\n",
       "             'FaceBook': 1018,\n",
       "             'Google': 1013})"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "counts = defaultdict(int)\n",
    "for name in names:\n",
    "    counts[name] = counts[name] + 1\n",
    "counts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: encrypting text\n",
    "\n",
    "In this exercise, let's learn a little bit about security and encryption by implementing a [cipher encryption function](https://en.wikipedia.org/wiki/Cipher). Given a string, the function must return an encrypted version and the decryption key (the key is the reverse mapping of the cipher and is needed to decrypt). The cipher is a dictionary that maps character to a new character. A cipher encryption works by replacing each character in the plaintext with a character from a key.  For example, if we have the following partial key, we'd encrypt `cat` as `nsz` and `taca` as `zsns`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.3 (20210619.1520)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"52pt\" height=\"58pt\"\n",
       " viewBox=\"0.00 0.00 52.00 58.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 54)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-54 48,-54 48,4 -4,4\"/>\n",
       "<!-- node140413443533920 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140413443533920</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"44,-50 0,-50 0,0 44,0 44,-50\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-34 2,-48 16,-48 16,-34 2,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"2\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;a&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"16\" y=\"-36.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"26,-34 26,-48 42,-48 42,-34 26,-34\"/>\n",
       "<text text-anchor=\"start\" x=\"27\" y=\"-38.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;s&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-32 2,-34 42,-34 42,-32 2,-32\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-18 2,-32 16,-32 16,-18 2,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;c&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"16\" y=\"-20.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"26,-18 26,-32 42,-32 42,-18 26,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"27\" y=\"-22.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;n&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-16 2,-18 42,-18 42,-16 2,-16\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-2 2,-16 16,-16 16,-2 2,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"5\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">&#39;t&#39; </text>\n",
       "<text text-anchor=\"start\" x=\"16\" y=\"-4.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"9.00\" fill=\"#444443\">→</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"26,-2 26,-16 42,-16 42,-2 26,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"27\" y=\"-6.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;z&#39;</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fb48d742978>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objviz({'a':'s', 'c':'n', 't':'z'})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Starting the design process at the highest level, it seems like we have two steps:\n",
    " \n",
    "1. create a cipher that maps all lowercase letters to a random unique character; create the decryption key by reversing the cipher\n",
    "2. create a new string by walking the original and replacing each character with the character from the cipher\n",
    "\n",
    "Step one is nontrivial, so we need to break that process down into some smaller chunks. Work backwards: the problem is straightforward if we have a list of characters a..z and a shuffled version of a..z.  If that's the case, we can simply move a finger through the a..z and the shuffled version, combining them into a dictionary.  \n",
    "\n",
    "Working backwards further: To get a list of a..z, I happen to know we can get it easily from Python in `string.ascii_lowercase` so let's not worry about that. \n",
    "\n",
    "How do we get a shuffled version? There are a number of solutions using list comprehensions but it's easier if we use a built-in shuffling function in numpy.  Given a vector/list of elements, `np.random.shuffle()` will shuffle them  in place (meaning it will alter the list we pass in instead of creating a new one and returning it)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[' ',\n",
       " 'z',\n",
       " 'm',\n",
       " 'u',\n",
       " 'e',\n",
       " 'a',\n",
       " 'x',\n",
       " 'g',\n",
       " 'y',\n",
       " 'i',\n",
       " 'd',\n",
       " 't',\n",
       " 'r',\n",
       " 'n',\n",
       " 'o',\n",
       " 'v',\n",
       " 'q',\n",
       " 'w',\n",
       " 'k',\n",
       " 'b',\n",
       " 'j',\n",
       " 's',\n",
       " 'p',\n",
       " 'c',\n",
       " 'f',\n",
       " 'h',\n",
       " 'l']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import string\n",
    "import numpy as np\n",
    "\n",
    "vocab = string.ascii_lowercase + ' ' # allow spaces as well\n",
    "shuffled_chars = list(vocab)\n",
    "np.random.shuffle( shuffled_chars )\n",
    "shuffled_chars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have the shuffled list, we can use `zip()` and a dictionary comprehension to glue them together. (A dictionary comprehension is the same as a list comprehension except you get a dictionary instead of a list.) The cipher would look something like:\n",
    "\n",
    "<img src=\"images/cipher.png\" width=\"50\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Please use a dictionary comprehension to get the cipher into variable `cipher`.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "cipher = {c:k for c,k in zip(vocab,shuffled_chars)}\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The decryption key is the reverse of the cipher and would look something like:\n",
    "\n",
    "<img src=\"images/decrypt.png\" width=\"60\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Walk that cipher dictionary and flip the dictionary key and value using a dict comprehension to get the decryption key and save into variable `key`.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "key = {v:k for k,v in cipher.items()} # flip key and value\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That completes the first step. For the second step, we have to create a new string from the original plaintext based on the cipher. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Walk the characters in `s`, looking them up in the cipher, and adding the translated character to a new string, `e`.  The encrypted text will look like: \n",
    "`rflv kkpowulykluoxm bz n n `.\n",
    "\n",
    "```python\n",
    "s = \"my password is dogcatbanana\"\n",
    "```\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "s = \"my password is dogcatbanana\"\n",
    "e = \"\"\n",
    "for c in s:\n",
    "    e += cipher[c]\n",
    "# same as: e = ''.join([cipher[c] for c in s])\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write code to print the decrypted `e` so it matches the plaintext in `s`: `my password is dogcatbanana.\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "s = ''.join([key[c] for c in e])\n",
    "print(s)\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "This \"junk drawer\" code appears to work, so please create two clean functions:\n",
    "\n",
    "```python\n",
    "def encrypt(s) -> (str,dict): # returns encrypted string and decryption key dictionary\n",
    "    ...\n",
    "def decrypt(e, key) -> str:    # returns a decrypted string from encrypted string e\n",
    "    ...\n",
    "```\n",
    "\n",
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "def encrypt(s) -> (str,dict):\n",
    "    vocab = string.ascii_lowercase + ' ' # allow spaces as well\n",
    "    shuffled_chars = list(vocab)\n",
    "    np.random.shuffle( shuffled_chars )\n",
    "    cipher = {c:k for c,k in zip(vocab,shuffled_chars)}\n",
    "    key = {v:k for k,v in cipher.items()}\n",
    "    e = ''.join([cipher[c] for c in s])\n",
    "    return e, key\n",
    "\n",
    "def decrypt(e, key) -> str:\n",
    "    return ''.join([key[c] for c in e])\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Give it a try with some sample strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e,key = encrypt(\"hi mom\")\n",
    "decrypt(e,key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e,key = encrypt(\"\")\n",
    "decrypt(e,key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e,key = encrypt(\"apple cat banana\")\n",
    "decrypt(e,key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a cool Python syntax trick.  If you have a tuple `t`, then `*t` unpacks that into an argument list and a function call, which lets us tighten up the syntax like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decrypt( *encrypt(\"apple cat banana\") )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decrypt( *encrypt(\"i like toast\") )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 and 4\n",
      "10 and 3000\n"
     ]
    }
   ],
   "source": [
    "def f(x,y):\n",
    "    print(x, 'and', y)\n",
    "    \n",
    "f(3,4)\n",
    "a = [10,3000]\n",
    "f( *a )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This encryption seems great! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subproblem How could somebody guess our randomized mapping of characters?\n",
    "\n",
    "Unfortunately, these simple ciphers fall immediately to character frequency analysis, as long as we have enough characters in the sample to get an accurate picture of character frequencies. For example, in English the letter `e` has the highest frequency so we replace the character with the highest frequency in the encrypted text with `e` and so on down the frequency list.  As we go along, we look for words in English dictionary or sequences that are close to endless words.  It's like a game of Jeopardy where we try to guess a phrase given some of the characters. We can also look at most common word pairs like `th` to tease out the original plaintext. If you'd like to read a fascinating and well-written (nonacademic) book on cryptography from ancient times to modern times, check out [The Code Book](https://www.amazon.com/Code-Book-Science-Secrecy-Cryptography/dp/0385495323) by Simon Singh. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Download and filter CSV data from the web\n",
    "\n",
    "As we will see in the data acquisitions class, a very common pattern is to collect some data from the web and process it in some way.  Let's get started  by downloading a CSV file from the web that contains information on [cities in various states](https://people.sc.fsu.edu/~jburkardt/data/csv/cities.csv) from the US. We could simply download that file onto our local disk, but let's do this automatically with a program. \n",
    "\n",
    "Let's say our next goal is to filter out any cities that are not in Washington state, code `WA`.   Let's finish up by saving those `WA` rows back to a text file, `/tmp/wa_cities.csv`, in CSV format. We'll avoid using pandas initially and then do it again with pandas.\n",
    "\n",
    "To get started, think about the overall sequence of steps needed to solve this problem at a high level; totally ignore the coding issues. In my mind, there are three things to do:\n",
    "\n",
    "1. Download the CSV file as a string\n",
    "2. Filter for just the `WA` states\n",
    "3. Write those rows to a new text file\n",
    "\n",
    "There are a number of details we need to flesh out for each step, but it's important to start at a high level before drilling down into the details.\n",
    "\n",
    "For step one, a quick Google search reveals that there is a package called `requests` for Python that allows us to download files easily so let's do that and take a look at what we get:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"LatD\", \"LatM\", \"LatS\", \"NS\", \"LonD\", \"LonM\", \"LonS\", \"EW\", \"City\", \"State\"\n",
      "   41,    5,   59, \"N\",     80,   39,    0, \"W\", \"Youngstown\", OH\n",
      "   42,   52,   48, \"N\",     97,   23,   23, \"W\", \"Yankton\", SD\n",
      "   46,   35,   59, \"N\",    120,   30,   36, \"W\", \"Yakima\", WA\n",
      "   42,   16,   12, \"N\",     71,  \n"
     ]
    }
   ],
   "source": [
    "import requests\n",
    "r = requests.get(\"https://people.sc.fsu.edu/~jburkardt/data/csv/cities.csv\")\n",
    "contents = r.text\n",
    "print(contents[0:300])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a lot of quotation marks in the data that are unnecessary and we can remove.  We did not know this detail when planning the overall process, but now we know and so let's clean up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LatD, LatM, LatS, NS, LonD, LonM, LonS, EW, City, State\n",
      "   41,    5,   59, N,     80,   39,    0, W, Youngstown, OH\n",
      "   42,   52,   48, N,     97,   23,   23, W, Yankton, SD\n",
      "   46,   35,   59, N,    120,   30,   36, W, Yakima, WA\n",
      "   42,   16,   12, N,     71,   48,    0, W, Worcester, MA\n",
      "   43,   37,\n"
     ]
    }
   ],
   "source": [
    "contents = contents.replace('\"', '')\n",
    "print(contents[0:300])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For step two, we need to filter for just those cities in Washington state but right now all we have is a string. Let's split that string into a list of strings, with one row per string and separate out the first row as the list of columns:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['   41,    5,   59, N,     80,   39,    0, W, Youngstown, OH',\n",
       " '   42,   52,   48, N,     97,   23,   23, W, Yankton, SD',\n",
       " '   46,   35,   59, N,    120,   30,   36, W, Yakima, WA',\n",
       " '   42,   16,   12, N,     71,   48,    0, W, Worcester, MA',\n",
       " '   43,   37,   48, N,     89,   46,   11, W, Wisconsin Dells, WI']"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lines = contents.split('\\n')\n",
    "columns = lines[0]\n",
    "lines = lines[1:]\n",
    "lines[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also should remove the extra spaces after delimiters like this but leave spaces in city names like `Walla Walla`:\n",
    "\n",
    "```\n",
    "LatD,LatM,LatS,NS,LonD,LonM,LonS,EW,City,State\n",
    "41,5,59,N,80,39,0,W,Youngstown,OH\n",
    "42,52,48,N,97,23,23,W,Yankton,SD\n",
    "46,35,59,N,120,30,36,W,Yakima,WA\n",
    "42,16,12,N,71,48,0,W,Worcester,MA\n",
    "43,37,48,N,89,46,11,W,Wisconsin Dells,WI\n",
    "36,5,59,N,80,15,0,W,Winston-Salem,NC\n",
    "49,52,48,N,97,9,0,W,Winnipeg,MB\n",
    "...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I tried multiple approaches. How would you clean up so we don't have extra spaces?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "cleaned = []\n",
    "for line in lines:\n",
    "    row = line.split(',')\n",
    "    row = [val.strip() for val in row]\n",
    "    cleaned.append(','.join(row))\n",
    "lines = cleaned\n",
    "\n",
    "# do for header too\n",
    "columns = columns.split(',')\n",
    "columns = [name.strip() for name in columns]\n",
    "columns = ','.join(columns)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have that list, we can use a list comprehension to filter the rows. Note that we don't have to split up the individual rows into fields or columns because a simple check for string `WA` in each row is sufficient:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['46,35,59,N,120,30,36,W,Yakima,WA',\n",
       " '47,25,11,N,120,19,11,W,Wenatchee,WA',\n",
       " '46,4,11,N,118,19,48,W,Walla Walla,WA',\n",
       " '47,14,24,N,122,25,48,W,Tacoma,WA',\n",
       " '47,40,11,N,117,24,36,W,Spokane,WA',\n",
       " '47,35,59,N,122,19,48,W,Seattle,WA']"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wa = [row for row in lines if 'WA' in row]\n",
    "wa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For step three, we can open up a text file as we normally do and iterate through the rows of data (starting out by writing the list of columns):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"/tmp/wa_cities.csv\", \"w\") as f:\n",
    "    f.write(columns+\"\\n\")\n",
    "    for row in wa:\n",
    "        f.write(row+\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Pandas alternative\n",
    "\n",
    "Pandas is also network aware and so we can give it a URL instead of a file name to read in a CSV file, which it processes heavily into a table rather than a simple list of strings as we did previously"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>LatD</th>\n",
       "      <th>LatM</th>\n",
       "      <th>LatS</th>\n",
       "      <th>NS</th>\n",
       "      <th>LonD</th>\n",
       "      <th>LonM</th>\n",
       "      <th>LonS</th>\n",
       "      <th>EW</th>\n",
       "      <th>City</th>\n",
       "      <th>State</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>41</td>\n",
       "      <td>5</td>\n",
       "      <td>59</td>\n",
       "      <td>N</td>\n",
       "      <td>80</td>\n",
       "      <td>39</td>\n",
       "      <td>0</td>\n",
       "      <td>W</td>\n",
       "      <td>Youngstown</td>\n",
       "      <td>OH</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>42</td>\n",
       "      <td>52</td>\n",
       "      <td>48</td>\n",
       "      <td>N</td>\n",
       "      <td>97</td>\n",
       "      <td>23</td>\n",
       "      <td>23</td>\n",
       "      <td>W</td>\n",
       "      <td>Yankton</td>\n",
       "      <td>SD</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>46</td>\n",
       "      <td>35</td>\n",
       "      <td>59</td>\n",
       "      <td>N</td>\n",
       "      <td>120</td>\n",
       "      <td>30</td>\n",
       "      <td>36</td>\n",
       "      <td>W</td>\n",
       "      <td>Yakima</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>42</td>\n",
       "      <td>16</td>\n",
       "      <td>12</td>\n",
       "      <td>N</td>\n",
       "      <td>71</td>\n",
       "      <td>48</td>\n",
       "      <td>0</td>\n",
       "      <td>W</td>\n",
       "      <td>Worcester</td>\n",
       "      <td>MA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>43</td>\n",
       "      <td>37</td>\n",
       "      <td>48</td>\n",
       "      <td>N</td>\n",
       "      <td>89</td>\n",
       "      <td>46</td>\n",
       "      <td>11</td>\n",
       "      <td>W</td>\n",
       "      <td>Wisconsin Dells</td>\n",
       "      <td>WI</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   LatD  LatM  LatS NS  LonD  LonM  LonS EW             City State\n",
       "0    41     5    59  N    80    39     0  W       Youngstown    OH\n",
       "1    42    52    48  N    97    23    23  W          Yankton    SD\n",
       "2    46    35    59  N   120    30    36  W           Yakima    WA\n",
       "3    42    16    12  N    71    48     0  W        Worcester    MA\n",
       "4    43    37    48  N    89    46    11  W  Wisconsin Dells    WI"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "df = pd.read_csv(\"https://people.sc.fsu.edu/~jburkardt/data/csv/cities.csv\",\n",
    "                 skipinitialspace=True) # need since lots of spaces after commas\n",
    "df.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For step two, it's easy to filter using a query like syntax.  Expression `df['State']=='WA'` gives us a vector of Boolean values indicating whether a row satisfies the conditions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0      False\n",
       "1      False\n",
       "2       True\n",
       "3      False\n",
       "4      False\n",
       "5      False\n",
       "6      False\n",
       "7      False\n",
       "8      False\n",
       "9      False\n",
       "10     False\n",
       "11     False\n",
       "12     False\n",
       "13     False\n",
       "14     False\n",
       "15     False\n",
       "16     False\n",
       "17      True\n",
       "18     False\n",
       "19     False\n",
       "20     False\n",
       "21     False\n",
       "22     False\n",
       "23     False\n",
       "24     False\n",
       "25     False\n",
       "26     False\n",
       "27     False\n",
       "28      True\n",
       "29     False\n",
       "       ...  \n",
       "98     False\n",
       "99     False\n",
       "100    False\n",
       "101    False\n",
       "102    False\n",
       "103    False\n",
       "104    False\n",
       "105    False\n",
       "106    False\n",
       "107    False\n",
       "108    False\n",
       "109    False\n",
       "110    False\n",
       "111    False\n",
       "112    False\n",
       "113    False\n",
       "114    False\n",
       "115    False\n",
       "116    False\n",
       "117    False\n",
       "118    False\n",
       "119    False\n",
       "120    False\n",
       "121    False\n",
       "122    False\n",
       "123    False\n",
       "124    False\n",
       "125    False\n",
       "126    False\n",
       "127    False\n",
       "Name: State, Length: 128, dtype: bool"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['State']=='WA'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That vector of Booleans is usable as an index into the rows of the data frame:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>LatD</th>\n",
       "      <th>LatM</th>\n",
       "      <th>LatS</th>\n",
       "      <th>NS</th>\n",
       "      <th>LonD</th>\n",
       "      <th>LonM</th>\n",
       "      <th>LonS</th>\n",
       "      <th>EW</th>\n",
       "      <th>City</th>\n",
       "      <th>State</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>46</td>\n",
       "      <td>35</td>\n",
       "      <td>59</td>\n",
       "      <td>N</td>\n",
       "      <td>120</td>\n",
       "      <td>30</td>\n",
       "      <td>36</td>\n",
       "      <td>W</td>\n",
       "      <td>Yakima</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>47</td>\n",
       "      <td>25</td>\n",
       "      <td>11</td>\n",
       "      <td>N</td>\n",
       "      <td>120</td>\n",
       "      <td>19</td>\n",
       "      <td>11</td>\n",
       "      <td>W</td>\n",
       "      <td>Wenatchee</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>28</th>\n",
       "      <td>46</td>\n",
       "      <td>4</td>\n",
       "      <td>11</td>\n",
       "      <td>N</td>\n",
       "      <td>118</td>\n",
       "      <td>19</td>\n",
       "      <td>48</td>\n",
       "      <td>W</td>\n",
       "      <td>Walla Walla</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>54</th>\n",
       "      <td>47</td>\n",
       "      <td>14</td>\n",
       "      <td>24</td>\n",
       "      <td>N</td>\n",
       "      <td>122</td>\n",
       "      <td>25</td>\n",
       "      <td>48</td>\n",
       "      <td>W</td>\n",
       "      <td>Tacoma</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>68</th>\n",
       "      <td>47</td>\n",
       "      <td>40</td>\n",
       "      <td>11</td>\n",
       "      <td>N</td>\n",
       "      <td>117</td>\n",
       "      <td>24</td>\n",
       "      <td>36</td>\n",
       "      <td>W</td>\n",
       "      <td>Spokane</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>78</th>\n",
       "      <td>47</td>\n",
       "      <td>35</td>\n",
       "      <td>59</td>\n",
       "      <td>N</td>\n",
       "      <td>122</td>\n",
       "      <td>19</td>\n",
       "      <td>48</td>\n",
       "      <td>W</td>\n",
       "      <td>Seattle</td>\n",
       "      <td>WA</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    LatD  LatM  LatS NS  LonD  LonM  LonS EW         City State\n",
       "2     46    35    59  N   120    30    36  W       Yakima    WA\n",
       "17    47    25    11  N   120    19    11  W    Wenatchee    WA\n",
       "28    46     4    11  N   118    19    48  W  Walla Walla    WA\n",
       "54    47    14    24  N   122    25    48  W       Tacoma    WA\n",
       "68    47    40    11  N   117    24    36  W      Spokane    WA\n",
       "78    47    35    59  N   122    19    48  W      Seattle    WA"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_wa = df[df['State']=='WA']\n",
    "df_wa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Step three is also much easier using pandas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "df_wa.to_csv(\"/tmp/wa_cities2.csv\", index=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final phase of our problem-solving template is to verify results, which we can do by comparing the two files we wrote to make sure they are the same.  Here I'm using the `diff` tool from the commandline."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [],
   "source": [
    "! diff /tmp/wa_cities.csv  /tmp/wa_cities2.csv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Getting no output indicates there are no differences, which is what we want."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: simple EDA of the text corpus\n",
    "\n",
    "The goal of this exercise is to load all of the text files in a directory and compute an overall vocabulary and count per word. This would be the first step in understanding a corpus of text we wanted to analyze. For example, what is the most common word used in English?  It's almost certainly `the`, right? Another interesting question is the length of the average word and the size of the overall vocabulary.\n",
    " \n",
    "Took a look at the [Berlitz](https://github.com/parrt/msds501/tree/master/data/berlitz1) data directory that's part of this course is repository. You will see a series of text files. Here's a terminal command to find all files that have the word Israel in the name:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "../data/berlitz1/HandRIsrael.txt   ../data/berlitz1/WhatToIsrael.txt\n",
      "../data/berlitz1/HistoryIsrael.txt ../data/berlitz1/WhereToIsrael.txt\n",
      "../data/berlitz1/IntroIsrael.txt\n"
     ]
    }
   ],
   "source": [
    "! ls ../data/berlitz1/*Israel*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The overall steps needed to solve this problem are something like:\n",
    "\n",
    "1.  Get a list of all files in a directory\n",
    "2.  Walked the list of files and extract the text, appending it to an overall string\n",
    "3.  Normalize the contents string by converting to lowercase and calling `split()` to break up the string into a list of words\n",
    "4.  Report the total number of words, number of unique words, average word length, and perhaps the top 20 most common words\n",
    "\n",
    "A bit of googling will lead you to `os.listdir()` for step 1 and step number 2 is just a for-each loop over that list that uses the \"fetch file contents\" pattern we've seen before. Using the `+` operator, we can add strings to an overall `contents` variable. Step 3 is just two function calls to `lower()` and `split()`. Depending on our knowledge of available libraries, step 4 could be a lot of work or it very simple; let's code the other parts first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 520878 words in the contents\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "\n",
    "contents = \"\"\n",
    "for filename in os.listdir(\"../data/berlitz1\"):\n",
    "    with open(f\"../data/berlitz1/{filename}\", \"r\") as f:\n",
    "        s = f.read()\n",
    "        contents += \" \" # add space so words don't get stuck together\n",
    "        contents += s\n",
    "contents = contents.lower()\n",
    "words = contents.split()\n",
    "print(f\"There are {len(words)} words in the contents\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get the unique words, we can either use numpy or `set(...)`. It looks like there are 57,894 words in the vocabulary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(57894, 57894)"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(np.unique(words)), len(set(words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's work backwards: To compute the average word length, we need a list of the word lengths and can then just compute the mean using numpy.  To get the word lengths, we can use a list comprehension to walk through the words. The code then looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0362503311715985"
      ]
     },
     "execution_count": 173,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "avg_len = np.mean([len(w) for w in words])\n",
    "avg_len"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we need to count the number of occurrences of the words, kind of like we did for the histogram exercise above. Since you know how to do that with your own code now, let's learn to use a built-in `Counter` object that does all the work for us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('the', 45163),\n",
       " ('of', 20438),\n",
       " ('and', 16739),\n",
       " ('a', 11830),\n",
       " ('in', 10670),\n",
       " ('to', 10473),\n",
       " ('is', 6845),\n",
       " ('for', 4282),\n",
       " ('on', 3909),\n",
       " ('with', 3762),\n",
       " ('from', 3604),\n",
       " ('by', 3263),\n",
       " ('are', 3190),\n",
       " ('as', 3104),\n",
       " ('at', 2884),\n",
       " ('was', 2686),\n",
       " ('its', 2539),\n",
       " ('it', 2499),\n",
       " ('you', 2406),\n",
       " ('that', 2146)]"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "ctr = Counter(words)\n",
    "c = ctr.most_common(20)\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution to this problem is not too hard given all of the libraries we have available to us.\n",
    "\n",
    "Let's also plot the counts to see the relationship between frequencies and just how fast it drops off."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = np.array(c)\n",
    "wds = c[:,0]\n",
    "counts = c[:,1].astype(int)  # numpy converted c to strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAABB8AAAFNCAYAAABIRsfzAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAABYlAAAWJQFJUiTwAAA0aUlEQVR4nO3debglVXnv8e8PEFSQZlAEB8IQcb4xiqKg0IBBNCgOeEFzCeAsIjIYNQ5MV65GEBAUiRpscLhgMIIDelGgQUEh4EAUBGloJYgj0G1D0wqs+8eqDbt3733GXb3P6f5+nuc8dU7VWlVv1amqXfXuVatSSkGSJEmSJKkta4w6AEmSJEmStGoz+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJaZfJBkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUqrVGHcDqJkkppYw6DEmSJEmSpiJTqWTLB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWrTXqADRznXTiR1m0eMmowwBgzvrrccihh486DEmSJEnSFJh80ECLFi/hiP3njDoMAI6Zt2jUIUiSJEmSpsjHLiRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJaZfJBkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUKpMPkiRJkiSpVSYfJEmSJElSq0w+SJIkSZKkVpl8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktaqV5EOSfZOU5ucNA8psn+T8JLcnuTvJNUkOSbLmGPPdL8mVSZYkWZRkfpI9xij/sCRHJ7k+yT1JfpfkS0mePEadxyU5PcmvkyxLsjDJSUk2nNxWkCRJkiRJ0ELyIcnjgVOAJWOU2RO4FNgR+ArwCWBt4ETgrAF1jgfmAZsBnwY+Dzwd+FqSg/qUXwf4NnAEsBj4GPAd4BXAVUm261Nna+Bq4ADgyiaem4B3AN9PsvF46y9JkiRJkpY31ORDkgCfBf4InDagzPrU5MF9wNxSyutLKf8EPAP4PrBXkn166mwPHA4sAP5HKeXQUsrbgGcBtwPHJ9miZ1GHATsA5wDblVLeXUp5LbAX8HDg9CS9638qsAlwcCnl5aWU95RSdqEmIZ4IHDvZbSJJkiRJ0upu2C0fDgZ2obYcuGtAmb2ARwFnlVKu6owspdwDvL/58609dd7SDI8tpdzRVWchtdXEOs0ygQeSIJ067yql3N9V5zzgu8BTgJ266mwF7AZ05tntyGZ99k2y7oD1kiRJkiRJfQwt+dD0o/Bh4GOllEvHKLpLM/xWn2mXAncD2zePTUykzjd7ygBsDWwO3FBKuXmCdTq/X9CdrAAopfwJuIzaYuK5feYnSZIkSZIGWGsYM0myFvA54FfAe8cp/sRmeEPvhFLKvUluBp4KbAVc17Q0eCywpJRyW5/5/aIZbjORZUyzzm5NnQsHlAEgydVjTZckSZIkaXUylOQDtVPHvwWeX0pZOk7ZOc1w0YDpnfEbTLH8yqwjSZIkSZLGMe3kQ5LnUFs7fLSU8v3ph0SaYZlkvcmUn8oyJlynlPKsgTNJJrtekiRJkiTNatPq86HrcYsbgA9MsFqnBcGcAdPX7yk3Xvl+LRYmu4yp1pEkSZIkSeOYboeT61H7QHgycE+S0vmhviEC4NPNuJOav69vhtvQo0lmbAncC9wEUEq5C7gVWC/JZn1ieEIz7O6rYeAyhlxHkiRJkiSNY7qPXSwD/m3AtGdS+4H4HvXGvvNIxkXAPwC7A/+3p86O1DdKXFpKWdY1/iJg36bOZ3vqvLirTMcCaueX2yTZss8bL/rVubgZ7pZkje43XiR5BLADsBT4Qd+1lSRJkiRJfU2r5UMpZWkp5Q39foCvNsXOaMad3fx9DvAHYJ8k23bmleShwAebPz/Zs6jTmuH7kmzYVWcL4G3UJMgDSYlSSumq85Eka3TV2RN4AXAtcElXnQXABUBnnt2OBtYFzmxaYkiSJEmSpAka1tsuJqyUsjjJG6lJiPlJzgJuB15Gfd3lOcDZPXUuT3ICcBhwTZJzgLWBvYGNgLeXUhb2LOoEYA9gL+CKJBcCmwOvBu4GXtfduqFxIHA5cHKSXYHrgO2AnamPW7xv+ltAkiRJkqTVy3T7fJiSUsq5wE7ApcCrgLcDf6EmF/ZpWi701jkc2B/4DfAm4B+BnwEvLaV8vE/5ZcALgWOor8c8FPg74Fzg2aWUK/rUWQBsC8yjJh0OB7YGTgaeV0r541TXWZIkSZKk1VVrLR9KKUcBR40x/TLgJZOc5xnAGZMov5Ta8eWR45XtqnMLcMBk4pIkSZIkSYONpOWDJEmSJElafZh8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktcrkgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJaZfJBkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUKpMPkiRJkiSpVSYfJEmSJElSq0w+SJIkSZKkVpl8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktcrkgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJaNZTkQ5J/SXJhkluSLE1ye5IfJTkyycYD6myf5Pym7N1JrklySJI1x1jOfkmuTLIkyaIk85PsMUb5hyU5Osn1Se5J8rskX0ry5DHqPC7J6Ul+nWRZkoVJTkqy4eS2iiRJkiRJguG1fDgUWBf4NvAx4AvAvcBRwDVJHt9dOMmewKXAjsBXgE8AawMnAmf1W0CS44F5wGbAp4HPA08HvpbkoD7l12niOQJY3MT1HeAVwFVJtutTZ2vgauAA4MomnpuAdwDfH5RIkSRJkiRJg601pPmsX0q5p3dkkmOB9wL/DBzYjFufmjy4D5hbSrmqGf8B4CJgryT7lFLO6prP9sDhwALg2aWUO5rxx1GTBccn+XopZWHX4g8DdgDOAfYupdzf1DkbOBc4PcnTO+MbpwKbAAeXUk7pWv4J1ATLscBbprSFJEmSJElaTQ2l5UO/xEPjS83wCV3j9gIeBZzVSTx0zeP9zZ9v7ZlP54b/2E7ioamzkNpqYh1qawUAkqSrzru6EwyllPOA7wJPAXbqqrMVsBvQmWe3I4G7gH2TrDtgXSVJkiRJUh9tdzj50mZ4Tde4XZrht/qUvxS4G9i+eWxiInW+2VMGYGtgc+CGUsrNE6zT+f2CntYQlFL+BFwGPBx4bp/5SZIkSZKkAYb12AUASd4JrAfMAbYFnk9NPHy4q9gTm+ENvfVLKfcmuRl4KrAVcF3T0uCxwJJSym19FvuLZrjNRJYxzTq7NXUuHFAGgCRXjzVdkiRJkqTVyVCTD8A7gUd3/f0tYP9Syu+7xs1phosGzKMzfoMpll+ZdSRJkiRJ0jiGmnwopWwKkOTRwPbUFg8/SrJHKeWHE5xNOrOb7OInUXYqy5hwnVLKswbOJJnsekmSJEmSNKu10udDKeW3pZSvUB9T2Bg4s2typwXBnBUqVuv3lBuvfL8WC5NdxlTrSJIkSZKkcbTa4WQp5ZfAtcBTkzyyGX19M9ymt3yStYAtgXuBm5p53AXcCqyXZLM+i+m8SaO7r4aByxhyHUmSJEmSNI6233YB8JhmeF8zvKgZ7t6n7I7UN0pcXkpZ1jV+rDov7ikDsAD4FbBNki0nWOfiZrhbkuW2S5JHADsAS4Ef9JmfJEmSJEkaYNrJhyRPSrJpn/FrJDkW2ISaTLijmXQO8AdgnyTbdpV/KPDB5s9P9szutGb4viQbdtXZAngbsAz4bGd8KaV01flIdzIhyZ7AC6gtMi7pqrMAuADozLPb0cC6wJlNSwxJkiRJkjRBw+hwcnfguCSXUlsc/JH6xoudqK/L/A3wxk7hUsriJG+kJiHmJzkLuB14GfV1l+cAZ3cvoJRyeZITgMOAa5KcA6wN7A1sBLy9lLKwJ64TgD2AvYArklwIbA68GrgbeF0p5f6eOgcClwMnJ9kVuA7YDtiZ+rjF+6aygSRJkiRJWp0NI/nwHeBT1McS/ob6Ksq7qDfrnwNOLqXc3l2hlHJukp2oN/OvAh4K3EhNLpzctFygp87hSa4BDgLeBNwP/BA4rpTy9T7llyV5IfAe4LXAocBi4FzgyFLKtX3qLGhaYxxDTaq8BLgNOBk4unc9JEmSJEnS+KadfCil/JQVH1OYSL3LqDf3k6lzBnDGJMovBY5sfiZa5xbggMnEJUmSJEmSBlsZHU5KkiRJkqTVmMkHSZIkSZLUKpMPkiRJkiSpVSYfJEmSJElSq0w+SJIkSZKkVpl8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktcrkgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJaZfJBkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUKpMPkiRJkiSpVSYfJEmSJElSq0w+SJIkSZKkVpl8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktcrkgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktSqaScfkmyc5A1JvpLkxiRLkyxK8r0kr0/SdxlJtk9yfpLbk9yd5JokhyRZc4xl7ZfkyiRLmmXMT7LHGOUfluToJNcnuSfJ75J8KcmTx6jzuCSnJ/l1kmVJFiY5KcmGk9sykiRJkiQJhtPy4dXAp4HtgCuAk4AvA08DPgN8KUm6KyTZE7gU2BH4CvAJYG3gROCsfgtJcjwwD9isWd7ngacDX0tyUJ/y6wDfBo4AFgMfA74DvAK4Ksl2fepsDVwNHABc2cRzE/AO4PtJNp7QFpEkSZIkSQ9YawjzuAF4GfCNUsr9nZFJ3ku9gX8V8EpqQoIk61OTB/cBc0spVzXjPwBcBOyVZJ9Sylld89oeOBxYADy7lHJHM/44arLg+CRfL6Us7IrrMGAH4Bxg705sSc4GzgVOT/L07piBU4FNgINLKad0Lf8E4FDgWOAtU99UkiRJkiStfqadfCilXDRg/G+SnEa9YZ9Lk3wA9gIeBZzZSTw05e9J8n7gQuCtLN8ConPDf2wn8dDUWZjkE8AHqK0VjgRoWlp06ryrO8FQSjkvyXeBFwA7ARc3dbYCdgMWUltidDsSeBOwb5LDSyl3jbNZNAInnfhRFi1eMuowAJiz/noccujhow5DkiRJkmaEYbR8GMtfmuG9XeN2aYbf6lP+UuBuYPsk65RSlk2gzjepyYddaJIPwNbA5sANpZSbB9R5QVPn4p5lXNDTGoJSyp+SXEZNTjyXmiDRDLNo8RKO2H/OqMMA4Jh5i0YdgiRJkiTNGK0lH5KsBfxj82d30uCJzfCG3jqllHuT3Aw8FdgKuC7JusBjgSWllNv6LOoXzXCbiSxjmnV2a+qMmXxIcvVY0yVJkiRJWp20+arND1M7nTy/lPL/usZ3vpoe9NVwZ/wGUyy/MutIkiRJkqRxtNLyIcnB1A4ifw7sO9nqzbBMst5kyk9lGROuU0p51sCZJJNdL0mSJEmSZrWht3xI8jbqay2vBXYupdzeU6TTgmDQw/nr95Qbr3y/FguTXcZU60iSJEmSpHEMNfmQ5BDg48BPqYmH3/Qpdn0z3KZ3QtNPxJbUDipvAmjeLHErsF6SzfrM7wnNsLuvhoHLGHIdSZIkSZI0jqElH5K8GzgR+DE18fC7AUU7r+bcvc+0HYGHA5d3velivDov7ikDsAD4FbBNki0nWKfz1ovdkiy3XZI8AtgBWAr8oM/8JEmSJEnSAENJPiT5ALWDyauBXUspfxij+DnAH4B9kmzbNY+HAh9s/vxkT53TmuH7kmzYVWcL4G3AMuCznfGllNJV5yPdyYQke1Jfs3ktcElXnQXABUBnnt2OBtYFzmxaYkiSJEmSpAmadoeTSfYDjgHuA74LHJykt9jCUso8gFLK4iRvpCYh5ic5C7gdeBn1dZfnAGd3Vy6lXJ7kBOAw4Jok5wBrA3sDGwFvL6Us7FnmCcAewF7AFUkuBDYHXg3cDbyulHJ/T50DgcuBk5PsClwHbAfsTH3c4n2T2jiSJEmSJGkob7voPNawJnDIgDKXAPM6f5RSzk2yE/Vm/lXAQ4EbqcmFk5uWC8sppRye5BrgIOBNwP3AD4HjSilf71N+WZIXAu8BXgscCiwGzgWOLKVc26fOgqY1xjHURzxeAtwGnAwc3afzTEmSJEmSNI5pJx9KKUcBR02h3mXUm/vJ1DkDOGMS5ZcCRzY/E61zC3DAZOKSJEmSJEmDDf1Vm5IkSZIkSd1MPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWrTXqAKTV0UknfpRFi5eMOgwA5qy/Hocceviow5AkSZK0CjP5II3AosVLOGL/OaMOA4Bj5i0adQiSJEmSVnE+diFJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJaZfJBkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUKpMPkiRJkiSpVSYfJEmSJElSq0w+SJIkSZKkVpl8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktcrkgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLVqrVEHIGnmO+nEj7Jo8ZJRhwHAnPXX45BDDx91GJIkSZImweSDpHEtWryEI/afM+owADhm3qJRhyBJkiRpknzsQpIkSZIktcrkgyRJkiRJatVQkg9J9kpySpLvJlmcpCT5/Dh1tk9yfpLbk9yd5JokhyRZc4w6+yW5MsmSJIuSzE+yxxjlH5bk6CTXJ7knye+SfCnJk8eo87gkpyf5dZJlSRYmOSnJhhPbGpIkSZIkqduwWj68HzgIeAZw63iFk+wJXArsCHwF+ASwNnAicNaAOscD84DNgE8DnweeDnwtyUF9yq8DfBs4AlgMfAz4DvAK4Kok2/WpszVwNXAAcGUTz03AO4DvJ9l4vHWTJEmSJEnLG1aHk4cC/w3cCOwEXDyoYJL1qcmD+4C5pZSrmvEfAC4C9kqyTynlrK462wOHAwuAZ5dS7mjGH0dNFhyf5OullIVdizoM2AE4B9i7lHJ/U+ds4Fzg9CRP74xvnApsAhxcSjmla/knNOt4LPCWyW0aSSuTb+aQJEmSZp6hJB9KKQ8kG5KMV3wv4FHAmZ3EQzOPe5K8H7gQeCvLt4Do3PAf20k8NHUWJvkE8AFqa4UjmxjSVedd3QmGUsp5Sb4LvICuREmSrYDdgIXUlhjdjgTeBOyb5PBSyl3jraSk0fDNHJIkSdLMM4pXbe7SDL/VZ9qlwN3A9knWKaUsm0Cdb1KTD7vQJB+ArYHNgRtKKTcPqPOCpk4ncdJZxgU9rSEopfwpyWXU5MRzqQkSSZo2W2pIkiRpdTCK5MMTm+ENvRNKKfcmuRl4KrAVcF2SdYHHAktKKbf1md8vmuE2E1nGNOvs1tQZM/mQ5OqxpktShy01JEmStDoYxas2O1fZg65yO+M3mGL5lVlHkiRJkiSNYxQtH8bT6TSiTLLeZMpPZRkTrlNKedbAmSSTXS9JkiRJkma1UbR86LQgGNTOeP2ecuOV79diYbLLmGodSZIkSZI0jlEkH65vhtv0TkiyFrAlcC9wE0DzZolbgfWSbNZnfk9oht19NQxcxpDrSJIkSZKkcYwi+XBRM9y9z7QdgYcDl3e96WK8Oi/uKQOwAPgVsE2SLSdYp/PWi92SLLddkjwC2AFYCvygz/wkSZIkSdIAo0g+nAP8AdgnybadkUkeCnyw+fOTPXVOa4bvS7JhV50tgLcBy4DPdsaXUkpXnY90JxOS7El9zea1wCVddRYAFwCdeXY7GlgXOLNpiSFJkiRJkiZoKB1OJnk58PLmz02b4fOSzGt+/0Mp5Z0ApZTFSd5ITULMT3IWcDvwMurrLs8Bzu6efynl8iQnAIcB1yQ5B1gb2BvYCHh7KWVhT1gnAHsAewFXJLkQ2Bx4NXA38LpSyv09dQ4ELgdOTrIrcB2wHbAz9XGL901qw0iSJEmSpKG97eIZwH4947ZqfgB+CbyzM6GUcm6Snag3868CHgrcSE0unNy0XFhOKeXwJNcABwFvAu4HfggcV0r5ep/yy5K8EHgP8FrgUGAxcC5wZCnl2j51FjStMY6hPuLxEuA24GTg6FLK7RPZGJIkSZIk6UFDST6UUo4CjppkncuoN/eTqXMGcMYkyi8Fjmx+JlrnFuCAycQlSZIkSZIGG0WfD5IkSZIkaTVi8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXyQJEmSJEmtMvkgSZIkSZJatdaoA5AkzR4nnfhRFi1eMuowmLP+ehxy6OGjDkOSJEkTZPJBkjRhixYv4Yj954w6DI6Zt2jUIUiSJGkSfOxCkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUKpMPkiRJkiSpVSYfJEmSJElSq0w+SJIkSZKkVpl8kCRJkiRJrTL5IEmSJEmSWmXyQZIkSZIktcrkgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqvWGnUAkiS14aQTP8qixUtGHQYAc9Zfj0MOPXzUYUiSJI2MyQdJ0ipp0eIlHLH/nFGHAcAx8xaNOgRJkqSRMvkgSdIMYEsNSZK0KjP5IEnSDDCbWmqYKJEkSZNl8kGSJE3KbEqUgMkSSZJmApMPkiRplTbbkiWSJK2KTD5IkiTNELOtlcZsi1eSNDomHyRJkmaI2dZKYzbFa6JEkkbL5IMkSZJWebMpUQImSyStekw+SJIkSTOMyZKpMVEizVwmHyRJkiRNy0xJlsymRAnYt4pWLyYfJEmSJK02ZkqiBOxbpU0mSmYekw+SJEmSpGmbTYkSMFmyspl8kCRJkiStdmZbsmS2W2PUAUiSJEmSpFWbyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKrTD5IkiRJkqRWmXzoI8njkpye5NdJliVZmOSkJBuOOjZJkiRJkmYbX7XZI8nWwOXAJsB5wM+B5wDvAHZPskMp5Y8jDFGSJEmSpFnFlg8rOpWaeDi4lPLyUsp7Sim7ACcCTwSOHWl0kiRJkiTNMiYfuiTZCtgNWAh8omfykcBdwL5J1l3JoUmSJEmSNGuZfFjeLs3wglLK/d0TSil/Ai4DHg48d2UHJkmSJEnSbGWfD8t7YjO8YcD0X1BbRmwDXDhoJkmuHnJckiRJkiTNWimljDqGGSPJp4A3Am8spXymz/RjgfcC7y2lfGiM+YyVfHjmtAOVJEmSJGlESimZbB1bPkxOZwOPmbEppTxrJcQyK3QSMbNhm8ymWGF2xTubYoXZFe9sihWMt02zKVaYXfHOplhhdsU7m2KF2RXvbIoVjLdNsylWmF3xzqZYZwL7fFjeomY4Z8D09XvKSZIkSZKkcZh8WN71zXCbAdOf0AwH9QkhSZIkSZJ6mHxY3sXNcLcky22bJI8AdgCWAj9Y2YFJkiRJkjRbmXzoUkpZAFwAbAG8rWfy0cC6wJmllLtWcmiSJEmSJM1adji5ogOBy4GTk+wKXAdsB+xMfdzifSOMTZIkSZKkWcdXbfaR5PHAMcDuwMbAbcC5wNGllNtHGJokSZIkSbOOyQdJkiRJktQq+3yQJEmSJEmtMvkgSZIkSZJaZfJBkiRJkiS1yuSDJEmSJElqlckHSZIkSZLUKpMPmrYkc5OUJEeNOpY2JNktyeVJ7mjW89xRxzRdSeYnWe1fdZNki+Z/Om/UsayKZvL2TXJwkmuTLG1iPGTUMa0OpnLuSbJ/8z/af5L1Vrn/8Uw+pqRVyWw/1mZ7/KO2qt/bjJLJB03I6noSS7IFcB6wJfBZ4GjgrFHGpNXP6nr8tSXJPsDHgHuAk6jH9Q9GGdPqrI2LPP/HUn9++TB1SeY156otRh3LVMz2+Idt1NdWo17+qKw16gCkGe6FwEOBw0spXxx1MBq6W4EnA4tGHcgqaqZu3z06w1LKr0cayernH4GHr4Tl+D+WNB0z9fNromZ7/FpFmXyQxvaYZujF6yqolPIX4OejjmNVNYO372MAvCld+Uopv1pJi/J/LGnKZvDn14TM9vi16vKxC42raQp7c/Pnfk0Toc7P/j1ln5HkG0nuTHJ3kkuSbD9gvmslOTDJD5Isbsr/KMlBSVrdN5P8zySXJlnUPA/8X0n+Ock6zfS5TbPEo5sqF3et89whxbB/ki8nuamJYXGSy5L8rz5l5zfLXivJe5P8IsmyJLck+Zckaw9Yxj5Jrm7m/7skn0vymH5lh20y6zcq/Zq8dTdLTPLmZt+4J8lvk3wqyZyVHONRjHP8JVkjyVuS/GeSJUnuan5/a9vH0jix99u+j05yfJLrmzjvbH6fl2SrluM5qjmud27+fmBbdpXZNcm3ktze/N9vSPLhfv/3ruNy7SRHNOuxrK0mlOOdt7rKLWx+Hp7kuCS/auK6Mcm7k2SKy18vyZ+TXNYz/mHNtipJ9u2ZdmAz/nXN38s1+W621cXNn0f27N9z+8SwczOPPzXnlG8keXLX9DH/x83v85NsmuQzSW5Ncl+6Pssmup2bsp1tvV6SE1PPyUuT/DjJy5sy3efte5IsSHLQZLZ9P0melOTcZl+9K8n3kuzWNf0tzfoeMaD+pkn+kuS/phtL1zyn8rk28PhJ8rgkH2/mtyzJH5N8NcmzhxXzNNdhq9TPhRubsrc3+8tpSTZuK8apxJzmfAzs1PzdfazNn+byh3FueFaSjyX5SR48//4iyUeTbNhnmWun9uvyw9Q+ue5ujsXzkrxwOuvTzH+5z69m2+3XTL65a9st7KozI/aHqcY/xGU/qZn3RWOU+a/m/LNp8/eEr2N6163PvMd9tCgt3NskeUxzLrssyW+aY+LXSb6Yrs+pyS5/VWPLB03EfGAD4B3AT4Bzu6b9uJkGsC3wLuD7wGeAzYFXARcmeUYp5fpOpSQPAb4GvAi4Hvgi9dncnYFTgO2A5T6ohiXJ/wH+GfhDs9wlwIuB/wO8KMnfAQupiYe51A/qM5pxdA2n65PAtcClwG3AxsBLgM8leWIp5QN96nwReAHwTWBxU/5dwCbAAd0FkxwKnADcCZzZDF8EXM7KaYY3lfWbST5C3V5fAy6g7ptvBP4a2GUlxjGfsY8/gM8BrwVuoR57BXgFcCrwfOAfVkag40nycOAyYGvg29RtG+CvgD2Bc4CbWgxhfjPcv1nm0d0Tk7yZut/eBfw78DvqOeDdwEuT7FBKubPPfL8MPJt6XJ7b1BuqiZy3mm+6Oh5C3W8f08R1L/By4MPUR8mWW/eJKKUsSXIlsF2SR5RS/tRM2gHo3JjvSt0fOzrHyoUDZntuM9wPuIQH/0ew4rl2D+p+8k3gNOAp1HPKs5M8pZTyB8b5Hzc2ovb/sAT4D+B+4Lcwpe0MdVt/u5nvecDawGuAL6cmAw6kfqZ9E1gGvBo4JcnvSylnD9gu49mS+ln7U+Bfgc2AvYFvJnltM9/PA/8CvCHJsaWU+3rm8TrqdeC/TjGGfqZy3u97/CR5JnUf3gj4f9T/1SOp+/H3kryilHL+EGOf1Dok2Qz4T2B94PxmPR5K/d/sC3wc+GML8U015jupx8P+rHhsLJzOwod0bngj9XPrEuA7wJrAM4HDgBcn2a5rvgDzqMfZT6nXOEup57vnA7s38ximo6n73t9Q+5O5sxl/J8y4/aGfMeMfplLKz5NcDOycZJtSyg3d05sb96cBXy6l/KYZvbKvY+Yz5HsbYEfgPdSE+pepnx9PAPYCXtZcQ/xkgstfdZVS/PFn3B9gC+qJYF6faXObaQXYv2fam5vxp/aMP6oZfwqwZtf4NYF/a6bt2cJ6PK+Z96+ATbvGr0W9ESrAe/vEObeFWLbuM25t6gfxX4DHdo2f38RxNbBR1/h1gRuB+3rWZwvqRe7twBZd49egnhBLPfxb3WcmvH6j+um3X1MvaDr7yOY9+8ilzbTnjDrOrmmvaab9EFivZ9+4qpn22pmwfYGXNn+fOGDfeMRKimt+7/5PvRhfRk3qPaln2qlN3J/qNx/gGuCRLcY72fPWwmbc+cDDusZvQr3QvBN4yBRjOaaZ9993jfsQNblxEXBL1/g1qDfxC8bZ9nObeR41YJn7N9PvBXbtmfahZtq7xvsfN+M7n1VnAmtNZzv3bOuvAet0jX9BM/526g3JBl3TtgL+DPxoCtu/c0wV4LieadtSz613AOs34z7elN2jp2yoib67gDlD3Fen8rm2wvHTbPMbqV9K7NQz7THU59lv697mK3sdgLc38b+jT/l16Tr22v6ZynZvIYbpnhv+iq7rwa7xr2/m++6ucXOoScOrBtTZeAjr0znW5nWNm9eM26JP+RmzP0wl/haWv1ezrOP7TOvE8XfN35O6jum3bj3zn9A+PtZ8mNq9zSb0uY6hJnyWAN+c6PJX5R8fu9AwXVZKmdcz7nTqB89zOiOa5lMHAb8BDi1d38Y0vx9OPRjb+Lb2dc3wg+XBbCullHub5d4PvKGF5a6glLKgz7g/A5+gXnjt2qfau0spt3eVvwv4AvWDfNuucv9AvfA4pZSysKv8/cA/UdezVVNcv5nkmNL1fHqzj3y2+fM5/auMRGeffk8pZUlnZLNvvLv5c6Xs05OwtHdEKeXPZflvtVa2/0U9Zj5eSul9TvZ9wJ+AfdOn6T3wgVK/dW/LVM9bB5dSlnaV/x31m/k5wBOnGEvnW8ru43dXamL0y8DjkmzTjH8G9RvYQa0eJuusUkrvvD7VDCdzTP4ZeGez/bpN5/PhkFLKsq4636U2qd2Qet6+s2vaTdQWQE9PsuYk4u62iHqz94BSylXUz4MNqN8YQv1GHOrFcrfdqN/Inl1KGVpLuCme9/sdP39PbSF1Sinlkp75/ZraMm3TAfOblimsQ7/z2V3dx17bZsjn7bTODaWUX5YVW+dAvY5cTG2J+EBxagJtGX2uZ0opo2xhMPL9YYY4l9pf2v7dn5tJNgD+J7CAB1unzOTrmAnd20D9jO13HVNqa4eLqC1BHtJWoLOFj11omK7qHVFK+UuS31IvwDq2oX7o/AJ4f/o/fryU2kvvsD2zGa7wHFop5YYk/w1smWSD0r959dAk2Zx6Ut2V2ozrYT1FHtun2grbmNpEDZbfxp31vKSnLKWUm5LcQv2WoTVTXL+ZZKLbetSeSb34mt9n2iXUVjF/uzIDGsMl1G8s39M0qT6fehP24wEXnSvTWOeGO5L8iNqk8knUJpLdrhxhbIPOW4tKKTf2mdd09+HvU8/PuwKk9oXxTOrNYCe+XYEbeLBZ9cDnfidpWMfkwiYR02uqnw939rv5o154b0m9+ep1K7Wl36bN75P1wwHJuvnUR1j+FjijlPKzJJdSm60/vpTS2V5vaoanTWHZA03xvN/v+HleM/yr9H8F6xOa4ZOp55GhmcQ6fJX6OM4nkryI+mjIZcC1pdSvNVeWGfJ5O61zQ3NT9mZgH+ojVXNYvm+6B9ahlLI4ydeorel+nOTLwHeBK0opdw99zSZmxuwPM0Ep5d4knwGOoD6m0Hlj3L7U/fNTXdtlJl/HTPTeBoAkfw+8hfqF4CNZ8V77kdRWW6stkw8apjsHjL+XepHV0el05wnAkWPMb70hxNRrTjMcdODfRv3gnkMLz8F1pHasdyX1xPVd6nOti6gn2C2oF48rfMM6ICHS+fauext31vO3A0L4DS0mH6a6fjPMnX3G9dvWozYHuL35lms5zYf/H6hNAUeuuWB8LvXZ05fx4DdZf0hyKvUb597n6VeWiZwb4MHnQLv9ps+4YZrKeevOAWWntQ+XUv6c5HvAC5NsQr1JXBO4sJRyXZJfU28wPtkMC8NLPtzZJ557mwT2ZNZn0P9rqp8Pg1oO3NvE2G965/8w1W/Bxjq3w4PrAvWxoR2p3xwe2XTw9jJq0m9oibNpnPf7/T861wmvHmexQ71OmMw6lFJ+meQ51Mczdwde2czmliTHl1JOHmZsw4i5TUM4N5xNbbFzE7WF1m+oLRsADumzDntTEy6v5cH+K+5Jcg61ZdOgY6QVM2V/mGE+BbyXmlTqJB/eRG199tmucjP5OubOAeN7721IcjC1P407qP0A/Qq4m7qvv5z6+MVMv/ZtnckHjULnQuwrpZRXjlmyvWVvSm3y1WuznnJtOYx6cXVAb3OuJK/hwR6Jp6oT/6OBn/WZvuk05z+ettdPD1oEbJTkIb037knWombZF48ksj5KKf8NvD71jvEp1G/A3kb9dmQNYFQdkXafG/odMwPPDSvhW62Zct7quAj4O+r/bnvqDUKnl/uLqd+yr0Pt9+BnA1oZjNKg/9dM285jefSA8Z1ze3eM/0FNVrw+yTG009EkTPG8P+D46cS/Zynlq8MMchyTWodSynXA3s259m+AF1Kf/f9YkrtKKf8202Ju2ZTODUm2pSYevgO8pPuzrHlU9129C2oeYzgKOCrJ46kJtv2pj9Bt0SxjpZoh+8OMUUq5tWmh8orUtz1sSO1o8uxSyu+7ik72OqbzqM2g+9gNhhH/ZDRxHk1Nmj2zlHJbz/Tn9a24GrLPB01Up0n0ML7x/Tk1k/jcETz79KNmOLd3QpK/Bh4H3Nz2IxfUNyZAfQ6y105DmP8PB82r+Zbk8UNYxljaXr/VzVjH34+o5/Id+0zbsanzwz7TRqpUPyulnEK9WIX6zcCojHVu2ID6jPI9wHUrLaIHzZTzVkf3s927UJ+Jvadr2kbAW6mdhU2kv4dhfr5Mx0zbzmN5ZpJH9Bk/txl21oXmYv4z1GbrL6W2gFhC7R9imIZ53v9BM1zZN5BTWodSyr2llKtLKf9C7TwPVt75bLIx3wcwjf5GxjLVc0NnHb7ap/Xbc1jxMZLllFJuKaV8gdqa7hfA89POqy0ndK4a8f4wllGca09thm/iwce9ehOfk72OuaMZrnAtm2R96uPdEzHM7fFIatLj8j6Jh/V48LG+tpY/a5h80ETdQf22aPPpzqjpvOsU6rdIJydZ4UMlyWZJnjLdZfVxejN8f5JHdS1vTeB46jGxMjLTC5vh3O6RzXOCw+hU5wvUHq7fnmSLrvmvARxH+8f+wmY4t3vkENdvdTPW8dfZpz+U+ipL4IHXWn64+XNGfNuS5Gnd+2OXzre4o3pWF+prCTvHzF/3TPvf1Nenfb67U8GVaKactzqupiaQ9wSeyvI3EZ3f/7kZTuSRi07ncNP+fJmmmbadxzKH2lroAc23x/9A/RbxKz3lP0W90P04tR+KLw7oM2I6FjbDuT1xTeW8fx619cnbkrykX4Ekz+s+5w3JwmY4t2dZK6xDkuck6dcCZWWfzxY2w7ndI8fY7m0eb1M9NyxshnO7Z9Y8vvGJ3oUkeVSS7fosf13gEdQm8Ss04R+CgdtuBu0PYxnFufZCaj8f+1E7mryhlHJxT5lJXcc0566fAzt03ys05+oTGCdZ1WVo9zbUVwTfDTyrSTZ0YnoI9VGMR7a8/FnDxy40IaW+w/kK4AVJvkA9kdxH7WBnKv43tUnaW4CXJrmI2unWJtS+IHag9jB/7XRj71ZKuTzJR6hN+H7aPBt4F/U97k8Dvke9OW/bqcABwL83HSXd2ix/d+BL1GcZp6yUsjDJe4CPAj9Kcjb1gvRF1MzsNcD/mM4yxtHq+q1uxjr+SilfTLIn9UP9Z0nO5cHnC7cEvtR8IzQTvBA4Icnl1AuH31G/Td6T2oxyZRx7fTXHzCHUC90fJvkS8HvqN4fPo8b77sFzaDW2mXLe6sRzf5JLqP83WL7H+l8lWUB9U8F99On0to/rqeeIfZL8mfqcbAE+V0r55VCDH8NM287juBR4Q3MDdhk1mb83NUHy5lLKco9aNf+Xb1D7eoDhP3IBQzzvNx26vZLaad83mnPGj6kX948Hnk19ZelmDPembjLr8FpqcuQS6mtB76Du9y+lPm5w0hDjGlbMUI/XVwP/keR8aieRvyylfG66gUzj3PCf1P34lc3/+nvUm/YXU88Pv+5Z1GOBHyS5jvqN+C3UBPEe1EePTm4hudZZn38CPt2cH5ZQO5z9ODNnfxjLWPG3opRSkpxGTQpAn3PPFK9jjqMmJC5L8u/Ulok7U/vR+Qn1HmO82IZ2b9Ps+ycD7wH+K8l51Ddo7Uxt8XNx8/uEll9KuWayMcwaZQa879Of2fFDbRb3NWrm9H6ad98y/jvaF1J7F+8dH2qvtxdS34X+Z+qH5veoHdQ8vsV12adZzp+oJ6yfUZMdD+0pd1SzbnNbiGF7aub/jiaO71FPtCtsT8Z4Z3HzP1jhPcTNtNdQP5jvod5IfZ76jvSB8xvF+o1wn96Cyb3He2SxDzr+mmlrAAdSe2W+u/m5mtqXwhozZftSe6Y/oYnz99QLsoXAOcD2KzGusY6n3agdtt3RxHcjtbf2DSYzn5binuh5ayF9zrnNtKGc03jwnfaLgDV7pv1rM+2KiW4z6s3khc387u+OcaxzXDO9APMnuJwVyk51O09gW4+1nw08z4wT2wPHVHM8ndfsq3dTb95eNEbdPZu6/9niPjqUz7WuMptQv/n8abOOS6jN6s+hPtu/1qjWAdiO2nniT6jXMEup54vPAk9raxsPYbuvSX0rw03U1l7jHhOTjGWq54aNqImUhc1xt6CJ8+G9xxn1S5QjmnW+lXquvq3Zp14DZAjr8cCx1jP+MOrjd8ua6Qtn2v4wlfhbjmVD6k31PcDGA8pM+joGeD31/LyM2tfCv1L7P5nPBD+bGeK9DfVL/cOoX5wubWL6HLWD93n0OecPWv7K3l9W5k+aFZckSdIqKvWVlUcCbyirWcd3kkYnyVzqN/+fL6XsO9poNGomHyRJklZhTeeUv6A2SX58KWUmPH8uaTXQPN7zYuC5pZQrRh2PRss+HyRJklZBSf6e2sv6S6nP0L/TxIOktiV5OrUPjmdREw9fN/EgMPkgSZK0qno1tZf53wIfAk4cbTiSVhPPovbZsRj4d2p/DpKPXUiSJEmSpHatMeoAJEmSJEnSqs3kgyRJkiRJapXJB0mSJEmS1CqTD5IkSZIkqVUmHyRJkiRJUqtMPkiSJEmSpFaZfJAkSZIkSa0y+SBJkiRJklpl8kGSJEmSJLXK5IMkSZIkSWqVyQdJkiRJktQqkw+SJEmSJKlVJh8kSZIkSVKr/j/kkWSNArtuvgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 612x180 with 1 Axes>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 166,
       "width": 527
      },
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig, ax = plt.subplots(1,1,figsize=(8.5,2.5))\n",
    "barcontainers = ax.bar(x=wds, height=counts, color='#FEE08F')\n",
    "\n",
    "# make it look good\n",
    "ax.spines['top'].set_visible(False)\n",
    "ax.spines['right'].set_visible(False)\n",
    "ax.spines['left'].set_linewidth(.5)\n",
    "ax.spines['bottom'].set_linewidth(.5)\n",
    "for rect in barcontainers.patches:\n",
    "    rect.set_linewidth(.5)\n",
    "    rect.set_edgecolor('grey')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Extract person and place names from a document\n",
    "\n",
    "**Warning**: On M1 macs, use `conda install spacy` not `pip install spacy`. See [issues with M1 and spaCy](https://github.com/explosion/spaCy/issues/7962).  (Hmm...Aug 1, 2021 `pip` worked again on Big Sur OS X.)\n",
    "\n",
    "Imagine trying to analyze a text document. One of the things you might want to know is who is referenced within. This is actually an extremely hard problem to solve, but fortunately the people at [spaCy](https://spacy.io) have provided a library that does a very good job. All we have to do is put the glue around it. To install it, we need a library and their model of English:\n",
    " \n",
    "```bash\n",
    "$ pip install spacy\n",
    "$ python -m spacy download en_core_web_sm\n",
    "...\n",
    "```\n",
    "\n",
    "If we have a library that can identify the names within a document, the overall process is straightforward:\n",
    "\n",
    "1. Load the text of a file into a string variable\n",
    "2. Give the string to the spaCy library and ask it to analyze the text\n",
    "3. Walk the list of names and add them to a set, which will create a unique collection\n",
    "\n",
    "Our implementation starts with an import and loading of the English model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [],
   "source": [
    "import spacy\n",
    "nlp = spacy.load(\"en_core_web_sm\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we load the text of a sample file and give it to the `nlp` object that represents the English model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(f\"../data/berlitz1/WhatToJamaica.txt\", \"r\") as f:\n",
    "    s = f.read()\n",
    "doc = nlp(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `doc` object represents the analyzed document and `doc.ents` represents a list of entities found during analysis. We can walk those entities with a for-each loop and, if the type of the entity is a person, we can add it to our unique set.  From the documentation of spaCy, I saw that `entity.label_` gives us the associated entity type and `entity.text` gives us the text of that entity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Accompong',\n",
       " 'Alfred Mitchell',\n",
       " 'Andrew\\n        Young',\n",
       " 'Annie',\n",
       " 'Arawak',\n",
       " 'Athenry Gardens',\n",
       " 'Bamboo Avenue',\n",
       " 'Barrett',\n",
       " 'Bettin',\n",
       " 'Bligh',\n",
       " 'Bob Marley',\n",
       " 'Bob Marley Museum',\n",
       " 'Bonnie View Hotel',\n",
       " 'Charles Square',\n",
       " 'Charlie',\n",
       " 'Charlie Chaplin',\n",
       " 'Cocktail',\n",
       " 'Cornwall Barracks',\n",
       " 'Coward',\n",
       " 'Dustin Hoffman']"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "names = set()\n",
    "for entity in doc.ents:\n",
    "    if entity.label_==\"PERSON\":\n",
    "        names.add(entity.text)\n",
    "sorted(names)[:20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That does a reasonable job, but also seems to include a lot of organizations and locations. For fun, we can also look for organizations and geopolitical entities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Air Force',\n",
       " 'Alligator Hole',\n",
       " 'Amsterdam',\n",
       " 'Anchovy',\n",
       " 'Annie Palmer\\n        ',\n",
       " 'Annie Palmers',\n",
       " 'Appleton Distillery',\n",
       " 'Berridale',\n",
       " 'Black\\n        River',\n",
       " 'Blue Lagoon',\n",
       " 'Blue Mountain',\n",
       " 'Blue Mountain\\n        ',\n",
       " 'Blue Mountain Peak',\n",
       " 'Bond',\n",
       " 'Boston',\n",
       " 'Boston Bay',\n",
       " 'Britain',\n",
       " 'British\\n        Intelligence',\n",
       " 'Canoe\\n        Valley Wetland',\n",
       " 'Carinosa']"
      ]
     },
     "execution_count": 183,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "orgs = set()\n",
    "for entity in doc.ents:\n",
    "    if entity.label_==\"ORG\" or entity.label_==\"GPE\":\n",
    "        orgs.add(entity.text)\n",
    "sorted(orgs)[:20]"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}