4. Sequences¶
Computers are really good at dealing with large amounts of information. They can repeat a task over and over again without getting bored. When they repeat a task they are generally doing the same thing to similar data or objects. It is natural to want to organize those objects into some kind of structure so that our program can easily switch from one object to the next. How objects are added to a sequence or collection and how we move from one item to the next has some impact on how we might want to organize the collection of data in a program.
In this chapter we look at different ways of organizing data into a sequence. We’ll also examine how to use Python to make working with sequences convenient. Operator overloading in Python lets us build sequences that we can manipulate with intuitive operations. Finally, we also examine how the organization of a sequence affects the computation complexity of operations on it.
4.1. The PyList Datatype¶
You can download the complete PyList datatype by clicking here.
1class PyList:
2 def __init__(self,contents=[], size=10):
3 # The contents allows the programmer to construct a list with
4 # the initial contents of this value. The initial_size
5 # lets the programmer pick a size for the internal size of the
6 # list. This is useful if the programmer knows he/she is going
7 # to add a specific number of items right away to the list.
8 self.items = [None] * size
9 self.numItems = 0
10 self.size = size
11
12 for e in contents:
13 self.append(e)
14
15 def __getitem__(self,index):
16 if index < self.numItems:
17 return self.items[index]
18
19 raise IndexError("PyList index out of range")
20
21 def __setitem__(self,index,val):
22 if index < self.numItems:
23 self.items[index] = val
24 return
25
26 raise IndexError("PyList assignment index out of range")
27
28 def insert(self,i,e):
29 if self.numItems == self.size:
30 self.__makeroom()
31
32 if i < self.numItems:
33 for j in range(self.numItems-1,i-1,-1):
34 self.items[j+1] = self.items[j]
35
36 self.items[i] = e
37 self.numItems += 1
38 else:
39 self.append(e)
40
41
42 def __add__(self,other):
43 result = PyList()
44
45 for i in range(self.numItems):
46 result.append(self.items[i])
47
48 for i in range(other.numItems):
49 result.append(other.items[i])
50
51 return result
52
53
54 def __contains__(self,item):
55 for i in range(self.numItems):
56 if self.items[i] == item:
57 return True
58
59 return False
60
61 def __delitem__(self,index):
62 for i in range(index, self.numItems-1):
63 self.items[i] = self.items[i+1]
64 self.numItems -= 1 # same as writing self.numItems = self.numItems - 1
65
66 def __eq__(self,other):
67 if type(other) != type(self):
68 return False
69
70 if self.numItems != other.numItems:
71 return False
72
73 for i in range(self.numItems):
74 if self.items[i] != other.items[i]:
75 return False
76
77 return True
78
79 def __iter__(self):
80 for i in range(self.numItems):
81 yield self.items[i]
82
83 def __len__(self):
84 return self.numItems
85
86 # This method is hidden since it starts with two underscores.
87 # It is only available to the class to use.
88 def __makeroom(self):
89 # increase list size by 1/4 to make more room.
90 newlen = (self.size // 4) + self.size + 1
91 newlst = [None] * newlen
92 for i in range(self.numItems):
93 newlst[i] = self.items[i]
94
95 self.items = newlst
96 self.size = newlen
97
98 def append(self,item):
99 if self.numItems == self.size:
100 self.__makeroom()
101
102 self.items[self.numItems] = item
103 self.numItems += 1 # Same as writing self.numItems = self.numItems + 1
104
105 def __str__(self):
106 s = "["
107 for i in range(self.numItems):
108 s = s + str(self.items[i])
109 if i < self.numItems - 1:
110 s = s + ", "
111 s = s + "]"
112 return s
113
114 def __repr__(self):
115 s = "PyList(["
116 for i in range(self.numItems):
117 s = s + str(self.items[i])
118 if i < self.numItems - 1:
119 s = s + ", "
120 s = s + "])"
121 return s
122
123 def sort(self):
124 pass
125
126
127def main():
128 lst = PyList()
129
130 for i in range(100):
131 lst.append(i)
132
133 lst2 = PyList(lst)
134
135 print(lst)
136 print(lst2)
137
138 if lst == lst2:
139 print("Test 1 Passed")
140 else:
141 print("Test 1 Failed")
142
143 lst3 = lst + lst2
144
145 if len(lst3) == len(lst) + len(lst2):
146 print("Test 2 Passed")
147 else:
148 print("Test 2 Failed")
149
150
151 if 1 in lst3:
152 print("Test 3 Passed")
153 else:
154 print("Test 3 Failed")
155
156 if 2 in lst3:
157 print("Test 4 Passed")
158 else:
159 print("Test 4 Failed")
160
161 del lst[1]
162
163 if 1 in lst:
164 print("Test 5 Failed")
165 else:
166 print("Test 5 Passed")
167
168 if len(lst) == 99:
169 print("Test 6 Passed")
170 else:
171 print("Test 6 Failed")
172
173 if lst == lst2:
174 print("Test 7 Failed")
175 else:
176 print("Test 7 Passed")
177
178 del lst2[2]
179
180 if lst == lst2:
181 print("Test 8 Failed")
182 else:
183 print("Test 8 Passed")
184
185
186 lst4 = PyList(lst)
187 lst.insert(0,100)
188 lst4 = PyList([100]) + lst4
189
190 if lst == lst4:
191 print("Test 9 Passed")
192 else:
193 print("Test 9 Failed")
194
195 lst.insert(1000,333)
196 lst4.append(333)
197
198 if lst == lst4:
199 print("Test 10 Passed")
200 else:
201 print("Test 10 Failed")
202
203 print(lst)
204 print(lst4)
205
206if __name__ == "__main__":
207 main()
208
209
210
211
212
4.2. The Sort Animation¶
You can download the complete sort animation by clicking here. You can also get source code for selection sort, merge sort, and quicksort from this animation program.
1import tkinter
2import turtle
3import random
4import time
5import math
6
7class Point(turtle.RawTurtle):
8 def __init__(self, canvas, x, y):
9 super().__init__(canvas)
10 canvas.register_shape("dot",((3,0),(2,2),(0,3),(-2,2),(-3,0),(-2,-2),(0,-3),(2,-2)))
11 self.shape("dot")
12 self.speed(0)
13 self.penup()
14 self.goto(x,y)
15
16 def __str__(self):
17 return "("+str(self.xcor())+","+str(self.ycor())+")"
18
19 def __lt__(self, other):
20 return self.ycor() < other.ycor()
21
22# This class defines the animation application. The following line says that
23# the SortAnimation class inherits from the Frame class.
24class SortAnimation(tkinter.Frame):
25 def __init__(self, master=None):
26 super().__init__(master)
27 self.pack()
28 self.buildWindow()
29 self.paused = False
30 self.stop = False
31 self.running = False
32
33
34 def buildWindow(self):
35
36 def partition(seq, start, stop):
37 pivotIndex = start
38 pivot = seq[pivotIndex]
39
40 theTurtle.color("red")
41 theTurtle.penup()
42 theTurtle.goto(start,pivot.ycor())
43 theTurtle.pendown()
44 theTurtle.goto(stop,pivot.ycor())
45 screen.update()
46
47 # Why twice? Because once doesn't seem to display
48 # the line the first time through for some reason
49 theTurtle.color("red")
50 theTurtle.penup()
51 theTurtle.goto(start,pivot.ycor())
52 theTurtle.pendown()
53 theTurtle.goto(stop,pivot.ycor())
54 screen.update()
55
56 i = start+1
57 j = stop-1
58
59 while i <= j:
60 while i <= j and not pivot < seq[i]:
61 i+=1
62 while i <= j and pivot < seq[j]:
63 j-=1
64
65 if i < j:
66 tmp = seq[i]
67 seq[i] = seq[j]
68 seq[i].goto(i,seq[i].ycor())
69 seq[j] = tmp
70 seq[j].goto(j,seq[j].ycor())
71 screen.update()
72 i+=1
73 j-=1
74
75 seq[pivotIndex] = seq[j]
76 seq[pivotIndex].goto(pivotIndex,seq[pivotIndex].ycor())
77 seq[j] = pivot
78 seq[j].goto(j,seq[j].ycor())
79 seq[j].color("green")
80 screen.update()
81
82 theTurtle.color("white")
83 theTurtle.penup()
84 theTurtle.goto(0,pivot.ycor())
85 theTurtle.pendown()
86 theTurtle.goto(len(seq),pivot.ycor())
87 screen.update()
88
89 return j
90
91
92 def quicksortRecursively(seq, start, stop):
93 if start >= stop:
94 return
95
96 if stopping():
97 return
98
99 pivotIndex = partition(seq, start, stop)
100
101 if stopping():
102 return
103
104 quicksortRecursively(seq, start, pivotIndex)
105
106 if stopping():
107 return
108
109 quicksortRecursively(seq, pivotIndex+1, stop)
110
111 def quicksort(seq):
112 quicksortRecursively(seq, 0, len(seq))
113
114 def merge(seq, start, mid, stop):
115 length = stop - start
116 log = math.log(length,2)
117
118 theTurtle.color("blue")
119 theTurtle.penup()
120 theTurtle.goto(start,-3*log)
121 theTurtle.pendown()
122 theTurtle.forward(length)
123 screen.update()
124
125 lst = []
126 i = start
127 j = mid
128
129 # Merge the two lists while each has more elements
130 while i < mid and j < stop:
131 if seq[i] < seq[j]:
132 lst.append(seq[i])
133 seq[i].goto(i,seq[i].ycor())
134 i+=1
135 else:
136 lst.append(seq[j])
137 seq[j].goto(j,seq[j].ycor())
138 j+=1
139 #screen.update()
140
141 # Copy in the rest of the start to mid sequence
142 while i < mid:
143 lst.append(seq[i])
144 seq[i].goto(i,seq[i].ycor())
145 i+=1
146 #screen.update()
147
148 # Copy in the rest of the mid to stop sequence
149 while j < mid:
150 lst.append(seq[j])
151 seq[j].goto(j,seq[j].ycor())
152 j+=1
153 #screen.update()
154
155 # Copy the elements back to the original sequence
156 for i in range(len(lst)):
157 seq[start+i]=lst[i]
158 lst[i].goto(start+i,lst[i].ycor())
159 lst[i].color("green")
160 screen.update()
161
162 def mergeSortRecursively(seq, start, stop):
163 # We must use >= here only when the sequence we are sorting
164 # is empty. Otherwise start == stop-1 in the base case.
165 if start >= stop-1:
166 return
167
168 mid = (start + stop) // 2
169
170 if stopping():
171 return
172
173 length = stop-start
174 log = math.log(length,2)
175
176 theTurtle.color("red")
177 theTurtle.penup()
178 theTurtle.goto(start,-3*log)
179 theTurtle.pendown()
180 theTurtle.forward(length)
181 screen.update()
182
183 # Why twice? Because once doesn't seem to display
184 # the line the first time through for some reason
185 theTurtle.color("red")
186 theTurtle.penup()
187 theTurtle.goto(start,-3*log)
188 theTurtle.pendown()
189 theTurtle.forward(length)
190 screen.update()
191
192 mergeSortRecursively(seq, start, mid)
193
194 if stopping():
195 return
196
197 mergeSortRecursively(seq, mid, stop)
198
199 if stopping():
200 return
201
202 theTurtle.color("blue")
203 theTurtle.penup()
204 theTurtle.goto(start,-3*log)
205 theTurtle.pendown()
206 theTurtle.forward(length)
207 screen.update()
208
209 merge(seq, start, mid, stop)
210
211 screen.update()
212 theTurtle.color("white")
213 theTurtle.goto(start-1,-3*log)
214 theTurtle.pendown()
215 theTurtle.forward(length+2)
216 screen.update()
217
218 def mergeSort(seq):
219 mergeSortRecursively(seq, 0, len(seq))
220
221 def select(seq, start):
222 minIndex = start
223 seq[minIndex].color("green")
224
225 for i in range(start+1, len(seq)):
226 if seq[minIndex] > seq[i]:
227 seq[minIndex].color("black")
228 minIndex = i
229 seq[minIndex].color("green")
230
231 return minIndex
232
233 def selectionSort(seq):
234 for i in range(len(seq)-1):
235 minIndex = select(seq, i)
236 if stopping():
237 return
238 tmp = seq[i]
239 seq[i] = seq[minIndex]
240 seq[minIndex] = tmp
241 seq[i].goto(i,seq[i].ycor())
242 seq[minIndex].goto(minIndex,seq[minIndex].ycor())
243 seq[i].color("green")
244
245 def pause():
246 while self.paused:
247 time.sleep(1)
248 screen.update()
249 screen.listen()
250
251 def stopping():
252 if self.paused:
253 pause()
254
255 if self.stop:
256 self.pause = False
257 self.running = False
258 screen.update()
259 screen.listen()
260 return True
261
262 return False
263
264 self.master.title("Sort Animations")
265
266 bar = tkinter.Menu(self.master)
267 fileMenu = tkinter.Menu(bar,tearoff=0)
268
269 def clear():
270 screen.clear()
271 screen.update()
272 screen.listen()
273
274 def newWindow():
275 clear()
276 if self.running:
277 self.stop = True
278
279 fileMenu.add_command(label="Clear",command=newWindow)
280 fileMenu.add_command(label="Exit",command=self.master.quit)
281 bar.add_cascade(label="File",menu=fileMenu)
282 self.master.config(menu=bar)
283
284 canvas = tkinter.Canvas(self,width=600,height=600)
285 canvas.pack(side=tkinter.LEFT)
286
287 theTurtle = turtle.RawTurtle(canvas)
288 theTurtle.ht()
289 theTurtle.speed(0)
290 screen = theTurtle.getscreen()
291 screen.tracer(0)
292
293 sideBar = tkinter.Frame(self,padx=5,pady=5)
294 sideBar.pack(side=tkinter.RIGHT, fill=tkinter.BOTH)
295
296 speedLabel = tkinter.Label(sideBar,text="Animation Speed")
297 speedLabel.pack()
298 speed = tkinter.StringVar()
299 speedEntry = tkinter.Entry(sideBar,textvariable=speed)
300 speedEntry.pack()
301 speed.set("10")
302
303 def selSortHandler():
304 self.running = True
305 clear()
306 screen.setworldcoordinates(0,0,200,200)
307 screen.tracer(0)
308 self.master.title("Selection Sort Animation")
309 seq = []
310 for i in range(200):
311 if stopping():
312 return
313
314 p = Point(screen,i,i)
315 p.color("green")
316 seq.append(p)
317
318 screen.update()
319 screen.tracer(1)
320
321 for i in range(200):
322 if stopping():
323 return
324
325 j = random.randint(0,199)
326
327 p = seq[i]
328 seq[i] = seq[j]
329 seq[j] = p
330 seq[i].goto(i,seq[i].ycor())
331 seq[j].goto(j,seq[j].ycor())
332 seq[i].color("black")
333 seq[j].color("black")
334
335 selectionSort(seq)
336 self.running = False
337 self.stop = False
338
339 button = tkinter.Button(sideBar, text = "Selection Sort", command=selSortHandler)
340 button.pack(fill=tkinter.BOTH)
341
342 def mergeSortHandler():
343 self.running = True
344 clear()
345 screen.setworldcoordinates(0,-25,200,200)
346 theTurtle.width(5)
347 screen.tracer(0)
348 self.master.title("Merge Sort Animation")
349 seq = []
350 for i in range(200):
351 if stopping():
352 return
353
354 p = Point(screen,i,i)
355 p.color("green")
356 seq.append(p)
357
358 screen.update()
359 screen.tracer(1)
360 for i in range(200):
361 if stopping():
362 return
363
364 j = random.randint(0,199)
365
366 p = seq[i]
367 seq[i] = seq[j]
368 seq[j] = p
369 seq[i].goto(i,seq[i].ycor())
370 seq[j].goto(j,seq[j].ycor())
371 seq[i].color("black")
372 seq[j].color("black")
373
374 screen.tracer(0)
375 mergeSort(seq)
376 self.running = False
377 self.stop = False
378
379 button = tkinter.Button(sideBar, text = "Merge Sort", command=mergeSortHandler)
380 button.pack(fill=tkinter.BOTH)
381
382 def quickSortHandler():
383 self.running = True
384 clear()
385 screen.setworldcoordinates(0,0,200,200)
386 theTurtle.width(5)
387 screen.tracer(0)
388 self.master.title("Quicksort Animation")
389 seq = []
390 for i in range(200):
391 if stopping():
392 return
393
394 p = Point(screen,i,i)
395 p.color("green")
396 seq.append(p)
397
398 screen.update()
399 screen.tracer(1)
400 for i in range(200):
401 if stopping():
402 return
403
404 j = random.randint(0,199)
405
406 p = seq[i]
407 seq[i] = seq[j]
408 seq[j] = p
409 seq[i].goto(i,seq[i].ycor())
410 seq[j].goto(j,seq[j].ycor())
411 seq[i].color("black")
412 seq[j].color("black")
413
414 screen.tracer(1)
415 quicksort(seq)
416 self.running = False
417 self.stop = False
418
419
420 button = tkinter.Button(sideBar, text = "Quicksort", command=quickSortHandler)
421 button.pack(fill=tkinter.BOTH)
422
423 def pauseHandler():
424 self.paused = not self.paused
425
426 button = tkinter.Button(sideBar, text = "Pause", command=pauseHandler)
427 button.pack(fill=tkinter.BOTH)
428
429 def stopHandler():
430 if not self.paused and self.running:
431 self.stop = True
432
433 button = tkinter.Button(sideBar, text = "Stop", command=stopHandler)
434 button.pack(fill=tkinter.BOTH)
435
436 screen.listen()
437
438# The main function in our GUI program is very simple. It creates the
439# root window. Then it creates the SortAnimation frame which creates
440# all the widgets and has the logic for the event handlers. Calling mainloop
441# on the frames makes it start listening for events. The mainloop function will
442# return when the application is exited.
443def main():
444 root = tkinter.Tk()
445 anim = SortAnimation(root)
446
447 anim.mainloop()
448
449if __name__ == "__main__":
450 main()
4.3. Tic Tac Toe¶
You can download the starter code for Tic Tac Toe by clicking here.
1from turtle import *
2import tkinter.messagebox
3import tkinter
4import random
5import math
6import datetime
7import time
8import sys
9
10screenMin = 0
11screenMax = 300
12Human = -1
13Computer = 1
14
15class Board:
16 # When a board is constructed, you may want to make a copy of the board.
17 # This can be a shallow copy of the board because Turtle objects are
18 # Immutable from the perspective of a board object.
19 def __init__(self, board=None, screen=None):
20 self.screen = screen
21 if screen == None:
22 if board!=None:
23 self.screen = board.screen
24
25 self.items = []
26 for i in range(3):
27 rowlst = []
28 for j in range(3):
29 if board==None:
30 rowlst.append(Dummy())
31 else:
32 rowlst.append(board[i][j])
33
34 self.items.append(rowlst)
35
36 # Accessor method for the screen
37 def getscreen(self):
38 return self.screen
39
40 # The getitem method is used to index into the board. It should
41 # return a row of the board. That row itself is indexable (it is just
42 # a list) so accessing a row and column in the board can be written
43 # board[row][column] because of this method.
44 def __getitem__(self,index):
45 return self.items[index]
46
47 # This method should return true if the two boards, self and other,
48 # represent exactly the same state.
49 # READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
50 def __eq__(self,other):
51 pass
52
53 # This method will mutate this board to contain all dummy
54 # turtles. This way the board can be reset when a new game
55 # is selected. It should NOT be used except when starting
56 # a new game.
57 def reset(self):
58
59 self.screen.tracer(1)
60 for i in range(3):
61 for j in range(3):
62 self.items[i][j].goto(-100,-100)
63 self.items[i][j] = Dummy()
64
65 self.screen.tracer(0)
66
67 # This method should return an integer representing the
68 # state of the board. If the computer has won, return 1.
69 # If the human has won, return -1. Otherwise, return 0.
70 # READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
71 def eval(self):
72 pass
73
74 # This method should return True if the board
75 # is completely filled up (no dummy turtles).
76 # Otherwise, it should return False.
77 # READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
78 def full(self):
79 pass
80
81 # This method should draw the X's and O's
82 # Of this board on the screen.
83 def drawXOs(self):
84
85 for row in range(3):
86 for col in range(3):
87 if self[row][col].eval() != 0:
88 self[row][col].st()
89 self[row][col].goto(col*100+50,row*100+50)
90
91 self.screen.update()
92
93# This class is just for placeholder objects when no move has been made
94# yet at a position in the board. Having eval() return 0 is convenient when no
95# move has been made.
96class Dummy:
97 def __init__(self):
98 pass
99
100 def eval(self):
101 return 0
102
103 def goto(self,x,y):
104 pass
105
106# In the X and O classes below the constructor begins by initializing the
107# RawTurtle part of the object with the call to super().__init__(canvas). The
108# super() call returns the class of the superclass (the class above the X or O
109# in the class hierarchy). In this case, the superclass is RawTurtle. Then,
110# calling __init__ on the superclass initializes the part of the object that is
111# a RawTurtle.
112class X(RawTurtle):
113 def __init__(self, canvas):
114 super().__init__(canvas)
115 self.ht()
116 self.getscreen().register_shape("X",((-40,-36),(-40,-44),(0,-4),(40,-44),(40,-36), \
117 (4,0),(40,36),(40,44),(0,4),(-40,44),(-40,36),(-4,0),(-40,-36)))
118 self.shape("X")
119 self.penup()
120 self.speed(5)
121 self.goto(-100,-100)
122
123 def eval(self):
124 return Computer
125
126class O(RawTurtle):
127 def __init__(self, canvas):
128 super().__init__(canvas)
129 self.ht()
130 self.shape("circle")
131 self.penup()
132 self.speed(5)
133 self.goto(-100,-100)
134
135 def eval(self):
136 return Human
137
138# The minimax function is given a player (1 = Computer, -1 = Human) and a
139# board object. When the player = Computer, minimax returns the maximum
140# value of all possible moves that the Computer could make. When the player =
141# Human then minimax returns the minimum value of all possible moves the Human
142# could make. Minimax works by assuming that at each move the Computer will pick
143# its best move and the Human will pick its best move. It does this by making a
144# move for the player whose turn it is, and then recursively calling minimax.
145# The base case results when, given the state of the board, someone has won or
146# the board is full.
147# READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
148def minimax(player,board):
149 pass
150
151
152
153class TicTacToe(tkinter.Frame):
154 def __init__(self, master=None):
155 super().__init__(master)
156 self.pack()
157 self.buildWindow()
158 self.paused = False
159 self.stop = False
160 self.running = False
161 self.turn = Human
162 self.locked = False
163
164 def buildWindow(self):
165
166 cv = ScrolledCanvas(self,600,600,600,600)
167 cv.pack(side = tkinter.LEFT)
168 t = RawTurtle(cv)
169 screen = t.getscreen()
170 screen.tracer(100000)
171
172 screen.setworldcoordinates(screenMin,screenMin,screenMax,screenMax)
173 screen.bgcolor("white")
174 t.ht()
175
176 frame = tkinter.Frame(self)
177 frame.pack(side = tkinter.RIGHT,fill=tkinter.BOTH)
178 board = Board(None, screen)
179
180 def drawGrid():
181 screen.clear()
182 screen.tracer(1000000)
183 screen.setworldcoordinates(screenMin,screenMin,screenMax,screenMax)
184 screen.bgcolor("white")
185 screen.tracer(0)
186 t = RawTurtle(cv)
187 t.ht()
188 t.pu()
189 t.width(10)
190 t.color("green")
191 for i in range(2):
192 t.penup()
193 t.goto(i*100+100,10)
194 t.pendown()
195 t.goto(i*100+100,290)
196 t.penup()
197 t.goto(10,i*100+100)
198 t.pendown()
199 t.goto(290,i*100+100)
200
201 screen.update()
202
203
204 def newGame():
205 #drawGrid()
206 self.turn = Human
207 board.reset()
208 self.locked =False
209 screen.update()
210
211
212 def startHandler():
213 newGame()
214
215 drawGrid()
216
217 startButton = tkinter.Button(frame, text = "New Game", command=startHandler)
218 startButton.pack()
219
220 def quitHandler():
221 self.master.quit()
222
223 quitButton = tkinter.Button(frame, text = "Quit", command=quitHandler)
224 quitButton.pack()
225
226 def computerTurn():
227 # The locked variable prevents another event from being
228 # processed while the computer is making up its mind.
229 self.locked = True
230
231 # Call Minimax to find the best move to make.
232 # READER EXERCISE: YOU MUST COMPLETE THIS CODE
233 # After writing this code, the maxMove tuple should
234 # contain the best move for the computer. For instance,
235 # if the best move is in the first row and third column
236 # then maxMove would be (0,2).
237
238 row, col = maxMove
239 board[row][col] = X(cv)
240 self.locked = False
241
242
243 def mouseClick(x,y):
244 if not self.locked:
245 row = int(y // 100)
246 col = int(x // 100)
247
248 if board[row][col].eval() == 0:
249 board[row][col] = O(cv)
250
251 self.turn = Computer
252
253 board.drawXOs()
254
255 if not board.full() and not abs(board.eval())==1:
256 computerTurn()
257
258 self.turn = Human
259
260 board.drawXOs()
261 else:
262 self.locked = True
263
264 if board.eval() == 1:
265 tkinter.messagebox.showwarning("Game Over","X wins!!!")
266
267 if board.eval() == -1:
268 tkinter.messagebox.showwarning("Game Over","O wins. How did that happen?")
269
270 if board.full():
271 tkinter.messagebox.showwarning("Game Over","It was a tie.")
272
273 screen.onclick(mouseClick)
274
275 screen.listen()
276
277def main():
278 root = tkinter.Tk()
279 root.title("Tic Tac Toe")
280 application = TicTacToe(root)
281 application.mainloop()
282
283if __name__ == "__main__":
284 main()
4.4. The Linked List Datatype¶
You can download the code for the linked list datatype by clicking here.
1class LinkedList:
2
3 # The __Node class is used internally by the LinkedList class. It is
4 # invisible from outside this class due to the two underscores
5 # that precede the class name. Python mangles names so that they
6 # are not recognizable outside the class when two underscores
7 # precede a name but aren't followed by two underscores at the
8 # end of the name (i.e. an operator name).
9 class __Node:
10 def __init__(self,item,next=None):
11 self.item = item
12 self.next = next
13
14 def getItem(self):
15 return self.item
16
17 def getNext(self):
18 return self.next
19
20 def setItem(self, item):
21 self.item = item
22
23 def setNext(self,next):
24 self.next = next
25
26 def __init__(self,contents=[]):
27 # Here we keep a reference to the first node in the linked list
28 # and the last item in the linked list. The both point to a
29 # dummy node to begin with. This dummy node will always be in
30 # the first position in the list and will never contain an item.
31 # Its purpose is to eliminate special cases in the code below.
32 self.first = LinkedList.__Node(None,None)
33 self.last = self.first
34 self.numItems = 0
35
36 for e in contents:
37 self.append(e)
38
39 def __getitem__(self,index):
40 if index >= 0 and index < self.numItems:
41 cursor = self.first.getNext()
42 for i in range(index):
43 cursor = cursor.getNext()
44
45 return cursor.getItem()
46
47 raise IndexError("LinkedList index out of range")
48
49 def __setitem__(self,index,val):
50 if index >= 0 and index < self.numItems:
51 cursor = self.first.getNext()
52 for i in range(index):
53 cursor = cursor.getNext()
54
55 cursor.setItem(val)
56 return
57
58 raise IndexError("LinkedList assignment index out of range")
59
60 def insert(self,index,item):
61 cursor = self.first
62
63 if index < self.numItems:
64 for i in range(index):
65 cursor = cursor.getNext()
66
67 node = LinkedList.__Node(item, cursor.getNext())
68 cursor.setNext(node)
69 self.numItems += 1
70 else:
71 self.append(item)
72
73
74 def __add__(self,other):
75 if type(self) != type(other):
76 raise TypeError("Concatenate undefined for " + \
77 str(type(self)) + " + " + str(type(other)))
78
79 result = LinkedList()
80
81 cursor = self.first.getNext()
82
83 while cursor != None:
84 result.append(cursor.getItem())
85 cursor = cursor.getNext()
86
87 cursor = other.first.getNext()
88
89 while cursor != None:
90 result.append(cursor.getItem())
91 cursor = cursor.getNext()
92
93 return result
94
95
96 def __contains__(self,item):
97 # This is left as an exercise for the reader.
98 pass
99
100 def __delitem__(self,index):
101 # This is left as an exercise for the reader.
102 pass
103
104 def __eq__(self,other):
105 if type(other) != type(self):
106 return False
107
108 if self.numItems != other.numItems:
109 return False
110
111 cursor1 = self.first.getNext()
112 cursor2 = other.first.getNext()
113 while cursor1 != None:
114 if cursor1.getItem() != cursor2.getItem():
115 return False
116 cursor1 = cursor1.getNext()
117 cursor2 = cursor2.getNext()
118
119 return True
120
121 def __iter__(self):
122 # This is left as an exercise for the reader.
123 pass
124
125 def __len__(self):
126 # This is left as an exercise for the reader.
127 pass
128
129 def append(self,item):
130 node = LinkedList.__Node(item)
131 self.last.setNext(node)
132 self.last = node
133 self.numItems += 1
134
135
136 def __str__(self):
137 # This is left as an exercise for the reader.
138 pass
139
140 def __repr__(self):
141 # This is left as an exercise for the reader.
142 pass
143
144def main():
145 lst = LinkedList()
146
147 for i in range(100):
148 lst.append(i)
149
150 lst2 = LinkedList(lst)
151
152 print(lst)
153 print(lst2)
154
155 if lst == lst2:
156 print("Test 1 Passed")
157 else:
158 print("Test 1 Failed")
159
160 lst3 = lst + lst2
161
162 if len(lst3) == len(lst) + len(lst2):
163 print("Test 2 Passed")
164 else:
165 print("Test 2 Failed")
166
167
168 if 1 in lst3:
169 print("Test 3 Passed")
170 else:
171 print("Test 3 Failed")
172
173 if 2 in lst3:
174 print("Test 4 Passed")
175 else:
176 print("Test 4 Failed")
177
178 del lst[1]
179
180 if 1 in lst:
181 print("Test 5 Failed")
182 else:
183 print("Test 5 Passed")
184
185 if len(lst) == 99:
186 print("Test 6 Passed")
187 else:
188 print("Test 6 Failed")
189
190 if lst == lst2:
191 print("Test 7 Failed")
192 else:
193 print("Test 7 Passed")
194
195 del lst2[2]
196
197 if lst == lst2:
198 print("Test 8 Failed")
199 else:
200 print("Test 8 Passed")
201
202
203 lst4 = LinkedList(lst)
204 lst.insert(0,100)
205 lst4 = LinkedList([100]) + lst4
206
207 if lst == lst4:
208 print("Test 9 Passed")
209 else:
210 print("Test 9 Failed")
211
212 lst.insert(1000,333)
213 lst4.append(333)
214
215 if lst == lst4:
216 print("Test 10 Passed")
217 else:
218 print("Test 10 Failed")
219
220 print(lst)
221 print(lst4)
222
223if __name__ == "__main__":
224 main()
225
226
227
228
229
4.5. The Stack Datatype¶
You can download the code for the stack datatype by clicking here.
1class Stack:
2 def __init__(self):
3 self.items = []
4
5 def pop(self):
6 if self.isEmpty():
7 raise RuntimeError("Attempt to pop an empty stack")
8
9 topIdx = len(self.items)-1
10 item = self.items[topIdx]
11 del self.items[topIdx]
12 return item
13
14 def push(self,item):
15 self.items.append(item)
16
17 def top(self):
18 if self.isEmpty():
19 raise RuntimeError("Attempt to get top of empty stack")
20
21 topIdx = len(self.items)-1
22 return self.items[topIdx]
23
24 def isEmpty(self):
25 return len(self.items) == 0
26
27 def clear(self):
28 self.items = []
29
30def main():
31 s = Stack()
32 items = list(range(10))
33 items2 = []
34
35 for k in items:
36 s.push(k)
37
38 if s.top() == 9:
39 print("Test 1 Passed")
40 else:
41 print("Test 1 Failed")
42
43 while not s.isEmpty():
44 items2.append(s.pop())
45
46 items2.reverse()
47
48 if items2 != items:
49 print("Test 2 Failed")
50 else:
51 print("Test 2 Passed")
52
53 try:
54 s.pop()
55 print("Test 3 Failed")
56
57 except RuntimeError:
58 print("Test 3 Passed")
59 except:
60 print("Test 3 Failed")
61
62 try:
63 s.top()
64 print("Test 4 Failed")
65
66 except RuntimeError:
67 print("Test 4 Passed")
68 except:
69 print("Test 4 Failed")
70
71if __name__=="__main__":
72 main()
4.6. The Queue Datatype¶
You can download the code for the queue datatype by clicking here.
1class Queue:
2 def __init__(self):
3 self.items = []
4 self.frontIdx = 0
5
6 def __compress(self):
7 newitems = []
8 for i in range(self.frontIdx,len(self.items)):
9 newitems.append(self.items[i])
10
11 self.items = newitems
12 self.frontIdx = 0
13
14 def dequeue(self):
15 if self.isEmpty():
16 raise RuntimeError("Attempt to dequeue an empty queue")
17
18 # When queue is half full, compress it. This
19 # achieves an amortized complexity of O(1) while
20 # not letting the list continue to grow unchecked.
21 if self.frontIdx * 2 > len(self.items):
22 self.__compress()
23
24 item = self.items[self.frontIdx]
25 self.frontIdx += 1
26 return item
27
28 def enqueue(self,item):
29 self.items.append(item)
30
31 def front(self):
32 if self.isEmpty():
33 raise RuntimeError("Attempt to access front of empty queue")
34
35 return self.items[self.frontIdx]
36
37
38 def isEmpty(self):
39 return self.frontIdx == len(self.items)
40
41 def clear(self):
42 self.items = []
43 self.frontIdx = 0
44
45def main():
46 q = Queue()
47 items = list(range(10))
48 items2 = []
49
50 for k in items:
51 q.enqueue(k)
52
53 if q.front() == 0:
54 print("Test 1 Passed")
55 else:
56 print("Test 1 Failed")
57
58 while not q.isEmpty():
59 items2.append(q.dequeue())
60
61 if items2 != items:
62 print("Test 2 Failed")
63 else:
64 print("Test 2 Passed")
65
66 for k in items:
67 q.enqueue(k)
68
69 items2 = []
70
71 while not q.isEmpty():
72 items2.append(q.dequeue())
73
74 if items2 != items:
75 print("Test 3 Failed")
76 else:
77 print("Test 3 Passed")
78
79 try:
80 q.dequeue()
81 print("Test 4 Failed")
82
83 except RuntimeError:
84 print("Test 4 Passed")
85 except:
86 print("Test 4 Failed")
87
88 try:
89 q.front()
90 print("Test 5 Failed")
91
92 except RuntimeError:
93 print("Test 5 Passed")
94 except:
95 print("Test 5 Failed")
96
97if __name__=="__main__":
98 main()
4.7. Figures from Text¶
Operation |
Complexity |
Usage |
Method |
|---|---|---|---|
List creation |
O(n) or O(1) |
x = list(y) |
calls __init__(y) |
indexed get |
O(1) |
a = x[i] |
x.__getitem__(i) |
indexed set |
O(1) |
x[i] = a |
x.__setitem__(i,a) |
concatenate |
O(n) |
z = x + y |
z = x.__add__(y) |
append |
O(1) |
x.append(a) |
x.append(a) |
insert |
O(n) |
x.insert(i,e) |
x.insert(i,e)) |
delete |
O(n) |
del x[i] |
x.__delitem__(i) |
equality |
O(n) |
x == y |
x.__eq__(y) |
iterate |
O(n) |
for a in x: |
x.__iter__() |
length |
O(1) |
len(x) |
x.__len__() |
membership |
O(n) |
a in x |
x.__contains__(a) |
sort |
O(n log n) |
x.sort() |
x.sort() |
Fig. 1: Complexity of List Operations¶
Fig. 2: A Sample PyList Object¶
Fig. 3: Selection Sort Snapshot¶
Fig. 4: Selection Sort of a List¶
Fig. 5: Merge Sort Snapshot¶
Fig. 6: Merge Sort Merges¶
Fig. 7: Quicksort Snapshot¶
Fig. 8: Quicksorting a List¶
Fig. 9: A 2-Dimensional Matrix¶
Fig. 10: A Sample LinkedList Object¶
Operation |
Complexity |
Usage |
Method |
|---|---|---|---|
List creation |
O(n) or O(1) |
x = LinkedList(y) |
calls __init__(y) |
indexed get |
O(n) |
a = x[i] |
x.__getitem__(i) |
indexed set |
O(n) |
x[i] = a |
x.__setitem__(i,a) |
concatenate |
O(n) |
z = x + y |
z = x.__add__(y) |
append |
O(1) |
x.append(a) |
x.append(a) |
insert |
O(n) |
x.insert(i,e) |
x.insert(i,e)) |
delete |
O(n) |
del x[i] |
x.__delitem__(i) |
equality |
O(n) |
x == y |
x.__eq__(y) |
iterate |
O(n) |
for a in x: |
x.__iter__() |
length |
O(1) |
len(x) |
x.__len__() |
membership |
O(n) |
a in x |
x.__contains__(a) |
sort |
N/A |
N/A |
N/A |
Fig. 11: Complexity of LinkedList Operations¶
Fig. 12: Deleting a Node from a Linked List¶
Operation |
Complexity |
Usage |
Description |
|---|---|---|---|
Stack Creation |
O(1) |
s=Stack() |
calls the constructor |
pop |
O(1) |
a=s.pop() |
returns the last item pushed and removes it from s |
push |
O(1) |
s.push(a) |
pushes the item, a, on the stack, s |
top |
O(1) |
a=s.top() |
returns the top item without popping s |
isEmpty |
O(1) |
s.isEmpty() |
returns True if s has no pushed items |
Fig. 13: Complexity of Stack Operations¶
Operation |
Complexity |
Usage |
Description |
|---|---|---|---|
Queue Creation |
O(1) |
q=Queue() |
calls the constructor |
dequeue |
O(1) |
a=q.dequeue() |
returns the first item enqueued and removes it from q |
enqueue |
O(1) |
q.enqueue(a) |
enqueues the item, a, on the queue, q |
front |
O(1) |
a=q.front() |
returns the front item without dequeueing the item |
isEmpty |
O(1) |
q.isEmpty() |
returns True if q has not enqueued items |
Fig. 14: Complexity of Queue Operations¶
Fig. 15: Infix Evaluation Step 1¶
Fig. 16: Infix Evaluation Step 2¶
Fig. 17: Infix Evaluation Step 3¶
Fig. 18: Radix Sort Step 1¶
Fig. 19: Radix Sort Step 2¶
Fig. 20: Radix Sort Step 3¶
Fig. 21: Radix Sort Step 4 - 3rd letter¶
Fig. 22: Radix Sort Step 5¶
Fig. 23: Radix Sort Step 6 - 2nd letter¶
Fig. 24: Radix Sort Step 7¶
Fig. 25: Radix Sort Step 8 - 1st letter¶
Fig. 26: Radix Sort Step 9¶