from sklearn import datasets
boston = datasets.load_boston()

print boston.DESCR

"""
Explanation: <img src='http://www.wpclipart.com/education/chalkboard/more_boards/welcome_back.png'>
Week 1 Review
End of explanation
"""


# create dictionary with values that are empty lists
prices = {
    'expensive' : [],
    'affordable' : []
}

# the price of a house will be appended to the corresponding list (expensive or affordable)
for value in boston.target:
    if value > 20:
        prices['expensive'].append(value)
    else:
        prices['affordable'].append(value)

from pprint import pprint as pp
pp(prices)

# how many affordable and expensive houses are there?
print "Expensive:", len(prices['expensive'])
print "Affordable:", len(prices['affordable'])

# What proportion of expensive houses are more than $40K?  List comprehension is good for operating on a list
from __future__ import division      # what's another way to do this without importing?

len([v for v in prices['expensive'] if v > 40])/len(prices['expensive'])

# whats the average price of an affordable house?
avg = sum(i for i in prices['affordable'])/len(prices['affordable'])
print avg
print "Average price: ${:,.0f}".format(avg*1000)    # make it pretty

"""
Explanation: Let's group house prices into expensive (> \$20K) or affordable (<= \$20K). This is 1978.
End of explanation
"""


def square(x):
    """Square of x"""    # what are these """ """ called? What are they for?
    return x**2

def cube(x):
    """Cube of x."""
    return x**3

def root(x):
    """Square root of x."""
    return x**.5

# create a dictionary of functions
funcs = {
    'square': square,
    'cube': cube,
    'root': root,
}

x = 2

print square(x)
print cube(x)
print root(x)

# print function name and output, sorted by function name
for key, val in sorted(funcs.items()):
    print key, val(x)

"""
Explanation: Week 2 - Functions

First class functions
Higher order functions
Anonymous functions
Recursion
Iterators
Review Problems

First class functions <a id='firstclass'></a>
Functions behave like any other object, such as an int or a list
<ul>
<li>Use functions as arguments to other functions
<li>Store functions as dictionary values
<li>Return a function from another function
<li>Common feature of functional programming languages like Lisp or Haskell or Scala
<li>Leads to many powerful ways to use functions.
</ul>
End of explanation
"""


def derivative(x, f, h = 0.01):       # using default value for h
    """ Calculate the derivative of any continuous, differentiable function """
    
    return (f(x+h) - f(x))/h

"""
Explanation: Functions can be passed in as arguments
End of explanation
"""


def some_func(x):    
    return 3*x**2 + 5*x + 3

derivative(2, some_func, h = 0.01) # passing in function f.   What happens if I include a value for h?

"""
Explanation: $$ f(x) = 3x^2 + 5x + 3$$
<br>
$$ f'(x) = 6x + 5$$
<br>
$$ f'(2) = 6\times2 + 5 = 17$$
End of explanation
"""


# this is how you might performing timing outside of the Jupyter notebook
# Lots of documentation online about time decorator

import time

def sum_squares(n):
    """ Sum of the squares from 0 to n-1 """
    
    return sum([x**2 for x in range(n)])

def timer(f,n):
    """ Time how long it takes to evaluate a function """
    
    start = time.clock()
    result = f(n)   
    elapsed = time.clock() - start
    return result, elapsed

n = 10000000
timer(sum_squares, n)

%timeit sum_squares(n)

"""
Explanation: Functions can also be returned by functions
End of explanation
"""


# The map function applies a function to each member of a collection
# map(some_function, some_sequence)

map(square, range(10))

# The filter function applies a predicate to each member of a collection,
# retaining only those members where the predicate is True

def is_even(x):
    return x % 2 == 0

filter(is_even, range(10))

# It is common to combine map and filter

map(square, filter(is_even, range(10)))

# The reduce function reduces a collection using a binary operator to combine sequential items, two at a time

def add_them(x, y):
    return x + y

# another implementation of the sum function - like a running total
reduce(add_them, [1,2,3,4,5])

def custom_sum(xs, func):
    """Returns the sum of xs after applying func to xs."""
    
    return sum(map(func, xs))

xs = range(10)
print custom_sum(xs, square)
print custom_sum(xs, cube)
print custom_sum(xs, root)

"""
Explanation: Higher order functions<a id='higherorder'></a>
<ul>
<li>A function that uses another function as an input argument or returns a function
<li>The most familiar are `map`, `filter` and `reduce`. These are very fast in Python.
<li>Custom functions are HOF
</ul>
End of explanation
"""


# Using standard functions
n = 10

def square(x):
    return x*x

square(n)

map(square, range(n))

# Using lambda function

sqr = lambda x: x*x

sqr(n)

n=10
map(sqr, range(n))

# what does this function do?

s1 = reduce(lambda x, y: x+y, map(lambda x: x**2, range(1,10)))
print(s1)

# functional expressions and lambdas are cool
# but can be difficult to read when over-used
# Here is a more comprehensible version

s2 = sum(x**2 for x in range(1, 10))
print(s2)

