Week 11 Recursion Review

By the assignment 3, I have more understand about Recursion:
1. For some functions, it seems like that recursion cannot apply on it, but I can develop a helper function with a recursion to help me to solve the problem. For example:

def distinct_node_count(root):
    '''(GameStateNode) -> int
   
    Return the number of nodes representing distinct game states in the
    tree rooted at root.  Two game states are distinct if they are not __eq__.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> distinct_node_count(root)
    10
    '''
This function have to return a int which cannot hold information about abstract object "GameStateNode" so recursion is not applicable; however, I can design a helper function which return a set to contain the data then recursion is applicable:

def distinct_node_set(root):
    '''(GameStateNode) -> set
   
    Return a set of all distinct nodes.
    '''
    if root.children == []:
        s = set()
        s.add(repr(root.value))
        return s
    else:
        result = set()
        result.add(repr(root.value))
        for r in root.children:
            for n in distinct_node_set(r):
                if n not in result:
                    result.add(n)
        return result

After that, the only thing I need to do is count the length of my set:  

def distinct_node_count(root):
    '''(GameStateNode) -> int
   
    Return the number of nodes representing distinct game states in the
    tree rooted at root.  Two game states are distinct if they are not __eq__.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> distinct_node_count(root)
    10
    '''
    return len(distinct_node_set(root))

2. Another interesting thing is that we can use dictionary in recursion. Recursive function can help us to accumulate values of each key:

def branching_stats(root):
    ''' (GameStateNode) -> {int: int}
   
    Return a dict that represents the distribution of branching factors in
    the tree rooted at root. Each key is a branching factor >= 0, and its
    value is the number of nodes with that branching factor.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> branching_stats(root) == {0: 4, 1: 6, 2: 3}
    True
    '''
    if root.children == []:
        return {0: 1}
    else:
        result = {}
        result[len(root.children)] = 1
        for r in root.children:
            for k in branching_stats(r).keys():
                if k not in result:
                    result[k] = branching_stats(r)[k]
                else:
                    result[k] += branching_stats(r)[k]
        return result

If the key exists in my dictionary, I just need to add the value by 1. If the key is not in the dictionary yet, I will create it and let its value equal to 1. After all, I can get a complete dictionary of the branch counting of my tree.

There is a similar function, but instead of the dictionary, it creates a list of string:

def game_descriptions(root):
    ''' (GameStateNode) -> list of str
   
    Return a list containing a str describing each complete game that is
    possible from the game stored at root.
   
    Assume root is the root of a game state tree specifically for the game
    Subtract Square.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> game_descriptions(root)
    ['p1:6 -> p2:2 -> p1:1 -> p2:0 = p1 wins!', 'p1:6 -> p2:5 -> p1:1 -> p2:0 = p1 wins!', 'p1:6 -> p2:5 -> p1:4 -> p2:0 = p1 wins!', 'p1:6 -> p2:5 -> p1:4 -> p2:3 -> p1:2 -> p2:1 -> p1:0 = p2 wins!']
    '''
    if root.children == []:
        if root.value.winner('p1'):
            return ['p2:0 = p1 wins!']
        elif root.value.winner('p2'):
            return ['p1:0 = p2 wins!']
    else:
        v = abbreviated(root.value) + ' -> '
        result = []
        for c in root.children:
            for d in game_descriptions(c):
                result.append(v + d)
        return result

At first, I have to decide what kind of the string should be printed for the end, then I add the other parts at front one by one.

Assignment 3 is a good practice of recursion. It shows me more ways to use recursion to solve complicate problems. I think it is a good preparation for final exam.

