PathGenerationExercise.sagews

Recursive path generation

In this tutorial, the goal is to recursively generate a family of paths.

Python yield

This section is an introduction to the yield command in python which is used to create generators

def stupid_generator(end):
    i = 0
    while i < end:
        yield i
        i+=1

stupid_generator(3)

The goal of the stupid_generator function is to list integers smaler than $end$. But instead of returning a list, it returns a generator of the list. Compare with this other function.

def stupid_list(end):
    i = 0
    result = []
    while i < end:
        result.append(i)
        i+=1
    return result

stupid_list(3)

To get the objects created by stupid_generator, you need to explicitly transform it to a list. You can also loop through the object directly without creating the list (that is why it is useful!)

list(stupid_generator(3))

for i in stupid_generator(3):
    print i

The instructions inside stupid_generator are not executed at the time of initial call but only when you start looping through it.

The following function gives you a more explicit example. The yield instruction acts as a "pause" on the execution, the rest of the code is executed only when the method next is called.

def test_generator():
    print "This instuction is executed when the 1st object is created"
    yield 1
    print "This instuction is executed when the 2nd object is created"
    yield 2
    print "This instuction is executed when the 3rd object is created"
    yield 3

t = test_generator()

t.next()

t.next()

t.next()

t.next()

Exercise: implement the following function whose goal is to generate the first $n$ prime numbers. You can check your function with the tests below.

To test if a number is prime, you can do

a = 7
is_prime(a)

True

def prime_generator(n):
    # write your code here

# test of the previous function. If it says nothing, then it's all good!
import types
assert(type(prime_generator(3)) == types.GeneratorType)
assert(list(prime_generator(5)) == [2,3,5,7,11])

In all previous examples, the generator stops by itself after some time. But you can also do infinite generators. Then, it is up to the caller to stop the generation.

def fibonacci_generator():
    u0 = 1
    u1 = 1
    yield u0
    yield u1
    while True: # infinite loop! But that's ok...
        u2 = u0 + u1
        yield u2
        u0, u1 = u1, u2

for f in fibonacci_generator():
    print f
    if f>100: # I have to break at some point, otherwise the for loop never stops
        break 

for f in fibonacci_generator():
    if f>100 and is_prime(f):
        print "I found the number I wanted !"
        print f
        break

Implement the following functions (you are given the documentation in the way we write it in Sage)

def infinite_prime_generator():
    """
    Return an infinite generator on prime numbers
    """
    # code here

import types
assert(type(infinite_prime_generator()) == types.GeneratorType)
g = infinite_prime_generator()
assert(g.next()==2)
assert(g.next()==3)
assert(g.next()==5)

def number_primes(n):
    """
    Use `infinite_prime_generator` to count the number of prime numbers smaller than or equal to ``n``.
    Output:
        the number of prime numbers smaller than or equal to ``n``
    """
    # code here

assert(number_primes(1)==0)
assert(number_primes(10)==4)
assert(number_primes(100)==25)

Path on the grid

Here is a python class to represent a path on the 2D-grid. A path is a list of step (2D vectors). We have implemented a basic printout and a plot. Look at the class and the examples.

class Path:
    
    def __init__(self, steps):
        self._steps = tuple(steps)
        
    def add_step(self, step):
        """
        Create a new path containing the steps of ``self`` and the extra step ``step``
        Input :
            - ``step`` a step to add to the path
        """
        new_steps = list(self._steps)
        new_steps.append(step)
        return Path(new_steps)
    
    def __len__(self):
        return len(self._steps)
        
    def __eq__(self, other):
        if not isinstance(other,Path):
            return False
        return self._steps == other._steps
    
    def __hash__(self):
        return hash(self._steps)
        
    def __repr__(self):
        return str(self._steps)
        
    def plot(self, *args, **keywords):
        dep = (0,0)
        points = [dep]
        for step in self._steps:
            end = (dep[0] + step[0],dep[1] + step[1])
            points.append(end)
            dep = end
        return line(points,aspect_ratio=1, *args, **keywords) + sum([point(p,aspect_ratio=1) for p in points])

p = Path([(1,1),(1,1),(1,-1),(1,-1),(1,1),(1,-1),(1,1),(1,1),(1,-1),(1,1),(1,-1),(1,-1)])
p.plot()

len(p)

p

p = Path([(0,1),(1,0),(0,-1),(0,-1),(-1,0),(-1,0),(0,1),(0,1),(0,1),(1,0),(1,0),(1,0),(0,-1),(0,-1),(0,-1),(0,-1),(-1,0),(-1,0),(-1,0),(-1,0)])
p.plot()

p = p.add_step((0,1))
p.plot()

Exercise: create a path that draws a 2x2 square.

︠e65db5c9-6d7d-49d9-ac17-e5ae9da95352i︠
%md

The goal of the tutorial is to generate the set of all possible paths following certain constraints. We will use two kinds of steps:

 * up steps (1,1)
 * down steps (1,-1)
 
We first generate the set of paths of a given length. Here is for example the list of paths of length 2.

The goal of the tutorial is to generate the set of all possible paths following certain constraints. We will use two kinds of steps:

• up steps (1,1)

• down steps (1,-1)

We first generate the set of paths of a given length. Here is for example the list of paths of length 2.

step_up = (1,1)
step_down = (1,-1)

paths2 = [Path([step_up, step_up]), Path([step_up, step_down]), Path([step_down, step_up]), Path([step_down, step_down])]
paths2

for p in paths2:
    p.plot()

Here are the functions generating paths of lengths 0, 1, and 2.

