Impression of Week 9

      We did some test on Minimax.
      We were given three SubtractSquareState and we wanted to know what outcome of our Minimax meant our function was more likely to be correct. For states with current value 9, 10 and 11, the outcomes are all win or all lose. From that we cannot conclude whether our Minimax is working or not, so we would want a state with less wins to test our code on. In the unit test for Minimax, Danny used a state whose current value is 25 and this state has only one move to win. If that winning move is returned, which is nearly impossible for a random strategy, our Minimax is very likely to be correct.
      Later in that week, we saw some other functions.

      N = 5
      M = 2

      def f(N):
          return M * g(N + 1)

      def g(N):
          return M * N

      def h(N):
          return f(g(N))

      What we learned from them was when the name of a variable is used more than one time, which one should we refer to. The rule is the nearest one is what we need.

Impression of Week 8

      We didn't do much during the lecture this week because this week is a test week. We had a test on Wednesday and that wasn't as bad as I thought it would be, it was actually pretty easy.
      On Monday's lecture, all we did was one function: deletion of data from BST from a certain node. In this function, we have several things to consider: if the node is None; using the BST characteristics  to avoid unnecessary iterations; is the node a leaf or a internal node; what should we return?
      So, when implementing the function, we should take all of these things into consideration. As Danny suggests, we should have a list of all the possible situations:

def delete(node, data):
    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> b = delete(b, 12)
    >>> print(b)
            14
        10
    8
            6
        4
            2
    <BLANKLINE>
    '''
    # Algorithm for delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node
    return_node = node
    if node is None:
        pass
    elif node.data > data:
        node.left = delete(node.left, data)
    elif node.data < data:
        node.right = delete(node.right, data)
    elif node.left is None:
        return_node = node.right
    elif node.right is None:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

      List a todo list and follows it. That is a good way to be thorough and organized.
     

Impression of Week 7

      LinkedList was introduced to us this week. And we are using that to do iteration and mutation.
      The way to solve LinkedList problems is iteration. We go over every element in the linked list and find what we want, then we make mutations.
      For example, the __contains__ method we did in the lecture:

def __contains__(self, value):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) contains value.

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> lnk.__contains__(1)
        True
        >>> lnk.__contains__(3)
        False
        '''
        cur_node = self.front
        while cur_node:
            if cur_node.value == value:
                return True
            cur_node = cur_node.nxt
        return False

      In this example, we are checking if value is in a linked list. Our thought was to go over all the nodes in the linked list, check every one of them to see if it has the same value as value. So, we store the node we are checking in a variable called cur_node, as we go deeper into the linked list, cur_node changes. If cur_node's value is equal to value, we return True, if not, we set cur_node to the next node and keep checking. When we go over all the nodes and nothing is returned, that means there are no value in the linked list, so we return False.

Recursion

      Recursion is a pretty new stuff that we just learned in class. It is somehow different from what we already known about python.
      Recursion is used in functions to solve problem with unknown layers and cannot be solved simply by for or while loops, for example, checking elements in arbitrarily nested-lists and that is the main problem that we've trying to solve with recursion so far. Recursion and loops are doing the same job which is repeating some lines of code, but the difference between them is that when recursion is used in a function, it is calling the function itself inside this function.
      This is an example of recursion:

    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

      This function is summing all the elements in the list up. The recursive idea in this function is that we keep looking inside nested-lists until there are no nested-lists left. As we can see in this function, a recursion contains an if statement. This if statement is important when we are trying to make a recursion. How do we so that?
      First, we need a base case which can be done without recursing. Base case is also the thing we are looking for using the recursion. In this case, is when L is an int, so that we don't need to look inside lists to find int and there is no need so sum up an int so we return that int. Now we have our first part of the code. Then we need to consider other cases. If L is a list, we should check the elements in L. If the element is an int, we return it and if it is a list, we keep checking the elements inside it. This is where we need recursion. We call this function on every element in L, so that this function does what we want. Using a list comprehension to collect the results and sum them up. The recursion basically looks like this: 'if base case, else: recursion'.
      When running this function on the doctest, the process should be as follows:
      sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
