day4_reading_journal.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 4 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 10\n",
    "\n",
    "**Due: Thursday, February 4 at 12 noon**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Chapter 10](http://www.greenteapress.com/thinkpython/html/thinkpython011.html)\n",
    "\n",
    "You may want to review [state diagrams in Chapter 2](http://www.greenteapress.com/thinkpython/html/thinkpython003.html#toc13). [Python Tutor](http://pythontutor.com/) is also helpful for visualizing the state of your program.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of using | total = total + x |\n",
    "  * can use | total += x |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use (pop) to delete an element from a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'c']\n",
      "b\n"
     ]
    }
   ],
   "source": [
    "# use pop to remove element from list\n",
    "t = ['a','b','c']\n",
    "x = t.pop(1)\n",
    "print t\n",
    "print x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'c']\n"
     ]
    }
   ],
   "source": [
    "# don't need the removed value returned, use del operator\n",
    "t = ['a','b','c']\n",
    "del t[1]\n",
    "print t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'c']\n"
     ]
    }
   ],
   "source": [
    "# don't know index, use remove\n",
    "t = ['a','b','c']\n",
    "t.remove('b')\n",
    "print t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'f']\n"
     ]
    }
   ],
   "source": [
    "# remove more than one element, use del with a slice index\n",
    "t = ['a','b','c','d','e','f']\n",
    "del t[1:5]\n",
    "print t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "List is a built-in function (try to avoid using it as a variable name)\n",
    "  * converts string to a list of characters\n",
    "  * breaks string into individual characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['s', 'p', 'a', 'm']\n"
     ]
    }
   ],
   "source": [
    "s = 'spam'\n",
    "t = list(s)\n",
    "print t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Break strings into words\n",
    "  * split method \n",
    "  * delimiter\n",
    "  * join is the inverse of split (takes list of strings and concatenates elements)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['pining', 'for', 'the', 'fjords']\n"
     ]
    }
   ],
   "source": [
    "# split method\n",
    "s = 'pining for the fjords'\n",
    "t = s.split()\n",
    "print t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['spam', 'spam', 'spam']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# delimiter\n",
    "s = 'spam-spam-spam'\n",
    "delimiter = '-'\n",
    "s.split(delimiter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'pining for the fjords'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# join\n",
    "t = ['pining for the fjords']\n",
    "delimiter = ' '\n",
    "delimiter.join(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If two lists have the same elements, they are **equivalent** but not **identical**\n",
    "  * can use (is) operator to check whether two variables are identical (aka if Python created one object that both variables refer to, or not)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "  * **reference** = association of a variable with an object\n",
    "  * **alias** = object with more than one reference (and more than one name)\n",
    "    * if aliased object is mutable, changes made with one alias affect the other"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4  \n",
    "Write a function called `middle` that takes a list and returns a new list that contains all but the first and last elements. So `middle([1,2,3,4])` should return `[2,3]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def middle(input_list):\n",
    "    \"\"\"\n",
    "    Takes input list and returns new list with all elements \n",
    "    excluding first and last elements\n",
    "    \n",
    "    >>> middle([1,2,3,4])\n",
    "    [2, 3]\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    output_list = []\n",
    "    del input_list[0]\n",
    "    del input_list[len(input_list) - 1]\n",
    "    output_list = input_list\n",
    "    return output_list\n",
    "\n",
    "\n",
    "    import doctest\n",
    "    doctest.run_docstring_examples(middle, globals())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5  \n",
    "Write a function called `chop` that takes a list, modifies it by removing the first and last elements, and returns `None`.\n",
    "\n",
    "What is the difference between `middle` and `chop`? Sketch out the program state or take a look at each in Python Tutor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def chop(input_list):\n",
    "    \"\"\"\n",
    "    Takes input list and modifies it by excluding first and last elements\n",
    "    Returns none\n",
    "    \n",
    "    >>> middle([1,2,3,4])\n",
    "    None\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    del input_list[0]\n",
    "    del input_list[len(input_list) - 1]\n",
    "    return None\n",
    "\n",
    "\n",
    "    import doctest\n",
    "    doctest.run_docstring_examples(chop, globals())\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7  \n",
    "Two words are anagrams if you can rearrange the letters from one to spell the other. Write a function called `is_anagram` that takes two strings and returns `True` if they are anagrams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_anagram(string_one, string_two):\n",
    "    \"\"\"\n",
    "    Takes input two strings and returns True is they are anagrams\n",
    "    \n",
    "    >>> is_anagram(\"car\", \"arc\")\n",
    "    True\n",
    "    \n",
    "    >>> is_anagram(\"blah\", \"nope\")\n",
    "    False\n",
    "    \"\"\"\n",
    "    if len(string_one) == len(string_two):  # words are the same length\n",
    "        for letter in string_one:\n",
    "            if letter in string_two:\n",
    "                return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "    import doctest\n",
    "    doctest.run_docstring_examples(is_anagram, globals())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 8  \n",
    "The (so-called) Birthday Paradox:\n",
    "1. Write a function called `has_duplicates` that takes a list and returns `True` if there is any element that appears more than once. It should not modify the original list.\n",
    "2. If there are 23 students in your class, what are the chances that two of you have the same birthday? You can estimate this probability by generating random samples of 23 birthdays and checking for matches. Hint: you can generate random birthdays with the randint function in the [random module](https://docs.python.org/2/library/random.html).\n",
    "\n",
    "You can read about this problem at http://en.wikipedia.org/wiki/Birthday_paradox, and you can download Allen's solution from http://thinkpython.com/code/birthday.py."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def has_duplicates(input_list):\n",
    "    \"\"\"\n",
    "    Part One: \n",
    "    Take input list and returns True if there is a repeat element\n",
    "    \n",
    "    Part Two:\n",
    "    Estimate probability that 2 students in class of 23 have the same \n",
    "    birthday\n",
    "    \n",
    "    >>> has_duplicates([1,1,2])\n",
    "    True\n",
    "    >>> has_duplicates([1,2,3])\n",
    "    False\n",
    "    >>> has_duplicates([\"hey\",\"hey\",\"hi\"])\n",
    "    True\n",
    "    >>> has_duplicates([\"yo\",\"sup\",\"hello\"])\n",
    "    \"\"\"\n",
    "    \n",
    "    temp = []       # creates temporary empty list\n",
    "    flag = False    # sets a \"flag\" that resorts to False\n",
    "         \n",
    "    for element in input_list:\n",
    "        if element in temp:      # if any repeat element in input_list\n",
    "            flag = True          # flag changes to True and break ends\n",
    "            break                # the search\n",
    "        else:\n",
    "            temp.append(element) # if not, adds to temp list and keeps\n",
    "    return flag                  # flag = False\n",
    "\n",
    "    \n",
    "    import doctest\n",
    "    doctest.run_docstring_examples(has_duplicates, globals())      \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge: Exercise 11 (optional)\n",
    "\n",
    "You should read [Chapter 9.1](http://www.greenteapress.com/thinkpython/html/thinkpython010.html) and do Exercise 1 first.\n",
    "\n",
    "To check whether a word is in the word list, you could use the `in` operator, but it would be relatively slow because it searches through the words in order (try it).\n",
    "\n",
    "Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary. You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, then you search the first half of the list the same way. Otherwise you search the second half.\n",
    "\n",
    "Either way, you cut the remaining search space in half. If the word list has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there.\n",
    "\n",
    "Write a function called `bisect` that takes a sorted list and a target value and returns the index of the value in the list, if it’s there, or `None` if it’s not.\n",
    "\n",
    "Or you could read the documentation of the `bisect` module and use that! Solution: http://thinkpython.com/code/inlist.py."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def bisect(input_list,target_word):\n",
    "    \"\"\"\n",
    "    Takes input of a list and a target value\n",
    "    If value exists in list, returns index of the value in the list\n",
    "    If not, returns None\n",
    "    \n",
    "    >>> bisect(['happy','sad','depressed','optimistic','good'],'sad')\n",
    "    4\n",
    "    >>> bisect(['happy','sad','depressed','optimistic','good'],'good')\n",
    "    1\n",
    "    >>> bisect(['happy','sad','depressed','optimistic','good'],'happy')\n",
    "    2\n",
    "    >>> bisect(['happy','sad','depressed','optimistic','good'],'poop')\n",
    "    None\n",
    "    \"\"\"\n",
    "    \n",
    "    input_list.sort()      # sorts input_list into alphabetical order\n",
    "    print input_list\n",
    "    middle_word = len(input_list) / 2    # finds where to bisect\n",
    "    \n",
    "    if target_word < input_list[middle_word]:   # if target is before middle\n",
    "        input_list = input_list[:middle_word]   # range --> bisected range\n",
    "        return input_list.index(target_word)    # finds target index\n",
    "    elif target_word > input_list[middle_word]: # if target is after middle\n",
    "        input_list = input_list[middle_word:] \n",
    "        return input_list.index(target_word) + middle_word # index in terms of whole input_list, not bisected list\n",
    "    elif target_word == input_list[middle_word]: \n",
    "        return middle_word\n",
    "    else:\n",
    "        return None\n",
    "\n",
    "    import doctest\n",
    "    doctest.run_docstring_examples(bisect, globals())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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": {},
   "source": [
    " "
   ]
  }
 ],
 "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
}