Page
1
M A N N I N G David Kopec
Page
2
Classic Computer Science Problems in Python
Page
3
(This page has no text content)
Page
4
Classic Computer Science Problems in Python DAVID KOPEC M A N N I N G SHELTER ISLAND
Page
5
For online information and ordering of this and other Manning books, please visit www.manning.com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact Special Sales Department Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 Email: orders@manning.com © 2019 by Manning Publications Co. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps. Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid-free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine. Manning Publications Co. Development editor: Jennifer Stout 20 Baldwin Road Technical development editor: Frances Buontemp PO Box 761 Review editor: Aleksandar Dragosavljević Shelter Island, NY 11964 Production editor: Deirdre Hiam Copy editor: Andy Carroll Proofreader: Katie Tennant Technical proofreader: Juan Rufes Typesetter: Dottie Marsico Cover designer: Marija Tudor ISBN 9781617295980 Printed in the United States of America 1 2 3 4 5 6 7 8 9 10 – SP – 24 23 22 21 20 19
Page
6
Dedicated to my grandmother, Erminia Antos, a lifelong teacher and learner.
Page
7
(This page has no text content)
Page
8
contents acknowledgments xi about this book xiii about the author xiv about the cover illustration xv Introduction 1 0.1 Why Python? 1 0.2 What is a classic computer science problem? 2 0.3 What kinds of problems are in this book? 2 0.4 Who is this book for? 3 0.5 Python versioning, source code repository, and type hints 4 0.6 No graphics, no UI code, just the standard library 5 0.7 Part of a series 5 1 Small problems 6 1.1 The Fibonacci sequence 6 A first recursive attempt 6 ■ Utilizing base cases 8 Memoization to the rescue 9 ■ Automatic memoization 10 Keep it simple, Fibonacci 11 ■ Generating Fibonacci numbers with a generator 11vii
Page
9
CONTENTSviii1.2 Trivial compression 12 1.3 Unbreakable encryption 16 Getting the data in order 16 ■ Encrypting and decrypting 18 1.4 Calculating pi 19 1.5 The Towers of Hanoi 20 Modeling the towers 20 ■ Solving The Towers of Hanoi 22 1.6 Real-world applications 24 1.7 Exercises 24 2 Search problems 25 2.1 DNA search 25 Storing DNA 25 ■ Linear search 27 ■ Binary search 28 A generic example 30 2.2 Maze solving 32 Generating a random maze 32 ■ Miscellaneous maze minutiae 33 ■ Depth-first search 34 ■ Breadth-first search 38 ■ A* search 42 2.3 Missionaries and cannibals 47 Representing the problem 47 ■ Solving 49 2.4 Real-world applications 51 2.5 Exercises 51 3 Constraint-satisfaction problems 52 3.1 Building a constraint-satisfaction problem framework 53 3.2 The Australian map-coloring problem 57 3.3 The eight queens problem 59 3.4 Word search 61 3.5 SEND+MORE=MONEY 65 3.6 Circuit board layout 66 3.7 Real-world applications 67 3.8 Exercises 67 4 Graph problems 68 4.1 A map as a graph 68 4.2 Building a graph framework 71 Working with Edge and Graph 75
Page
10
CONTENTS ix4.3 Finding the shortest path 76 Revisiting breadth-first search (BFS) 76 4.4 Minimizing the cost of building the network 78 Workings with weights 78 ■ Finding the minimum spanning tree 82 4.5 Finding shortest paths in a weighted graph 88 Dijkstra’s algorithm 88 4.6 Real-world applications 93 4.7 Exercises 93 5 Genetic algorithms 94 5.1 Biological background 94 5.2 A generic genetic algorithm 95 5.3 A naive test 102 5.4 SEND+MORE=MONEY revisited 104 5.5 Optimizing list compression 107 5.6 Challenges for genetic algorithms 109 5.7 Real-world applications 110 5.8 Exercises 111 6 K-means clustering 112 6.1 Preliminaries 113 6.2 The k-means clustering algorithm 115 6.3 Clustering governors by age and longitude 119 6.4 Clustering Michael Jackson albums by length 124 6.5 K-means clustering problems and extensions 125 6.6 Real-world applications 126 6.7 Exercises 126 7 Fairly simple neural networks 127 7.1 Biological basis? 128 7.2 Artificial neural networks 129 Neurons 129 ■ Layers 130 ■ Backpropagation 131 The big picture 135 7.3 Preliminaries 135 Dot product 135 ■ The activation function 136
Page
11
CONTENTSx7.4 Building the network 136 Implementing neurons 137 ■ Implementing layers 138 Implementing the network 140 7.5 Classification problems 143 Normalizing data 143 ■ The classic iris data set 144 Classifying wine 147 7.6 Speeding up neural networks 149 7.7 Neural network problems and extensions 150 7.8 Real-world applications 151 7.9 Exercises 152 8 Adversarial search 153 8.1 Basic board game components 153 8.2 Tic-tac-toe 155 Managing tic-tac-toe state 155 ■ Minimax 158 Testing minimax with tic-tac-toe 160 ■ Developing a tic-tac-toe AI 162 8.3 Connect Four 163 Connect Four game machinery 163 ■ A Connect Four AI 168 ■ Improving minimax with alpha-beta pruning 169 8.4 Minimax improvements beyond alpha-beta pruning 170 8.5 Real-world applications 170 8.6 Exercises 171 9 Miscellaneous problems 172 9.1 The knapsack problem 172 9.2 The Traveling Salesman Problem 177 The naive approach 177 ■ Taking it to the next level 182 9.3 Phone number mnemonics 182 9.4 Real-world applications 184 9.5 Exercises 184 appendix A Glossary 186 appendix B More resources 191 appendix C A brief introduction to type hints 195 index 201
Page
12
acknowledgments Thank you, everyone at Manning who helped in the production of this book: Cheryl Weisman, Deirdre Hiam, Katie Tennant, Dottie Marsico, Janet Vail, Barbara Mirecki, Aleksandar Dragosavljević, Mary Piergies, and Marija Tudor. I thank acquisitions editor Brian Sawyer, who wisely steered us toward attacking Python after I finished Swift. Thank you, development editor Jennifer Stout, for always having a positive attitude. Thanks go to technical editor Frances Buontempo, who provided careful consideration of each chapter and gave detailed, useful feedback at every turn. I thank copyeditor Andy Carroll, whose superb attention to detail on both the Swift book and this one caught several of my mistakes, and also my technical proofreader, Juan Rufes. The following people also reviewed the book: Al Krinker, Al Pezewski, Alan Bogusiewicz, Brian Canada, Craig Henderson, Daniel Kenney-Jung, Edmond Sesay, Ewa Baranowska, Gary Barnhart, Geoff Clark, James Watson, Jeffrey Lim, Jens Chris- tian, Bredahl Madsen, Juan Jimenez, Juan Rufes, Matt Lemke, Mayur Patil, Michael Bright, Roberto Casadei, Sam Zaydel, Thorsten Weber, Tom Jeffries, and Will Lopez. Thanks go to all who provided constructive and specific criticism during the book’s development. Your feedback was incorporated. I thank my family, friends, and colleagues who encouraged me to take on this book project immediately following the publication of Classic Computer Science Problems in Swift. I thank my online friends on Twitter and elsewhere who have provided encour- aging words and helped promote the book in ways small and large. And I thank my wife, Rebecca Kopec, and my mom, Sylvia Kopec, who are always supportive of my projects.xi
Page
13
ACKNOWLEDGMENTSxii We developed this book in a fairly short period of time. The vast majority of the manuscript was written over the summer of 2018, based on the earlier Swift version. I appreciate that Manning was willing to compress its (usually much longer) process to enable me to work during a schedule that was convenient to me. I know this put pressure on the entire team as we went through three rounds of reviews at multiple different levels amongst many different people in just a few months. Most readers would be amazed at how many different kinds of reviews a technical book by a tradi- tional publisher goes through and how many people have their part in critiquing and revising it. From the technical proofer to the copy editor, the review editor, all of the official reviewers, and everyone in between, I thank you! Finally, most importantly, I thank my readers for purchasing this book. In a world full of halfhearted online tutorials, I think it is important to support the development of books that provide the same author’s voice throughout an extended volume. Online tutorials can be superb resources, but your purchase enables full-length, vetted, and carefully developed books to still have a place in computer science education.
Page
14
about this book Trademarks Trademarked names appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, the names are only used in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. “Python” is a registered trademark of the Python Software Founda- tion. “Connect Four” is a trademark of Hasbro, Inc. Book forum Purchase of Classic Computer Science Problems in Python includes free access to a private web forum run by Manning Publications where you can make comments about the book, ask technical questions, and receive help from the author and from other users. To access the forum, go to https://www.manning.com/books/classic-computer- science-problems-in-python. You can also learn more about Manning's forums and the rules of conduct at https://forums.manning.com/forums/about. Manning’s commitment to our readers is to provide a venue where a meaningful dialogue between individual readers and between readers and the author can take place. It is not a commitment to any specific amount of participation on the part of the author, whose contribution to the forum remains voluntary (and unpaid). We sug- gest you try asking him some challenging questions lest his interest stray! The forum and the archives of previous discussions will be accessible from the publisher’s website as long as the book is in print.xiii
Page
15
about the author David Kopec is an assistant professor of Computer Sci- ence & Innovation at Champlain College in Burlington, Vermont. He is an experienced software developer and the author of Classic Computer Science Problems in Swift (Manning, 2018), and Dart for Absolute Beginners (Apress, 2014). David holds a bachelor’s degree in economics and a master’s in computer science, both from Dartmouth College. You can reach David on Twitter @davekopec.xiv
Page
16
about the cover illustration The figure on the cover of Classic Computer Science Problems in Python is captioned “Habit of a Bonza or Priest in China.” The illustration is taken from Thomas Jefferys’ A Collection of the Dresses of Different Nations, Ancient and Modern (four volumes), Lon- don, published between 1757 and 1772. The title page states that these are hand- colored copperplate engravings, heightened with gum arabic. Thomas Jefferys (1719–1771) was called “Geographer to King George III.” He was an English cartographer who was the leading map supplier of his day. He engraved and printed maps for government and other official bodies and produced a wide range of commercial maps and atlases, especially of North America. His work as a map maker sparked an interest in local dress customs of the lands he surveyed and mapped, which are brilliantly displayed in this collection. Fascination with faraway lands and travel for pleasure were relatively new phenomena in the late eighteenth century, and collections such as this one were popular, introducing both the tourist as well as the armchair traveler to the inhabitants of other countries. The diversity of the drawings in Jefferys’ volumes speaks vividly of the uniqueness and individuality of the world’s nations some 200 years ago. Dress codes have changed since then, and the diversity by region and country, so rich at the time, has faded away. It’s now often hard to tell the inhabitants of one continent from another. Perhaps, try- ing to view it optimistically, we’ve traded a cultural and visual diversity for a more var- ied personal life—or a more varied and interesting intellectual and technical life. At a time when it’s difficult to tell one computer book from another, Manning cel- ebrates the inventiveness and initiative of the computer business with book covers based on the rich diversity of regional life of two centuries ago, brought back to life by Jefferys’ pictures.xv
Page
17
(This page has no text content)
Page
18
Introduction Thank you for purchasing Classic Computer Science Problems in Python. Python is one of the most popular programming languages in the world, and people become Python programmers from a variety of backgrounds. Some have a formal computer science education. Others learn Python as a hobby. Still others use Python in a pro- fessional setting, but their primary job is not to be a software developer. The prob- lems in this intermediate book will help seasoned programmers refresh themselves on ideas from their CS education while learning some advanced features of the lan- guage. Self-taught programmers will accelerate their CS education by learning clas- sic problems in the language of their choice: Python. This book covers such a diversity of problem-solving techniques that there is truly something for everyone. This book is not an introduction to Python. There are numerous excellent books from Manning and other publishers in that vein.1 Instead, this book assumes that you are already an intermediate or advanced Python programmer. Although this book requires Python 3.7, mastery of every facet of the latest version of Python is not assumed. In fact, the book’s content was created with the assumption that it would serve as learning material to help readers achieve such mastery. On the other hand, this book is not appropriate for readers completely new to Python. Why Python? Python is used in pursuits as diverse as data science, film-making, computer science education, IT management, and much more. There really is no computing field that 1 If you are just starting your Python journey, you may want to first check out The Quick Python Book, 3rd edi- tion, by Naomi Ceder (Manning, 2018) before beginning this book.1
Page
19
2 IntroductionPython has not touched (except maybe kernel development). Python is loved for its flexibility, beautiful and succinct syntax, object-oriented purity, and bustling community. The strong community is important because it means Python is welcoming to newcom- ers and has a large ecosystem of available libraries for developers to build upon. For the preceding reasons, Python is sometimes thought of as a beginner-friendly language, and that characterization is probably true. Most people would agree that Python is easier to learn than C++, for example, and its community is almost certainly friendlier to newcomers. As a result, many people learn Python because it is approach- able, and they start writing the programs they want to write fairly quickly. But they may never have received an education in computer science that teaches them all of the powerful problem-solving techniques available to them. If you are one of those pro- grammers who knows Python but does not know CS, this book is for you. Other people learn Python as a second, third, fourth, or fifth language after a long time working in software development. For them, seeing old problems they’ve already seen in another language will help them accelerate their learning of Python. For them, this book may be a good refresher before a job interview, or it might expose them to some problem-solving techniques they had not previously thought of exploit- ing in their work. I would encourage them to skim the table of contents to see if there are topics in this book that excite them. What is a classic computer science problem? Some say that computers are to computer science as telescopes are to astronomy. If that’s the case, then perhaps a programming language is like a telescope lens. In any event, the term “classic computer science problems” is used here to mean “program- ming problems typically taught in an undergraduate computer science curriculum.” There are certain programming problems that are given to new programmers to solve and that have become commonplace enough to be deemed classic, whether in a classroom setting during the pursuit of a bachelor’s degree (in computer science, soft- ware engineering, and the like) or within the confines of an intermediate program- ming textbook (for example, a first book on artificial intelligence or algorithms). A selection of such problems is what you will find in this book. The problems range from the trivial, which can be solved in a few lines of code, to the complex, which require the buildup of systems over multiple chapters. Some problems touch on artificial intelligence, and others simply require common sense. Some problems are practical, and other problems are fanciful. What kinds of problems are in this book? Chapter 1 introduces problem-solving techniques that will likely look familiar to most readers. Things like recursion, memoization, and bit manipulation are essential build- ing blocks of other techniques explored in later chapters. This gentle introduction is followed by chapter 2, which focuses on search prob- lems. Search is such a large topic that you could arguably place most problems in the
Page
20
3Who is this book for?book under its banner. Chapter 2 introduces the most essential search algorithms, including binary search, depth-first search, breadth-first search, and A*. These algo- rithms are reused throughout the rest of the book. In chapter 3, you will build a framework for solving a broad range of problems that can be abstractly defined by variables of limited domains that have constraints between them. This includes such classics as the eight queens problem, the Australian map-coloring problem, and the cryptarithmetic SEND+MORE=MONEY. Chapter 4 explores the world of graph algorithms, which to the uninitiated are sur- prisingly broad in their applicability. In this chapter, you will build a graph data struc- ture and then use it to solve several classic optimization problems. Chapter 5 explores genetic algorithms, a technique that is less deterministic than most covered in the book but that sometimes can solve problems traditional algo- rithms cannot solve in a reasonable amount of time. Chapter 6 covers k-means clustering and is perhaps the most algorithmically spe- cific chapter in the book. This clustering technique is simple to implement, easy to understand, and broadly applicable. Chapter 7 aims to explain what a neural network is and to give the reader a taste of what a very simple neural network looks like. It does not aim to provide comprehen- sive coverage of this exciting and evolving field. In this chapter, you will build a neural network from first principles, using no external libraries, so you can really see how a neural network works. Chapter 8 is on adversarial search in two-player perfect information games. You will learn a search algorithm known as minimax, which can be used to develop an arti- ficial opponent that can play games like chess, checkers, and Connect Four well. Finally, chapter 9 covers interesting (and fun) problems that did not quite fit any- where else in the book. Who is this book for? This book is for both intermediate and experienced programmers. Experienced pro- grammers who want to deepen their knowledge of Python will find comfortably famil- iar problems from their computer science or programming education. Intermediate programmers will be introduced to these classic problems in the language of their choice: Python. Developers getting ready for coding interviews will likely find this book to be valuable preparation material. In addition to professional programmers, students enrolled in undergraduate computer science programs who have an interest in Python will likely find this book helpful. It makes no attempt to be a rigorous introduction to data structures and algo- rithms. This is not a data structures and algorithms textbook . You will not find proofs or extensive use of big-O notation within its pages. Instead, it is positioned as an approachable, hands-on tutorial to the problem-solving techniques that should be the end product of taking data structure, algorithm, and artificial intelligence classes.