# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + [markdown] slideshow={"slide_type": "subslide"}
# # How do we loop over the elements on a list?
# -

numbers = [1, 2, 3, 4, 5]
for n in numbers:
    print(n)

# + [markdown] slideshow={"slide_type": "subslide"}
# # We all agree that's much better than:
# -

for index in range(0, len(numbers)):
    print(numbers[index])

# Every time somebody loops over the indexes, a kitten dies.

# + [markdown] slideshow={"slide_type": "subslide"}
# # ... or, even worse:
# -

index = 0
while index < len(numbers):
    print(numbers[index])
    index += 1

# This is going to get at least *two* kittens dead.

# + [markdown] slideshow={"slide_type": "subslide"}
# # Python's for loop
# - Known as 'for-each' in other programming languages.
# - **Higher abstraction** level $\rightarrow$ more **readable** and clear.
# - We don't care about indexes or implementation details.
# - We just say *"loop over this"* (whatever it is)
# -

# Recommended talk: [Loop Like a Native](https://www.youtube.com/watch?v=EnSu9hHGq5o), by <NAME>.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## It's safer
# - Not manipulating indexes $\rightarrow$ fewer places were we can make mistakes.
# - Actually, we can arguably err nowhere using a for-each loop.

# + slideshow={"slide_type": "-"}
index = 0
while index <= len(numbers):  # Ooops!
    print(numbers[index])
    index += 1

# + [markdown] slideshow={"slide_type": "subslide"}
# # The for loop not only works with lists
# -

# ## Strings 

for letter in "aeiou":
    print(letter)

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Sets
# -

numbers = {"one", "two", "three"}
for n in numbers:
    print(n)

# Note: no guarantees as for the order. See [All Your Ducks In A Row](https://www.youtube.com/watch?v=fYlnfvKVDoM), by <NAME>

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Dictionaries
# -

numbers = {1 : "one", 2 : "two", 3 : "three"}
for key, value in numbers.items():
    print(key, "->", value)

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Files
# -

with open("quixote.txt") as fd:
    for line in fd:
        print(line, end="") # line already includes a newline

# + [markdown] slideshow={"slide_type": "subslide"}
# # We can use the for loop with anything that's *iterable*

# + [markdown] slideshow={"slide_type": "skip"}
# Advanced tip: we can use [Abstract Base Classes](https://docs.python.org/3/library/abc.html).
#
# [collections.abc.Iterable](https://docs.python.org/3/library/collections.abc.html#collections.abc.Iterable) is an ABC for classes that are iterable.

# + slideshow={"slide_type": "skip"}
import collections.abc

print(issubclass(list, collections.abc.Iterable))
print(issubclass(str,  collections.abc.Iterable))

# + slideshow={"slide_type": "skip"}
isinstance({1, 2}, collections.Iterable)
isinstance("abcd", collections.Iterable)

# + [markdown] slideshow={"slide_type": "subslide"}
# # Detour: What's an iterable?
# -

# From the [Glossary](https://docs.python.org/3/glossary.html#term-iterable):
# > An object capable of returning its members one at a time. Examples of iterables include all sequence types (such as `list`, `str`, and `tuple`) and some non-sequence types like dict, file objects, and objects of any classes you define with an `__iter__()` or `__getitem__()` method. 

# So our object will be iterable if it implements `__iter__()` [`*`]

# [`*`] ... or `__getitem__()`, but let's focus on  `__iter__()`.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## What's `__iter__()`?

# + [markdown] slideshow={"slide_type": "-"}
# Again, [from the docs](https://docs.python.org/3/reference/datamodel.html#object.__iter__):
#
# > This method is called when an iterator is required for a container. This method should return a new iterator
# object that can iterate over all the objects in the container. For mappings, it should iterate over the keys of the container.
#
# - So we need to implement `__iter__()` and make it return an *iterator*
# - This method is called implicitly by the built-in `iter()`
#

# + [markdown] slideshow={"slide_type": "subslide"}
# ### I don't believe you

# + slideshow={"slide_type": "-"}
numbers = [1, 2, 3]

print(numbers.__iter__)
# -

# OK, `__iter__()` exists.

it = iter(numbers) # calls __iter__()
print(it)


# ... and it returns an iterator.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## But... what's an *iterator*?
#
# It's an object that conforms to the [**Iterator Protocol**](https://docs.python.org/3/library/stdtypes.html#iterator-types), implementing two methods.

# + [markdown] slideshow={"slide_type": "subslide"}
# ### `iterator.__iter__()`
#
# > Return the iterator object itself. This is required to allow both containers and iterators to be used with the for and in statements. This method corresponds to the `tp_iter` slot of the type structure for Python objects in the Python/C API.
#
# - TL;DR: implement `__iter__()`, make it return `self`.
# - We need to do this, for... whatever reasons.

# + [markdown] slideshow={"slide_type": "subslide"}
# I'll follow the instructions, then.
# -

class MyIterator(object):    
    
    def __iter__(self):
        return self


# This feels pointless.

# + [markdown] slideshow={"slide_type": "subslide"}
# ### `iterator.__next__()` 
#
# > Return the next item from the container. If there are no further items, raise the `StopIteration` exception. This method corresponds to the `tp_iternext` slot of the type structure for Python objects in the Python/C API.
#
# - No, I did not understand the second sentence either.
# - This was `.next()` in the now long-forgotten, barely remembered Python 2.

# + slideshow={"slide_type": "subslide"}
class MyIterator(object):
    
    def __init__(self, elements):
        self.elements = elements
        self.index = 0
    
    def __iter__(self):
        return self
    
    def __next__(self):
        # No elements left, so raise exception.
        if self.index >= len(self.elements):
            raise StopIteration
        
        result = self.elements[self.index]
        self.index += 1
        return result

    
it = MyIterator([1, 2, 3])
print(next(it)) # calls __next__()
print(next(it))
print(next(it))
# -

# - We've built our own ugly, awkward iterator object. Yay!
# - Recommended reading: [Understanding Python Iterables and Iterators](http://www.shutupandship.com/2012/01/understanding-python-iterables-and.html)

# + [markdown] slideshow={"slide_type": "subslide"}
# The fourth time we call `next()`, `StopIteration` happens:
# -

print(next(it))

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `next()` must be used on iterators
#
# Even if our class is iterable, we need an iterator to loop over it:
# -

numbers = [1, 2, 3]
next(numbers)

# + slideshow={"slide_type": "subslide"}
numbers = [1, 2, 3]
it = iter(numbers) # calls __iter__(), returns iterator
print("Iterator:", it)  # it is an iterator indeed
# -

print(next(it)) # returns 1
print(next(it)) # returns 2
print(next(it)) # returns 3
print(next(it)) # raises StopIteration

# + [markdown] slideshow={"slide_type": "subslide"}
# ### This is exactly what the `for` loop does under the hood
#
#
# - Uses `iter()` to get an iterator.
# - Repeatedly calls `next()`.
# - Stops when `StopIteration` is raised.

# +
numbers = [1, 2, 3]

def awkward_for(iterable):
    it = iter(iterable)
    while True:
        try:
            print(next(it))
        except StopIteration:
            break
            
awkward_for(numbers)
# -

# I'm so happy we have the built-in `for` instead of this monster.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `for` and `StopIteration`
#
# - Although the iterator *will* raise StopIteration, we don't have to worry about it.
# - It turns out that the for loop listens for StopIteration explicitly.
# - It doesn't catch other exceptions raised by the iterator...
# - ... or `StopIteration` raised within the body of the loop.

# +
numbers = [1, 2, 3]

for n in numbers:
    raise StopIteration # break stuff


# + [markdown] slideshow={"slide_type": "subslide"}
# # Detour: Generators
#
# Generators are a special type of iterator.
#
# How a normal function works:
#
# - The execution starts at the function's first line.
# - It continues until we reach a `return` statement...
# - ... or the end of the function — that returns `None` implicitly.
# - Whatever result we return, must be returned at once.
# -

# Recommended readings:
# - ['yield' and Generators Explained](https://jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/)
# - [Generator Tricks for Systems Programmers](http://www.dabeaz.com/generators/)

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Single exit point

# +
def foo(x):
    """Add one, then square."""
    
    y = x + 1  # we first do this
    z = y ** 2 # then we do this
    return z   # exit the function here


