Think Like a Programmer An Introduction to Creative Problem Solving (V. Anton Spraul) (Z-Library)

C O DE E A T SLEEP A N I N T R O D U C T I O N T O C R E A T I V E P R O B L E M S O L V I N G V . A N T O N S P R A U L T H I N K L I K E A P R O G R A M M E R C O DE E A T SLEEPR E W I R E Y O U R B R A I N $34.95 ($36.95 CDN) www.nostarch.com TH E F I N EST I N G E E K E NTE RTA I N M E NT™ “ I L I E F LAT .” Th is book uses RepKover — a durab le b ind ing that won’t snap shut. SHELVE IN : PROGRAM M ING/GENERAL • Master more advanced programming tools like recursion and dynamic memory • Organize your thoughts and develop strategies to tackle particular types of problems Although the book’s examples are written in C++, the creative problem-solving concepts they illustrate go beyond any particular language; in fact, they often reach outside the realm of computer science. As the most skillful programmers know, writing great code is a creative art—and the first step in creating your masterpiece is learning to Think Like a Programmer. distillation of the techniques he has used and honed over A B O U T T H E A U T H O R V. Anton Spraul has taught introductory programming and computer science for more than 15 years. This book is a many one-on-one sessions with struggling programmers. He is also the author of Computer Science Made Simple. The real challenge of programming isn’t learning a language’s syntax—it’s learning to creatively solve problems so you can build something great. In this one-of-a-kind text, author V. Anton Spraul breaks down the ways that programmers solve problems and teaches you what other introductory books often ignore: how to Think Like a Programmer. Each chapter tackles and recursion, and open-ended exercises throughout a single programming concept, like classes, pointers, challenge you to apply your knowledge. You’ll also learn how to: them easier to solve • Split problems into discrete components to make • Make the most of code reuse with functions, classes, and libraries • Pick the perfect data structure for a particular job C O DE E A T SLEEP T H IN K L IK E A P R O G R A M M E R T H IN K L IK E A P R O G R A M M E R

THINK LIKE A PROGRAMMER D ow n lo a d f ro m W o w ! e B o o k < w w w .w o w e b o o k. co m >

THINK LIKE A PROGRAMMER A n I n t r o d u c t i o n t o C r e a t i v e P r o b l e m S o l v i n g by V. Anton Spraul San Francisco

THINK LIKE A PROGRAMMER. Copyright © 2012 by V. Anton Spraul. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. First printing 15 14 13 12 1 2 3 4 5 6 7 8 9 ISBN-10: 1-59327-424-6 ISBN-13: 978-1-59327-424-5 Publisher: William Pollock Production Editor: Alison Law Cover Design: Charlie Wylie Interior Design: Octopod Studios Developmental Editor: Keith Fancher Technical Reviewer: Dan Randall Copyeditor: Julianne Jigour Compositor: Susan Glinert Stevens Proofreader: Ward Webber For information on book distributors or translations, please contact No Starch Press, Inc. directly: No Starch Press, Inc. 38 Ringold Street, San Francisco, CA 94103 phone: 415.863.9900; fax: 415.863.9950; info@nostarch.com; www.nostarch.com Library of Congress Cataloging-in-Publication Data A catalog record of this book is available from the Library of Congress. No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

B R I E F C O N T E N T S Acknowledgments .......................................................................................................... xi Introduction ................................................................................................................. xiii Chapter 1: Strategies for Problem Solving ..........................................................................1 Chapter 2: Pure Puzzles.................................................................................................25 Chapter 3: Solving Problems with Arrays .........................................................................55 Chapter 4: Solving Problems with Pointers and Dynamic Memory .......................................81 Chapter 5: Solving Problems with Classes ......................................................................111 Chapter 6: Solving Problems with Recursion ...................................................................143 Chapter 7: Solving Problems with Code Reuse................................................................171 Chapter 8: Thinking Like a Programmer .........................................................................195 Index .........................................................................................................................227

