The time passing faster and now is almost
the final week of winter semester. Through the computer study at short time, I achieved a lot. I
know how to choose a topic and make some preparations for it, also know how to
deal with the assignment we solved. What`s the most important is
I enjoyed the process working together with my teammates and I think
a group`s success is true success, the success belongs to every member.
It comes the final of this term. Looking backward to so many things happened
during the past three months. I suddenly felt I grew up quickly from the series
of problems I had ever met. Life is so difficult at sometimes, putting a lot of
troubles together in front of you. I still remembered the midnight three of us
were typing on the computer and confused with the extremely hard
method—‘Minimax’. Our team fight for it to three a.m. in morning and finally
solved it. It was such an excited time I`ve met in my university life. Looking
back for the past sLog, I`d found some of my old idea was funny. However some
of them were eligible to nowadays computer scientist`s ideology. Wish the strike
ended soon and be fast to give my mark of my assignment 2.
:)
Thursday, March 26, 2015
Week 9
We took second term test in week 9 and it seems not harder than the first term test. I am guessing it was affected by the strike. Wish it can stop as soon as possible. In week 9 we learned the BTNode again and I know that insert must obey the BST condition. here is the example:
def insert(node, data):
''' (BTNode, object) -> BTNode
Insert data in BST rooted at node if necessary, and return new root.
>>> 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)
>>> print(b)
14
12
10
8
6
4
2
<BLANKLINE>
'''.
After the example is the function code of def insert:
def insert(node, data):
return_node = node
if not node:
return_node = BTNode(data)
elif data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
else: # nothing to do
pass
return return_node
Sunday, March 15, 2015
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()
Week 7
In week 7 all of us learnt the new
knowledge of Binary Tree Node. Binary tree is harder enough to understand and
it cost me a lot of times to consider about it. This was the code of a basic
btnode function:
class BTNode:
'''Binary Tree node.'''
def __init__(self, data, left=None, right=None):
''' (BTNode, object, BTNode, BTNode) -> NoneType
Create BTNode (self) with data and children left and right.
'''
self.data, self.left, self.right = data, left, right
def __repr__(self):
''' (BTNode) -> str
Represent BTNode (self) as a string that can be evaluated to
produce an equivalent BTNode.
>>> BTNode(1, BTNode(2), BTNode(3))
BTNode(1, BTNode(2, None, None), BTNode(3, None, None))
'''
return 'BTNode({}, {}, {})'.format(repr(self.data),
repr(self.left),
repr(self.right))
def __str__(self, indent=''):
''' (BTNode) -> str
Return a user-friendly string representing BTNode (self) inorder.
Indent by indent.
>>> b = BTNode(1, BTNode(2, BTNode(3)), BTNode(4))
>>> print(b)
4
1
2
3
<BLANKLINE>
'''
right_tree = self.right.__str__(indent + ' ') if self.right else ''
left_tree = self.left.__str__(indent + ' ') if self.left else ''
return right_tree + '{}{}\n'.format(indent, str(self.data)) + left_tree
if __name__ == '__main__':
import doctest
doctest.testmod()
Fortunately our assignment do not required
btnode inside. Although it do not need it, I and our team were absolutely stuck
in the assignment part minimax. It`s so hard that let us working on it for two nights,
both night we stay in the lab till three A.M.. At last we still not solved the
problem and our team feel disappointment. It`s almost the due date we have to
finished it. Wish next night we can finish it..
Sunday, March 8, 2015
Abstract Data Types
In computer
science, Abstract Data Types (ADT) is a programming methodology where one
defines not only the data structure to be used but the processes to manipulate the
structure.
Same as the
progress abstraction, ADT can be directly support by any programming languages.
To support the ADT, there needs to be mechanisms for defining data structures,
which is the basis and the primary in ADT. Second encapsulation of data
structures and their routines to manipulate the structures into one unit. It can
be compiled at one time by placing all definitions in one unit.
In programming
languages, there are some common types of ADTs such as Associative Array (we called it Dictionary in Python), method ‘append’,
list, queue and priority
queue, storage, method ‘pop’ and ‘push’ (in python), string and the tree we
have recently learned it. The data structure should only be accessible from
code encapsulated with it so that the structure is hidden and protected from
the outside. Users need only care for the interface but not how to realize. This
means that as long as the users follow the interface, the ADT can be implemented by any method and will never affect the users.
picture from http://www.cafepy.com/article/python_types_and_objects/python_types_and_objects.html
Subscribe to:
Comments (Atom)