print(foo(4))

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Multiple exit points

# +
import random

def spam(x):
    """Square if even, halve if odd."""
    
    if x % 2 == 0:
        return x ** 2  # we may exit here...
    return x / 2       # ... or here.


print(spam(4)) # 4 ** 2 = 16
print(spam(7)) # 7 / 2  = 3.5


# + [markdown] slideshow={"slide_type": "subslide"}
# ## Implicit `None`

# + slideshow={"slide_type": "-"}
def foobar(x):
    y = x + 1  # do nothing with 'y'
    # implicit `return None`
    
    
print(foobar(2))


# + [markdown] slideshow={"slide_type": "subslide"}
# Let's say that we want to work with even numbers.
# -

def get_even(stop):
    """Return all the even numbers <= stop."""
    
    numbers = []
    n = 0
    while n <= stop:
        numbers.append(n)
        n += 2
    return numbers


# ... or, of course, simply:

# +
def get_even(stop):
    return list(range(0, stop + 1, 2))


print(get_even(10)) # [2 ... 10]
print("Sum:", sum(get_even(10))) 

# + [markdown] slideshow={"slide_type": "subslide"}
# ## When problems arise
#
# - The problem is that we're building the list...
# - ... and returning all the elements **at once**.
# - Working with large intervals becomes impractical, to say the least.
# -

sum(get_even(int(1e18)))  # not enough RAM modules


# + [markdown] slideshow={"slide_type": "subslide"}
# ## Generators to the rescue
# - Generators are functions that are able to return values **one by one**.
# - The state of the function is frozen until the next value is requested.
# - They use they `yield` keyword instead of `return`.
# - If there's $\gt 1$ `yield` in our function, it becomes a `generator function`.
# - Generator functions return generator iterators (generators, for short)

# + slideshow={"slide_type": "subslide"}
def simple_generator():
    yield 1  # will return this the first time
    yield 2  # this the second time
    yield 3  # and this the third time

    
g = simple_generator()
print(g)
print(next(g)) # returns 1
print(next(g)) # returns 2
print(next(g)) # returns 3
print(next(g)) # raises StopIteration


# + [markdown] slideshow={"slide_type": "subslide"}
# Let's say that we want a function that returns **all** natural numbers:

# +
def count():
    n = 1
    while True:
        yield n
        n += 1
        
        
numbers = count()
print(numbers) # again, it's a generator
print(next(numbers)) # 1
print(next(numbers)) # 2
print(next(numbers)) # 3


# -

# ... and so on, up to infinity and beyond.

# + [markdown] slideshow={"slide_type": "subslide"}
# This is not possible with a normal function — we can't return *all* the natural numbers.

# + slideshow={"slide_type": "-"}
def count():
    """Try to return all natural numbers, and fail."""
    
    result = []
    n = 1
    while True:
        result.append(n)
        n += 1


# -

# Don't run this code.

# + [markdown] slideshow={"slide_type": "skip"}
# ## Extra points: generator expressions
#
# - Like comprehension lists, but with **lazy** evaluation.
# - They generate the elements one by one, as needed.

# + slideshow={"slide_type": "skip"}
g = (x ** 2 for x in range(1, 1000000))

# + slideshow={"slide_type": "skip"}
print(g) # it's a generator indeed
print(next(g)) # computes the square of 1
print(next(g)) # computes the square of 2
print(next(g)) # computes the square of 3

# + [markdown] slideshow={"slide_type": "skip"}
# ## Even more extra points:
#
# - `range()` is **not** a generator
# - In the old world of Python 2 it returned a list.
# - But now, in Python3, generates elements one by one.

# + slideshow={"slide_type": "skip"}
numbers = range(1, 100)

# + slideshow={"slide_type": "skip"}
print(numbers) # range(1, 100) 
print(type(numbers)) # it's a 'range' object

# + slideshow={"slide_type": "skip"}
it = iter(numbers)
print(next(it)) # returns the first element
print(next(it)) # returns the second element

# + [markdown] slideshow={"slide_type": "skip"}
# ## So...
#
# - `range` is a `sequence object` that produces numbers on demand.
# - `sequences` in Python are object that support random access.
# - It can also contain if the number is part of the range in $\mathcal{O}(1)$...
# - ... instead of the $\mathcal{O}(n)$ that it would take to scan through all of them.

# + slideshow={"slide_type": "skip"}
odd = range(1, int(1e50), 2)

# + slideshow={"slide_type": "skip"}
print(odd)  # a really large range indeed

# + slideshow={"slide_type": "skip"} active=""
# print(odd[9]) # tell me what's the 10th odd number

# + slideshow={"slide_type": "skip"}
print(int(1e48) in odd) # completes before the heat death of the Universe

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Summary
#
# - Iterators are objects on which we can call `next()`
# - Generators generate elements one by one.
# - Every generator is an iterator, but not vice versa.
# - We could achieve the same with a custom iterator — but this is nicer.
#
# Recommended reading: [this answer by <NAME> on Stack Owerflow](http://stackoverflow.com/a/2776865).

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Extra: Measuring a generator
#
# How do we calculate the number of elements of a generator?
# -

g = (x ** 2 for x in range(1, 101))

# This doesn't work.

len(g) # TypeError

# + [markdown] slideshow={"slide_type": "subslide"}
# ### Idea: cast to list

# + slideshow={"slide_type": "-"}
g = (x ** 2 for x in range(1, 101))
len(list(g))
# -

# But we need a temporary list.

# + [markdown] slideshow={"slide_type": "subslide"}
# ### Better: use `sum()`
# -

g = (x ** 2 for x in range(1, 101))
sum(1 for x in g)  # use another generator

# Or more idiomatic, as we don't care about the vale of the numbers:

g = (x ** 2 for x in range(1, 101))
sum(1 for _ in g)


# Use `_` as a throwaway variable.

# + [markdown] slideshow={"slide_type": "slide"}
# # Finally, time for some Kung Fu
#
# <img src="./images/Deflected_Kick.jpg" style="height: 400px; width:auto"/>
#
# [Photo](https://www.flickr.com/photos/kurt-b/9453209945/) by <NAME> / [CC BY-SA 2.0](https://creativecommons.org/licenses/by-sa/2.0/)

# + [markdown] slideshow={"slide_type": "subslide"}
# # Prime numbers
#
# How do we determine whether a number is prime?

# +
def is_prime(n):
    """Checks whether a number is prime."""

    divisor = 2
    while divisor < n:
        if n % divisor == 0:
            return False
        divisor += 1
    return True


print(is_prime(2)) # True
print(is_prime(3)) # True
print(is_prime(8)) # False


# + [markdown] slideshow={"slide_type": "subslide"}
# But we already now there's a much better way with `range()`!

# +
def is_prime(n):
    """Checks whether a number is prime."""

    for divisor in range(2, n):
        if n % divisor == 0:
            return False
        divisor += 1
    return True


print(is_prime(5)) # True
print(is_prime(6)) # False
print(is_prime(7)) # True

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Mandatory optimization: check divisors only until $\sqrt{n}$
# - Because a non-prime number $n$ will have a divisor $\le \sqrt{n}$
# - Brings us down from $\mathcal{O}(n)$ to $\mathcal{O}(\sqrt{n})$. Not bad.
# - Recommended reading, with proof for humans: [this answer on Stack Overflow](http://stackoverflow.com/a/5811176)

# +
import math

def is_prime(n):
    """Checks whether a number is prime."""

    stop = int(math.sqrt(n)) + 1
    for divisor in range(2, stop):
        if n % divisor == 0:
            return False
        divisor += 1
    return True


print(is_prime(10))
print(is_prime(13))


# + [markdown] slideshow={"slide_type": "slide"}
# # Integer factorization
# - Now we want to decompose a number into its prime factors.
# - For example, $8 = 2 \times 2 \times 2 = 2^3$, and $30 = 2 \times 3 \times 5$
# - Simplest method: [trial division](https://en.wikipedia.org/wiki/Trial_division), one by one
# - For this we'll need to loop over prime numbers

# + [markdown] slideshow={"slide_type": "subslide"}
# # Getting the first n prime numbers
# ## Attempt 1

# + slideshow={"slide_type": "-"}
def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""
    
    primes = []
    n = 2
    while len(primes) < how_many:
        if is_prime(n):
            primes.append(n)
        n += 1
    return primes