C O N T E N T S I N D E T A I L ACKNOWLEDGMENTS xi INTRODUCTION xiii About This Book ...................................................................................................... xv Prerequisites .............................................................................................. xv Chosen Topics ........................................................................................... xv Programming Style .................................................................................... xvi Exercises .................................................................................................. xvi Why C++? ...............................................................................................xvii 1 STRATEGIES FOR PROBLEM SOLVING 1 Classic Puzzles ........................................................................................................ 2 The Fox, the Goose, and the Corn ................................................................ 3 Problem: How to Cross the River? ....................................................................... 3 Sliding Tile Puzzles ...................................................................................... 7 Problem: The Sliding Eight .................................................................................. 7 Problem: The Sliding Five ................................................................................... 8 Sudoku .................................................................................................... 11 Problem: Completing a Sudoku Square ............................................................. 11 The Quarrasi Lock ..................................................................................... 13 Problem: Opening the Alien Lock ...................................................................... 13 General Problem-Solving Techniques ........................................................................ 15 Always Have a Plan .................................................................................. 16 Restate the Problem ................................................................................... 17 Divide the Problem .................................................................................... 17 Start with What You Know ......................................................................... 18 Reduce the Problem ................................................................................... 19 Look for Analogies .................................................................................... 20 Experiment ............................................................................................... 20 Don’t Get Frustrated .................................................................................. 21 Exercises ............................................................................................................... 22 2 PURE PUZZLES 25 Review of C++ Used in This Chapter ........................................................................ 26 Output Patterns ...................................................................................................... 26 Problem: Half of a Square ................................................................................ 26 Problem: A Square (Half of a Square Reduction) ............................................... 27 Problem: A Line (Half of a Square Further Reduction) ......................................... 27 Problem: Count Down by Counting Up .............................................................. 28 Problem: A Sideways Triangle .......................................................................... 29 Input Processing ..................................................................................................... 31 Problem: Luhn Checksum Validation ................................................................. 31 Breaking Down the Problem ....................................................................... 33

viii Contents in Detai l Problem: Convert Character Digit to Integer ...................................................... 35 Problem: Luhn Checksum Validation, Fixed Length ............................................ 36 Problem: Simple Checksum Validation, Fixed Length ......................................... 36 Problem: Positive or Negative .......................................................................... 39 Putting the Pieces Together ......................................................................... 39 Tracking State ........................................................................................................ 41 Problem: Decode a Message ............................................................................ 41 Problem: Reading a Number with Three or Four Digits ...................................... 45 Problem: Reading a Number with Three or Four Digits, Further Simplified .......... 46 Conclusion ............................................................................................................ 53 Exercises ............................................................................................................... 53 3 SOLVING PROBLEMS WITH ARRAYS 55 Review of Array Fundamentals ................................................................................. 56 Store ....................................................................................................... 56 Copy ....................................................................................................... 57 Retrieval and Search ................................................................................. 57 Sort ........................................................................................................ 59 Compute Statistics ..................................................................................... 61 Solving Problems with Arrays ................................................................................... 62 Problem: Finding the Mode .............................................................................. 62 Refactoring ............................................................................................... 65 Arrays of Fixed Data .............................................................................................. 67 Non-scalar Arrays .................................................................................................. 69 Multidimensional Arrays .......................................................................................... 71 Deciding When to Use Arrays ................................................................................. 74 Exercises ............................................................................................................... 78 4 SOLVING PROBLEMS WITH POINTERS AND DYNAMIC MEMORY 81 Review of Pointer Fundamentals ............................................................................... 82 Benefits of Pointers ................................................................................................. 83 Runtime-Sized Data Structures ..................................................................... 83 Resizable Data Structures ........................................................................... 83 Memory Sharing ....................................................................................... 84 When to Use Pointers ............................................................................................. 84 Memory Matters ..................................................................................................... 85 The Stack and the Heap ............................................................................. 86 Memory Size ............................................................................................ 88 Lifetime .................................................................................................... 90 Solving Pointer Problems ......................................................................................... 91 Variable-Length Strings ............................................................................... 91 Problem: Variable-Length String Manipulation .................................................. 91 Linked Lists ............................................................................................. 101 Problem: Tracking an Unknown Quantity of Student Records ........................... 101 Conclusion and Next Steps ................................................................................... 108 Exercises ............................................................................................................. 109

