Srini Devadas - Programming for the Puzzled: Learn to Program While Solving Puzzles

Programming for the Puzzled

Learn to Program While Solving Puzzles

Srini Devadas

The MIT Press

Cambridge, Massachusetts

London, England

2017 The Massachusetts Institute of Technology

All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.

This book was set in Times Roman by Westchester Publishing Services. Printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Names: Devadas, Srinivas, author.

Title: Programming for the puzzled : learn to program while solving puzzles / Srini Devadas.

Description: Cambridge, MA : The MIT Press, [2017] | Includes bibliographical references and index.

Identifiers: LCCN 2017010148 | ISBN 9780262534307 (pbk. : alk. paper)

Subjects: LCSH: Computer programming--Computer-assisted instruction. | Mathematical recreations--Data processing. | Puzzles--Data processing. | Computer games.

Classification: LCC QA76.6 .D485 2017 | DDC 005.10285--dc23 LC record available at https://lccn.loc.gov/2017010148

Contents

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 algorithma 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 reasonit 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 programmings sake. Puzzles are some of the coolest applications aroundthey 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 momenta search strategy, data structure, or mathematical factand 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 codes 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. Ive 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 dont 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 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 books 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 dont 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 doesnt 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 puzzles 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 codes 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 doingif 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.