print(get_primes(5))


# + [markdown] slideshow={"slide_type": "-"}
# **Problem:** we need to generate all the prime numbers at once.
#
# Let's use a generator instead!

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Attempt 2
# -

def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""
    
    counter = 0
    n = 2
    while counter < how_many:
        if is_prime(n):
            yield n
            counter += 1
        n += 1


# Twice as many places where we can commit a mistake, as we're keeping track of:
# - How many prime numbers we have generated so far.
# - What's the next number we need to evaluate.
#
# `range()` is not an option because we don't know what the stop is. But we can use...

# + [markdown] slideshow={"slide_type": "subslide"}
# ## itertools.count()
#
# - Makes an iterator that returns evenly spaced values starting with $n$.
# - By default, we start counting from zero.
# - The default step is one.
# -

import itertools
numbers = itertools.count()
print(numbers) # tells us what the next element will be
print(next(numbers)) # 0
print(next(numbers)) # 1
print(next(numbers)) # 2

odd = itertools.count(1, step=2)
print(next(odd)) # first odd number
print(next(odd)) # second odd number


# + [markdown] slideshow={"slide_type": "subslide"}
# ## Attempt 3
# We can thus simplify our code a little bit:
# -

def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""
    
    counter = 0
    for n in itertools.count(2):
        if is_prime(n):
            yield n
            counter += 1
            if counter == how_many:
                break


# However, this is still awkward, as our function does two things:
#
# - Generates prime numbers
# - Keeps track if how many we have generated so far. 
#
# Let's split it in two different steps.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Attempt 4

# +
def primes():
    """An endless generator of prime numbers."""
    
    for n in itertools.count(2):
        if is_prime(n):
            yield n

def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""
    
    counter = 0
    all_primes = primes()
    while counter < how_many:
        yield next(all_primes)
        counter += 1


# -

# Good! But this can be simplified even further!

# + [markdown] slideshow={"slide_type": "subslide"}
# To get all the prime numbers we can use a generator expression
# -

primes = (n for n in itertools.count(2) if is_prime(n))

# ... or `filter()`:

primes = filter(is_prime, itertools.count(2))


# Notes:
# - generator expressions are usually shorter and more readable
# - But in this case `filter()` is arguably better — we're taking the value as it is.
# - `filter()` was `itertools.ifilter()` before...
# - ... but nobody uses Python 2 anymore.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Attempt 5

# + slideshow={"slide_type": "-"}
def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""
    
    counter = 0
    primes = filter(is_prime, itertools.count(2))
    while counter < how_many:
        yield next(all_primes)
        counter += 1


# + [markdown] slideshow={"slide_type": "subslide"}
# ## Take how many?
#
# - This thing that we're doing in `get_primes()` is a common pattern.
# - *"Give me the first n elements of this iterable"*
# - We cannot use slice notation:
# -

numbers = [1, 2, 3, 4, 5]
print(numbers[:3]) # the first three
print(get_primes(10)[:5]) # slicing doesn't work with generators

# + [markdown] slideshow={"slide_type": "subslide"}
# ## itertools.islice()
#
# - Like slice notation, but works with all things iterable.
# - Lazy evaluation, of course, asking for elements once at a time.
# -

for n in itertools.islice(itertools.count(), 5):
    print(n)

# + slideshow={"slide_type": "subslide"}
word = "abcde"
print(list(itertools.islice(word, 3))) # the first three letters
# -

# If start != 0, skip elements until it's reached
squares = (x ** 2 for x in itertools.count(1))
print(list(itertools.islice(squares, 10, 15))) # start=10, stop=15

# + slideshow={"slide_type": "-"}
# We can use a step other than one.
numbers = range(100000)
print(list(itertools.islice(numbers, 0, 20, 2))) # step=2

# + [markdown] slideshow={"slide_type": "subslide"}
# So if we want the first $n$ prime numbers:
# -

primes = filter(is_prime, itertools.count(2))
for n in itertools.islice(primes, 10):
    print(n)


# + [markdown] slideshow={"slide_type": "subslide"}
# ## Attempt 6
#
# Let's rewrite our function:

# +
def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""

    primes = filter(is_prime, itertools.count(2))
    for n in itertools.islice(primes, how_many):
        yield n
        
        
for n in get_primes(5):
    print(n)


# -

# We're just looping over the elements of a iterator and in turn `yield`ing them. 
#
# This is what `yield from` was invented for!

# + [markdown] slideshow={"slide_type": "subslide"}
# ## yield from
#
# - Allows a generator to delegate part of its operations to another generator.
# - That is, each `next()` which ask the sub-generator for another value.
# - Usually we delegate to subgenerators, but it works with anything *iterable*.
# - `yield from iterable` $\approx$ `for item in iterable: yield item`
# - It is also a transparent two-way channel from the caller to the sub-generator.

# +
def foo():
    yield 1
    yield 2
    yield 3
    
def spam():
    yield from foo() # for x in foo(): yield x


print(list(spam()))


# + slideshow={"slide_type": "subslide"}
def vowels():
    # Works with anything iterable
    yield from "aeiou"

    
print(list(vowels()))


# -

# Recommended reading:
# [A Curious Course on Coroutines and Concurrency](http://dabeaz.com/coroutines/)

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Attempt 7
# So we can rewrite our function as:

# +
def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""

    primes = filter(is_prime, itertools.count(2))
    yield from itertools.islice(primes, how_many)


for n in get_primes(5):
    print(n)

# + [markdown] slideshow={"slide_type": "skip"}
# Yet we can make this even shorter.
#
# - We're just defining a generator that delegates all the work to another generator.
# - The first argument to `islice()` is always the same: `primes`.
# - The only thing that changes is the second one, `how_many`. 
#
# This is what `functools.partial()` was invented for!

# + [markdown] slideshow={"slide_type": "skip"}
# ## functools.partial()
#
# - Used for partial function application. That's formal language for...
# - ... *"freezing some portion of a function's arguments"*.
# - It also supports freezing keyword arguments.
# - Allows us to simplifying a function signature.
# - You don't know you need it in your life until you come across it.

# + slideshow={"slide_type": "skip"}
import functools

power_two = functools.partial(math.pow, 2) # freeze 'math.pow(2, ...'
print(power_two)

# + slideshow={"slide_type": "skip"}
print(power_two(3)) # math.pow(2, 3)
print(power_two(5)) # math.pow(2, 5)
print(power_two(9)) # math.pow(2, 9)

# + [markdown] slideshow={"slide_type": "skip"}
# Used in real life to create handy shortcuts for a function we'll **call repeatedly**, and where some arguments are always the same:

# + slideshow={"slide_type": "skip"}
import os.path

src_dir = "/home/vterron/src/"
print(os.path.join(src_dir, "file1.py"))
print(os.path.join(src_dir, "file2.py"))
print(os.path.join(src_dir, "file3.py"))
# This is getting a little tedious...

# + [markdown] slideshow={"slide_type": "skip"}
# We can do instead:

# + slideshow={"slide_type": "skip"}
get_src = functools.partial(os.path.join, "/home/vterron/src/")
print(get_src("file1.py")) # os.path.join("/home/vterron/src/", "file1.py")
print(get_src("file2.py"))
print(get_src("file3.py"))

# + [markdown] slideshow={"slide_type": "skip"}
# ... or as a shorcut to define a function:

# + slideshow={"slide_type": "skip"}
import random

def bonoloto():
    """Get a random ticket to play BonoLoto."""
    return random.sample(range(1, 50), 6)


bonoloto()

# + slideshow={"slide_type": "skip"}
import functools
import random

bonoloto = functools.partial(random.sample, range(1, 50), 6)
bonoloto()


# + [markdown] slideshow={"slide_type": "skip"}
# ## Attempt 8
# So going back to our function...

# + slideshow={"slide_type": "skip"}
def get_primes(how_many):
    """Return the first 'how_many' prime numbers."""

    primes = filter(is_prime, itertools.count(2))
    yield from itertools.islice(primes, how_many)


# + [markdown] slideshow={"slide_type": "skip"}
# We can do instead:

# + slideshow={"slide_type": "skip"}
primes = filter(is_prime, itertools.count(2))
get_primes = functools.partial(itertools.islice, primes)
        
for n in get_primes(5):
    print(n)