Week 7 Recursion

  In these weeks we go through the topics about recursion and how to use recursion in programming. Recursion is a method which will call itself when I operating it. I thought it likes while loop because both of them keep looping until the target is met. Overall, recursion is a useful method to evaluate the nested lists and nested abstract object, which means it will contain a same datatype value in its self. My first image about recursion is that this topic must be very hard to understand, because unlike other methods, recursion is very abstract, it is hard to image that how recursion is working? My recursion is working well or not? After the lectures, I sort out the steps to write a recursion code.

  First of all, I have to assume the parameter did not contain a data with a same datatype inside it such as a normal list but not a nested list. My code will go through all normal elements inside the list then return a simple result such as a number. After that, I assume that if the parameter is a nested list, I will apply this function again on every elements in the nested list. If the element is a normal, it will return a simple value. If the elements is a list or nested list, the function will apply on them again until there are no more data need to be evaluated. After all, I can evaluate all data in the nested list and return the results that I want.

  Although I have method it write a recursion code, it may not make the coding easy. In lab5 we use tree-related code to do the recursion. One assignment in the lab is challenging:

 def list_if(t, p):

    ''' (Tree, function) -> list

    Return a list of values in Tree t that satisfy p(value)

    >>> def p(v): return v > 4

    >>> t = descendents_from_list(Tree(0), [1, 2, 3, 4, 5, 6, 7, 8], 3)

    >>> L = list_if(t, p)

    >>> L.sort()

    >>> L

    [5, 6, 7, 8]

    >>> def p(v): return v % 2 == 0

    >>> L = list_if(t, p)

    >>> L.sort()

    >>> L

    [0, 2, 4, 6, 8]

'''

The target is compare each number in the tree, return a list of number which is larger than p. At first, I created an empty list named new, and if the tree does not have a children and the data is larger than p, the data will be appended:

    new = []

    if len(t.children) == 0 and p(t.value):

        new.append(t.value)

After that, I start to consider the situation which is that a tree with branches of children. First I have to evaluate its own value, than I call this function itself on the children tree:

else:

        if p(t.value):

            new.append(t.value)

        new.extend(gather_lists([list_if(n, p) for n in t.children]))

    return new

The tree is different from the nested list, I have to evaluate its own value otherwise I will not get right results.

   In this week I started to write the assignment 2. When I considering the recursion code in the minimax strategy I felt it is very hard. So I visit some slogs of my classmates to get some advice. In Zhou's blog(http://csc148wendezhou.blogspot.ca/), he suggests that consider more about the BTNode and its recursion method will be helpful to complete assignment. I am not sure that his method is useful. But it still helps me a lot because it notices me that I can create a new tree-related class to store all moves, and the moves after previous move in my tippy game.

Week 5 slog

Week 4
The topic in week 4 is recursion. If we want  to sum all nums in a nest list, a recursion method will be useful. Recursion means we can let a fuction call itself in order to solve this problem.  Some recursion codes are hard to understand so we can trace the code step by step:

def sum_list(L):
    ’’’
    (arbitrarily nested list of int or int) -> int
    Return the sum of all ints in L.
    >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
    36
    ’’’
    if isinstance(L, list):
        return sum([sum_list(x) for x in L])
    else:
        return L

Trace:
sum_list([[4,2], 1, 8]) --> sum( [ sum_list(4), sum_list(1), sum_list(8) ] )
--> sum( [6, 1, 8])
-->15

For some recursion, if we enter a empty list it may cause error, e.g.

def nested_concat(L):
    ’’’ (list or non-list) -> int
    Return 0 if L is not a list, or the maximum of len(L)
    and the lengths of L’s non-empty sublists.
    Assume: L is a non-list, or a non-empty list
    >>> length(17)
    0
    >>> length([1, [2, 3, 4, 5], 6])
    4
    >>> length([1, [2, 3, [4, 5]], 6])
    3
    ’’’

    if isinstance(L, list):
        return max(len(L),max([length(x) for x in L]))
    else:
        return 0