"""
Explanation: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
EXERCISE TIME!
1) Using map, write python program to calculate the length of each element in a list: ['Donald','Ted','Hilary','Joe','Bernie'].
2) Using reduce and map, write a python program to find the largest element in the list of integers, floats or strings (that are numbers). <br>
For example: [2, '3', 4.0, 2, -1, '10', 9, -4.3, 8, 7, 11, 3]. Should return 11.
<br>
<br>
Hint:
<ol>
<li>How can you tell Python to compare `'10'` to `8`? Should the types be the same?
<li>You can use `reduce` to find the maximum in a similar way as we used it to find the `sum` in the example above.
</ol>

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Anonymous functions<a id='anonymous'></a>
<ul>
<li>In functional programming, there is often a need to create small specific functions that perform a limited task as input to a HOF such as `map` or `filter`. Think `sum()`, `square()`, ...
<li>In such cases, these functions are often written as anonymous or **lambda** functions
</ul>

If you find it hard to understand what a lambda function is doing, it should probably be rewritten as a regular function.
End of explanation
"""


ans = map(lambda x: x*x, filter(lambda x: x%2 == 0, range(10)))
print ans

"""
Explanation: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
EXERCISE TIME!
Rewrite the following as a list comprehension, i.e. one liner without using map or filter
End of explanation
"""


def fact(n):
    """Returns the factorial of n"""
    
    # base case
    if n==0:
        return 1
    
    # recursive case
    else:
        return n * fact(n-1)

[(n,fact(n)) for n in range(1,10)]

"""
Explanation: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Recursion<a id='recursion'></a>
<ul>
<li>A recursive function is one that calls itself
<li>Extremely useful examples of the divide-and-conquer paradigm in algorithm development
<li>However, they can be computationally inefficient and their use in Python is quite rare in practice
</ul>

Recursive functions generally have:
<ul>
<li>a set of base cases 
<ul>
<li>the answer is obvious
<li>can be returned immediately
</ul>
<li>a set of recursive cases
<ul>
<li>which are split into smaller pieces
<li>each of which is given to the same function called recursively
</ul>
</ul>

Examples
Factorial:
$$ n! = n\times(n-1)\times(n-2)\times...\times2\times1$$ 
For example, $$4! = 4\times3\times2\times1 = 24 $$
End of explanation
"""


def fib1(n):
    """Fibonacci with recursion"""

    # base case
    if n==0 or n==1:
        return 1
    # recursive caae
    else:
        return fib1(n-1) + fib1(n-2)

[(i,fib1(i)) for i in range(20)]

# In Python, a more efficient version that does not use recursion is

def fib2(n):
    """Fibonacci without recursion"""
    
    a, b = 0, 1
    for i in range(1, n+1):
        a, b = b, a + b  # notice the variable setting is on one line
    return b

[(i,fib2(i)) for i in range(20)]

# Note that the recursive version is much slower than the non-recursive version

%time fib1(30)
%time fib2(30)

"""
Explanation: Fibonacci sequence:
$$F_n = F_{n-1} + F_{n-2},!\,$$
Output is:
$$1, 1, 2, 3, 5, 8, 13, 21, ...$$
<img src='../images/rabbits.png'>
End of explanation
"""


def quick_sort(xs):
    """ Classic quick sort """

    # base case
    if xs == []:
        return xs
    # recursive case
    else:
        pivot = xs[0] # choose starting pivot to be on the left
        less_than = [x for x in xs[1:] if x <= pivot]
        more_than = [x for x in xs[1:] if x > pivot]
        
        return quick_sort(less_than) + [pivot] + quick_sort(more_than)

xs = [11,3,1,4,1,5,9,2,6,5,3,5,9,0,10,4,3,7,4,5,8,-1]
print quick_sort(xs)

"""
Explanation: This is because it makes many duplicate function calls. For example:
<img src="../images/fib_calculation_tree.png"> 
We can get around that by caching results, but we won't cover that here.
Classic use of recursion - Quick Sort
End of explanation
"""


# Iterators can be created from sequences with the built-in function iter()

xs = [1,2,3]
x_iter = iter(xs)

print x_iter.next() # python "remembers" where the pointer is
print x_iter.next()
print x_iter.next()
print x_iter.next()

# Most commonly, iterators are used (automatically) within a for loop
# which terminates when it encouters a StopIteration exception

x_iter = iter(xs)
for x in x_iter:
    print x

"""
Explanation: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
EXERCISE TIME!
Euclid's algorithm for finding the greatest common divisor of two numbers is
python
gcd(a, 0) = a
gcd(a, b) = gcd(b, a modulo b)
<ol>
<li>What is the greatest common divisor of `17384` and `1928`? Write the `gcd(a,b)` function.
<li>Write a function to calculate the least common multiple, `lcm(a,b)`. Hint: Using `gcd` makes this very easy. Feel free to Google it.
<li>What is the least common multiple of `17384` and `1928`? Hint: Google it!
</ol>

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Iterators<a id='iterators'></a>
<ul>
<li>Iterators represent streams of values. 
<li>Will produce the next value when you call `next()` on it
<li>Because only one value is consumed at a time, they use very little memory.
<li>Use of iterators is very helpful for working with data sets too large to fit into RAM.
</ul>
End of explanation
"""