Contents in Detai l ix 5 SOLVING PROBLEMS WITH CLASSES 111 Review of Class Fundamentals ............................................................................... 112 Goals of Class Use ............................................................................................... 113 Encapsulation ......................................................................................... 114 Code Reuse ............................................................................................ 114 Dividing the Problem ............................................................................... 115 Information Hiding .................................................................................. 115 Readability ............................................................................................. 117 Expressiveness ........................................................................................ 117 Building a Simple Class ........................................................................................ 118 Problem: Class Roster .................................................................................... 118 The Basic Class Framework ...................................................................... 119 Support Methods ..................................................................................... 122 Classes with Dynamic Data ................................................................................... 125 Problem: Tracking an Unknown Quantity of Student Records ........................... 126 Adding a Node ...................................................................................... 128 Rearranging the List ................................................................................. 130 Destructor ............................................................................................... 133 Deep Copy ............................................................................................. 134 The Big Picture for Classes with Dynamic Memory ....................................... 139 Mistakes to Avoid ................................................................................................ 140 The Fake Class ........................................................................................ 140 Single-Taskers ......................................................................................... 141 Exercises ............................................................................................................. 141 6 SOLVING PROBLEMS WITH RECURSION 143 Review of Recursion Fundamentals ......................................................................... 144 Head and Tail Recursion ....................................................................................... 144 Problem: How Many Parrots? ......................................................................... 144 Approach 1 ............................................................................................ 145 Approach 2 ............................................................................................ 146 Problem: Who’s Our Best Customer? .............................................................. 148 Approach 1 ............................................................................................ 149 Approach 2 ............................................................................................ 151 The Big Recursive Idea .......................................................................................... 152 Problem: Computing the Sum of an Array of Integers ...................................... 153 Common Mistakes ................................................................................................ 155 Too Many Parameters .............................................................................. 155 Global Variables ..................................................................................... 156 Applying Recursion to Dynamic Data Structures ....................................................... 158 Recursion and Linked Lists ........................................................................ 158 Problem: Counting Negative Numbers in a Singly Linked List ........................... 159 Recursion and Binary Trees ...................................................................... 160 Problem: Find the Largest Value in a Binary Tree ............................................. 162 Wrapper Functions ............................................................................................... 163 Problem: Find the Number of Leaves in a Binary Tree ...................................... 163 When to Choose Recursion ................................................................................... 165 Arguments Against Recursion .................................................................... 166

x Contents in Detai l Problem: Display a Linked List in Order .......................................................... 168 Problem: Display a Linked List in Reverse Order .............................................. 168 Exercises ............................................................................................................. 170 7 SOLVING PROBLEMS WITH CODE REUSE 171 Good Reuse and Bad Reuse .................................................................................. 172 Review of Component Fundamentals ...................................................................... 173 Code Block ............................................................................................ 173 Algorithms .............................................................................................. 173 Patterns .................................................................................................. 174 Abstract Data Types ................................................................................ 175 Libraries ................................................................................................. 175 Building Component Knowledge ............................................................................ 176 Exploratory Learning ................................................................................ 176 Problem: The First Student .............................................................................. 177 As-Needed Learning ................................................................................ 180 Problem: Efficient Traversal ............................................................................ 180 Choosing a Component Type ................................................................................ 188 Component Choice in Action .................................................................... 189 Problem: Sorting Some, Leaving Others Alone ................................................ 189 Comparing the Results ............................................................................. 193 Exercises ............................................................................................................. 193 8 THINKING LIKE A PROGRAMMER 195 Creating Your Own Master Plan ............................................................................ 196 Playing to Your Strengths and Weaknesses ................................................ 196 Putting the Master Plan Together ............................................................... 202 Tackling Any Problem ........................................................................................... 203 Problem: Cheating at Hangman ..................................................................... 204 Finding a Way to Cheat .......................................................................... 205 Required Operations for Cheating at Hangman .......................................... 206 Initial Design .......................................................................................... 208 Initial Coding .......................................................................................... 210 Analysis of Initial Results .......................................................................... 217 The Art of Problem Solving ....................................................................... 218 Learning New Programming Skills .......................................................................... 219 New Languages ...................................................................................... 219 New Skills for a Language You Already Know ............................................ 222 New Libraries ......................................................................................... 223 Take a Class ........................................................................................... 223 Conclusion .......................................................................................................... 224 Exercises ............................................................................................................. 225 INDEX 227

A C K N O W L E D G M E N T S No book is truly the work of one author, and I’ve received lots of help on Think Like a Programmer. I’m grateful to everyone at No Starch Press, especially Keith Fancher and Alison Law, who edited, shaped, and shepherded the book throughout its production. I must also thank Bill Pollock for his decision to sign me up in the first place—I hope he is as pleased with the result as I am. The folks at No Starch have been unfailingly kind and helpful in their correspondence with me. I hope one day to meet them in person and see to what degree they resemble their cartoon avatars on the company website. Dan Randall did a wonderful job as technical editor. His numerous sug- gestions beyond the technical review helped me strengthen the manuscript in many areas. On the home front, the most important people in my life, Mary Beth and Madeline, provided love, support, and enthusiasm—and, crucially, time to write. Finally, to all the students of programming I’ve had over the years: Thank you for letting me be your teacher. The techniques and strategies described in this book were developed through our joint efforts. I hope we’ve made the journey easier for the next generation of programmers.