def getPaths0():
    """
    Return a generator on paths of length 0
    Note: there is a unique path of size 0 called the empty path
    """
    yield Path([]) # the unique possible path of size 0

def getPaths1():
    """
    Return a generator on paths of lentgh 1.
    """
    yield Path([(1,1)]) # first possibility
    yield Path([(1,-1)]) # second possibility

def getPaths2():
    """
    Return a generator on paths of length 2.
    """
    for p in getPaths1():
        yield p.add_step((1,1))
        yield p.add_step((1,-1))

Follow the same idea and write getPaths3.

def getPaths3():
    """
    Return a generator on paths of length 3.
    """
    # code here

paths3 = [Path([(1, 1), (1, 1), (1, 1)]),
 Path([(1, 1), (1, 1), (1, -1)]),
 Path([(1, 1), (1, -1), (1, 1)]),
 Path([(1, 1), (1, -1), (1, -1)]),
 Path([(1, -1), (1, 1), (1, 1)]),
 Path([(1, -1), (1, 1), (1, -1)]),
 Path([(1, -1), (1, -1), (1, 1)]),
 Path([(1, -1), (1, -1), (1, -1)])]
assert(set(getPaths3()) == set(paths3))

Now that you get the idea, write a recursive function that generates the set of all paths of a given size $n$.

def getPaths(n):
    """
    Return a generator on paths of length n using 2 kinds of steps (up and down)
    """
    # code here

paths3 = [Path([(1, 1), (1, 1), (1, 1)]),
 Path([(1, 1), (1, 1), (1, -1)]),
 Path([(1, 1), (1, -1), (1, 1)]),
 Path([(1, 1), (1, -1), (1, -1)]),
 Path([(1, -1), (1, 1), (1, 1)]),
 Path([(1, -1), (1, 1), (1, -1)]),
 Path([(1, -1), (1, -1), (1, 1)]),
 Path([(1, -1), (1, -1), (1, -1)])]
assert(set(getPaths(3)) == set(paths3))
assert(len(list(getPaths(5))) == 32)

If the given $n$ is negative, the function should not return anything (the empty path is of size 0!). Test if your function is well adapted to this rule.

assert(list(getPaths(-1)) == [])

More difficult now we want all paths that ends on a given point $(x,y)$

Hint answer first the following questions:

• If my path ends in $(x,y)$ with an up step, where was is before the up step? Same question with a down step.

• What are the positions I can never get to? What should I do in this case?

• When should I return the empty path?

def getPathsEndPoint(x,y):
    """
    Return a generator on paths ending at point (x,y) using step_up and step_down
    """
    # code here

assert(list(getPathsEndPoint(0,0)) == [Path([])])
assert(list(getPathsEndPoint(0,2)) == [])
assert(list(getPathsEndPoint(1,1)) == [Path([(1,1)])])
assert(list(getPathsEndPoint(1,-1)) == [Path([(1,-1)])])
assert(all([len(list(getPathsEndPoint(2*n,0)))== binomial(2*n,n) for n in xrange(6)]))

Last step! Now, we want to generate the paths that end in $(x,y)$ but are ALSO never going under the line $y=0$.

def getDyckPathsPref(x,y):
    """
    Return a generator on paths ending at point (x,y) using step_up and step_down without going under the line y=0
    """
    # code here

assert(list(getDyckPathsPref(0,0)) == [Path([])])
assert(list(getDyckPathsPref(0,2)) == [])
assert(list(getDyckPathsPref(1,1)) == [Path([(1,1)])])
assert(list(getDyckPathsPref(1,-1)) == [])
assert(all([len(list(getDyckPathsPref(2*n,0)))== catalan_number(n) for n in xrange(6)]))

Do you know these numbers?

[len(list(getDyckPathsPref(2*n,0))) for n in xrange(10)]

These objects actually already exist in Sage. They are called Dyck words. You can look through their methods and implementation.

DyckWords?

DW5 = DyckWords(5)
DW5.cardinality()

42

list(DW5)

[[1, 0, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 1, 1, 0, 0, 1, 0], [1, 0, 1, 0, 1, 1, 0, 1, 0, 0], [1, 0, 1, 0, 1, 1, 1, 0, 0, 0], [1, 0, 1, 1, 0, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 1, 1, 0, 0, 0], [1, 0, 1, 1, 1, 0, 0, 0, 1, 0], [1, 0, 1, 1, 1, 0, 0, 1, 0, 0], [1, 0, 1, 1, 1, 0, 1, 0, 0, 0], [1, 0, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 0, 1, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 1, 0, 0, 1, 0], [1, 1, 0, 0, 1, 1, 0, 1, 0, 0], [1, 1, 0, 0, 1, 1, 1, 0, 0, 0], [1, 1, 0, 1, 0, 0, 1, 0, 1, 0], [1, 1, 0, 1, 0, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 1, 0, 0], [1, 1, 0, 1, 0, 1, 1, 0, 0, 0], [1, 1, 0, 1, 1, 0, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0, 1, 0, 0], [1, 1, 0, 1, 1, 0, 1, 0, 0, 0], [1, 1, 0, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0, 0, 1, 0], [1, 1, 1, 0, 0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0, 0, 1, 0], [1, 1, 1, 0, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 1, 0, 1, 0, 0, 0], [1, 1, 1, 0, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0, 0, 1, 0], [1, 1, 1, 1, 0, 0, 0, 1, 0, 0], [1, 1, 1, 1, 0, 0, 1, 0, 0, 0], [1, 1, 1, 1, 0, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]]

DW5._iter_by_recursion??

?