Week 8

Finally!! We solved the minimax problem and the game can run perfectly, uhmm, just in the size of game board for 9 and 16 which means the length of the square was 3 and 4. If the length became larger, the tracing time of the game will growing explosively. Sometime the game will cost 20 minutes of half an hour to decide the next step. Though the time cos a lot, the game can still run in the best way. You will love this game if you have enough time! Last assignment we forgot to run pep8 in our project. This small negligence made us miss the full mark! This time we will not make this stupid mistake and try to get a full mark in assignment2.

This week we learned linked list in our class. It`s not so hard to comprehend. Also we`ve learned how to build a tree when you have some numbers. I thought it was easy but I messed it up at first. Fortunately I knew how to write it in right way.

# On Wednesday (4 Mar) we
# - traced prepend
# - wrote __contains__ from scratch
# - figured out that delete_back needs to find the node one before the end.
#   This can be done by having two pointers traverse the list,
#   with one a step behind the other.

# Exercises
# - write and test delete_back
# - write append (I gave out a handout for that one)
# - Use all the methods.  See how you can use "in" syntax, since we have defined
#   the special method __contains__

class LLNode:
    '''Node to be used in linked list

    nxt: LLNode -- next node
                   None iff we're at end of list
    value: object --- data for current node
    '''

    def __init__(self, value, nxt=None):
        ''' (LLNode, object, LLNode) -> NoneType

        Create LLNode (self) with data value and successor nxt.
        '''
        self.value, self.nxt = value, nxt

    def __repr__(self):
        ''' (LLNode) -> str

        Return a string representation of LLNode (self) that can yields
        an equivalent LLNode if evaluated in Python.

        >>> n = LLNode(5, LLNode(7))
        >>> n.nxt
        LLNode(7)
        >>> n
        LLNode(5, LLNode(7))
        '''
        if self.nxt is None:
            return 'LLNode({})'.format(repr(self.value))
        else:
            return 'LLNode({}, {})'.format(repr(self.value), repr(self.nxt))

    def __str__(self):
        ''' (LLNode) -> str

        Return a user-friendly representation of this LLNode.

        >>> n = LLNode(5, LLNode(7))
        >>> print(n)
        5 -> 7 ->|
        '''
        if self.nxt is None:
            return '{} ->|'.format(str(self.value))
        else:
            return '{} -> {}'.format(str(self.value), str(self.nxt))

    def __eq__(self, other):
        ''' (LLNode, object) -> bool

        Return whether LLNode (self) is equivalent to other.

        >>> LLNode(5).__eq__(5)
        False
        >>> n = LLNode(5, LLNode(7))
        >>> n2 = LLNode(5, LLNode(7, None))
        >>> n.__eq__(n2)
        True
        '''
        return (type(self) == type(other) and
                (self.value, self.nxt) == (other.value, other.nxt))



class LinkedList:
    '''Collection of LLNodes organized in a linear sequence.

    front: LLNode -- front of list
    back:  LLNode -- back of list
    size: int -- number of nodes in the list'''

    def __init__(self):
        ''' (LinkedList) -> NoneType

        Create an empty linked list.
        '''
        self.front, self.back = None, None
        self.size = 0

    def __str__(self):
        ''' (LinkedList) -> str

        Return a human-friendly string representation of
        LinkedList (self)

        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> print(lnk)
        5 ->|
        '''
        return str(self.front)

    def __eq__(self, other):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) is equivalent to
        other.

        >>> LinkedList().__eq__(None)
        False
        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> lnk2 = LinkedList()
        >>> lnk2.prepend(5)
        >>> lnk.__eq__(lnk2)
        True
        '''
        return (type(self) == type(other) and
                (self.size, self.front) == (other.size, other.front))

#    def append(lnk, value):
#        ''' (LinkedList, object) -> NoneType
#
#        Insert a new node with value at back of lnk.
#
#        >>> lnk = LinkedList()
#        >>> lnk.append(5)
#        >>> lnk.size
#        1
#        >>> print(lnk.front)
#        5 ->|
#        >>> lnk.append(6)
#        >>> lnk.size
#        2
#        >>> print(lnk.front)
#        5 -> 6 ->|
#        '''

    def prepend(self, value):
        ''' (LinkedList, object) -> Nonetype

        Insert value at front of LLNode (self).

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> str(lnk.front)
        '2 -> 1 -> 0 ->|'
        >>> lnk.size
        3
        '''
        self.front = LLNode(value, self.front)
        if self.back is None:
            self.back = self.front
        self.size += 1

#    def delete_front(self):
#        ''' (LinkedList) -> NoneType
#
#        Delete front node from LinkedList (self).
#
#        self.front must not be None
#
#        >>> lnk = LinkedList()
#        >>> lnk.prepend(0)
#        >>> lnk.prepend(1)
#        >>> lnk.prepend(2)
#        >>> lnk.delete_front()
#        >>> str(lnk.front)
#        '1 -> 0 ->|'
#        >>> lnk.size
#        2
#        '''
    
#    def delete_back(lnk):
#        ''' (LinkedList) -> NoneType
#    
#        Delete back node of lnk, if it exists, otherwise
#        do nothing.
#    
#        >>> lnk = LinkedList()
#        >>> lnk.prepend(5)
#        >>> lnk.prepend(7)
#        >>> print(lnk.front)
#        7 -> 5 ->|
#        >>> delete_back(lnk)
#        >>> lnk.size
#        1
#        >>> print(lnk.front)
#        7 ->|
#        >>> delete_back(lnk)
#        >>> lnk.size
#        0
#        >>> print(lnk.front)
#        None
#        '''

#    def __getitem__(self, index):
#        ''' (LinkedList, int|slice) -> object
#
#        Return the value at index.
#        # Don't worry about slices for now
#
#        >>> lnk = LinkedList()
#        >>> lnk.prepend(1)
#        >>> lnk.prepend(0)
#        >>> lnk.__getitem__(1)
#        1
#        >>> lnk[-1]
#        1
#        '''

    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
        '''
        current_node = self.front
        while current_node:
            if value == current_node.value:
                return True
            current_node = current_node.nxt
        return False    

if __name__ == '__main__':
    import doctest
    doctest.testmod()