C O DE E A T SLEEP I N T R O D U C T I O N Do you struggle to write programs, even though you think you understand program- ming languages? Are you able to read through a chapter in a programming book, nodding your head the whole way, but unable to apply what you’ve read to your own programs? Are you able to comprehend a program example you’ve read online, even to the point where you could explain to someone else what each line of the code is doing, yet you feel your brain seize up when faced with a programming task and a blank screen in your text editor? You’re not alone. I have taught programming for over 15 years, and most of my students would have fit this description at some point in their instruc- tion. We will call the missing skill problem solving, the ability to take a given problem description and write an original program to solve it. Not all pro- gramming requires extensive problem solving. If you’re just making minor modifications to an existing program, debugging, or adding testing code, the

xiv In t roduct ion programming may be so mechanical in nature that your creativity is never tested. But all programs require problem solving at some point, and all good programmers can solve problems. Problem solving is hard. It’s true that a few people make it look easy— the “naturals,” the programming world’s equivalent of a gifted athlete, like Michael Jordan. For these select few, high-level ideas are effortlessly translated into source code. To make a Java metaphor, it’s as if their brains execute Java natively, while the rest of us have to run a virtual machine, interpreting as we go. Not being a natural isn’t fatal to becoming a programmer—if it were, the world would have few programmers. Yet I’ve seen too many worthy learners struggle too long in frustration. In the worst cases, they give up programming entirely, convinced that they can never be programmers, that the only good programmers are those born with an innate gift. Why is learning to solve programming problems so hard? In part, it’s because problem solving is a different activity from learning programming syntax and therefore uses a different set of mental “muscles.” Learning programming syntax, reading programs, memorizing elements of an application programming interface—these are mostly analytical “left brain” activities. Writing an original program using previously learned tools and skills is a creative “right brain” activity. Suppose you need to remove a branch that has fallen into one of the rain gutters on your house, but your ladder isn’t quite long enough for you to reach the branch. You head into your garage and look for something, or a combination of things, that will enable you to remove the branch from the gutter. Is there some way to extend the ladder? Is there something you can hold at the top of the ladder to grab or dislodge the branch? Maybe you could just get on the roof from another place and get the branch from above. That’s problem solving, and it’s a creative activity. Believe it or not, when you design an original program, your mental process is quite similar to that of the person figuring out how to remove the branch from the gutter and quite different from that of a person debugging an existing for loop. Most programming books, though, focus their attention on syntax and semantics. Learning the syntax and semantics of a programming language is essential, but it’s only the first step in learning how to program in that lan- guage. In essence, most programming books for beginners teach how to read a program, not how to write one. Books that do focus on writing are often effectively “cookbooks” in that they teach specific “recipes” for use in particu- lar situations. Such books can be quite valuable as time savers, but not as a path toward learning to write original code. Think about cookbooks in the original sense. Although great cooks own cookbooks, no one who relies upon cookbooks can be a great cook. A great cook understands ingredients, prepa- ration methods, and cooking methods and knows how they can be combined to make great meals. All a great cook needs to produce a tasty meal is a fully stocked kitchen. In the same way, a great programmer understands language syntax, application frameworks, algorithms, and software engineering princi- ples and knows how they can be combined to make great programs. Give a great programmer a list of specifications, turn him loose with a fully stocked programming environment, and great things will happen.