# + [markdown] slideshow={"slide_type": "slide"}
# # Integer factorization, Part II
#
# - This is all neat and good, but not exactly what we need here.
# - We don't want the first whatever prime numbers...
# - ... but all the prime numbers $\le \sqrt{n}$.
# - For example, to factorize 15 we need to test all the primes until $\left \lceil{\sqrt{15}}\right \rceil = 3$:

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Generating all the divisors $\le x$
# ### Naive attempt

# +
def primes_until(stop):
    """Return all the prime numbers <= stop."""

    primes = filter(is_prime, itertools.count(2))
    for p in primes:
        if p <= stop:
            yield p
        else:
            break

            
print(list(primes_until(15)))
# -

# This is also a common pattern: loop over the elements of an iterable, stopping as soon as some condition is no longer satisfied. And this is what `takewhile()` was invented for!

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `itertools.takewhile()`
# - Make an iterator that returns elements.
# - Stop when the predicate is no longer `True`.
# - Frequently used in conjunction with lambda functions.

# +
numbers = range(1, 10000)

# Take numbers as long as they're < 4
it = itertools.takewhile(lambda x: x < 4, numbers)
print(next(it)) # 1 is < 4, so we return it
print(next(it)) # 2 is < 4, so we return it
print(next(it)) # 3 is < 4, so we return it
print(next(it)) # 4 is *not* < 4, so stop


# + [markdown] slideshow={"slide_type": "subslide"}
# ### Lambda functions are not mandatory

# +
def smaller_than_ten(x):
    """Checks whether the number is < 10."""
    return x < 10

numbers = range(0, int(1e12), 2)
list(itertools.takewhile(smaller_than_ten, numbers))


# + [markdown] slideshow={"slide_type": "skip"}
# ### But since we're at it...

# + slideshow={"slide_type": "skip"}
def is_smaller(x, than=float("inf")):
    return x < than

numbers = range(0, int(1e18), 2)
# functools.partial() + keyword argument = more readable!
for n in itertools.takewhile(functools.partial(is_smaller, than=10), numbers):
    print(n)

# + [markdown] slideshow={"slide_type": "skip"}
# ## `operator`
# This [must-know module](https://docs.python.org/3/library/operator.html) exports all standard operators as functions.

# + slideshow={"slide_type": "skip"}
import operator

print(operator.lt(3, 5))   # 3 < 5 -> True
print(operator.not_(True)) # not True -> False
print(operator.add(2, 1))   # 2 + 1 -> 3
print(operator.neg(-1))    # -(-1) -> 1

# In-place addition
x = [1, 2, 3]
operator.iadd(x, [4, 5]) # x += [4, 5]
print(x) # [1, 2, 3, 4, 5]

# + [markdown] slideshow={"slide_type": "skip"}
# So we can rewrite our solution as...

# + slideshow={"slide_type": "skip"}
numbers = range(0, int(1e24), 2)

smaller_than_ten = functools.partial(operator.gt, 10)
for n in itertools.takewhile(smaller_than_ten, numbers):
    print(n)


# + [markdown] slideshow={"slide_type": "skip"}
# - Note that with `partial()` we have to bind arguments left to right.
# - Instead of testing whether $x < 10$...
# - ... we're rewriting it as $10 > x$
#
# Anyway.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Generating all the divisors $\le x$
# ### Kung Fu version

# +
def primes_until(stop):
    """Return all the prime numbers <= stop."""    
    primes = filter(is_prime, itertools.count(2))
    yield from itertools.takewhile(lambda p: p < stop, primes)
    
            
for x in primes_until(15):
    print(x)
# -

# Woo-hoo! And what about the *opposite*?

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `itertools.dropwhile()`
# - Make an iterator that returns elements.
# - Ignore elements as long as the predicate is `True`.
# - As soon as it's not anymore, return everything.

# +
numbers = range(1, 10000)

# Ignore numbers as long as they're < 4
it = itertools.dropwhile(lambda x: x < 4, numbers)
print(next(it)) # 'it' returns 1 -> 1 < 4, so we drop it, so ...
                # 'it' returns 2 -> 2 < 4, so we drop it, so ...
                # 'it' returns 3 -> 3 < 4, so we drop it, so ...
                # returns 4
                
print(next(it)) # returns 5
print(next(it)) # returns 6
print(next(it)) # returns 7
print(next(it)) # returns 8

# ... and so on until we exhaust 'numbers'

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Prime numbers within a range
# Using both `takewhile()` and `dropwhile()` gets us this:
# -

def primes_range(start=2, stop=float("inf")):
    """Return all the prime numbers start <= x < stop."""
    
    primes = filter(is_prime, itertools.count(2))
    it = itertools.dropwhile(lambda x: x < start, primes)
    yield from itertools.takewhile(lambda y: y < stop, it)


# + slideshow={"slide_type": "subslide"}
print(list(primes_range(100, 125))) # 100 <= x < 125
# -

print(list(primes_range(stop=20)))  # all primes < 20

# +
it = primes_range(start=1000)       # all primes >= 1000
print(next(it)) # 1009
print(next(it)) # 1013
print(next(it)) # 1019
print(next(it)) # 1021

# ... and so on until infinity.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Integer factorization: The Algorithm
#
#
# - Iterate over the prime numbers $p \le \sqrt{n}$
# - If $n$ is divisible by $p$, then $p$ is a factor.
# - Divide $n$ by $p$ and factorize the quotient, recursively.
# - Base case: we ran out of prime numbers, so $n$ is prime too.
# - The factorization is all found factors.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Example: factorize $30$
#
# - Is $30$ divisible by $2$? Yes.
# - Therefore, $2$ is a factor.
#
# Factorize now the quotient, $30 \div 2 = 15$:
#
# - Is $15$ divisible by $2$? No.
# - Is $15$ divisible by $3$? Yes.
# - Therefore, $3$ is a factor.
#
# Factorize now the quotient, $15 \div 3 = 5$:
# - There're no primes $\le \sqrt{5}$, so $5$ is prime too.
# - $30 = 2 \times 3 \times 5$

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Show me the code

# +
import math

def factorize(n):
    """Decompose n into prime numbers."""

    for p in primes_until(int(math.sqrt(n))):
        quotient, remainder = divmod(n, p)
        if remainder == 0:
            # 'p' is a prime factor 
            return [p] + factorize(quotient)
    # Base case, reached only if we run out of primes
    return [n] # n is prime


print(factorize(30)) # [2, 3, 5]
print(factorize(70)) # [2, 3, 7]
print(factorize(78)) # [2, 3, 13]
print(factorize(11)) # we hit the base case directly


# + [markdown] slideshow={"slide_type": "slide"}
# # The `uniq` command
#
# A Unix command that collapses adjacent identical lines into one.

# + language="bash"
#
# cat ~/letters.txt

# + language="bash"
#
# uniq ~/letters.txt
# -

# Note that we're only removing **consecutive** duplicates.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Our own version 
# ### Padawan attempt
#
# For simplicity's sake, let's accept only strings as input.

# +
def uniq(word):
    """Remove consecutive duplicates letters."""
    
    # Don't break if string is empty
    if not word:
        return ''
    
    result = [word[0]]
    for letter in word[1:]:
        if letter != result[-1]:
            result.append(letter)
    return ''.join(result)


print(uniq("a"))             # 'a'
print(uniq("bbb"))           # 'b'    
print(uniq("abc"))           # 'abc'
print(uniq("aabbbccccdee"))  # 'abcde'

# + [markdown] slideshow={"slide_type": "subslide"}
# ## itertools.groupby()
#
# - Make an iterator that returns consecutive `keys` and `groups` from the iterable.
# - A new `group` starts every time the value of the key changes.
# - The `group` objects are a sub-iterator over the elements in the group.
# -

word = "aabccc"
groups = itertools.groupby(word)
print(groups) # a 'groupby' object — an iterable

# + slideshow={"slide_type": "subslide"}
key1, group1 = next(groups) # give me the first group
print("Key:", key1) # 'a'
# -

print("Group:", group1) # a '_grouper' object... another iterable

# + slideshow={"slide_type": "-"}
print("Next:", next(group1)) # the first 'a'
print("Next:", next(group1)) # the second 'a'
print("Next:", next(group1)) # StopIteration