Therefore, we can add a str to the list, so it will return 0:

    if isinstance(L, list):
        return max(len(L),max([length(x) for x in (L + ['hi']]))
    else:
        return 0

Recursion can also be used for drawing diagrams, such as a snow flake or a tree diagram. Divergence will keep going until it mathes the depth that we want.

Week4 Slog

Week 1
In the first week we reviewed some basic knowledge from CSC108. Then we took the class Point and class stack as example to learn more details about class in python.
Notes:

1. We can use loop in a list, e.g. If we what to create a list which contain all square number from integer 1 to 9, we can write:
>>> s = [x**x for x in range(1, 10)]
By this method we can calculate a set of objects but not implement them one by one.We can also use function in this method:
>> def square(x):
    return x**2
>>> s = [square(x) for x in range(1, 10)]

2. The minimum need to create a class in python is the name of the class, e.g.
>>> class Point():
    Pass

3. There are some special methods for class:

__init__ : initialize the class e.g.
 
def __init__(self, coord):
        """ (Point, list-of-floats) -> NoneType

        Create and initialize this point.

        >>> p = Point([3, 4])
        """
        self.coord = [float(x) for x in coord]

__repr__ : Use a str to represent a class instance e.g.

def __repr__(self):

    """ (Point) -> str

    Return a string representation of self that evaluates
    into an equivalent Point.
        
    >>> p = Point([3, 4])
    >>> p
    Point([3.0, 4.0])
    """
    return "Point({})".format(self.coord)

__str__: sometimes we may need more specific words to describe the class, so we may use __str__ method. If we dont state it, python will use __repr__ to represent the class instance.

def __str__(self):

""" (Point) -> str

Return a string version of self.
>>> p = Point([3, 4])
    >>> print(p)
    (3.0, 4.0）

    """

return str(tuple(self.coord))



_eq_ : Being used for check whether two objects are same. e.g.



def __eq__(self, other):

    """ (Point, object) -> bool

    Return whether self is equivalent to other.

    >>> p1 = Point([3, 4, 5])
    >>> p2 = Point([3.0, 4.0, 5.0])
    >>> p1 == p2
    True
    """
    return (isinstance(other, Point) and self.coord == other.coord)


Week2
The topic in week 2 is stacks. We can create a class named Stacks to hold the elements. There are four basic method in Staks:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return (self.items == [])

__init__: initialize an empty stack(an empty list).
pop: remove the top item in the stack.
push(n): add the element n to the top of the stack.
is_empty: check whether the stack is empty.

We can use some method in the stack, for example:

def adding(n):
    '''(str) -> int
       Pre-condition: n contains a math symbol in  '+-*/'.
       Return the sum all numbers in n.
       >>>n = '123456789'
       >>>adding(n)
       579
    '''
    k = Stack()
    for x in n:
        k.push(x)
    for i in k.items:
   

Week3
In the third week we studied how to build a sub class base on a main class. A sub class will inherit all method from the main class also we can add new method to sub class. If same method exist in both sub class and main class (e.g.__repr__, __str__, __init__), python will implement the closer method.

To use the methods from main class:

class A:

def square(x):
    return x ** 2

class B(A):

def double_square:
    return (A.square(x)) * 2

To import a specific class from another file:

from file import A

class B(A):
    Pass

If a method in main class cannot be state but can be stated in sub class, we can raise a Error:

class A:

def double_square(x):
    raise ValueError

2015/01/24 Week 3 (Why Geeks Should Know How to Write）

Why Geeks Should Know How to Write

Although programmers do not require high writing skills like an author, we still can be benefited by some writing work. At first, programmers should always have a plan before coding. A specific plan or sketch can make our object more clear so we will know what are we want to do then we can reduce the mistakes during the coding and know how to test our codes. Coding can be very complex when we have to combine a lot of modules to finish the program. If we do not have a plan and start coding directly we may produce something that cannot meet our targets. Therefore, write a plan and draw a clear structure for the codes before working can save a lot of time by making sure that we are following the spec file.

Furthermore, the programmers may want to write their ideas on the paper. Because the ideas maybe lost or blurring during the thinking. If I write ideas on the paper and state them in details then I will never forget. Sometimes the ideas maybe bad or cannot work, so if we write down them on the paper we can analysis each of them, fix the problems or choose the best one. When a target can be achieved by different ways, we should display all the ways on the paper then find out advantages and disadvantages of each one to make the final decision.

During testing the codes, programmers can build a list of test case on the paper so we will not ignore any important cases, and delete the useless test cases to save the time. After the testing, we have to record each wrong cases down so we can check them one by one and redesign the codes, then repeat these steps until all tests are passed.

The geeks will never stop learning new knowledge, also include find out ways to solve hard problems. Sort out what we learned every week and every month can help us to maintain the new skills and know how to apply them. We should record the test cases which are not passed and write down the ways to solve; therefore, we can prevent same mistakes next time, or generate new methods from these cases to solve new problems. These are reasons for why writing skills are still important to geeks and help us a lot.