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.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
class PyList:
    def __init__(self,contents=[], size=10):
        # The contents allows the programmer to construct a list with
        # the initial contents of this value. The initial_size
        # lets the programmer pick a size for the internal size of the 
        # list. This is useful if the programmer knows he/she is going 
        # to add a specific number of items right away to the list.
        self.items = [None] * size
        self.numItems = 0
        self.size = size
        
        for e in contents:
            self.append(e)
          
    def __getitem__(self,index):
        if index < self.numItems:
            return self.items[index]
        
        raise IndexError("PyList index out of range")
    
    def __setitem__(self,index,val):
        if index < self.numItems:
            self.items[index] = val
            return
        
        raise IndexError("PyList assignment index out of range")
    
    def insert(self,i,e):
        if self.numItems == self.size:
            self.__makeroom()
           
        if i < self.numItems: 
            for j in range(self.numItems-1,i-1,-1):
                self.items[j+1] = self.items[j]
                
            self.items[i] = e  
            self.numItems += 1
        else:
            self.append(e)
            
            
    def __add__(self,other):
        result = PyList()
        
        for i in range(self.numItems):
            result.append(self.items[i])
            
        for i in range(other.numItems):
            result.append(other.items[i])
            
        return result
    
    
    def __contains__(self,item):
        for i in range(self.numItems):
            if self.items[i] == item:
                return True
            
        return False
    
    def __delitem__(self,index):
        for i in range(index, self.numItems-1):
            self.items[i] = self.items[i+1]
        self.numItems -= 1 # same as writing self.numItems = self.numItems - 1
            
    def __eq__(self,other):
        if type(other) != type(self):
            return False
        
        if self.numItems != other.numItems:
            return False
        
        for i in range(self.numItems):
            if self.items[i] != other.items[i]:
                return False
            
        return True
    
    def __iter__(self):
        for i in range(self.numItems):
            yield self.items[i]  
            
    def __len__(self):
        return self.numItems
    
    # This method is hidden since it starts with two underscores. 
    # It is only available to the class to use. 
    def __makeroom(self):
        # increase list size by 1/4 to make more room.
        newlen = (self.size // 4) + self.size + 1
        newlst = [None] * newlen
        for i in range(self.numItems):
            newlst[i] = self.items[i]
            
        self.items = newlst
        self.size = newlen        

    def append(self,item):
        if self.numItems == self.size:
            self.__makeroom()
            
        self.items[self.numItems] = item
        self.numItems += 1 # Same as writing self.numItems = self.numItems + 1
        
    def __str__(self):
        s = "["
        for i in range(self.numItems):
            s = s + str(self.items[i])
            if i < self.numItems - 1:
                s = s + ", "
        s = s + "]"
        return s
    
    def __repr__(self):
        s = "PyList(["
        for i in range(self.numItems):
            s = s + str(self.items[i])
            if i < self.numItems - 1:
                s = s + ", "
        s = s + "])"
        return s        
            
    def sort(self):
        pass
        
                
def main():
    lst = PyList()
    
    for i in range(100):
        lst.append(i)
    
    lst2 = PyList(lst)
    
    print(lst)
    print(lst2)
    
    if lst == lst2:
        print("Test 1 Passed")
    else:
        print("Test 1 Failed")
    
    lst3 = lst + lst2
    
    if len(lst3) == len(lst) + len(lst2):
        print("Test 2 Passed")
    else:
        print("Test 2 Failed")
        
    
    if 1 in lst3:
        print("Test 3 Passed")
    else:
        print("Test 3 Failed")        
    
    if 2 in lst3:
        print("Test 4 Passed")
    else:
        print("Test 4 Failed")        
    
    del lst[1]
    
    if 1 in lst:
        print("Test 5 Failed")
    else:
        print("Test 5 Passed")        
    
    if len(lst) == 99:
        print("Test 6 Passed")
    else:
        print("Test 6 Failed")        
        
    if lst == lst2:
        print("Test 7 Failed")
    else:
        print("Test 7 Passed")        
    
    del lst2[2]
    
    if lst == lst2:
        print("Test 8 Failed")
    else:
        print("Test 8 Passed")  
        
    
    lst4 = PyList(lst)
    lst.insert(0,100)
    lst4 = PyList([100]) + lst4
    
    if lst == lst4:
        print("Test 9 Passed")
    else:
        print("Test 9 Failed")
        
    lst.insert(1000,333)
    lst4.append(333)

    if lst == lst4:
        print("Test 10 Passed")
    else:
        print("Test 10 Failed")  
        
    print(lst)
    print(lst4)
    
if __name__ == "__main__":
    main()
                
            
            
        
            

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.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
import tkinter
import turtle
import random
import time
import math

class Point(turtle.RawTurtle):
    def __init__(self, canvas, x, y):
        super().__init__(canvas)
        canvas.register_shape("dot",((3,0),(2,2),(0,3),(-2,2),(-3,0),(-2,-2),(0,-3),(2,-2)))
        self.shape("dot")
        self.speed(0)
        self.penup()
        self.goto(x,y)

    def __str__(self):
        return "("+str(self.xcor())+","+str(self.ycor())+")"

    def __lt__(self, other):
        return self.ycor() < other.ycor()     

# This class defines the animation application. The following line says that
# the SortAnimation class inherits from the Frame class. 
class SortAnimation(tkinter.Frame):
    def __init__(self, master=None):
        super().__init__(master)
        self.pack()
        self.buildWindow()    
        self.paused = False
        self.stop = False
        self.running = False


    def buildWindow(self):

        def partition(seq, start, stop):
            pivotIndex = start
            pivot = seq[pivotIndex]

            theTurtle.color("red")
            theTurtle.penup()
            theTurtle.goto(start,pivot.ycor())
            theTurtle.pendown()
            theTurtle.goto(stop,pivot.ycor())
            screen.update()

            # Why twice? Because once doesn't seem to display
            # the line the first time through for some reason            
            theTurtle.color("red")
            theTurtle.penup()
            theTurtle.goto(start,pivot.ycor())
            theTurtle.pendown()
            theTurtle.goto(stop,pivot.ycor())
            screen.update()

            i = start+1
            j = stop-1

            while i <= j:
                while i <= j and not pivot < seq[i]:
                    i+=1
                while i <= j and pivot < seq[j]:
                    j-=1

                if i < j:
                    tmp = seq[i]
                    seq[i] = seq[j]
                    seq[i].goto(i,seq[i].ycor())
                    seq[j] = tmp
                    seq[j].goto(j,seq[j].ycor())
                    screen.update()
                    i+=1
                    j-=1

            seq[pivotIndex] = seq[j]
            seq[pivotIndex].goto(pivotIndex,seq[pivotIndex].ycor())
            seq[j] = pivot
            seq[j].goto(j,seq[j].ycor())
            seq[j].color("green")
            screen.update()

            theTurtle.color("white")
            theTurtle.penup()
            theTurtle.goto(0,pivot.ycor())
            theTurtle.pendown()
            theTurtle.goto(len(seq),pivot.ycor())
            screen.update()   

            return j


        def quicksortRecursively(seq, start, stop):
            if start >= stop:
                return 

            if stopping():
                return

            pivotIndex = partition(seq, start, stop)

            if stopping():
                return

            quicksortRecursively(seq, start, pivotIndex)

            if stopping():
                return

            quicksortRecursively(seq, pivotIndex+1, stop)

        def quicksort(seq):
            quicksortRecursively(seq, 0, len(seq))   

        def merge(seq, start, mid, stop):
            length = stop - start
            log = math.log(length,2)

            theTurtle.color("blue")
            theTurtle.penup()
            theTurtle.goto(start,-3*log)
            theTurtle.pendown()
            theTurtle.forward(length)
            screen.update()

            lst = []
            i = start
            j = mid

            # Merge the two lists while each has more elements
            while i < mid and j < stop:
                if seq[i] < seq[j]:
                    lst.append(seq[i])
                    seq[i].goto(i,seq[i].ycor())
                    i+=1
                else:
                    lst.append(seq[j])
                    seq[j].goto(j,seq[j].ycor())
                    j+=1
                #screen.update()

            # Copy in the rest of the start to mid sequence    
            while i < mid:
                lst.append(seq[i])
                seq[i].goto(i,seq[i].ycor())
                i+=1
                #screen.update()

            # Copy in the rest of the mid to stop sequence
            while j < mid:
                lst.append(seq[j])
                seq[j].goto(j,seq[j].ycor())
                j+=1
                #screen.update()

            # Copy the elements back to the original sequence   
            for i in range(len(lst)):
                seq[start+i]=lst[i]
                lst[i].goto(start+i,lst[i].ycor())
                lst[i].color("green")
                screen.update()

        def mergeSortRecursively(seq, start, stop):
            # We must use >= here only when the sequence we are sorting
            # is empty. Otherwise start == stop-1 in the base case.
            if start >= stop-1:
                return 

            mid = (start + stop) // 2

            if stopping():
                return

            length = stop-start
            log = math.log(length,2)

            theTurtle.color("red")
            theTurtle.penup()
            theTurtle.goto(start,-3*log)
            theTurtle.pendown()
            theTurtle.forward(length)
            screen.update()

            # Why twice? Because once doesn't seem to display
            # the line the first time through for some reason
            theTurtle.color("red")
            theTurtle.penup()
            theTurtle.goto(start,-3*log)
            theTurtle.pendown()
            theTurtle.forward(length)
            screen.update()  

            mergeSortRecursively(seq, start, mid)

            if stopping():
                return            

            mergeSortRecursively(seq, mid, stop)

            if stopping():
                return

            theTurtle.color("blue")
            theTurtle.penup()
            theTurtle.goto(start,-3*log)
            theTurtle.pendown()
            theTurtle.forward(length)
            screen.update()

            merge(seq, start, mid, stop)

            screen.update()
            theTurtle.color("white")
            theTurtle.goto(start-1,-3*log)
            theTurtle.pendown()
            theTurtle.forward(length+2)
            screen.update()           

        def mergeSort(seq):
            mergeSortRecursively(seq, 0, len(seq))                     

        def select(seq, start):
            minIndex = start
            seq[minIndex].color("green")

            for i in range(start+1, len(seq)):
                if seq[minIndex] > seq[i]:
                    seq[minIndex].color("black")
                    minIndex = i
                    seq[minIndex].color("green")

            return minIndex

        def selectionSort(seq):
            for i in range(len(seq)-1):
                minIndex = select(seq, i)
                if stopping():
                    return
                tmp = seq[i]
                seq[i] = seq[minIndex]
                seq[minIndex] = tmp
                seq[i].goto(i,seq[i].ycor())
                seq[minIndex].goto(minIndex,seq[minIndex].ycor())
                seq[i].color("green")        

        def pause():
            while self.paused:
                time.sleep(1)
                screen.update()
                screen.listen()                

        def stopping():
            if self.paused:
                pause()

            if self.stop:
                self.pause = False
                self.running = False
                screen.update()
                screen.listen()                 
                return True

            return False

        self.master.title("Sort Animations")

        bar = tkinter.Menu(self.master)
        fileMenu = tkinter.Menu(bar,tearoff=0)

        def clear():
            screen.clear() 
            screen.update()
            screen.listen()

        def newWindow():
            clear()
            if self.running:
                self.stop = True

        fileMenu.add_command(label="Clear",command=newWindow)
        fileMenu.add_command(label="Exit",command=self.master.quit)   
        bar.add_cascade(label="File",menu=fileMenu)
        self.master.config(menu=bar)    

        canvas = tkinter.Canvas(self,width=600,height=600)
        canvas.pack(side=tkinter.LEFT)

        theTurtle = turtle.RawTurtle(canvas)
        theTurtle.ht()
        theTurtle.speed(0)
        screen = theTurtle.getscreen()
        screen.tracer(0)

        sideBar = tkinter.Frame(self,padx=5,pady=5)
        sideBar.pack(side=tkinter.RIGHT, fill=tkinter.BOTH)

        speedLabel = tkinter.Label(sideBar,text="Animation Speed")
        speedLabel.pack()
        speed = tkinter.StringVar()
        speedEntry = tkinter.Entry(sideBar,textvariable=speed)
        speedEntry.pack()
        speed.set("10")            

        def selSortHandler():
            self.running = True
            clear()
            screen.setworldcoordinates(0,0,200,200)
            screen.tracer(0)
            self.master.title("Selection Sort Animation")
            seq = []
            for i in range(200):
                if stopping():
                    return

                p = Point(screen,i,i)
                p.color("green")
                seq.append(p)

            screen.update()
            screen.tracer(1)

            for i in range(200):
                if stopping():
                    return 

                j = random.randint(0,199)

                p = seq[i]
                seq[i] = seq[j]
                seq[j] = p
                seq[i].goto(i,seq[i].ycor())
                seq[j].goto(j,seq[j].ycor())
                seq[i].color("black")
                seq[j].color("black")

            selectionSort(seq)
            self.running = False 
            self.stop = False

        button = tkinter.Button(sideBar, text = "Selection Sort", command=selSortHandler)
        button.pack(fill=tkinter.BOTH) 

        def mergeSortHandler():
            self.running = True
            clear()
            screen.setworldcoordinates(0,-25,200,200)
            theTurtle.width(5)
            screen.tracer(0)
            self.master.title("Merge Sort Animation")
            seq = []
            for i in range(200):
                if stopping():
                    return

                p = Point(screen,i,i)
                p.color("green")
                seq.append(p)

            screen.update()
            screen.tracer(1)
            for i in range(200):
                if stopping():
                    return 

                j = random.randint(0,199)

                p = seq[i]
                seq[i] = seq[j]
                seq[j] = p
                seq[i].goto(i,seq[i].ycor())
                seq[j].goto(j,seq[j].ycor())
                seq[i].color("black")
                seq[j].color("black")

            screen.tracer(0) 
            mergeSort(seq)
            self.running = False 
            self.stop = False

        button = tkinter.Button(sideBar, text = "Merge Sort", command=mergeSortHandler)
        button.pack(fill=tkinter.BOTH)         

        def quickSortHandler():
            self.running = True
            clear()
            screen.setworldcoordinates(0,0,200,200)
            theTurtle.width(5)
            screen.tracer(0)
            self.master.title("Quicksort Animation")
            seq = []
            for i in range(200):
                if stopping():
                    return

                p = Point(screen,i,i)
                p.color("green")
                seq.append(p)

            screen.update()
            screen.tracer(1)
            for i in range(200):
                if stopping():
                    return 

                j = random.randint(0,199)

                p = seq[i]
                seq[i] = seq[j]
                seq[j] = p
                seq[i].goto(i,seq[i].ycor())
                seq[j].goto(j,seq[j].ycor())
                seq[i].color("black")
                seq[j].color("black")

            screen.tracer(1) 
            quicksort(seq)
            self.running = False 
            self.stop = False


        button = tkinter.Button(sideBar, text = "Quicksort", command=quickSortHandler)
        button.pack(fill=tkinter.BOTH)  

        def pauseHandler():
            self.paused = not self.paused

        button = tkinter.Button(sideBar, text = "Pause", command=pauseHandler)
        button.pack(fill=tkinter.BOTH)  

        def stopHandler():
            if not self.paused and self.running:
                self.stop = True

        button = tkinter.Button(sideBar, text = "Stop", command=stopHandler)
        button.pack(fill=tkinter.BOTH)  

        screen.listen()

# The main function in our GUI program is very simple. It creates the 
# root window. Then it creates the SortAnimation frame which creates 
# all the widgets and has the logic for the event handlers. Calling mainloop
# on the frames makes it start listening for events. The mainloop function will 
# return when the application is exited. 
def main():
    root = tkinter.Tk()  
    anim = SortAnimation(root)  

    anim.mainloop()

if __name__ == "__main__":
    main()

4.3. Tic Tac Toe

You can download the starter code for Tic Tac Toe by clicking here.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
from turtle import *
import tkinter.messagebox
import tkinter
import random
import math
import datetime
import time
import sys

screenMin = 0
screenMax = 300
Human = -1
Computer = 1  

class Board:
    # When a board is constructed, you may want to make a copy of the board.
    # This can be a shallow copy of the board because Turtle objects are 
    # Immutable from the perspective of a board object. 
    def __init__(self, board=None, screen=None):
        self.screen = screen
        if screen == None: 
            if board!=None:
                self.screen = board.screen
                
        self.items = []
        for i in range(3):
            rowlst = []
            for j in range(3):
                if board==None:
                    rowlst.append(Dummy())
                else:
                    rowlst.append(board[i][j])
                
            self.items.append(rowlst)
     
    # Accessor method for the screen
    def getscreen(self):
        return self.screen
    
    # The getitem method is used to index into the board. It should 
    # return a row of the board. That row itself is indexable (it is just 
    # a list) so accessing a row and column in the board can be written
    # board[row][column] because of this method.
    def __getitem__(self,index):
        return self.items[index]
                
    # This method should return true if the two boards, self and other,
    # represent exactly the same state. 
    # READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
    def __eq__(self,other):
        pass
    
    # This method will mutate this board to contain all dummy 
    # turtles. This way the board can be reset when a new game
    # is selected. It should NOT be used except when starting
    # a new game. 
    def reset(self):
        
        self.screen.tracer(1)
        for i in range(3):
            for j in range(3):
                self.items[i][j].goto(-100,-100)
                self.items[i][j] = Dummy()
                
        self.screen.tracer(0)
        
    # This method should return an integer representing the 
    # state of the board. If the computer has won, return 1.
    # If the human has won, return -1. Otherwise, return 0.
    # READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
    def eval(self):
        pass

    # This method should return True if the board 
    # is completely filled up (no dummy turtles). 
    # Otherwise, it should return False.
    # READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
    def full(self):
        pass
    
    # This method should draw the X's and O's
    # Of this board on the screen. 
    def drawXOs(self):
        
        for row in range(3):
            for col in range(3):
                if self[row][col].eval() != 0:
                    self[row][col].st()
                    self[row][col].goto(col*100+50,row*100+50)
        
        self.screen.update()        

# This class is just for placeholder objects when no move has been made
# yet at a position in the board. Having eval() return 0 is convenient when no
# move has been made. 
class Dummy:
    def __init__(self):
        pass
    
    def eval(self):
        return 0
    
    def goto(self,x,y):
        pass
    
# In the X and O classes below the constructor begins by initializing the 
# RawTurtle part of the object with the call to super().__init__(canvas). The
# super() call returns the class of the superclass (the class above the X or O
# in the class hierarchy). In this case, the superclass is RawTurtle. Then, 
# calling __init__ on the superclass initializes the part of the object that is
# a RawTurtle. 
class X(RawTurtle):
    def __init__(self, canvas):
        super().__init__(canvas)
        self.ht()
        self.getscreen().register_shape("X",((-40,-36),(-40,-44),(0,-4),(40,-44),(40,-36), \
                             (4,0),(40,36),(40,44),(0,4),(-40,44),(-40,36),(-4,0),(-40,-36)))
        self.shape("X")
        self.penup()
        self.speed(5)
        self.goto(-100,-100)  
        
    def eval(self):
        return Computer
    
class O(RawTurtle):
    def __init__(self, canvas):
        super().__init__(canvas)
        self.ht()
        self.shape("circle")
        self.penup()
        self.speed(5)
        self.goto(-100,-100)
        
    def eval(self):
        return Human

# The minimax function is given a player (1 = Computer, -1 = Human) and a
# board object. When the player = Computer, minimax returns the maximum 
# value of all possible moves that the Computer could make. When the player =
# Human then minimax returns the minimum value of all possible moves the Human
# could make. Minimax works by assuming that at each move the Computer will pick
# its best move and the Human will pick its best move. It does this by making a 
# move for the player whose turn it is, and then recursively calling minimax. 
# The base case results when, given the state of the board, someone has won or 
# the board is full.    
# READER EXERCISE: YOU MUST COMPLETE THIS FUNCTION
def minimax(player,board):
    pass

      

class TicTacToe(tkinter.Frame):
    def __init__(self, master=None):
        super().__init__(master)
        self.pack()
        self.buildWindow()    
        self.paused = False
        self.stop = False
        self.running = False
        self.turn = Human
        self.locked = False
 
    def buildWindow(self):
        
        cv = ScrolledCanvas(self,600,600,600,600)
        cv.pack(side = tkinter.LEFT)
        t = RawTurtle(cv)
        screen = t.getscreen()
        screen.tracer(100000)
    
        screen.setworldcoordinates(screenMin,screenMin,screenMax,screenMax)
        screen.bgcolor("white")
        t.ht()
            
        frame = tkinter.Frame(self)
        frame.pack(side = tkinter.RIGHT,fill=tkinter.BOTH)
        board = Board(None, screen)
    
        def drawGrid():
            screen.clear()
            screen.tracer(1000000)
            screen.setworldcoordinates(screenMin,screenMin,screenMax,screenMax)
            screen.bgcolor("white")
            screen.tracer(0)
            t = RawTurtle(cv)
            t.ht()
            t.pu()
            t.width(10)
            t.color("green")
            for i in range(2):
                t.penup()
                t.goto(i*100+100,10)
                t.pendown()
                t.goto(i*100+100,290)
                t.penup()
                t.goto(10,i*100+100)
                t.pendown()
                t.goto(290,i*100+100)
    
            screen.update()
    
    
        def newGame():
            #drawGrid()
            self.turn = Human
            board.reset()
            self.locked =False
            screen.update()
    
      
        def startHandler():
            newGame()
            
        drawGrid()
    
        startButton = tkinter.Button(frame, text = "New Game", command=startHandler)
        startButton.pack()  
        
        def quitHandler():
            self.master.quit()
            
        quitButton = tkinter.Button(frame, text = "Quit", command=quitHandler)
        quitButton.pack()
    
        def computerTurn():
            # The locked variable prevents another event from being 
            # processed while the computer is making up its mind. 
            self.locked = True
	    
            # Call Minimax to find the best move to make.
            # READER EXERCISE: YOU MUST COMPLETE THIS CODE
            # After writing this code, the maxMove tuple should
            # contain the best move for the computer. For instance,
            # if the best move is in the first row and third column
            # then maxMove would be (0,2).
	    
            row, col = maxMove
            board[row][col] = X(cv)
            self.locked = False
    
      
        def mouseClick(x,y):
            if not self.locked:
                row = int(y // 100)
                col = int(x // 100)
    
                if board[row][col].eval() == 0:
                    board[row][col] = O(cv) 
                    
                    self.turn = Computer
                    
                    board.drawXOs()
                    
                    if not board.full() and not abs(board.eval())==1:
                        computerTurn()
                    
                        self.turn = Human
                        
                        board.drawXOs()
                    else:
                        self.locked = True
                        
                    if board.eval() == 1:
                        tkinter.messagebox.showwarning("Game Over","X wins!!!")
          
                    if board.eval() == -1:
                        tkinter.messagebox.showwarning("Game Over","O wins. How did that happen?")
                        
                    if board.full():
                        tkinter.messagebox.showwarning("Game Over","It was a tie.")
     
        screen.onclick(mouseClick)
        
        screen.listen()

def main():
    root = tkinter.Tk()
    root.title("Tic Tac Toe")    
    application = TicTacToe(root)  
    application.mainloop()
        
if __name__ == "__main__":
    main()

4.4. The Linked List Datatype

You can download the code for the linked list datatype by clicking here.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
class LinkedList:
    
    # The __Node class is used internally by the LinkedList class. It is 
    # invisible from outside this class due to the two underscores
    # that precede the class name. Python mangles names so that they
    # are not recognizable outside the class when two underscores
    # precede a name but aren't followed by two underscores at the
    # end of the name (i.e. an operator name). 
    class __Node:
        def __init__(self,item,next=None):
            self.item = item
            self.next = next
            
        def getItem(self):
            return self.item
        
        def getNext(self):
            return self.next
        
        def setItem(self, item):
            self.item = item
            
        def setNext(self,next):
            self.next = next
            
    def __init__(self,contents=[]):
        # Here we keep a reference to the first node in the linked list
        # and the last item in the linked list. The both point to a 
        # dummy node to begin with. This dummy node will always be in
        # the first position in the list and will never contain an item. 
        # Its purpose is to eliminate special cases in the code below. 
        self.first = LinkedList.__Node(None,None)
        self.last = self.first
        self.numItems = 0

        for e in contents:
            self.append(e)
          
    def __getitem__(self,index):
        if index >= 0 and index < self.numItems:
            cursor = self.first.getNext()
            for i in range(index):
                cursor = cursor.getNext()
                
            return cursor.getItem()
        
        raise IndexError("LinkedList index out of range")
    
    def __setitem__(self,index,val):
        if index >= 0 and index < self.numItems:
            cursor = self.first.getNext()
            for i in range(index):
                cursor = cursor.getNext()
                
            cursor.setItem(val)
            return 
        
        raise IndexError("LinkedList assignment index out of range")
    
    def insert(self,index,item):
        cursor = self.first
        
        if index < self.numItems: 
            for i in range(index):
                cursor = cursor.getNext()
                
            node = LinkedList.__Node(item, cursor.getNext())
            cursor.setNext(node)
            self.numItems += 1
        else:
            self.append(item)
            
            
    def __add__(self,other):
        if type(self) != type(other):
            raise TypeError("Concatenate undefined for " + \
                str(type(self)) + " + " + str(type(other)))

        result = LinkedList()
        
        cursor = self.first.getNext()
        
        while cursor != None:
            result.append(cursor.getItem())
            cursor = cursor.getNext()
            
        cursor = other.first.getNext()
                    
        while cursor != None:
            result.append(cursor.getItem())
            cursor = cursor.getNext()
   
        return result
    
    
    def __contains__(self,item):
        # This is left as an exercise for the reader.
        pass
 
    def __delitem__(self,index):
        # This is left as an exercise for the reader. 
        pass 
            
    def __eq__(self,other):
        if type(other) != type(self):
            return False
        
        if self.numItems != other.numItems:
            return False
        
        cursor1 = self.first.getNext()
        cursor2 = other.first.getNext()
        while cursor1 != None:
            if cursor1.getItem() != cursor2.getItem():
                return False
            cursor1 = cursor1.getNext()
            cursor2 = cursor2.getNext()
            
        return True
    
    def __iter__(self):
        # This is left as an exercise for the reader.
        pass
            
    def __len__(self):
        # This is left as an exercise for the reader.
        pass

    def append(self,item):
        node = LinkedList.__Node(item)
        self.last.setNext(node)
        self.last = node
        self.numItems += 1

        
    def __str__(self):
        # This is left as an exercise for the reader. 
        pass
    
    def __repr__(self):
        # This is left as an exercise for the reader.
        pass              
                
def main():
    lst = LinkedList()
    
    for i in range(100):
        lst.append(i)
    
    lst2 = LinkedList(lst)
    
    print(lst)
    print(lst2)
    
    if lst == lst2:
        print("Test 1 Passed")
    else:
        print("Test 1 Failed")
    
    lst3 = lst + lst2
    
    if len(lst3) == len(lst) + len(lst2):
        print("Test 2 Passed")
    else:
        print("Test 2 Failed")
        
    
    if 1 in lst3:
        print("Test 3 Passed")
    else:
        print("Test 3 Failed")        
    
    if 2 in lst3:
        print("Test 4 Passed")
    else:
        print("Test 4 Failed")        
    
    del lst[1]
    
    if 1 in lst:
        print("Test 5 Failed")
    else:
        print("Test 5 Passed")        
    
    if len(lst) == 99:
        print("Test 6 Passed")
    else:
        print("Test 6 Failed")        
        
    if lst == lst2:
        print("Test 7 Failed")
    else:
        print("Test 7 Passed")        
    
    del lst2[2]
    
    if lst == lst2:
        print("Test 8 Failed")
    else:
        print("Test 8 Passed")  
        
    
    lst4 = LinkedList(lst)
    lst.insert(0,100)
    lst4 = LinkedList([100]) + lst4
    
    if lst == lst4:
        print("Test 9 Passed")
    else:
        print("Test 9 Failed")
        
    lst.insert(1000,333)
    lst4.append(333)

    if lst == lst4:
        print("Test 10 Passed")
    else:
        print("Test 10 Failed")  
        
    print(lst)
    print(lst4)
    
if __name__ == "__main__":
    main()
                
            
            
        
            

4.5. The Stack Datatype

You can download the code for the stack datatype by clicking here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Stack:
    def __init__(self):
        self.items = []
        
    def pop(self):
        if self.isEmpty():
            raise RuntimeError("Attempt to pop an empty stack")
        
        topIdx = len(self.items)-1
        item = self.items[topIdx]
        del self.items[topIdx]
        return item
    
    def push(self,item):
        self.items.append(item)
        
    def top(self):
        if self.isEmpty():
            raise RuntimeError("Attempt to get top of empty stack")
        
        topIdx = len(self.items)-1
        return self.items[topIdx]
    
    def isEmpty(self):
        return len(self.items) == 0

    def clear(self):
        self.items = []
    
def main():
    s = Stack()
    items = list(range(10))
    items2 = []
    
    for k in items:
        s.push(k)
        
    if s.top() == 9:
        print("Test 1 Passed")
    else:
        print("Test 1 Failed")
        
    while not s.isEmpty():
        items2.append(s.pop())

    items2.reverse()
    
    if items2 != items:
        print("Test 2 Failed")
    else:
        print("Test 2 Passed")
        
    try:
        s.pop()
        print("Test 3 Failed")
        
    except RuntimeError:
        print("Test 3 Passed")
    except:
        print("Test 3 Failed")

    try:
        s.top()
        print("Test 4 Failed")
        
    except RuntimeError:
        print("Test 4 Passed")
    except:
        print("Test 4 Failed")   
        
if __name__=="__main__":
    main()

4.6. The Queue Datatype

You can download the code for the queue datatype by clicking here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Queue:
    def __init__(self):
        self.items = []
        self.frontIdx = 0
        
    def __compress(self):
        newitems = []
        for i in range(self.frontIdx,len(self.items)):
            newitems.append(self.items[i])
            
        self.items = newitems
        self.frontIdx = 0
        
    def dequeue(self):
        if self.isEmpty():
            raise RuntimeError("Attempt to dequeue an empty queue")
        
        # When queue is half full, compress it. This 
        # achieves an amortized complexity of O(1) while
        # not letting the list continue to grow unchecked. 
        if self.frontIdx * 2 > len(self.items):
            self.__compress()
            
        item = self.items[self.frontIdx]
        self.frontIdx += 1
        return item
    
    def enqueue(self,item):
        self.items.append(item)
        
    def front(self):
        if self.isEmpty():
            raise RuntimeError("Attempt to access front of empty queue")
        
        return self.items[self.frontIdx]
        
    
    def isEmpty(self):
        return self.frontIdx == len(self.items)

    def clear(self):
        self.items = []
        self.frontIdx = 0
    
def main():
    q = Queue()
    items = list(range(10))
    items2 = []
    
    for k in items:
        q.enqueue(k)
        
    if q.front() == 0:
        print("Test 1 Passed")
    else:
        print("Test 1 Failed")
        
    while not q.isEmpty():
        items2.append(q.dequeue())
    
    if items2 != items:
        print("Test 2 Failed")
    else:
        print("Test 2 Passed")

    for k in items:
        q.enqueue(k)   
      
    items2 = []
    
    while not q.isEmpty():
        items2.append(q.dequeue())  
        
    if items2 != items:
        print("Test 3 Failed")
    else:
        print("Test 3 Passed")
    
    try:
        q.dequeue()
        print("Test 4 Failed")
        
    except RuntimeError:
        print("Test 4 Passed")
    except:
        print("Test 4 Failed")

    try:
        q.front()
        print("Test 5 Failed")
        
    except RuntimeError:
        print("Test 5 Passed")
    except:
        print("Test 5 Failed")  
        
if __name__=="__main__":
    main()