In t roduct ion xv In general, current programming education doesn’t offer much guidance in the area of problem solving. Instead, it’s assumed that if programmers are given access to all of the tools of programming and requested to write enough programs, eventually they will learn to write such programs and write them well. There is truth in this, but “eventually” can be a long time. The journey from initiation to enlightenment can be filled with frustration, and too many who start the journey never reach the destination. Instead of learning by trial and error, you can learn problem solving in a systematic way. That’s what this book is all about. You can learn techniques to organize your thoughts, procedures to discover solutions, and strategies to apply to certain classes of problems. By studying these approaches, you can unlock your creativity. Make no mistake: Programming, and especially prob- lem solving, is a creative activity. Creativity is mysterious, and no one can say exactly how the creative mind functions. Yet, if we can learn music composi- tion, take advice on creative writing, or be shown how to paint, then we can learn to creatively solve programming problems, too. This book isn’t going to tell you precisely what to do; it’s going to help you develop your latent problem-solving abilities so that you will know what you should do. This book is about helping you become the programmer you are meant to be. My goal is for you and every other reader of this book to learn to system- atically approach every programming task and to have the confidence that you will ultimately solve a given problem. When you complete this book, I want you to think like a programmer and to believe that you are a programmer. About This Book Having explained the necessity of this book, I need to make a few comments about what this book is and what it is not. Prerequisites This book assumes you are already familiar with the basic syntax and seman- tics of the C++ language and that you have begun writing programs. Most of the chapters will expect you to know specific C++ fundamentals; these chap- ters will begin with a review of those fundamentals. If you are still absorbing language basics, don’t worry. There are plenty of great books on C++ syntax, and you can learn problem solving in parallel to learning syntax. Just make sure you have studied the relevant syntax before attempting to tackle a chap- ter’s problems. Chosen Topics The topics covered in this book represent areas in which I have most often seen new programmers struggle. They also present a broad cross-section of different areas in early and intermediate programming. I should emphasize, however, that this is not a “cookbook” of algorithms or patterns for solving specific problems. Although later chapters discuss how to employ well-known algorithms or patterns, you should not use this D ow n lo a d f ro m W o w ! e B o o k < w w w .w o w e b o o k. co m >

xvi In t roduct ion book as a “crib sheet” to get you past particular problems or focus on just the chapters that directly relate to your current struggles. Instead, I would work through the entire book, skipping material only if you lack the prerequisites needed to follow the discussion. Programming Style A quick note here about the programming style employed in this book: This book is not about high-performance programming or running the most com- pact, efficient code. The style I have chosen for the source code examples is intended to be readable above all other considerations. In some cases, I take multiple steps to accomplish something that could be done in one step, just so the principle I’m trying to demonstrate is made clear. Some aspects of programming style will be covered in this book—but larger issues, like what should or should not be included in a class, not small issues, like how code should be indented. As a developing programmer, you will of course want to employ a consistent, readable style in all of the work you do. Exercises The book includes a number of programming exercises. This is not a text- book, and you won’t find answers to any of the exercises in the back. The exercises provide opportunities for you to apply the concepts described in the chapters. Whether you choose to try any of the exercises is, of course, up to you, but it is essential that you put these concepts into practice. Simply reading through the book will accomplish nothing. Remember that this book is not going to tell you exactly what to do in each situation. In applying the techniques shown in this book, you will develop your own ability to discover what to do. Furthermore, growing your confidence, another primary goal of this book, requires success. In fact, that’s a good way to know when you have worked through enough exercises in a given problem area: when you are con- fident that you can tackle other problems in the area. Lastly, programming exercises should be fun. While there may be moments where you’d rather be doing something else, working out a programming problem should be a rewarding challenge. You should think of this book as an obstacle course for your brain. Obstacle courses build strength, stamina, and agility and give the trainer confidence. By reading through the chapters and applying the concepts to as many exer- cises as you can, you’re going to build confidence and develop problem-solving skills that can be used in any programming situation. In the future, when you are faced with a difficult problem, you’ll know whether you should try going over, under, or through it.

In t roduct ion xvii Why C++? The programming examples in this text are coded using C++. Having said that, this book is about solving problems with programs, not specifically about C++. You won’t find many tips and tricks specific to C++ here, and the general concepts taught throughout this book can be employed in any pro- gramming language. Nevertheless, you can’t discuss programming without discussing programs, and a specific language had to be chosen. C++ was selected for a number of reasons. First, it’s popular in a variety of problem areas. Second, because of its origins in the strictly procedural C language, C++ code can be written using both the procedural and object- oriented paradigms. Object-oriented programming is so common now that it could not be omitted from a discussion on problem solving, but many funda- mental problem-solving concepts can be discussed in strictly procedural programming terms, and doing so simplifies both the code and the discus- sion. Third, as a low-level language with high-level libraries, C++ allows us to discuss both levels of programming. The best programmers can “hand-wire” solutions when required and make use of high-level libraries and application programming interfaces to reduce development time. Lastly, and partly as a function of the other reasons listed, C++ is a great choice because once you have learned to solve problems in C++, you have learned to solve problems in any programming language. Many programmers have discovered how the skills learned in one language easily apply to other languages, but this is espe- cially true for C++ because of its cross-paradigm approach and, frankly, because of its difficulty. C++ is the real deal—it’s programming without training wheels. This is daunting at first, but once you start succeeding in C++, you’ll know that you’re not going to be someone who can do a little coding—you’re going to be a programmer.