Python/Python (2).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python: syntax and concepts\n",
    "\n",
    "This is a tutorial on basic Python syntax and concepts for the [KIPAC computing boot camp](http://kipac.github.io/BootCamp).\n",
    "\n",
    "Author: [Sean McLaughlin](https://github.com/mclaughlin6464)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Part 0: Basic syntax:\n",
    "\n",
    "Python syntax is very much *unlike* most other standard languages, in some subtle ways at least. \n",
    "\n",
    "This leads to otherwise skilled programmers writing very bad python code. \n",
    "\n",
    "Let's start with something simple: The Zen of python. Press Shift+Enter to evaluate the cell below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Zen of Python, by Tim Peters\n",
      "\n",
      "Beautiful is better than ugly.\n",
      "Explicit is better than implicit.\n",
      "Simple is better than complex.\n",
      "Complex is better than complicated.\n",
      "Flat is better than nested.\n",
      "Sparse is better than dense.\n",
      "Readability counts.\n",
      "Special cases aren't special enough to break the rules.\n",
      "Although practicality beats purity.\n",
      "Errors should never pass silently.\n",
      "Unless explicitly silenced.\n",
      "In the face of ambiguity, refuse the temptation to guess.\n",
      "There should be one-- and preferably only one --obvious way to do it.\n",
      "Although that way may not be obvious at first unless you're Dutch.\n",
      "Now is better than never.\n",
      "Although never is often better than *right* now.\n",
      "If the implementation is hard to explain, it's a bad idea.\n",
      "If the implementation is easy to explain, it may be a good idea.\n",
      "Namespaces are one honking great idea -- let's do more of those!\n"
     ]
    }
   ],
   "source": [
    "import this"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This encapsulates the design ideas of python. If something is complex or obtuse, python probably has a better way to do it! \n",
    "\n",
    "Writing slick, clean python code is very easy, if you just know the basics. Unlike langues like C++ or Java, python has:\n",
    "\n",
    "- No semicolons (;). Each line needs to be a complete statment, unless broken by a backslash (\\).\n",
    "- Variables can be declared dynamically. \n",
    "- Nested statments are opened by colons (:), and the structures are specified by **indentation**.\n",
    "\n",
    "Not everything will be covered here, so make sure to check out the [python docs](https://docs.python.org/2/) to learn more! \n",
    "\n",
    "Let's start with a 'hello world' in the cell below! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, run this cell if you're using Python 2.7 instead of 3. This should resolve some differences between those using the two. There may be a few others that arise, and I'll try to point them out as they come. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function, division"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello world!\n"
     ]
    }
   ],
   "source": [
    "print('Hello world!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "### Part 1: Simple Types\n",
    "\n",
    "All variables in python are dynamically typed; no declaraion necessary! Here are the built in data types in python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2.2\n",
      "1j\n",
      "STRANG\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#PSST. I'm a comment! I don't affect anything!\n",
    "#These are all 5 of the built-ins in pythonn\n",
    "x =1 #int\n",
    "print(x)\n",
    "x = 2.2 #float\n",
    "print(x)\n",
    "x  = 1.0J #complex\n",
    "print(x)\n",
    "x = 'STRANG' #string\n",
    "print(x)\n",
    "x = True #bool\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Certain operations will cast variables from one type to another; it's also possible to manually cast them. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "20\n",
      "30.0\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "s= '10'\n",
    "print(s)\n",
    "y = int(s)\n",
    "print(y+10)\n",
    "print(y*3.0) #cast as float\n",
    "print(int(y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Details on all of python's built-ins can be found [here](https://docs.python.org/2/library/stdtypes.html). I'm going to shy away from droning on about the details of the syntax; what you want to know you can look up there. I'll just make a few key mentions.\n",
    " * bools' are a subset of integers. When you cast `True` to an `int`, you get `1`. What do you think `False` does?\n",
    " * Most types have an interesting `bool` casting that can be used in control flow. More on that in a bit.\n",
    " * the `is` operator is kinda cool, but it compares memory addresses, not equality. Sometimes this is the same thing and sometimes it's not.\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "x = 2\n",
    "print(x is 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1.1: String Aside\n",
    "\n",
    "Strings are different enought form the numeric types that they warrent a little bit of their own discussion. A string can be created using either double or single quotes. This can be used to insert the other into the string. Escapes are also possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm a string!\n",
      "I'm a string too!\n"
     ]
    }
   ],
   "source": [
    "print(\"I'm a string!\")\n",
    "print('I\\'m a string too!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the most important things with strings is formatting. This is done using the `%` sign and the right letter. Once again, details [here](https://docs.python.org/2/library/stdtypes.html#string-formatting). Here's a few short examples of printing fancy strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Look it's a one: 1\n",
      "Look it's a one followed by a float 2!: 1, 2.000000\n",
      "And finally, pi to 3 digits of precesion is 3.142?\n"
     ]
    }
   ],
   "source": [
    "print(\"Look it's a one: {}\".format(1))\n",
    "print(\"Look it's a one followed by a float 2!: {0}, {1:f}\".format(1, 2.0) )\n",
    "pi = 3.141592653\n",
    "print(\"And finally, pi to 3 digits of precesion is {0:.3f}?\".format(pi) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the really interesting things about python strings is that they're kinda like container types. I'll be going into grave detail about them in the next section, but here's a few examples of some things you can do. \n",
    "\n",
    "I'm also going to use some of the cool string methods/functions. There's a list of them [here](https://docs.python.org/2/library/stdtypes.html#string-methods). There are a **ton** of them and they're really useful. I suggest you familizarize yourself with them. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "supacalifragilisticexpialidocious\n",
      "\n",
      "s\n",
      "u\n",
      "Supacalifragilisticexpialidocious\n",
      "['supacal', 'frag', 'l', 'st', 'cexp', 'al', 'doc', 'ous']\n"
     ]
    }
   ],
   "source": [
    "s = 'supacalifragilisticexpialidocious'\n",
    "for char in s: #go character by character\n",
    "    print(char,end='')\n",
    "print('\\n') #newline\n",
    "    \n",
    "print(s[0]) #first char\n",
    "print(s[-2]) #second to last char\n",
    "print(s.capitalize())\n",
    "print(s.split('i')) #remove i's and partition into chunks aroudn them"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "#### Answers at the bottom!\n",
    "\n",
    "What is the first digit of `4**16-27`? How about the last?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'int' object is not subscriptable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-10-6f4311d0e48a>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0;36m16\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m27\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'int' object is not subscriptable"
     ]
    }
   ],
   "source": [
    "n = 4**16-27\n",
    "print(n[0], n[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------\n",
    "## Part 2: Container Types\n",
    "\n",
    "Now that you know all there is to know about the basics, you can put them places! There are four container types in python:\n",
    " * lists\n",
    " * tuples\n",
    " * sets\n",
    " * dictionaries\n",
    " \n",
    "They have a lot of similarities, but let's break them down one by one.\n",
    "\n",
    "#### Lists\n",
    "Lists are like arrays in other languages, but with 2 major differences.\n",
    "\n",
    "1) They can hold data of any type.\n",
    "They're meant to hold data of the same type, like the names of the files in a directory or data from voltage source. However, they can hold data of any type. Look!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6] ['potato', 3, True, 89.6]\n"
     ]
    }
   ],
   "source": [
    "x = [1,2,3,4,5,6]\n",
    "y = ['potato', 3, True, 89.6]\n",
    "print(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) They are dynamically sized.\n",
    "This is **AWESOME**. No more worrying about allocating memory in advance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[1, 2, 3, 4, 'I LOVE APPENDING']\n"
     ]
    }
   ],
   "source": [
    "x = []\n",
    "x.append(1)\n",
    "print(x)\n",
    "x.extend([2,3,4])\n",
    "x.append('I LOVE APPENDING')\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are also performance costs with this; those are laid out [here](https://wiki.python.org/moin/TimeComplexity) along with the time complexity of a few other operations I'll show you below. \n",
    "\n",
    "As for other regular list stuff, check out the examples below. The rest of the list functions are [here](https://docs.python.org/2/tutorial/datastructures.html). As per my usual shpeal, there are many and they are awesome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "[8, 2, -1]\n",
      "7\n",
      "[-1, -1, 1, 2, 8, 37, 140]\n",
      "[-1, -1, 2, 8, 37, 140]\n"
     ]
    }
   ],
   "source": [
    "arr = [1,8,2,-1, 37,140, -1]\n",
    "print(arr[1] )#access the second element\n",
    "print(arr[1:4])#this is slicing. It cuts the array from the second to the 4th element\n",
    "print(len(arr))# get the array's length\n",
    "arr.sort() #sort the array in place\n",
    "print(arr)\n",
    "arr.remove(1)#remove the first element valued 1\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll be revisiting lists in a bit after we cover control flow structures. They're pretty integral to the layout of `for` loops.\n",
    "\n",
    "#### Tuples\n",
    "\n",
    "Tuples are...weird. They are a lot like lists in a lot of ways,except for one major one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "5\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "'tuple' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-14-a5fea10e91f6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtup\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m#1st elem\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtup\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m#length\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mtup\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;31m#modify\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'tuple' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "tup = (1,2,3,4,5)\n",
    "print(tup[0]) #1st elem\n",
    "print(len(tup)) #length\n",
    "tup[0] = -1#modify"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`'tuple' object does not support item assignment`.\n",
    "\n",
    "Tuples differ from lists in that tuples are **immutable**. Once they're set, they can't be changed. This may seem a little bit odd at first, but there are reasons for this. Tuples are not supposed to be homogenous sequences like lists; there are heterogenous. Each element represents a different idea, like cartesian coordinates. Their unique properties also give them unique roles in:\n",
    " * They are hashable, so they can be used as keys for dicts or sets (see that in a sec)\n",
    " * They can be used to have functions return multiple values at once (see that in 2 secs)\n",
    " * Tuple unpacking is crazy cool.\n",
    " \n",
    "The last one I want to elaborate on. Python, as it runs, evalutates comma separated things as tuples automagically. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, 3, 4, 5)\n",
      "<class 'tuple'>\n"
     ]
    }
   ],
   "source": [
    "x = 1,2,3,4,5\n",
    "print(x)\n",
    "print(type(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This also works in reverse. You can assign to individual elements of a tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 9\n"
     ]
    }
   ],
   "source": [
    "a,b,c,d,e = x\n",
    "print(a,b,c,d+e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By combinging these 2 effects you encounter something truly unique. In other languages, variable swapping takes a 3rd temp variable like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1\n"
     ]
    }
   ],
   "source": [
    "a = 1\n",
    "b =2\n",
    "tmp = a\n",
    "a = b\n",
    "b = tmp\n",
    "print(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python says no more! One line variable swaps!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1\n"
     ]
    }
   ],
   "source": [
    "a, b = 1,2\n",
    "#GAHHHHHHH\n",
    "b,a = a,b\n",
    "print(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The future is here!\n",
    "\n",
    "#### Sets\n",
    "\n",
    "Sets behave exactly like logical sets. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5}\n",
      "{3}\n",
      "{1, 2}\n",
      "{1, 2, 3}\n",
      "True False\n"
     ]
    }
   ],
   "source": [
    "a = set([1,2,3])\n",
    "b = set([3,4,5])\n",
    "print(a | b) #a U b\n",
    "print(a & b) # a intersect b\n",
    "print(a-b) #a-b\n",
    "a.add(1) #add an element already in a\n",
    "print(a) #duplicates not allowed\n",
    "print(1 in a, 1 in b) #check for membership"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sets can only store immutable objects. This means you can't store a list, but you can store a tuple. This is because sets are ***hash driven***. The details of how that works aren't too important, just remember that immutable objects are the only type that are hashable. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "range(0, 3) range(0, 5)\n",
      "{0, 1, 2}\n"
     ]
    }
   ],
   "source": [
    "x,y = range(3),range(5) # make a few lists\n",
    "print(x,y)\n",
    "print(set(tuple(x)) ) #attempt to put them in a set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number one important thing about sets is that they have constant time membership checks. Check out below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Aside: I'm using `xrange` below, which is python 2.7 compatible. If you're using python 3, switch it to just say `range`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Membership is size 10\n",
      "List:\n",
      "149 ns ± 0.0979 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "Set:\n",
      "82.9 ns ± 0.525 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "____________________\n",
      "Membership is size 100\n",
      "List:\n",
      "983 ns ± 3.29 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n",
      "Set:\n",
      "83.5 ns ± 1.21 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "____________________\n",
      "Membership is size 1000\n",
      "List:\n",
      "9.31 µs ± 120 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n",
      "Set:\n",
      "84.3 ns ± 0.565 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "____________________\n",
      "Membership is size 10000\n",
      "List:\n",
      "92 µs ± 627 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n",
      "Set:\n",
      "83.3 ns ± 0.534 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "____________________\n",
      "Membership is size 100000\n",
      "List:\n",
      "930 µs ± 3.97 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "Set:\n",
      "84.2 ns ± 0.548 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "____________________\n",
      "Membership is size 1000000\n",
      "List:\n",
      "9.79 ms ± 47.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "Set:\n",
      "84.6 ns ± 0.34 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
      "____________________\n"
     ]
    }
   ],
   "source": [
    "for n in range(1,7):#We're doing control flow structures next!\n",
    "#for n in xrange(1,7):#We're doing control flow structures next!\n",
    "    N = 10**n\n",
    "    print('Membership is size %d'%N)\n",
    "    l = list(range(N))#make a list of size N\n",
    "    s = set(l) #note that the creation of a set is O(N), so you need to be careful about how you do it.\n",
    "    print('List:')\n",
    "    #I'm usign some ipython magic here\n",
    "    %timeit N/2 in l#check membership\n",
    "    print('Set:')\n",
    "    %timeit N/2 in s#check membership\n",
    "    print('_'*20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an insanely useful feature and I reccomend you think of ways to use it in your code wherever you can to increase peformance. \n",
    "\n",
    "#### Dictionaries\n",
    "\n",
    "Dictionaries are python's best data structure; even the language designers have said so. They're like set's older, better brother. Dictionaries are a mapping type, so they pair a key to a value. The key must be immutable, but values need not be. They have a variety of uses, like binning or counting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'red': 3, 'yellow': 1, 'cyan': 1, 'green': 2, 'blue': 1, 'black': 1}\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "#counting\n",
    "colors = ['red', 'yellow', 'cyan', 'red', 'green', 'green', 'blue', 'red', 'black']\n",
    "colorDict = {}\n",
    "for color in colors:\n",
    "    if color not in colorDict: #O(1) membership checks\n",
    "        colorDict[color] = 0\n",
    "    colorDict[color]+=1\n",
    "print(colorDict)\n",
    "print(colorDict['red'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_keys([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])\n",
      "[961] [121, 143, 187, 209, 253, 319, 341, 407, 451, 473, 517, 583, 649, 671, 737, 781, 803, 869, 913, 979]\n"
     ]
    }
   ],
   "source": [
    "#binning\n",
    "divDict= {} #dictionary of the smallest prime factor of a number.\n",
    "from math import sqrt #I'll show off imports later\n",
    "# Python 3 users should change the xranges below to ranges\n",
    "for n in range(1,10**3):#iterate from 1 to 1000\n",
    "#for n in range(1,10**3):#iterate from 1 to 1000\n",
    "    for d in range(2, int(sqrt(n))+1):#iterate from 2 to sqrt(N) in the denominator\n",
    "    #for d in range(2, int(sqrt(n))+1):#iterate from 2 to sqrt(N) in the denominator\n",
    "        result = n/float(d)\n",
    "        if int(result) == result: #it's an int\n",
    "            if d not in divDict: #initialize the dict\n",
    "                divDict[d] = []\n",
    "            divDict[d].append(n)\n",
    "            break\n",
    "print(divDict.keys())\n",
    "print(divDict[31],divDict[11])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Name': 'Sean', 'Height': 6.166, 'Eye Color': 'blue'}\n"
     ]
    }
   ],
   "source": [
    "#Making a simple pseudo object\n",
    "person = {}\n",
    "person['Name'] = 'Sean'\n",
    "person['Height'] = 6.166 #feet\n",
    "person['Eye Color'] = 'blue'\n",
    "print(person)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dicts are also just useful to treat like arrays, but with keys that aren't easily encoded as ints. Use them often.\n",
    "\n",
    "### Exercise 2\n",
    "#### Answers at the bottom\n",
    "Using the dictionary below, print 'Hello World' in the ICAO alphabet. Can you generalize it to any message?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'A'.lower()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hotel\n",
      "echo\n",
      "lima\n",
      "lima\n",
      "oscar\n",
      "whiskey\n",
      "oscar\n",
      "romeo\n",
      "lima\n",
      "delta\n"
     ]
    }
   ],
   "source": [
    "d = {'a':'alfa', 'b':'bravo', 'c':'charlie', 'd':'delta', 'e':'echo', 'f':'foxtrot',\n",
    "     'g':'golf', 'h':'hotel', 'i':'india', 'j':'juliett', 'k':'kilo', 'l':'lima',\n",
    "     'm':'mike', 'n':'november', 'o':'oscar', 'p':'papa', 'q':'quebec', 'r':'romeo',\n",
    "     's':'sierra', 't':'tango', 'u':'uniform', 'v':'victor', 'w':'whiskey', \n",
    "     'x':'x-ray', 'y':'yankee', 'z':'zulu', ' ': \" \"}\n",
    "\n",
    "#your code here\n",
    "#HINT You'll need a for loop. If you'd like, read ahead and come back.\n",
    "\n",
    "s = 'Hello World'\n",
    "\n",
    "for char in s.lower():\n",
    "    if char == ' ':\n",
    "        continue\n",
    "    print(d[char])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "## Part 3: Control Flow Structures and Iterators\n",
    "Now that we know about the data, let's do stuff with it conditionally. In python, the mainstays in control flow:\n",
    " * if\n",
    " * else and elif\n",
    " * while\n",
    " * for\n",
    " \n",
    "For the most part, the first 3 behave as you'd expect. For is a little different than in other languages, and deserves more time. Before going into detail on each though, there is one important general comment. \n",
    "\n",
    "For most other languages, blocks of code are set off from others by brackets. In python this is instead done with *whitespace*. Namespaces are set off by tabs (actually, the python style guide specifies 4 spaces. Adjust your text editor for that). It forces pretty looking code. How great is that?\n",
    "\n",
    "#### If, else and elif\n",
    "All three work like you'd expect them to work. If the statement evaluates to true, move into the block, else keep going. Example below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "It isn't either!\n",
      "It isn't either!\n",
      "It's 2!\n",
      "It isn't either!\n",
      "It's 4!\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "#for i in range(5)\n",
    "    if i ==2:\n",
    "        print('It\\'s 2!')\n",
    "    elif i==4:\n",
    "        print('It\\'s 4!')\n",
    "    else:\n",
    "        print('It isn\\'t either!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The one thing worth mentioning is that if,else,elif and while all evaluate an object's `bool()` method. Certain objects have interesting bools, which can be put to use. \n",
    "\n",
    "For example, an empty list is false, but anything else is true.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "Still need more things\n"
     ]
    }
   ],
   "source": [
    "shoppingList = ['milk','eggs','beer','tofu','beer']\n",
    "print(bool(shoppingList))\n",
    "print(bool([]))\n",
    "\n",
    "if shoppingList:\n",
    "    print('Still need more things')\n",
    "else:\n",
    "    print('We\\'re done!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One little aside if that if and else can be used for some elegant assignment/ return statements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Even\n"
     ]
    }
   ],
   "source": [
    "n = 68\n",
    "evenOrOdd = 'Even' if n%2==0 else 'Odd'\n",
    "print(evenOrOdd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### While\n",
    "While works just like you'd expect. It continues the loop while the bool expression at it's top continues to be true."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "beer\n",
      "tofu\n",
      "beer\n",
      "eggs\n",
      "milk\n"
     ]
    }
   ],
   "source": [
    "while shoppingList:\n",
    "    print(shoppingList.pop()) #pop the last element off the list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll take the time to mention a few other keywords that work for looping functions, like while and for. The 2 keywords are `break` and `continue`. \n",
    "Break exits the loop.\n",
    "Continue skips to the next iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'beer'}\n",
      "{'beer', 'eggs'}\n",
      "{'milk', 'beer', 'eggs'}\n"
     ]
    }
   ],
   "source": [
    "shoppingList = ['tofu','milk','eggs','beer','beer']\n",
    "bought = set()\n",
    "vegetarian = False\n",
    "while(shoppingList):\n",
    "    item = shoppingList.pop()\n",
    "    if item == 'tofu' and not vegetarian:\n",
    "        break\n",
    "    if item in bought: #don't buy again\n",
    "        continue\n",
    "    bought.add(item)\n",
    "    print(bought)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### For\n",
    "For loops are possibly part of the 5% of the time python's deisgners messed up. The problem isn't in the implementation; it's powerful and works well. The problem is the name. \n",
    "**For should've been called for each.**\n",
    "The way a C programmer would iterate over a loop is like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tofu\n",
      "milk\n",
      "eggs\n",
      "beer\n",
      "beer\n"
     ]
    }
   ],
   "source": [
    "shoppingList = ['tofu','milk','eggs','beer','beer']\n",
    "for i in range(len(shoppingList)):\n",
    "    print(shoppingList[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is bad code. All of that work has been implemented for you already under python's hood. The better way would be to do this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tofu\n",
      "milk\n",
      "eggs\n",
      "beer\n",
      "beer\n"
     ]
    }
   ],
   "source": [
    "for item in shoppingList:\n",
    "    print(item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's faster and more readable. If you really need the index, there's another, faster way. \n",
    "\n",
    "Here's an example of that, along with a few other functions that make iterating over lists easier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 tofu\n",
      "1 milk\n",
      "2 eggs\n",
      "3 beer\n",
      "4 beer\n",
      "____________________\n",
      "beer\n",
      "beer\n",
      "eggs\n",
      "milk\n",
      "tofu\n",
      "____________________\n",
      "beer\n",
      "beer\n",
      "eggs\n",
      "milk\n",
      "tofu\n",
      "____________________\n",
      "steak tofu\n",
      "buns milk\n",
      "ketchup eggs\n",
      "coffee beer\n"
     ]
    }
   ],
   "source": [
    "for idx, item in enumerate(shoppingList): #get index too\n",
    "    print(idx, item)\n",
    "print('_'*20)\n",
    "for item in sorted(shoppingList): #sort before hand\n",
    "    print(item)\n",
    "print('_'*20)\n",
    "for item in reversed(shoppingList): #reverse!\n",
    "    print(item)\n",
    "print('_'*20)\n",
    "otherList = ['steak', 'buns', 'ketchup', 'coffee']\n",
    "for other, item in zip(otherList, shoppingList):#combine 2 lists and iteratte together\n",
    "    print(other, item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `continue` and `break` keywords I mentioend above also work with `for`. `for` also has an `else` clause, which is poorly named. It'd be better titled \"no break.\" It activates if the for loop exits its iteration normally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HOORAY\n"
     ]
    }
   ],
   "source": [
    "for item in shoppingList:\n",
    "    if item == 'spinach':\n",
    "        print('EWWWW')\n",
    "        break\n",
    "else:\n",
    "    print('HOORAY')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I mentioned earlier that `for` is integral to some of the cooler parts of lists and dicts. Welcome to the world of list and dict comprehension, where we can build lists and dicts on the fly with `for`. It's fast, elegant and easy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]\n",
      "{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}\n",
      "[[1], [], [], [], [], [], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "sqs = [x**2 for x in range(10)]\n",
    "sqDict = {x:x**2 for x in range(10)}\n",
    "\n",
    "#sqs = [x**2 for x in range(10)]\n",
    "#sqDict = {x:x**2 for x in xrange(10)}\n",
    "\n",
    "listOfLists = [[] for i in range(10)]\n",
    "#listOfLists = [[] for i in range(10)]\n",
    "\n",
    "listOfLists[0].append(1)\n",
    "print(sqs)\n",
    "print(sqDict)\n",
    "print(listOfLists)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Iterators\n",
    "Also tightly connected with `for` loops is iterator objects. The under the hood details are a little complex, but they are essentially memory efficient ways to step over objects. \n",
    "\n",
    "You may have noticed me using `range` and `xrange` above. What's the difference? \n",
    "\n",
    "`xrange` is an iterator. It's poorly named, for sure, but you should **always** use it with loops. `range` generates the entire list in memory all at once. Take a look at the code below.\n",
    "\n",
    "*For Python 3 users, the below cell won't work. That's because in Python 3, the designers made range equal to xrange, and got rid of range entirely. *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N :1\tIter Size (bytes): 48\t List Size (bytes): 80\n",
      "N :10\tIter Size (bytes): 48\t List Size (bytes): 152\n",
      "N :100\tIter Size (bytes): 48\t List Size (bytes): 872\n",
      "N :1000\tIter Size (bytes): 48\t List Size (bytes): 8072\n",
      "N :10000\tIter Size (bytes): 48\t List Size (bytes): 80072\n",
      "N :100000\tIter Size (bytes): 48\t List Size (bytes): 800072\n"
     ]
    }
   ],
   "source": [
    "from sys import getsizeof\n",
    "for ex in range(6):\n",
    "    listSize = getsizeof([0]*10**ex)\n",
    "    xrangeSize = getsizeof(range(10**ex))\n",
    "    print('N :%d\\tIter Size (bytes): %d\\t List Size (bytes): %d'%(10**ex,xrangeSize, listSize) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iterators make an apperance in a lot of places in python, and you should use them wherever you find them. Take for example, the `items` and `iteritems` dictionary methods. If you are simply iterating over a dictionary, `iteritems` is a better, faster choice. However, if you are **modifying** the dict, though, you should use `items`. It generates a copy, which is more expensive, but if you attempt to modify something while you are iterating over it **you are living in a state of sin and you deserve what happens to you.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n",
      "1 1\n",
      "2 4\n",
      "3 9\n",
      "4 16\n",
      "5 25\n",
      "6 36\n",
      "7 49\n",
      "8 64\n",
      "9 81\n"
     ]
    }
   ],
   "source": [
    "sqDict = {x:x**2 for x in range(10)}\n",
    "#sqDict = {x:x**2 for x in xrange(10)}\n",
    "\n",
    "for val, valSq in sqDict.items():\n",
    "    print(val, valSq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "for i in sqDict.keys():\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3\n",
    "#### Answers at the bottom!\n",
    "Create a list of all numbers under 10,000 divisible by both 3 and 5. Then, find it's sum. You may find the `%`(modulus) operator useful, as well as the `sum` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3331665\n"
     ]
    }
   ],
   "source": [
    "nums = []\n",
    "for i in range(10000):\n",
    "    if i%3==0 and i%5==0:\n",
    "        nums.append(i)\n",
    "        \n",
    "print(sum(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9855, 9870, 9885, 9900, 9915, 9930, 9945, 9960, 9975, 9990]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums[-10:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "## Part 4: Functions\n",
    "Creating functions in python is very easy and simple. All you need is the `def` keyword, and possibly `return`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def print1():\n",
    "    print(1)\n",
    "    \n",
    "def return1():\n",
    "    return(1)\n",
    "\n",
    "print1()\n",
    "x =return1()\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You do not need to define the type of returns a function gives. In fact, you can make a function that returns any type, and any number of results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "(1, 2.0)\n",
      "GAH\n"
     ]
    }
   ],
   "source": [
    "def bananas(val):\n",
    "    if val%2 == 0:\n",
    "        return True\n",
    "    elif val%3 == 0:\n",
    "        return 1,2.0\n",
    "    else:\n",
    "        return 'GAH'\n",
    "    \n",
    "print(bananas(6))\n",
    "print(bananas(9))\n",
    "print(bananas(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another great feature of function is default arguments. You can write a function that had default values, or use keywords  to specify specific ones. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n",
      "2\n",
      "----------\n",
      "3\n",
      "----------\n",
      "6\n",
      "6\n",
      "----------\n"
     ]
    }
   ],
   "source": [
    "def printValue(value, nTimes = 2):\n",
    "    for n in range(nTimes):\n",
    "    #for n in range(nTimes):\n",
    "        print(value)\n",
    "    print('-'*10)\n",
    "\n",
    "printValue(2, 3)\n",
    "printValue(3,nTimes = 1)\n",
    "printValue(value = 6) #use the default value here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Passing around functions refs is easy too. Check this out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def addOne(val):\n",
    "    return val+1\n",
    "\n",
    "def addTwo(val):\n",
    "    return val+2\n",
    "\n",
    "myVal = 16\n",
    "myFunc = addOne if myVal%2==1 else addTwo\n",
    "myFunc(myVal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aside: Anonymous functions\n",
    "Python also has included an artifact from functional programming days. The keyword `lambda` creates an anonymous, oneline function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "double = lambda x: x*2\n",
    "print(double(2))\n",
    "print(double(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There have a variety of uses, but I like using them to make easy key functions. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('green', 2), ('blue', 8), ('red', 10), ('orange', 19)]\n",
      "[('blue', 8), ('green', 2), ('orange', 19), ('red', 10)]\n"
     ]
    }
   ],
   "source": [
    "d = {'red': 10, 'blue': 8, 'green':2, 'orange':19}\n",
    "sortedVal = sorted(d.items(), key = lambda x: x[1]) #sort by the second val in the tuple.\n",
    "alphaVal = sorted(d.items(), key = lambda x: x[0]) #sort by the keys\n",
    "print(sortedVal) #now it's a sorted list of tuples. \n",
    "print(alphaVal) #sorted in alphabetical order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4\n",
    "Write a function that calculates the factorial of a given number `N`. Can you do it recursively? How about procedurally?\n",
    "\n",
    "Recall:\n",
    "\n",
    "$N! \\equiv \\Pi_{i=1}^N{i} $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "range(0, 5)"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "range(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "720 720\n"
     ]
    }
   ],
   "source": [
    "def fact(n):\n",
    "    out = 1\n",
    "    #for i in xrange(2, n+1):\n",
    "        #out*=i\n",
    "        #out = out*i\n",
    "    while n:\n",
    "        out*=n\n",
    "        n-=1\n",
    "    return out\n",
    "\n",
    "def fact2(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    return n*fact2(n-1)\n",
    "\n",
    "print(fact(6), fact2(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "## Part 5: Imports and Module Structure\n",
    "\n",
    "The largest structural component of python is the module. It is the name for an entire .py file. We've been cheating a little bit in this iPython notebook, as things behave a little differently. \n",
    "\n",
    "I've included in the directory with this notebook an example python file. I reccomend you take a look at it now; I'll be importing it below. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm in a module\n",
      "I'm in a function\n"
     ]
    }
   ],
   "source": [
    "import ex\n",
    "ex.exFunc()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Importing is one of the best parts of python. It's possible to import from any module, at any point in a module. You can import a whole module, like I did above, and that gives you access to everything in the **global scope**. I've shied away from discussion of python scopes, because there a few subtleties about how they work. Details for the curious can be found [here](https://docs.python.org/2/tutorial/classes.html#multiple-inheritance).\n",
    "\n",
    "For now, the global scope is everything on the top level of indentation. Similarly, you can import just a particilar variable or function, like below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm in a function\n"
     ]
    }
   ],
   "source": [
    "from ex import exFunc\n",
    "exFunc()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also rename them, so as to not pollute your local namespace. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm in a function\n"
     ]
    }
   ],
   "source": [
    "from ex import exFunc as myFunc\n",
    "myFunc()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that, the first time you imported from ex, it printed a statement. What is that? When a module is imported, the whole module is run first. It is only run the first time it's imported, not any time afterward. This is important to know so you can design them appropriately. If you want to have code that doesn't run when the module is imported, take a look at ex.py. It shows an example of how to do that, using python's `__name__` variable. \n",
    "\n",
    "It is of couse possible to import from modules other than your own. Python built-in's and installed third party applications can be imported in the same way. Installing third party packages is easy with [pip](https://pypi.python.org/pypi/pip)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1593031826.6281579\n",
      "<class 'numpy.ndarray'>\n"
     ]
    }
   ],
   "source": [
    "from time import time #built-in time module\n",
    "import numpy as np #third-party numeric module\n",
    "\n",
    "print(time())\n",
    "x = np.array(range(10))\n",
    "print(type(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5\n",
    "#### Answers at the bottom!\n",
    "Write a function in an external module that calculates the Nth Fibonacci number, where \n",
    "\n",
    "$F_i = F_{i-1} + F{i-2}$\n",
    "\n",
    "and\n",
    "\n",
    "$F_0 =0,\\; F_1 = 1$\n",
    "\n",
    "You can do it recursively or functionally (depending on how much of a math nerd you are). Import it and run it below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "## Part 6: Objects\n",
    "\n",
    "Objects are a very powerful and complex part of Python (and many other languages). We'll only touch on the basics today, but I encourage you to delve more deeply into them later! \n",
    "\n",
    "Let's start with the basics. What *is* an object?\n",
    "\n",
    "Well, first what *is* programming? \n",
    "\n",
    "Programming, in the most abstract sense, is defining logic to perform manipulations on data. It's a simulation of some operation, real or abstract. \n",
    "\n",
    "An object is an abstract... um... *object* that contains both its relevant data and functions to manipulate that data. It follows from the idea that what we really care about are these abstract objects than the logic or data separately. They are building blocks you can use to construct your programs. \n",
    "\n",
    "Ok sure but... what *is* an object?\n",
    "\n",
    "It can be a lot of things. It can represent something real, like a student or an astronomical object. It can represent something more abstract, like a statistical model or a cosmology. It could even be something completely abstract. For example, all the widgets and cells in this notebook are actually instances of objects within the Jupyter code. \n",
    "\n",
    "\n",
    "Programming with objects allows you to design your programs the way you actually understand the logic yourself. \n",
    "\n",
    "Let's make a simple class to get started. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Student(object):\n",
    "    'A class defining a student!'\n",
    "    \n",
    "    def __init__(self, name, gpa, major = 'Physics'):\n",
    "        '''\n",
    "        Initialize the student. \n",
    "        \n",
    "        name: String, the student's name\n",
    "        gpa: The student's overall gpa\n",
    "        major: The student's major. Default is Physics. \n",
    "        '''\n",
    "        self.name = name\n",
    "        self.gpa = gpa\n",
    "        self.major = major\n",
    "        \n",
    "    def change_major(self, new_major):\n",
    "        '''\n",
    "        Change the student's major. \n",
    "        \n",
    "        new_major: str, the student's new major\n",
    "        '''\n",
    "        if new_major != self.major:\n",
    "            self.major=new_major\n",
    "        else:\n",
    "            print(\"%s is already %s's major!\"%(self.major, self.name) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GradStudent(Student):\n",
    "    \n",
    "    def __init__(self, name, gpa, major = 'Physics'):\n",
    "        self.name = name\n",
    "        self.gpa = gpa\n",
    "        self.major = major\n",
    "        self.busy = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "gradStudent = GradStudent('Elliot', 1.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gradStudent.busy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "gradStudent.change_major('English')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There's a lot to unpack here, so lets break it down. We've defined a class `Student` that has three attributes and two methods.\n",
    "\n",
    "The attributes are:\n",
    "* name\n",
    "* gpa\n",
    "* major\n",
    "\n",
    "And the methods are:\n",
    "* \\__init__\n",
    "* change_major\n",
    "\n",
    "How do these work? Let's make some instances to see. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class '__main__.Student'> True\n",
      "Sean 3.0 English\n"
     ]
    }
   ],
   "source": [
    "student1 = Student(name = 'Sean', gpa = 3.0, major =  'English')\n",
    "print(type(student1), isinstance(student1, Student) )\n",
    "print(student1.name, student1.gpa, student1.major )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "student2 = Student('Alice', 4.5, major='Biology')\n",
    "\n",
    "student2.change_major('Physics')#she wised up\n",
    "student1.change_major('Physics')#this should print! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Physics\n",
      "Physics\n"
     ]
    }
   ],
   "source": [
    "print(student2.major)\n",
    "print(student1.major)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A class defining a student!\n"
     ]
    }
   ],
   "source": [
    "print(student1.__doc__) #access the docstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There's a few things to notice here:\n",
    "* student1 and student2 are *instances* of the student object. \n",
    "* We can access a Student's attributes and methods via `.` syntax\n",
    "* The \\__init\\__ method is what is called the *constructor*. It details the initialization of the instance. \n",
    "* Both methods have *self* as their first argument, but it is not passed in when called. This is how class methods are defined, and allows them to access the object's attributes.\n",
    "\n",
    "These are just the basics of objects, but you should try using them, or exploring some more advanced things like operator overloading and inheritance! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Exercise 6\n",
    "#### Answers Below\n",
    "Define a class named `Professor` with the following attributes:\n",
    "* A name attribute\n",
    "* An integer attribute `n_papers`\n",
    "* A boolean attribute `tenure` that defaults to `False`.\n",
    "* A `group` attribute that is a list of `Student` objects that defaults to `[]`. \n",
    "\n",
    "And the following methods:\n",
    "* An `__init__` method that initializes the attributes\n",
    "* A `write_paper` method that increments `n_papers` by one. \n",
    "* A `check_tenure` method that sets `tenure` to true if `n_papers` is greater than 10. \n",
    "\n",
    "Make sure to test it out! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "## Epilogue\n",
    "I hope you enjoyed this tutorial. If you have any questions or comments, email me at [smclau2@stanford.edu](mailto:swmclau2@staford.edu). I leave you with one of python's best little secrets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "import antigravity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "## Answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 9\n"
     ]
    }
   ],
   "source": [
    "#Ex. 1\n",
    "n = 4**16-27\n",
    "strN = str(n)\n",
    "#first and last\n",
    "print(strN[0], strN[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hotel\n",
      "echo\n",
      "lima\n",
      "lima\n",
      "oscar\n",
      " \n",
      "whiskey\n",
      "oscar\n",
      "romeo\n",
      "lima\n",
      "delta\n"
     ]
    }
   ],
   "source": [
    "#Ex.2\n",
    "d = {'a':'alfa', 'b':'bravo', 'c':'charlie', 'd':'delta', 'e':'echo', 'f':'foxtrot',\n",
    "     'g':'golf', 'h':'hotel', 'i':'india', 'j':'juliett', 'k':'kilo', 'l':'lima',\n",
    "     'm':'mike', 'n':'november', 'o':'oscar', 'p':'papa', 'q':'quebec', 'r':'romeo',\n",
    "     's':'sierra', 't':'tango', 'u':'uniform', 'v':'victor', 'w':'whiskey', \n",
    "     'x':'x-ray', 'y':'yankee', 'z':'zulu'}\n",
    "\n",
    "message = 'Hello World'\n",
    "message = message.lower()#dict's in Lowercase\n",
    "for char in message:\n",
    "    if char in d:\n",
    "        print(d[char])\n",
    "    else:\n",
    "        print(char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 15, 30, 45, 60, 75, 90, 105, 120, 135] 3331665\n"
     ]
    }
   ],
   "source": [
    "#Ex. 3\n",
    "nums = []\n",
    "for n in range(10**4):\n",
    "    if n%3 ==0 and n%5 ==0:\n",
    "        nums.append(n)\n",
    "print(nums[:10], sum(nums)   )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3628800 3628800\n"
     ]
    }
   ],
   "source": [
    "#Ex. 4\n",
    "def fact(N):#recursive\n",
    "    if N==1:\n",
    "        return 1\n",
    "    return N*fact(N-1)\n",
    "\n",
    "def fact_2(N):#procedural\n",
    "    num = 1\n",
    "    while N>1:\n",
    "        num*=N\n",
    "        N-=1\n",
    "    return num\n",
    "\n",
    "print(fact(10), fact_2(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "89 89\n"
     ]
    }
   ],
   "source": [
    "#Ex. 5\n",
    "#Not writing externally\n",
    "def fib(N):\n",
    "    if N==0 or N==1:\n",
    "        return 1\n",
    "    return fib(N-1) + fib(N-2) #Expensive recursion!\n",
    "\n",
    "def fib_2(N):\n",
    "    N+=1 #this formula defined differently\n",
    "    gold_ratio = 1.61803\n",
    "    from math import sqrt\n",
    "    num = (gold_ratio**N-(1-gold_ratio)**N)\n",
    "    return int(round(num/sqrt(5)))\n",
    "\n",
    "print(fib(10), fib_2(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Ex. 6\n",
    "class Professor(object):\n",
    "    'A professor on a surprisngly easy tenure track.'\n",
    "    \n",
    "    def __init__(self,name, n_papers, tenure=False, group=[] ):\n",
    "        'Initialize the professor.'\n",
    "        self.name = name\n",
    "        self.n_papers = n_papers\n",
    "        self.tenure=tenure\n",
    "        self.group = group\n",
    "        \n",
    "    def write_paper(self):\n",
    "        self.n_papers+=1\n",
    "        \n",
    "    def check_tenure(self):\n",
    "        self.tenure = self.n_papers > 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}