Preface
Puzzles are wonderfully recreational. The best puzzles have nonobvious solutions that need an “Aha moment” to be discovered. An algorithmic puzzle is a puzzle whose solution is an algorithm—a set of steps that can be mechanized. Algorithms can be described in English or any other natural language, though for greater precision they are often described in “pseudocode.” Pseudocode is called that for a reason—it is not detailed enough that it can be run on a computer, unlike code written in a programming language.
Computer programming is a livelihood for a growing number of people in the world. To learn programming, one first learns basic programming constructs like assignment statements and control loops through simple examples, and programming exercises often involve translating the pseudocode of an algorithm into code in the programming language being learned. Programmers benefit from the same analytical skills that puzzle-solving requires. These skills are required when translating specifications into programming constructs, as well as discovering errors in early versions of code, called the debugging process.
While teaching programming at MIT to freshmen and sophomores over decades, it became clear to me that students are strongly motivated by applications. Few want to program for programming’s sake. Puzzles are some of the coolest applications around—they have the advantage of being easy to describe and attention-grabbing. The latter is particularly important today, when lecturers have to compete for attention with Snapchat, Facebook, and Instagram. And I discovered, as others have before me, that the best way of putting students to sleep is to describe programming syntax or semantics ad nauseum, meaning for more than a couple of minutes!
This book is my attempt at teaching programming by building a bridge between the recreational world of algorithmic puzzles and the pragmatic world of computer programming. I assume a rudimentary grasp of programming concepts that can be obtained from introductory or AP computer science classes in high school, or classes like MITx/edX 6.0001x.
Each lesson in the book starts with the description of a puzzle. Many of these puzzles (chapters) are popular ones that have been described in several publications and websites, with many variations. After a failed attempt or two at solving the puzzle, we arrive at an Aha moment—a search strategy, data structure, or mathematical fact—and voilà, the solution presents itself. Sometimes there is an obvious “brutish” way of solving the puzzle, and I explain the associated algorithm and code before deeming it a “failure.” And then there is an insight that leads to a more elegant and efficient solution.
The solution to the puzzle is the specification of the code we need to write. As you read, you will learn what the code is supposed to do before you see the code. This is a powerful pedagogical philosophy that I believe in, since it decouples understanding the code’s functionality from understanding programming language syntax and semantics. Syntax and semantics required to understand the code are explained on a “pay as you go” basis.
Going from the physical world of the puzzle to the computer world of the program is fun but not always smooth. In some cases you will have to pretend in the computer world that some operation is not efficient because it is not efficient in the physical world. I’ve tried to minimize that in the book, but have not eliminated it entirely. I trust this will not cause confusion, and I point it out in the very few instances it occurs.
You could read and use this book in many ways. If you are only interested in puzzles and their solutions, you can stop after you come up with the solution or after you have read the provided solution. I hope you don’t stop there, because showing how to take the described solution and turn it into executable code was a primary purpose in my writing the book. Reading an entire puzzle will give you a good sense of what it takes to produce a useful program that anyone can run and use for themselves. I tried hard to ensure that my descriptions of Python syntax and semantics were self-contained, but if you have questions about Python syntax, semantics, and libraries, python.org is an excellent resource, and the edX/MITx course 6.0001x is a great introduction to programming in Python.
If you can install and run Python on your machine, you will get a lot more from this book. You can do this by visiting https://www.python.org/downloads/. The code for all the puzzle solutions in the book is conveniently downloadable from the book’s MIT Press website or from https://mitpress.mit.edu/books/programming-puzzled. The code has been tested for Python version 2.7 and above, including Python 3.x releases.1 Of course, you are welcome to ignore the website and write your own code that solves the puzzle. You can run the programs downloaded from the book’s website, or the programs that you have written for different inputs from the examples in the book, and I strongly encourage you to do so. I don’t make any guarantees about there being no bugs in the code, though I did try to get rid of all of them. Be warned that the provided code makes assumptions about its inputs corresponding to the puzzle statement and doesn’t behave gracefully when it receives inputs it does not expect. Adding these checks would have cluttered the code. A good way of deepening your understanding of programming is to augment each puzzle’s code to explicitly check for malformed input.
At the end of each puzzle I have a few programming exercises. These exercises vary in challenge level and the amount of code that needs to be written. Doing the exercises for each puzzle will help you get the most of out of this book. You will have to understand the code associated with the puzzle well enough to be able to modify it or augment the code’s functionality. A few of the exercises in the book relate to including checks for malformed input. The exercises marked Puzzle Exercise require significant code-writing or restructuring of the provided puzzle code. Some of these could be viewed as advanced puzzles related to the puzzle described. Solutions to the exercises and puzzles are not provided in the book, but are available to instructors from the MIT Press book website.
I am a firm believer in learning by doing—if you successfully do all the exercises by yourself, you will be well on your way to becoming a computer scientist! I wish you the best of luck on your journey.