-> sum([sum_list(1), sum_list([2, 3]), sum_list([4, 5, [6, 7], 8])])
-> sum([1, sum([sum_list(2), sum_list(3)]), sum([sum_list(4), sum_list(5), sum_list([6, 7]), sum_list(8)])])
-> sum([1, sum([2, 3]), sum([4, 5, sum([sum_list(6), sum_list(7)]), 8])])
-> sum([1, 5, sum([4, 5, sum([6, 7]), 8])
-> sum([1, 5, sum([4, 5, 13, 8])])
-> sum([1, 5, 30])
-> 36
      Basically what recursion does is it stops and return stuff when we find what we need, int for example, if not we keep checking.

Impression of Week 6

    This week, we met a new class - Tree. And we are implementing a huge amount of recursions inside this class. This class is basically nested-list inside nested-list but in the form of  nodes and children. So whatever we are going to de with the tree, we have to go over every node and its children and this is where recursion fits in.
    In the lecture, we did the function contains which is used to check if a number is in a tree.
    To implement contains, first we start with simple tree which is just a leaf with no children. We check if the root value is equal to the given value. And now we have the worst part of the function:
            def contains(t, v):
                  if len(t.children) == 0:
                      return t.children == v
                  else:
                        ...
    Now the question is what if the tree has children and its children have children? Recursion!
    The thought is, we have to check every node to see if its root value is v and check if v is in its children or children's children until we find all the leaves and check all of them. Checking a leaf needs the same code as in the if statement we just implemented checking a node needs the code to check its children and its own value. As the function will return a list of boolean outputs, if v is in the tree, at least one True should be in the list. Now we have the code:
                 else:
                       return t.value == v or True in [contains(c, v) for c in t.children]
    Also, we can make the function contains a special function __contains__. By doing so, running the function would be using 'in'.
           >>> t = Tree(3)
           >>> 3 in t
           True

    On Wednesday, we did a recursion called leaf_count which has basically the same idea. If the tree we are checking has no children then it is a leaves, so return 1. If not return nothing.
Here's the code:
             def leaf_count(t):
                   if t.children == []:
                        return 1
                   else:
                         return sum([leaf_count(c) for c in t.children])

Impression of Week 5

     This week, we learned more on recursion.
     It was snowing heavily on Monday and the TTC was delayed again. But I luckily made it to 148's lecture ;)
     On Monday, we did the quick sort using recursion first. The basic process is picking the first element and sort those greater than or equal to it to the right and those less than it to the left and repeat this process until all the elements are in the right position.
    Here's the code:

def quick_sort(L):
    ''' (list) -> list

    Return a list containing the same elements as L in ascending order.

    >>> quick_sort([])
    []
    >>> quick_sort([5])
    [5]
    >>> import random
    >>> L = [1, 2, 3, 4, 5, 6, 7]
    >>> random.shuffle(L)
    >>> quick_sort(L)
    [1, 2, 3, 4, 5, 6, 7]
    '''
    if len(L) < 2: # there's nothing to sort
        return L
    else:
        return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

The recursion here is for those lists who have more than 1 element that is to say can be sorted. But in this code, we are not checking the order of the sequence but we keep sort things and dividing list up until the length of the list remains is 1.
      After that, we did the parenthesizetion using the ADT we coded before. Noticing that the computer can only see one character at a time, we are using Stack to store the parenthesis we see so far and check to see if they are in the correct position.
     Here's the code:

def balanced_delimiters(s):
    ''' (str) -> bool

    Return whether the brackets in string s are balanced.

    Assume: Only delimiters are brackets
    >>> balanced_delimiters('[({])}')
    False
    >>> balanced_delimiters('[({})]]')
    False
    >>> balanced_delimiters('[[]')
    False
    >>> balanced_delimiters('[(){}]')
    True
    '''
    st = stack.Stack()
    for c in s:
        if not c in '(){}[]':
            pass
        elif c in '({[':
            st.push(c)
        # now must have c in ')}]'
        elif not st.is_empty():
            c2 = st.pop()
            if ((c == ')' and not c2 == '(') or
                (c == '}' and not c2 == '{') or
                (c == ']' and not c2 == '[')):
                return False
        else: # prematurely empty stack!
            return False
    return st.is_empty() # better be empty at the end

Basically we are checking the type and the order at the same time, so using a stack which is a first in last out thing is reasonable as the first half of parenthesis should appear last in the application.

     Wednesday was the term test, so no lectures.

Impression of Week 4

    The forth week, we did recursion. It is a function but it's using itself in the function. Recursions are used to solve questions that requires unknown loops to check the nested-list inside the nested-list. For example:
 def rec_max(L):

    ''' (list or int) -> int

    Return L if it's an int, or the maximum int in L,
    a possibly nested list of numbers.

    Assume: L is an int or non-empty list

    >>> rec_max([17, 21, 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    '''
    if isinstance(L, list):
        return max([rec_max(x) for x in L])
    else:
        return L

In this function, the function re_max is called again and again until we find the elements that are not lists and the loop stops.
We did a lot of tracing in the lecture and in the tutorial, starting with depth 0 and moved on to more complicated examples gradually. We can also find the docstring by calling and tracing examples, just like we did in the tutorial.
By calling non-lists or empty list, we get the special cases of the function. How I understand this is checking the 'else:' and checking the build-in method called in the recursion. Then we check examples with more depth, and we can conclude the docstring and the assumption.

The first term test is next week, wish everyone a good grade!