Kotlin from Scratch A Project-Based Introduction for the Intrepid Programmer (Faisal Islam) (Z-Library)

® A P R O J E C T - B A S E D I N T R O D U C T I O N F O R T H E I N T R E P I D P R O G R A M M E R F A I S A L I S L A M K O T L I N F R O M S C R A T C H

KOTLIN FROM SCRATCH

® KO T L I N F R O M S C R AT C H A P r o j e c t - B a s e d I n t r o d u c t i o n f o r t h e I n t r e p i d P r o g r a m m e r by Faisal Is lam San Francisco

[E] KOTLIN FROM SCRATCH. Copyright © 2025 by Faisal Islam. 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 ISBN-13: 978-1-7185-0352-6 (print) ISBN-13: 978-1-7185-0353-3 (ebook) Published by No Starch Press®, Inc. 245 8th Street, San Francisco, CA 94103 phone: +1.415.863.9900 www .nostarch .com; info@nostarch .com Publisher: William Pollock Managing Editor: Jill Franklin Production Manager: Sabrina Plomitallo-González Production Editor: Jennifer Kepler Developmental Editors: Nathan Heidelberger and Abigail Schott-Rosenfield Cover Illustrator: Josh Kemble Interior Design: Octopod Studios Technical Reviewer: Anton Arhipov Copyeditor: James Brook Proofreader: Audrey Doyle Indexer: BIM Creatives, LLC Figure 9-3, created by Aiyaan Faisal, has been reproduced with permission. Library of Congress Cataloging-in-Publication Data Names: Islam, Faisal (Author of books on computer programming), author. Title: Kotlin from scratch : A project-based introduction for the intrepid programmer / by Faisal Islam. Description: San Francisco : No Starch Press, [2025] | Includes index. Identifiers: LCCN 2024023794 (print) | LCCN 2024023795 (ebook) | ISBN 9781718503526 (paperback) | ISBN 9781718503533 (ebook) Subjects: LCSH: Kotlin (Computer program language) | Functional programming (Computer science) Classification: LCC QA76.73.K68 I85 2025 (print) | LCC QA76.73.K68 (ebook) | DDC 005.13/3--dc23/eng20240805 LC record available at https://lccn.loc.gov/2024023794 LC ebook record available at https://lccn.loc.gov/2024023795 For customer service inquiries, please contact info@nostarch .com. For information on distribution, bulk sales, corporate sales, or translations: sales@nostarch .com. For permission to translate this work: rights@nostarch .com. To report counterfeit copies or piracy: counterfeit@nostarch .com. No Starch Press and the No Starch Press iron 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. ®

To Saila and Aiyaan, for their unwavering patience and steadfast support, and to all the curious minds

About the Author Faisal Islam is a manager, educator, developer, and author of both fiction and nonfiction. With over two decades of coding experience in languages such as C, Java, Python, and Kotlin, he thrives on solving complex real- world challenges. Faisal’s background in engineering and economics equips him with a unique perspective, allowing him to apply computational think- ing, modeling, simulation, and optimization techniques effectively. Beyond his technical pursuits, Faisal is an advocate for STEM educa- tion, particularly among young learners. His passion lies in inspiring the next generation of coders. In his spare time, Faisal enjoys photography, sci-fi novels, and traveling with his family. About the Technical Reviewer Anton Arhipov is a developer advocate for the Kotlin team at JetBrains. With a professional background in server-side development, Anton has been building tools for developers for over a decade. Recognized as a Java Champion since 2014, he often presents as a speaker at large software devel- opment conferences.

B R I E F C O N T E N T S Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi PART I: PROGRAMMING FUNDAMENTALS . . . . . . . . . . . . . . . . . . . . . . . . .1 Chapter 1: Kotlin Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chapter 2: Arrays, Collections, and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Chapter 3: Visualizing with JavaFX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 PART II: APPLICATIONS IN MATH AND SCIENCE . . . . . . . . . . . . . . . . . . .125 Chapter 4: Solving Mathematical Problems with Code . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Chapter 5: Modeling and Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 PART III: RECURSION, SORTING, AND SEARCHING . . . . . . . . . . . . . . . .223 Chapter 6: Recursive Functions and Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Chapter 7: Sorting and Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 PART IV: OPTIMIZATION WITH NATURE-INSPIRED ALGORITHMS . . . . . . .303 Chapter 8: The Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Chapter 9: Agent-Based Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 Afterword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

C O N T E N T S I N D E T A I L ACKNOWLEDGMENTS xix INTRODUCTION xxi The Power of Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii Why Kotlin? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii Who Is This Book For? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxiii What’s in This Book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxiv The Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxx Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxx PART I: PROGRAMMING FUNDAMENTALS 1 1 KOTLIN BASICS 3 Using Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Common Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Unary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Relational . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Logical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Working with Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 String Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Escape Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Null and Nullable Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Conditional Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Built-in Mathematical Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Custom Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Scope Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Lambda Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Basic Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Console-Based Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Simple File Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Project 1: Build a Console-Based Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

