day7_reading_journal.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 7 Reading Journal\n",
    "\n",
    "This journal includes several required exercises, but it is meant to encourage active reading more generally.  You should use the journal to take detailed notes, catalog questions, and explore the content from Think Python deeply.\n",
    "\n",
    "Reading: Think Python Chapter 11, 12\n",
    "\n",
    "**Due: Thursday, February 18 at 12 noon**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Chapter 11](http://www.greenteapress.com/thinkpython/html/thinkpython012.html)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quick check:** In about one sentence using your own words, what is a dictionary?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Dictionary** = general list that contains any and all types\n",
    "  * maps a set of indices to a set of values (**key-value pair** / **item**)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}\n"
     ]
    }
   ],
   "source": [
    "# given a string, count how many times each letter appears\n",
    "\n",
    "def histogram(s):\n",
    "    d = dict()    # create empty dictionary\n",
    "    for c in s:   # traverse string\n",
    "        if c not in d:\n",
    "            d[c] = 1\n",
    "        else:\n",
    "            d[c] += 1\n",
    "    return d\n",
    "h = histogram('brontosaurus')\n",
    "print h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Lookup** = given a dictionary d and a key k, you can find the corresponding value v\n",
    "  * v = d[k]\n",
    "  * **Reverse lookup** = you have v and want to find k\n",
    "    * have to search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r\n"
     ]
    }
   ],
   "source": [
    "def reverse_lookup(d,v):\n",
    "    for k in d:\n",
    "        if d[k] == v:\n",
    "            return k\n",
    "    raise ValueError\n",
    "h = histogram('parrot')\n",
    "k = reverse_lookup(h,2)\n",
    "print k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}\n",
      "{1: ['a', 'p', 't', 'o'], 2: ['r']}\n"
     ]
    }
   ],
   "source": [
    "# invert dictionary\n",
    "# ex: original dictionary maps letters to frequencies\n",
    "# inverted dictionary maps frequencies to letters\n",
    "\n",
    "def invert_dict(d):\n",
    "    inverse = dict()\n",
    "    for key in d:\n",
    "        val = d[key]\n",
    "        if val not in inverse:\n",
    "            inverse[val] = [key]\n",
    "        else:\n",
    "            inverse[val].append(key)\n",
    "    return inverse\n",
    "hist = histogram('parrot')\n",
    "print hist\n",
    "inverse = invert_dict(hist)\n",
    "print inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "State Diagram for Inverted Dictionary of Parrot\n",
    "![text](http://www.greenteapress.com/thinkpython/html/thinkpython018.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Keys in dictionary need to be **hashable** \n",
    "  * **hash** = function that takes a value and returns an integer\n",
    "  * dictionaries use these integers (hash values) to store and look up key-value pairs\n",
    "  * best used when keys are immutable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Memo** = previously computed value stored for later use\n",
    "  * can store values in a dictionary!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# fibonacci code using memos\n",
    "\n",
    "known = {0:0,1:1}\n",
    "      # dictionary to keep track of fibonacci numbers we already know\n",
    "      # starts with two items: 0 maps to 0, 1 maps to 1 (base cases)\n",
    "     \n",
    "def fibonacci(n):\n",
    "    if n in known:\n",
    "        return known[n]\n",
    "\n",
    "    res = fibonacci(n-1) + fibonacci(n-2)\n",
    "    known[n] = res\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Global** variables = variables that belong to frame called --main--\n",
    "  * can be accessed by any function\n",
    "  * common to use globa var for **flags**\n",
    "  * cannot reassign global var inside functions \n",
    "    * must **declare** global var before you use it\n",
    "  * can add, remove, replace elements of global list/dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 11.2"
   },
   "source": [
    "### Exercise 2  \n",
    "\n",
    "Dictionaries have a [method called `get`](https://docs.python.org/2/library/stdtypes.html#mapping-types-dict) that takes a key and a default value. If the key appears in the dictionary, `get` returns the corresponding value; otherwise it returns the default value. For example:\n",
    "\n",
    "```\n",
    ">>> h = histogram('a')\n",
    ">>> print h\n",
    "{'a': 1}\n",
    ">>> h.get('a', 0)\n",
    "1\n",
    ">>> h.get('b', 0)\n",
    "0\n",
    "```\n",
    "\n",
    "Use `get` to write `histogram` more concisely. You should be able to eliminate the `if` statement. Add unit tests for your histogram implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false,
    "solution": "Exercise 11.2"
   },
   "outputs": [],
   "source": [
    "def histogram(s,v):\n",
    "    \"\"\"\n",
    "    shorten histogram function using get method\n",
    "    \n",
    "    >>> histogram('banana',0)\n",
    "    {'a': 3, 'b': 1, 'n': 2}\n",
    "    \"\"\"\n",
    "    d = dict()   \n",
    "    for c in s:\n",
    "        d[c] = d.get(c,v) + 1\n",
    "    return d\n",
    "\n",
    "import doctest\n",
    "doctest.run_docstring_examples(histogram, globals())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 11.4"
   },
   "source": [
    "### Exercise 4  \n",
    "\n",
    "Modify `reverse_lookup` so that it builds and returns a list of all keys that map to `v`, or an empty list if there are none. Add unit tests for your implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "solution": "Exercise 11.4"
   },
   "outputs": [],
   "source": [
    "def reverse_lookup(d, v):\n",
    "    \"\"\"\n",
    "    modify function to build and return a list of all keys that map to \n",
    "    v or to return an empty list if there are none\n",
    "    \n",
    "    >>> reverse_lookup(histogram('moonshine',0),2)\n",
    "    ['o', 'n']\n",
    "    \n",
    "    >>> reverse_lookup(histogram('happy',0),3)\n",
    "    None\n",
    "    \"\"\"\n",
    "    \n",
    "    d_new = []\n",
    "    for k in d:\n",
    "        if d[k] == v:\n",
    "            d_new.append(k)\n",
    "    return d_new\n",
    "    raise ValueError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you'd like to learn more about errors and exceptions, you can check out the [Python tutorial](https://docs.python.org/2/tutorial/errors.html) or read ahead to [Appendix A](http://www.greenteapress.com/thinkpython/html/thinkpython021.html) of Think Python. If you choose to use doctest for your unit testing, it can also [deal with exceptions](https://docs.python.org/2/library/doctest.html#what-about-exceptions)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quick check** What type of objects can be used as keys to a dictionary, i.e. what property must they have?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 11.6"
   },
   "source": [
    "### Exercise 6 (modified)\n",
    "\n",
    "Create a memoized version of your Levenshtein distance function from Day 7. What kind of performance change do you see?\n",
    "\n",
    "Optional: If you'd like to get some quantitative results, you could check out the [timeit](https://docs.python.org/2/library/timeit.html) module\n",
    "\n",
    "Note: You can also study Fibonacci here if you prefer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false,
    "solution": "Exercise 11.6"
   },
   "outputs": [],
   "source": [
    "def Lev1(a,b):\n",
    "    # first pass at Levenshtein distance code\n",
    "    if not a:\n",
    "        return len(b)\n",
    "    if not b:\n",
    "        return len(a)\n",
    "    # Strategy 1: Change the first character to match\n",
    "    if a[0] == b[0]:\n",
    "        # First characters already match, so no extra distance\n",
    "        option1 = levenshtein(a[1:], b[1:])\n",
    "    else:\n",
    "        option1 = levenshtein(a[1:], b[1:]) + 1\n",
    "\n",
    "    # Strategy 2: Insert b[0] as the first character of a\n",
    "    option2 = 1 + levenshtein(a, b[1:])\n",
    "    \n",
    "    # Strategy 3: Delete the first character of a\n",
    "    option3 = 1 + levenshtein(a[1:], b)\n",
    "\n",
    "    return min(option1, option2, option3)\n",
    "\n",
    "def Lev2(a,b):\n",
    "    # memoized version\n",
    "    x = len(a)\n",
    "    y = len(b)\n",
    "    \n",
    "    if x == 0:\n",
    "        return y\n",
    "    if y == 0:\n",
    "        return x\n",
    "    \n",
    "    return min(Lev2(a[:x-1],b)+1, Lev2(a,b[:y-1])+1, Lev2(a[:x-1],b[:y-1]+substCost(a[y-1],b[x-1])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Chapter 12](http://www.greenteapress.com/thinkpython/html/thinkpython013.html)\n",
    "\n",
    "**Quick check:** In about one sentence using your own words, what is a tuple?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Tuple** = sequence of values\n",
    "  * any type, indexed by integers (~ to lists)\n",
    "  * tuples are *immutable*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "()\n",
      "('r', 'a', 'c', 'h', 'e', 'l')\n"
     ]
    }
   ],
   "source": [
    "# create a tuple by including a final comma\n",
    "t1 = 'a',\n",
    "type(t1)\n",
    "\n",
    "\n",
    "\n",
    "# or use built-in function tuple\n",
    "\n",
    "   # no arguments creates empty tuple\n",
    "t = tuple()\n",
    "print t\n",
    "\n",
    "   # if argument = sequence (string, list, tuple), \n",
    "    # returns tuple with elements of sequence\n",
    "t2 = tuple('rachel')\n",
    "print t2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "('b', 'c')\n",
      "('A', 'b', 'c', 'd', 'e')\n"
     ]
    }
   ],
   "source": [
    "# most list operators work on tuples\n",
    "\n",
    "# bracket operator indexes element\n",
    "a = ('a','b','c','d','e')\n",
    "print a[0]\n",
    "\n",
    "# slice operator\n",
    "print a[1:3]\n",
    "\n",
    "# can't modify elements in tuple, but can replace\n",
    "a = ('A',) + a[1:]\n",
    "print a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "monty\n",
      "python.org\n"
     ]
    }
   ],
   "source": [
    "# tuple assignment\n",
    "# left side = tuple of variables, right side = tuple of expressions\n",
    "# number of elements on L side must == number on R side\n",
    "# R side can be any sequence (string, list, tuple)\n",
    "\n",
    "addr = 'monty@python.org'\n",
    "uname, domain = addr.split('@')\n",
    "print uname\n",
    "print domain\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 1)\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# when returning tuples, returns multiple values \n",
    "\n",
    "# ex: returning quotient and remainder\n",
    "q = divmod(7,3)\n",
    "print q\n",
    "\n",
    "quot,rem = divmod(7,3)\n",
    "print quot\n",
    "print rem\n",
    "\n",
    "# ex: returning biggest/smallest elements of sequence\n",
    "def min_max(l):\n",
    "    return min(l),max(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beginning argument with (*) gathers/scatters arguments into tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2.0, '3')\n"
     ]
    }
   ],
   "source": [
    "def printall(*args):\n",
    "    print args\n",
    "printall(1,2.0,'3')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "divmod expected 2 arguments, got 1",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-14-cb11f7a184b5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[0mt\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m7\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mdivmod\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mt\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: divmod expected 2 arguments, got 1"
     ]
    }
   ],
   "source": [
    "t = (7,3)\n",
    "divmod(t)\n",
    "\n",
    "# need to scatter tuple because divmod needs 2 input arguments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 1)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = (7,3)\n",
    "divmod(*t)\n",
    "\n",
    "# (*) scatters tuple and so, function works"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('a', 0), ('b', 1), ('c', 2)]\n",
      "[('A', 'E'), ('n', 'l'), ('n', 'k')]\n"
     ]
    }
   ],
   "source": [
    "# zip = built-in function that zips 2+ sequences into list of tuples\n",
    "# each tuple contains one element from each sequence\n",
    "\n",
    "s = 'abc'\n",
    "t = [0,1,2]\n",
    "print zip(s,t)\n",
    "\n",
    "# if sequences aren't same length, takes length of shorter one\n",
    "print zip('Anne','Elk')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# can use tuples to traverse 2+ sequences at the same time\n",
    "\n",
    "# ex: input 2 sequences and returns True if there is an index such that\n",
    "# t1[i] == t2[i]:\n",
    "\n",
    "def has_match(t1,t2):\n",
    "    for x, y in zip(t1,t2):\n",
    "        if x == y:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 a\n",
      "1 b\n",
      "2 c\n"
     ]
    }
   ],
   "source": [
    "# enumerate = built-in function that traverses elements of sequence\n",
    "# and their indices\n",
    "\n",
    "for index,element in enumerate('abc'):\n",
    "    print index,element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('a', 0), ('c', 2), ('b', 1)]\n",
      "0 a\n",
      "2 c\n",
      "1 b\n",
      "{'s': 1, 'r': 0, 't': 2}\n"
     ]
    }
   ],
   "source": [
    "# dictionaries have method (.items) that returns list of tuples\n",
    "# each tuple is a key-value pair\n",
    "\n",
    "d = {'a':0,'b':1,'c':2}\n",
    "t = d.items()\n",
    "print t\n",
    "\n",
    "# can use .items to traverse keys and values of dictionary\n",
    "for key,val in d.items():\n",
    "    print val,key\n",
    "\n",
    "# can use list of tuples to initialize a dictionary\n",
    "r = [('r',0), ('t',2), ('s',1)]\n",
    "z = dict(r)\n",
    "print z\n",
    "\n",
    "# method (.update) also takes list of tuples and adds them to existing\n",
    "# dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# relational operators work with tuples\n",
    "# compares first element of sequence\n",
    "# only if they are equal does Python compare next elements\n",
    "\n",
    "(0,1,2) < (0,3,4)\n",
    "\n",
    "(0,1,200000) < (0,3,4)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**DSU**\n",
    "  * Decorate sequence by building list of tuples with 1+ sort keys before elements from sequence\n",
    "  * Sort list of tuples\n",
    "  * Undecorate by extracting sorted elements of the sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['banana', 'happy', 'poop']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sort_by_length(words):\n",
    "    t = []\n",
    "    for word in words:\n",
    "        t.append((len(word),word))\n",
    "        \n",
    "    t.sort(reverse=True)\n",
    "    \n",
    "    res = []\n",
    "    for length,word in t:\n",
    "        res.append(word)\n",
    "    return res\n",
    "sort_by_length(['poop','banana','happy'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strings are more limited than other sequences\n",
    "  * elements have to be characters\n",
    "  * immutable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists are more common than tuples bc they are mutable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use tuples when:\n",
    "  * it's simpler to create a tuple over a list\n",
    "  * need immutable tuple/string to use sequence as a dictionary key\n",
    "  * need to reduce unexpected behavior due to aliasing when passing a sequence as an argument to a function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tuples can't use methods (.sort, .reverse) but can use (.sorted, .reversed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 12.1"
   },
   "source": [
    "### Exercise 1  \n",
    "\n",
    "Many of the built-in functions use variable-length argument tuples. For example, `max` and `min` can take any number of arguments:\n",
    "\n",
    "```\n",
    ">>> max(1,2,3)\n",
    "3\n",
    "```\n",
    "\n",
    "But `sum` does not.\n",
    "\n",
    "```\n",
    ">>> sum(1,2,3)\n",
    "TypeError: sum expected at most 2 arguments, got 3\n",
    "```\n",
    "\n",
    "Write a function called ```sumall``` that takes any number of arguments and returns their sum. \n",
    "\n",
    "Write unit tests for your function. Do I actually need to keep saying this? Let's assume it's always a good idea :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "solution": "Exercise 12.1"
   },
   "outputs": [],
   "source": [
    "def sumall(*args):\n",
    "    \"\"\"\n",
    "    takes any number of arguments and returns their sum\n",
    "    \n",
    "    >>> sumall(1,2,3)\n",
    "    6\n",
    "    \n",
    "    >>> sumall(100,5,30)\n",
    "    135\n",
    "    \n",
    "    >>> sumall(1.4,2,5.6)\n",
    "    9.0\n",
    "    \"\"\"\n",
    "    total = 0\n",
    "    for arg in args:\n",
    "        total = total + arg\n",
    "    return total\n",
    "\n",
    "import doctest\n",
    "doctest.run_docstring_examples(sumall, globals())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you're interested in more flexible ways to pass arguments to functions, check out the [Python tutorial](https://docs.python.org/2/tutorial/controlflow.html#more-on-defining-functions). For instance, you can also use keyword arguments, which are collected into a dictionary just like `*` gathers variable numbers of positional arguments into a tuple.\n",
    "\n",
    "This pattern is very common for defining functions with complex optional behaviors in Python, and you will often see definitions like:\n",
    "\n",
    "```\n",
    "def my_func(required_argument1, *arguments, **keywords):\n",
    "    ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 12 sort"
   },
   "source": [
    "### Exercise\n",
    "\n",
    "Write a function `sort_by_last_letter` that takes a list of words and returns a new list with the words sorted alphabetically by the _last letter_ in the word. Hint: use the **Decorate, Sort, Undecorate** pattern. Write unit tests for your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "solution": "Exercise 12 sort"
   },
   "outputs": [],
   "source": [
    "def sort_by_last_letter(words):\n",
    "    \"\"\"\n",
    "    takes list of words and returns new list with words sorted\n",
    "    alphabetically by last letter in the word\n",
    "    \n",
    "    >>> sort_by_last_letter(['poop', 'turd', 'fart'])\n",
    "    ['turd', 'poop', 'fart']\n",
    "    \n",
    "    >>> sort_by_last_letter(['what', 'bat', 'wart'])\n",
    "    ['bat', 'what', 'wart']\n",
    "    \"\"\"\n",
    "    \n",
    "    sort_words = []\n",
    "    for word in words:            \n",
    "        sort_words.append((word[::-1], word))\n",
    "        \n",
    "    sort_words.sort()\n",
    "    \n",
    "    res_words = []\n",
    "    for last_letter, word in sort_words:\n",
    "        res_words.append(word)\n",
    "    return res_words\n",
    "import doctest\n",
    "doctest.run_docstring_examples(sort_by_last_letter, globals())    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quick check** Give an example of when you might use each sequence type:\n",
    "\n",
    "- tuple\n",
    "\n",
    "- list\n",
    "\n",
    "- string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 12.3"
   },
   "source": [
    "### Exercise 3  \n",
    "\n",
    "Write a function called `most_frequent` that takes a string and prints the letters in decreasing order of frequency. Find text samples from several different languages and see how letter frequency varies between languages. Compare your results with the tables at http://en.wikipedia.org/wiki/Letter_frequencies. \n",
    "\n",
    "Allen's solution (try it on your own first): http://thinkpython.com/code/most_frequent.py. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false,
    "solution": "Exercise 12.3"
   },
   "outputs": [],
   "source": [
    "def most_frequent(s):\n",
    "    \"\"\"\n",
    "    takes a string and prints letters in decreasing order of frequency\n",
    "    \n",
    "    >>> most_frequent(\"apple\")\n",
    "    ['p', 'l', 'e', 'a']\n",
    "    \n",
    "    >>> most_frequent(\"manzana\")\n",
    "    ['a', 'n', 'z', 'm']\n",
    "    \n",
    "    >>> most_frequent(\"pomme\")\n",
    "    ['m', 'p', 'o', 'e']\n",
    "    \n",
    "    >>> most_frequent(\"eat apples\")\n",
    "    ['p', 'e', 'a', 't', 's', 'l']\n",
    "    \"\"\"\n",
    "    s = s.replace(' ', '')\n",
    "    d = {}\n",
    "    for c in s:\n",
    "        d[c] = d.get(c,0) + 1\n",
    "\n",
    "    sort_d = []\n",
    "    for x, freq in d.items():\n",
    "        sort_d.append((freq, x))\n",
    "        \n",
    "    sort_d.sort(reverse = True)\n",
    "    \n",
    "    res_d = []\n",
    "    for freq, x in sort_d:\n",
    "        res_d.append(x)\n",
    "    return res_d\n",
    "\n",
    "import doctest\n",
    "doctest.run_docstring_examples(most_frequent, globals())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Exercise 12.6"
   },
   "source": [
    "### Challenge: Exercise 6   (optional)\n",
    "\n",
    "From a [Car Talk Puzzler](http://www.cartalk.com/content/puzzlers):\n",
    "\n",
    "What is the longest English word, that remains a valid English word, as you remove its letters one at a time?\n",
    "\n",
    "Now, letters can be removed from either end, or the middle, but you can’t rearrange any of the letters. Every time you drop a letter, you wind up with another English word. If you do that, you’re eventually going to wind up with one letter and that too is going to be an English word—one that’s found in the dictionary. I want to know what’s the longest word and how many letters does it have?\n",
    "\n",
    "I’m going to give you a little modest example: Sprite. Ok? You start off with sprite, you take a letter off, one from the interior of the word, take the r away, and we’re left with the word spite, then we take the e off the end, we’re left with spit, we take the s off, we’re left with pit, it, and I. \n",
    "\n",
    "Write a program to find all words that can be reduced in this way, and then find the longest one.\n",
    "\n",
    "This exercise is a little more challenging than most, so here are some suggestions:\n",
    "\n",
    "- You might want to write a function that takes a word and computes a list of all the words that can be formed by removing one letter. These are the “children” of the word.\n",
    "- Recursively, a word is reducible if any of its children are reducible. As a base case, you can consider the empty string reducible.\n",
    "- The word list from [Chapter 9.1](http://www.greenteapress.com/thinkpython/html/thinkpython010.html) Exercise 1 doesn’t contain single letter words. So you might want to add “I”, “a”, and the empty string.\n",
    "- To improve the performance of your program, you might want to memoize the words that are known to be reducible.\n",
    "\n",
    "Allen's solution: http://thinkpython.com/code/reducible.py."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "solution": "Exercise 12.6"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "is_question": true,
    "problem": "Feedback"
   },
   "source": [
    "## Reading Journal feedback\n",
    "\n",
    "Have any comments on this Reading Journal? Feel free to leave them below and we'll read them when you submit your journal entry. This could include suggestions to improve the exercises, topics you'd like to see covered in class next time, or other feedback.\n",
    "\n",
    "If you have Python questions or run into problems while completing the reading, you should post them to Piazza instead so you can get a quick response before your journal is submitted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "feedback_response": true,
    "solution": "Feedback"
   },
   "source": [
    " "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit Metadata",
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}