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()