xii   Contents in Detail Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Resource . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2 ARRAYS, COLLECTIONS, AND CLASSES 47 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Primitive Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 The Array Constructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Array Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Multidimensional Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 An Introduction to Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 The init Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 The this Keyword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Inheritance and Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Common Classes and Custom Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Data Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Pairs and Triples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Enum Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Copying Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Shallow Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Deep Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Project 2: Build a Versatile Task Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Resource . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3 VISUALIZING WITH JAVAFX 87 Data Visualization Tools for Kotlin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 An Overview of JavaFX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Key Functionalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Project 3: Build “Hello, World!” in JavaFX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 The JavaFX Object Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 The Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Scenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Layout Containers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Child Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Contents in Detail   xiii Creating JavaFX Charts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Project 4: Visualize Data as a Bar Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Project 5: Create a Multiseries Line Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Drawing with the Canvas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 A Simple Shape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Common Graphics Context Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Project 6: Draw a Spiral Seashell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Animation in JavaFX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Project 7: Animate a Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Project 8: Animate a Bouncing Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Setting Keyframes Explicitly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Using an Action Event Listener . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 PART II: APPLICATIONS IN MATH AND SCIENCE 125 4 SOLVING MATHEMATICAL PROBLEMS WITH CODE 127 Project 9: Find the Square Root with the Babylonian Algorithm . . . . . . . . . . . . . . . . . . . 128 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Project 10: Create Pythagorean Triples with Euclid’s Formula . . . . . . . . . . . . . . . . . . . . 130 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Project 11: Identify Prime Numbers with the Sieve of Eratosthenes . . . . . . . . . . . . . . . . 133 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Project 12: Calculate Earth’s Circumference the Ancient Way . . . . . . . . . . . . . . . . . . . . 136 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Project 13: Code the Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 The Golden Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 The Fibonacci Spiral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Project 14: Find the Shortest Distance Between Two Locations on Earth . . . . . . . . . . . . . 148 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

xiv   Contents in Detail Project 15: Do Encryption with the Hill Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 How It Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Project 16: Simulate a One-Dimensional Random Walk . . . . . . . . . . . . . . . . . . . . . . . . 164 A One-Dimensional Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 5 MODELING AND SIMULATION 175 Project 17: Predict the Flight of a Cannonball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Project 18: Design a Fountain with Water Jets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Project 19: Track a Pendulum’s Motion and Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 The Motion of a Simple Pendulum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Project 20: The Physics of Coffee Cooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 Newton’s Law of Cooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 The Effect of Mixing Liquids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Project 21: Simulate a Binary Star System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 The Science of Binary Star Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 PART III: RECURSION, SORTING, AND SEARCHING 223 6 RECURSIVE FUNCTIONS AND FRACTALS 225 The Concept of Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

Contents in Detail   xv Project 22: The “Hello, World!” of Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 Project 23: Draw the Sierpiński Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Project 24: Create a Fractal Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 The L-System and Turtle Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 Formalizing the L-System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 Drawing L-System Patterns with Turtle Graphics . . . . . . . . . . . . . . . . . . . . . . 243 Project 25: Design an L-System Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 The Mighty Mandelbrot Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Project 26: Code and Visualize the Mandelbrot Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 7 SORTING AND SEARCHING 265 Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 Project 27: Space-Efficient Sorting with Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 268 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 Project 28: Faster Sorting with Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 Project 29: High-Efficiency Sorting with Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 What Is a Graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 How to Search a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 Project 30: Stack-Based Searching with Depth-First Search . . . . . . . . . . . . . . . . . . . . . . 280 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Project 31: Queue-Based Searching with Breadth-First Search . . . . . . . . . . . . . . . . . . . 284 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 Project 32: Heuristic Searching with A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 The Heuristic Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

xvi   Contents in Detail PART IV: OPTIMIZATION WITH NATURE-INSPIRED ALGORITHMS 303 8 THE GENETIC ALGORITHM 305 Nature-Inspired Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 The Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 When to Use NIAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 An Overview of the Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 Genetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Elitism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Project 33: Evolve Gibberish into Shakespeare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 Project 34: Solve the Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 Project 35: Optimize a Multivariate Function with the Genetic Algorithm . . . . . . . . . . . . 332 The Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 Stopping Condition for Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 9 AGENT-BASED ALGORITHMS 345 An Overview of Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 Implementing PSO for Function Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Project 36: Optimize a Multivariate Function with a Particle Swarm . . . . . . . . . . . . . . . 350 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 The ACS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 Symbols and Their Meanings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 The Steps of ACS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 Project 37: Solve the Traveling Salesman Problem with an Ant Colony System . . . . . . . . 361 The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 The Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376

Contents in Detail   xvii AFTERWORD 379 APPENDIX 381 Key Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 Workflow for Creating an App . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 Setting Up Shop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Step 1: Download and Install IntelliJ IDEA . . . . . . . . . . . . . . . . . . . . . . . . . 384 Step 2: Download and Set Up the JDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 Step 3: Create a New Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 INDEX 389