# + [markdown] slideshow={"slide_type": "subslide"}
# - Each call to `next()` will return two elements: the `key` and the `group`.
# - The `key` is what this group contains — e.g., the letter *a*. 
# - The `group` are the actual occurrences of the key — e.g., *"aa"*.
#
# Let's keep going on...

# +
print("Word", word)         # 'aabcc'
key2, group2 = next(groups) # give me the second group
print("Key:", key2)         # ok, so this group contains 'b'

# And how many occurrences of 'b' are there?
print("Group:", group2) # the occurrences of 'b'
print(list(group2))     # ['b'] — oh, only one.
# -

# The third and last group
key3, group3 = next(groups)
print("Key:", key3) # 'c'
print(list(group3)) # ['c', 'c', 'c']

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Using a `for` loop instead
# -

word = "aabccc"
for key, group in itertools.groupby(word):
    print(key, "->", list(group))


# This might seem silly, but it's very powerful indeed.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Our `uniq` command
# ### Kung Fu version

# +
def uniq(word):
    result = []
    # We don't need the group for all, hence the '_'
    for key, _ in itertools.groupby(word):
        result.append(key)
    return ''.join(result)


word = "aaabbcccccdee"
print(uniq(word))


# -

# ... or even more succinct:

# +
def uniq(word):
    return ''.join(key for key, _ in itertools.groupby(word))

print(uniq(word))


# + [markdown] slideshow={"slide_type": "subslide"}
# # A (rudimentary) compression algorithm
#
# - Let's implement a very basic string compression function...
# - ... using the counts of repeated characters.
# - For example, "aaabbcccccdee" returns "a3b2c5d1e2"

# + [markdown] slideshow={"slide_type": "subslide"}
# Without `itertools`, the solution brings us pain and misery.

# +
def compress(word):
    """Return a compressed version of the string."""
    
    result = []
    current = word[0]
    counter = 1
    
    for letter in word[1:]:
        if letter == current:
            # We're still in the same group
            counter += 1
        else:
            # We need to start a new group
            result += [current, str(counter)]
            current = letter # start a new group
            counter = 1
    result += [current, str(counter)]
    return ''.join(result)


word = "<KEY>"
print(compress(word))  # 'a3b2c5d1e2'


# + [markdown] slideshow={"slide_type": "subslide"}
# ### Kung Fu version

# +
def compress(word):
    """Return a compressed version of the string."""
    
    result = []
    for key, group in itertools.groupby(word):
        result.append("{}{}".format(key, len(list(group))))
    return ''.join(result)

word = "<KEY>"
print(compress(word))  # 'a3b2c5d1e2'

# + [markdown] slideshow={"slide_type": "skip"}
# ## Making it case case-insensitive
#
# A problem is that letters in different case are considered to be different.

# + slideshow={"slide_type": "skip"}
print(compress("aaAAAA"))  # 'a2A4'


# + [markdown] slideshow={"slide_type": "skip"}
# This might make sense, but we're into compressing our strings so much that we decide to ignore the case... *respecting the case of the first occurrence* — otherwise, we would just `.upper()` or `.lower()` the entire string. That is:
#
# - "aaAAAA" $\rightarrow$ "a6"
# - "AAaaaa" $\rightarrow$ "A6"
# - "BbBccC" $\rightarrow$ "B3c3".
#
# How do we do this?

# + [markdown] slideshow={"slide_type": "subslide"}
# ## The `key` function
#
# - By default, `groupby()` compares the elements as they are seen.
# - The keyword argument `key` allows us to specify a different criteria.
# - It is a function that transforms each elements before it's compared.
# - This is known as the *"key value for each element"*
# -

# How is this useful?

# + [markdown] slideshow={"slide_type": "skip"}
# ### Let's do this:

# + slideshow={"slide_type": "skip"}
def compress_more(word):
    """Return an even more compressed version of the string."""
    
    result = []
    # Make the comparison between letters case-insensitive.
    for _, group in itertools.groupby(word, key=lambda x: x.upper()):
        group = list(group)
        # Take first element to respect case of the first occurrence.
        result.append("{}{}".format(group[0], len(group)))
    return ''.join(result)


print(compress_more("aaAAAA"))  # 'a6'
print(compress_more("AAaaaa"))  # 'A6'
print(compress_more("BbBccC"))  # 'B3c3'

# + [markdown] slideshow={"slide_type": "skip"}
# - We can't use the key, as they will always be in upper case.
# - 'group' is an iterator, so we store it as a list to use slices and `len()`.

# + [markdown] slideshow={"slide_type": "subslide"}
# # Grouping letters by length
#
# Let's say that we have a series of words, and we want to group them by their length.
# -

words = "red orange yellow green blue indigo violet gray".split()

# ### Rookie version

# +
# Map each length to a list of words
lengths = collections.defaultdict(list)

for w in words:
    lengths[len(w)].append(w)
    
for key, value in lengths.items():
    print(key, '->', value)

# + [markdown] slideshow={"slide_type": "subslide"}
# ### Kung Fu version
# -

words.sort(key=len)
for key, group in itertools.groupby(words, key=len):
    print(key, '->', list(group))

# Two things to note:
#
# - We have to sort the list first; otherwise it only groups consecutive items.
# - The first solution is $\mathcal{O}(n)$ vs $\mathcal{O}(n \log n)$, because we have to sort the list. But `groupby()` is arguably better here as it's shorter and clearly conveys what we're doing: grouping the words according to a criteria.

# + [markdown] slideshow={"slide_type": "skip"}
# # Anagrams
#
# How do we find anagrams in a list of wors?

# + slideshow={"slide_type": "skip"}
words = ['listen', 'meteor', 'dawn', 'remote', 'silent']

# If two words are an anagram, sorted() returns the same
print(sorted('listen')) # ['e', 'i', 'l', 'n', 's', 't']
print(sorted('silent')) # ['e', 'i', 'l', 'n', 's', 't']

# + [markdown] slideshow={"slide_type": "skip"}
# ### Neophyte version

# + slideshow={"slide_type": "skip"}
anagrams = collections.defaultdict(list)
for w in words:
    # Because lists are not hashable
    anagrams[tuple(sorted(w))].append(w)

for words_ in anagrams.values():
    # 'dawn' doesn't match anything else
    if len(words_) >= 2:
        print(words_)

# + [markdown] slideshow={"slide_type": "skip"}
# ### Kung Fu version

# + slideshow={"slide_type": "skip"}
words.sort(key=sorted)
for _, group in itertools.groupby(words, key=sorted):
    words_ = list(group)
    if len(words_) >= 2:
        print(words_)

# + slideshow={"slide_type": "skip"}
# %matplotlib inline

# + [markdown] slideshow={"slide_type": "subslide"}
# # Consecutive values over a threshold
#
# Let's say we have this function:
#
# $\frac{x^3}{14} + \frac{x^2}{14} - \frac{13 x}{14} - \frac{1}{14}$

# +
import numpy

# Build polynomial from coefficients
coeffs = [1/14, 1/14, -13/14, -1/14]
func = numpy.poly1d(coeffs)

func(0.5) # evaluate function at 0.5

# + [markdown] slideshow={"slide_type": "-"}
# Maths! Run for your lives!

# + [markdown] slideshow={"slide_type": "subslide"}
# ### It looks like this

# + slideshow={"slide_type": "-"}
from matplotlib import pyplot
xp = numpy.linspace(-4, 4.5, 100)
pyplot.plot(xp, func(xp), 'b', alpha = 0.7)
pyplot.grid(True)

# + [markdown] slideshow={"slide_type": "-"}
# <img src="./images/curve-one.svg"/>

# + [markdown] slideshow={"slide_type": "subslide"}
# ### Let's say it's time versus some value we're monitoring

# + [markdown] slideshow={"slide_type": "-"}
# <img src="./images/curve-two.svg"/>
# -

# We want to **trigger an alarm** if we spent $>= 3$ seconds below zero.

# + slideshow={"slide_type": "skip"}
import numpy
from matplotlib import pyplot

coeffs = [1/14, 1/14, -13/14, -1/14]
func = numpy.poly1d(coeffs)

print(numpy.roots(coeffs))


xp = numpy.linspace(-4, 4.5, 100)

xzero = numpy.linspace(-0.077, 3.183, 100)
yzero = func(xzero)

