'''
    第一个问题是构造pascal 三角。下一行最两边是1， 生下来的元素是上一行两两元素的和。所以这么构造：
    1： 只有一行或者两行，那就是1
    2： 从第三行开始，两边是1，中间是上一行从第一个元素开始，第一个元素与第二个元素的和。

    Question 1. Pascal's Triangle:

                  1
               1     1
            1     2    1
          1    3     3    1
       1    4     6     4    1
    1    5    10     10    5    1
    '''

    def pascal_t(n):
        if n == 1:
            return [1]
        elif n == 2:
            return [1, 1]
        elif n > 2:
            po = pascal_t(n - 1)
            return [1] + [po[i] + po[i+1] for i in range(len(po)-1)] + [1]

    print pascal_t(6)

    [1, 5, 10, 10, 5, 1]


    '''
    Fibonacci数：第n个数是前面两个数的和

    Question 2: Fibonacci numbers from Pascal Triangle
    '''
    def fib(n):
        pass

    memo = {0:0, 1:1}
    def fibm(n):
        if not n in memo:
            memo[n] = fibm(n-1) + fibm(n-2)
        return memo[n]

    fibm(6)    

    8


    '''
    列出小于等于n的质数：列出从2到n的所有数，然后对i=2，删去i的2倍，3倍，等等；对i=3，做同样的事情；
    最后生下来的数字既不是2的倍数，也不是3的倍数，也不是4的倍数，等等。它们就是质数

    Question 3. prime numbers. The sieve of Eratosthenes to find all prime numbers up to n.
    1. Create a list of integers from two to n: 2, 3, 4, ..., n
    2. Start with a counter i set to 2, i.e. the first prime number
    3. Starting from i+i, count up by i and remove those numbers from the list, i.e. 2*i, 3*i, 4*i ...
    4. Find the first number of the list following i. This is the next prime number.
    5. Set i to the number found in the previous step
    6. Repeat steps 3 and 4 until i is greater than n. (As an improvement: It's enough to go to the square root of n)
    7. All the numbers, which are still in the list, are prime numbers
    '''
    def sieve_prime_1(n):
        if n == 0 or n == 1:
            return []
        else:
            lst = range(2, n+1)                                     # step 1
            for i in range(2, n):                                   # step 2
                no_p = [j for j in range(i + i, n + 1, i)]          # step 3
                rest = [j for j in lst if j not in no_p]            # step 3 to remove and step 4
                lst = rest                                          # step 5, 6
            return rest

    def sieve_prime_2(n):
        if n == 0 or n == 1:
            return []
        else:
            p = range(2, n + 1)     # step 1
            for i in p:
                no_p = [j for i in p for j in range(i * 2, n + 1, i)]        # step 2, 3   2*i, 3*i, 4*i ...
                p = [j for j in range(2, n + 1) if j not in no_p]            # step 4, 5, 6
            return p


    print sieve_prime_1(50)
    print sieve_prime_2(50)

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]


    '''
    爬n级台阶：每次可以爬一级或者两级。总共有多少爬法。
    从第n-1到第n：增加了一级台阶，把这一级台阶插到第n-1次的所有办法里面每个办法里每个位置。然后去除重复的办法。
    如果n是偶数，增加一个办法：每次都爬两级

    Question 4. I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time.
    How many different ways can I go up this flight of stairs?  
    '''
    # n=3,  s = [[1,1,1], [1,2], [2,1]]

    import itertools

    # de-dup the duplicated elements in the list while the elements are lists
    def dedup_list(ls):
        ls0 = sorted(ls)
        newls = [ls0[i] for i in xrange(len(ls0)) if i == 0 or ls[i] != ls[i - 1]]
        return newls

    # from n-1 to n, insert '1' to all the positions in the results of step n-1
    # s is the result in step n-1, it is a list of lists
    # n=3,  s = [[1,1,1], [1,2], [2,1]]
    def inserts(s):
        newls = []
        for ls0 in s:          #e.g. ls0 = [1,1,1]
            for p in xrange(len(list(ls0)) + 1):
                ls0p = ls0[:p] + [1] + ls0[p:]
                newls.append(ls0p)
        return dedup_list(newls)

    def steps(n):
        if n == 1:
            return [[1]]
        else:
            s0 = steps(n - 1)
            if n % 2 == 1:
                return inserts(s0)
            else:
                return inserts(s0) + [[2] * (n / 2)]

    steps(3)

    [[1, 1, 1], [1, 2], [2, 1]]


    '''
    反序一个列表：把最后一个元素拿出来放最前面，然后反序拿出最后一个元素后剩下来的列表
    '''

    def reverse_iter(x):
        if len(x) == 1:
            return x
        elif len(x) > 1:
            return [x[-1]] + reverse_iter(x[:-1])

    reverse_iter([1, 2, 3, 4, 5])

    [5, 4, 3, 2, 1]