pyplot.plot(xp, func(xp), 'b', alpha = 0.7)
pyplot.grid(True)
pyplot.xlabel("Time")
pyplot.ylabel("Important Thing")
pyplot.fill_between(xzero, 0, func(xzero), facecolor='red')
pyplot.savefig("images/curve-three.svg")

# + [markdown] slideshow={"slide_type": "subslide"}
# We know that the answer is yes...
#
# <img src="./images/curve-three.svg"/>
#
# How do we do it... in code?

# + slideshow={"slide_type": "skip"}
# Use three decimal digits
numpy.set_printoptions(precision=3)

# + [markdown] slideshow={"slide_type": "subslide"}
# For simplicity, evaluate it only at integers.

# +
xp = range(-4, 5)
yp = func(xp)

for x, y in zip(xp, yp):
    print("f({}) -> {:.3f}".format(x, y))
# -

# Are there three consecutive points here with negative sign?

# + [markdown] slideshow={"slide_type": "subslide"}
# ## It's as simple as this

# + slideshow={"slide_type": "-"}
# Group the func(x) values by whether they're negative or not.
for is_negative, group in itertools.groupby(yp, key=lambda x: x < 0):
    values = numpy.array(list(group))
    print(is_negative, "->", values)
    
    if is_negative and len(values) >= 3:
        print("Trigger alarm!!")
        break
# -

# Don't even try to implement this without `groupby()`.

# + [markdown] slideshow={"slide_type": "subslide"}
# <img src="./images/Dashi.jpg" style="height: 400px; width:auto"/>
#
# [Photo](https://en.wikipedia.org/wiki/File:Wushu_dao.jpg) by AEMHZ~commonswiki / [CC BY-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0/deed.en) / Cropped from original

# + [markdown] slideshow={"slide_type": "skip"}
# <img src="./images/Wushu_Dao.jpg" style="height: 400px; width:auto"/>
#
# [Photo](https://en.wikipedia.org/wiki/File:Wushu_dao.jpg) by <NAME> / [CC BY-SA 2.0](https://creativecommons.org/licenses/by-sa/2.0/) / Cropped from original

# + [markdown] slideshow={"slide_type": "skip"}
# # Iterators are a one-way road
#
# In order to check how many elements there are in a iterator we need to consume it.

# + slideshow={"slide_type": "skip"}
g = (x ** 2 for x in range(1, 101))
sum(1 for _ in g)

# + [markdown] slideshow={"slide_type": "skip"}
# Which... works, but the generator is now exhausted, so we can't use it anymore. 

# + slideshow={"slide_type": "skip"}
list(g) # iterator is empty, so empty list

# + [markdown] slideshow={"slide_type": "skip"}
# There is no way we can go backwards in the traversal of the iterator.

# + [markdown] slideshow={"slide_type": "skip"}
# ## There's no going back
#
# Every time we call `next()` the iterator moves one step forward — forever.

# + slideshow={"slide_type": "skip"}
it = iter("abcdefghijk")
next(it) # 'a'
next(it) # now b, we'll never see 'a' again

# + [markdown] slideshow={"slide_type": "skip"}
# That's why, if we'll need each element more than once, we need to store them in a list.

# + [markdown] slideshow={"slide_type": "skip"}
# ## `itertools.tee()`
#
# - Returns $n$ independent iterators from a single iterable.
# - This allows us to move forward using of these iterators...
# - ... while the rest still point at the same place.

# + slideshow={"slide_type": "skip"}
even = itertools.count(2, step=2)
a, b = itertools.tee(even)

print(next(a)) # 2
print(next(a)) # 4

# + [markdown] slideshow={"slide_type": "skip"}
# We haven't yet called `next()` with `b`, to it's still at $2$.

# + slideshow={"slide_type": "skip"}
print(next(b)) # 2

# + [markdown] slideshow={"slide_type": "skip"}
# ## Measuring an iterator, Part II
#
# We could be tempted to do something like this:

# + slideshow={"slide_type": "skip"}
g = (x ** 2 for x in range(1, 101))

# Fork the iterator, rebind name 'g'
g, tmp = itertools.tee(g)
length = sum(1 for _ in tmp)
print("Length:", length)

# + [markdown] slideshow={"slide_type": "skip"}
# - We have exahusted the original iterator `g`...
# - ... but we use the same name for one of the copies.
# - The other copy, `tmp`, is the one we use for counting.

# + [markdown] slideshow={"slide_type": "skip"}
# ## However...
#
# This is a bad idea. From [the documentation](https://docs.python.org/3/library/itertools.html#itertools.tee):
#
# > This itertool may require significant auxiliary storage (depending on how much temporary data needs to be stored). In general, if one iterator uses most or all of the data before another iterator starts, it is faster to use `list()` instead of `tee()`.
#
# These independent iterators need to store the elements in memory until they've been consumed by all the elements, so if we are going to exahust one of the iterators we're better off by simply using a list.

# + slideshow={"slide_type": "skip"}
g = (x ** 2 for x in range(1, 11))
g = list(g)
print(len(g))

# + slideshow={"slide_type": "skip"}
print(g)

# + [markdown] slideshow={"slide_type": "skip"}
# ## When is this iseful, then?
#
# When the independent generators are going to be used more or less **at the same time**.
#
# For example, if we need to compute the difference between consecutive elements in list:

# + slideshow={"slide_type": "skip"}
numbers = [1, 5, 7]

# The output will be [4, 2], because 5 - 1 = 4 and 7 - 5 = 2

def diff(sequence):
    # Pair element with the previous one
    pairs = zip(sequence, sequence[1:])
    return [p[1] - p[0] for p in pairs]

diff(numbers)

# + [markdown] slideshow={"slide_type": "skip"}
# However, we can't use this with a generator, because **we can't use slicing**.

# + slideshow={"slide_type": "skip"}
numbers = (x ** 2 for x in [1, 5, 7])

diff(numbers)


# + [markdown] slideshow={"slide_type": "skip"}
# ## `tee()`  to the rescue
#
# This is a job `tee()` was designed for:

# + slideshow={"slide_type": "skip"}
def diff(iterable):
    a, b = itertools.tee(iterable)
    next(b)
    return [p[1] - p[0] for p in zip(a, b)]

numbers = (x for x in [1, 5, 7])
diff(numbers)

# + [markdown] slideshow={"slide_type": "skip"}
# ## NumPy already did it
#
# By the way, if we're working with sequences NumPy already includes [a function for this](http://docs.scipy.org/doc/numpy/reference/generated/numpy.diff.html):

# + slideshow={"slide_type": "skip"}
import numpy
numpy.diff([1, 5, 7])

# + [markdown] slideshow={"slide_type": "skip"}
# Don't reinvent the wheel!

# + [markdown] slideshow={"slide_type": "slide"}
# # A NeverEnding Story
#
# How do we alternate indefinitely between -1 and 1?
#
# ### Absolute n00b version
# -

x = 1
while True:
    print(x)
    if x == 1:
        x = -1
    else:
        x = 1

# An infinite loop, of catastrophic consequences if executed.

# + [markdown] slideshow={"slide_type": "subslide"}
# ### A little-less-beginner version
# -

x = 1
while True:
    print(x)
    x *= -1

# We're all still going to die if we run this.

# + [markdown] slideshow={"slide_type": "skip"}
# ### The FIFO version
#
# Using a [first in, first out](https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics) queue.

# + slideshow={"slide_type": "skip"}
import collections

class Alternate(object):
    """Alternate between 1 and -1 endlessly, via pop()."""
    
    def __init__(self):
        self.values = collections.deque()
        self._refill()

    def _refill(self):
        """Insert some 1's and -1's in the queue."""
        self.values.extend([1, -1] * 10)
               
    def __len__(self):
        return len(self.values)

    def pop(self):
        """Return the next 1 or -1 value."""
        
        # We ran out of values, so generate a few more.
        if not len(self):
            self._refill()
        return self.values.popleft()


# + [markdown] slideshow={"slide_type": "skip"}
# The [`collections`](https://docs.python.org/3/library/collections.html#collections.deque) module is awesome, but this is totally overkill.

# + [markdown] slideshow={"slide_type": "subslide"}
# ### The pr0 version
#
# The *"I was paying attention, so I know we have to use a generator"* approach:

# +
def alternate():
    """Alternate between 1 and -1 endlessly."""

    x = 1
    while True:
        yield x
        x *= -1

        
ones = alternate()
print(next(ones)) #  1
print(next(ones)) # -1
print(next(ones)) #  1
# ...

# + [markdown] slideshow={"slide_type": "subslide"}
# ### Kung Fu version

# +
ones = itertools.cycle([1, -1])

print(next(ones)) #  1
print(next(ones)) # -1
print(next(ones)) #  1
print(next(ones)) # -1
print(next(ones)) #  1
# ...

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `itertools.cycle()`
# - Make an iterator returning elements from the iterable...
# - ... and save a copy of each of the returned elements.
# - When the iterable is exhausted, iterate over the saved copy.
# - Repeat indefinitely, until the end of time.

# +
vowels = itertools.cycle("aeiou")

# Endless generator, so we need islice()
for v in itertools.islice(vowels, 10):
    print(v)

# + slideshow={"slide_type": "subslide"}
g = (x ** 2  for x in range(1, 4))

squares = itertools.cycle(g)
print(list(itertools.islice(squares, 11)))

# We've exahusted the generator...

next(g) # StopIteration

# +
# ... but 'cycle' still keeps a copy.

next(squares) # 9

# + [markdown] slideshow={"slide_type": "skip"}
# ## Waiting patiently
#
# A real-life case where `cycle()` proves useful:

# + slideshow={"slide_type": "skip"}
import itertools
import sys
import time

def sleep(seconds):
    """Show an animated spinner while we sleep."""
    
    symbols = itertools.cycle('-\|/')
    tend = time.time() + seconds
    while time.time() < tend:
        # '\r' is carriage return: return cursor to the start of the line.
        sys.stdout.write('\rPlease wait... ' + next(symbols)) # no newline
        sys.stdout.flush()
        time.sleep(0.1)
    print() # newline
    
if __name__ == "__main__":     
    sleep(20)

# + [markdown] slideshow={"slide_type": "skip"}
# [![asciicast](https://asciinema.org/a/8ocljajktav6nkm3lbtrv7i8l.png)](https://asciinema.org/a/8ocljajktav6nkm3lbtrv7i8l?size=medium&t=3&autoplay=1)

# + [markdown] slideshow={"slide_type": "subslide"}
# # Iterating over *two* (or more) iterables
#
# Let's count from $1$ to $10$, then down to $1$ again, and so on.

# +
up   = list(range(1, 11))
down = list(reversed(range(2, 10)))

print("Up  :", up)
print("Down:", down)
# -

itertools.cycle(numbers, vowels)

# We have a problem — `cycle()` only accepts an iterable.

# + [markdown] slideshow={"slide_type": "subslide"}
# And, by extension, what do we do if we want to loop over two iterables? This?

# +
numbers = [1, 2, 3]
vowels = "aeiou"

for item in numbers:
    print(item)
for item in vowels:
    print(item)
# -

# There must be a better way — as [<NAME> always reminds us](https://youtu.be/wf-BqAjZb8M?t=23m7s).

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `itertools.chain()`
# - Make an iterator returning elements from the first iterable...
# - ... then proceed to the next iterable...
# - ... and so on until all of the iterables are exhausted.

# +
numbers = [1, 2, 3]
vowels = "aeiou"

for item in itertools.chain(numbers, vowels):
    print(item)

# + [markdown] slideshow={"slide_type": "subslide"}
# So going back to what we wanted to do...

# +
up   = range(1, 11)
down = reversed(range(2, 10))

numbers = itertools.cycle(itertools.chain(up, down))
list(itertools.islice(numbers, 25))

# + [markdown] slideshow={"slide_type": "skip"}
# # Doing it lazily
#
# And the other way around? What it we have our iterables already in a list?

# + slideshow={"slide_type": "skip"}
words = "Past glories are poor feeding".split() # ― <NAME>ov
print(words)

# + [markdown] slideshow={"slide_type": "skip"}
# We want to loop other the letters of all the words.

# + [markdown] slideshow={"slide_type": "skip"}
# ## I'll use `chain()` then

# + slideshow={"slide_type": "skip"}
for letter in itertools.chain(words):
    print(letter)


# + [markdown] slideshow={"slide_type": "skip"}
# It doesn't work! `chain()` iterates over the strings of the single iterable (the list) it receives. What we want is to chain the *letters* in each word — so each word will need to be an input argument.

# + [markdown] slideshow={"slide_type": "skip"}
# ## Unpacking Arguments
#
# - Here's where we would normally use **argument unpacking**.
# - From list or tuple to separate positional arguments...
# - ... using the `*` operator to unpack the arguments out.

# + slideshow={"slide_type": "skip"}
def add(x, y):
    return x + y

values = [2, 3]

# Works, but terribly ugly
add(values[0], values[1])

# + slideshow={"slide_type": "skip"}
# values[0] becomes the first positional argument...
# ... and values[1] becomes the second one.
add(*values)

# + [markdown] slideshow={"slide_type": "skip"}
# ## Unpacking our words

# + slideshow={"slide_type": "skip"}
words = "Past glories are poor feeding".split() # ― Isaac Asimov

letters = itertools.chain(*words) # notice the *
list(itertools.islice(letters, 15))

# + [markdown] slideshow={"slide_type": "skip"}
# Works! But —

# + [markdown] slideshow={"slide_type": "skip"}
# ## Intertwining iterators

# + slideshow={"slide_type": "skip"}
squares = (x ** 2 for x in range(2, 100000000)) # 1e8
sep     = itertools.cycle(["->"])
powers  = zip(squares, sep)

print(next(powers)) # (4, '->')
print(next(powers)) # (9, '->')
print(next(powers)) # (16, '->')

# + [markdown] slideshow={"slide_type": "skip"}
# How do we chain these values? That is: $4 \rightarrow 9 \rightarrow 16 \rightarrow$...

# + [markdown] slideshow={"slide_type": "skip"}
# Do we... unpack it, as we just said?

# + slideshow={"slide_type": "skip"}
squares = (x ** 2 for x in range(2, 100000000)) # 1e8
sep     = itertools.cycle(["->"])
powers  = zip(squares, sep)

it = itertools.chain(*powers) # unpacks 1e8 arguments

# + [markdown] slideshow={"slide_type": "skip"}
# Blood, toil, tears, and sweat ensue.

# + [markdown] slideshow={"slide_type": "skip"}
# ## `itertools.chain.from_iterable()`
# - Alternate constructor for `chain()`
# - Chained inputs from a **single iterable argument**...
# - ... that is evaluated lazily.

# + slideshow={"slide_type": "skip"}
numbers = [1, 2, 3]
vowels = "aeiou"
things = [numbers, vowels]

# Instead of chain() + argument unpacking
for item in itertools.chain.from_iterable(things):
    print(item)

# + [markdown] slideshow={"slide_type": "skip"}
# Since the evaluation is lazy, we could even chain an *infinite* number of iterables.

# + slideshow={"slide_type": "skip"}
squares = (x ** 2 for x in range(2, 100000000)) # 1e8
sep     = itertools.cycle(["->"])
powers  = zip(squares, sep)

it = itertools.chain.from_iterable(powers) # doesn't explode
list(itertools.islice(it, 10)) # just the first ten elements


# + [markdown] slideshow={"slide_type": "subslide"}
# <img src="./images/Steven_Ho_540_Kick.jpg" style="height: 400px; width:auto"/>
#
# [Photo](https://commons.wikimedia.org/wiki/File:Steven_ho_about.jpg) by <NAME> / [CC BY 3.0](https://creativecommons.org/licenses/by/3.0/)

# + [markdown] slideshow={"slide_type": "slide"}
# # Rolling dices
#
# If we roll two six-sided dices, how many unique combinations are there?

# + slideshow={"slide_type": "-"}
def product(first, second):
    """A generator of the Cartesian product of two iterables."""
    
    for x in first:
        for y in second:
            yield (x, y)
            

dice = range(1, 7)
pairs = list(product(dice, dice))
pairs[:8]

# + slideshow={"slide_type": "skip"}
# set() needed because (1, 3) is the same result as (3, 1)
len(set(pairs))


# + [markdown] slideshow={"slide_type": "-"}
# What if it's *three* dices?

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Three (or more) dices
#
# We need to generalize our solution. For example, via recursion:

# +
def product(*args):
    """A generator of the Cartesian product of multiple iterables."""
    
    # Base case
    if not args:
        yield ()
        return
    
    for element in args[0]:
        for subproduct in product(*args[1:]):
            yield (element,) + subproduct
            
            
dice = range(1, 7)
triplets = product(dice, dice, dice)
for x in itertools.islice(triplets, 7):
    print(x)

# + [markdown] slideshow={"slide_type": "subslide"}
# ## `itertools.product()`
#
# - Make an iterator returning the Cartesian product of the input iterables.
# - Cycles with the rightmost element advancing on every iteration.
# - To compute the product of an iterable with itself, we use `repeat`.
# -

g = itertools.product([1, 2], "ab")
print(g)

for pair in g:
    print(pair)

# + [markdown] slideshow={"slide_type": "subslide"}
# ### `repeat` keyword argument
#
# Instead of writing several times the same input iterable:

# +
dice = range(1, 7)
pairs = itertools.product(dice, repeat=2)

for pair in itertools.islice(pairs, 10):
    print(pair)

# + [markdown] slideshow={"slide_type": "subslide"}
# ## An easy question
#
# If we roll four six-sided dices, in how many outcomes they add up to 5?

# +
results = itertools.product(range(1, 7), repeat=4)
results = filter(lambda x: sum(x) == 5, results)

for x in results:
    print(x)


# -

# That is — we need a $2$ in one dice and $1$ in the other three.

# + [markdown] slideshow={"slide_type": "subslide"}
# ## Pixels
#
# Let's say we need to work with pixels — lots of them!

# +
class Pixel(object):

    def __init__(self, row, column):
        self.row = row
        self.column = column

    def __repr__(self):
        """Return a nicely formatted representation string."""
        return "Pixel(row={}, column={})".format(self.row, self.column)
    
    
p = Pixel(2, 3)
print(p)

# + [markdown] slideshow={"slide_type": "subslide"}
# ### [`collections.namedtuple()`](https://docs.python.org/3/library/collections.html#collections.namedtuple)
#
# - Factory function for creating tuple subclasses with named fields.
# - Makes our live much easier if we don't need our class to be mutable...
# - ... because we get `__init__()`, `__repr__()` and others for free.
# - We can add our own methods via inheritance.
# -

Pixel = collections.namedtuple("Pixel", "row, column")

# That's all.

p = Pixel(5, 1)
print(p)


# + [markdown] slideshow={"slide_type": "subslide"}
# ### Adding a method
#
# To compute the distance between two points:

# +
class Pixel(collections.namedtuple("Pixel", "row, column")):
    
    def distance(self, other):
        """Return the Euclidean distance between two picels."""
        
        delta_x = self.row    - other.row
        delta_y = self.column - other.column
        return math.sqrt(delta_x ** 2 + delta_y ** 2)
    
    
p1 = Pixel(2, 3)
p2 = Pixel(5, 1)
print("Distance:", p1.distance(p2), "pixels")


# + [markdown] slideshow={"slide_type": "subslide"}
# ## Getting the neighbors
#
# Let's add a method to get the eight neighbors, lateral and diagonal:
#
# ### Naive version:
# -

class Pixel(collections.namedtuple("Pixel", "row, column")):

    def neighbours(self):
        """Return a generator of the eight neighbours of the Pixel."""
        
        yield Pixel(self.row - 1, self.column - 1)
        yield Pixel(self.row - 1, self.column    )
        yield Pixel(self.row - 1, self.column + 1)
        yield Pixel(self.row    , self.column - 1)
        yield Pixel(self.row    , self.column + 1)
        yield Pixel(self.row + 1, self.column - 1)
        yield Pixel(self.row + 1, self.column    )
        yield Pixel(self.row + 1, self.column + 1)


# That's a lot of code.

# + [markdown] slideshow={"slide_type": "subslide"}
# ### Kung Fu version

# +
class Pixel(collections.namedtuple("Pixel", "row column")):
    
    def neighbours(self):
        """Return a generator of the eight neighbours of the Pixel."""
        
        for x_delta, y_delta in itertools.product([-1, 0, 1], repeat=2):
            if x_delta or y_delta:  # ignore delta (0, 0)
                yield Pixel(self.row + x_delta, self.column + y_delta)
                
                
for p in Pixel(3, 4).neighbours():
    print(p)


# + [markdown] slideshow={"slide_type": "subslide"}
# ### Kung Fu Master version
#
# Don't hardcode the class name.

# + slideshow={"slide_type": "-"}
class Pixel(collections.namedtuple("Pixel", "row column")):
    
    def neighbours(self):
        """Return a generator of the eight neighbours of the Pixel."""
        
        cls = type(self)  # we can use now 'cls' to create new objects
        for x_delta, y_delta in itertools.product([-1, 0, 1], repeat=2):
            if x_delta or y_delta:  # ignore delta (0, 0)
                yield cls(self.row + x_delta, self.column + y_delta)
                
                
for p in Pixel(4, 7).neighbours():
    print(p)

# + [markdown] slideshow={"slide_type": "subslide"}
# <img src="./images/Bulletproof_Bruce_Lee.jpg" style="height: 400px; width:auto"/>
#
# [Photo](http://viviannepierre.deviantart.com/art/Bulletproof-Bruce-Lee-103466411) by <NAME> / [CC BY-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0/)

# + [markdown] slideshow={"slide_type": "slide"}
# # Parting Words
#
# We've covered a bunch of stuff ...
#
# - [`itertools.count()`](https://docs.python.org/3/library/itertools.html#itertools.count)
# - [`itertools.islice()`](https://docs.python.org/3/library/itertools.html#itertools.islice)
# - [`itertools.takewhile()`](https://docs.python.org/3/library/itertools.html#itertools.takewhile)
# - [`itertools.dropwhile()`](https://docs.python.org/3/library/itertools.html#itertools.dropwhile)
# - [`itertools.groupby()`](https://docs.python.org/3/library/itertools.html#itertools.groupby)
# - [`itertools.cycle()`](https://docs.python.org/3/library/itertools.html#itertools.cycle)
# - [`itertools.chain()`](https://docs.python.org/3/library/itertools.html#itertools.chain)
# - [`itertools.product()`](https://docs.python.org/3/library/itertools.html#itertools.product)
# - [`yield from`](https://docs.python.org/3/whatsnew/3.3.html#pep-380)
# - [`collections.namedtuple()`](https://docs.python.org/3/library/collections.html#collections.namedtuple)

# + [markdown] slideshow={"slide_type": "fragment"}
# ... but, still, we just scratched the surface.

# + [markdown] slideshow={"slide_type": "subslide"}
# # The head-fake
#
# The building blocks provided by `itertools` are inspired in languages like [Haskell](https://www.haskell.org/):
#
# - `itertools.count()` $\rightarrow$ [Infinite lists](https://en.wikibooks.org/wiki/Haskell/Lists_II#Infinite_Lists)
# - `itertools.islice()` $\rightarrow$ [`take`](http://hackage.haskell.org/package/base-4.9.0.0/docs/Prelude.html#v:take)
# - `itertools.takewhile()` $\rightarrow$ [`takeWhile`](http://hackage.haskell.org/package/base-4.9.0.0/docs/Prelude.html#v:takeWhile)
# - `itertools.dropwhile()` $\rightarrow$ [`dropWhile`](http://hackage.haskell.org/package/base-4.9.0.0/docs/Prelude.html#v:dropWhile)
# - `itertools.groupby()` $\rightarrow$ [`groupBy`](http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-List.html#v:groupBy)
# - `itertools.cycle()` $\rightarrow$ [`cycle`](http://hackage.haskell.org/package/base-4.9.0.0/docs/Prelude.html#v:cycle)

# + [markdown] slideshow={"slide_type": "fragment"}
# — we were also learning [functional programming](https://en.wikipedia.org/wiki/Functional_programming).

# + [markdown] slideshow={"slide_type": "subslide"}
# <img src="./images/Bruce_Lee_Statue.jpg" style="height: 400px; width:auto"/>
#
# [Photo](https://www.flickr.com/photos/iqremix/9454511368) by IQRemix / [CC BY-SA 2.0](https://creativecommons.org/licenses/by-sa/2.0/) / Cropped from original

StarcoderdataJupyterScriptsDedupFiltered