Algorithmic Thinking A Problem-Based Introduction (Early Access) (Daniel Zingaro) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 3.8 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

EAR LY ACCE SS

📄 Page 2

N O S T A R C H P R E S S E A R LY A C C E S S P R O G R A M : F E E D B A C K W E L C O M E ! Welcome to the Early Access edition of the as yet unpublished Algorithmic Thinking by Daniel Zingaro! As a prepublication title, this book may be incomplete and some chapters may not have been proofread. Our goal is always to make the best books possible, and we look forward to hearing your thoughts. If you have any comments or questions, email us at earlyaccess@nostarch.com. If you have specific feedback for us, please include the page number, book title, and edition date in your note, and we’ll be sure to review it. We appreciate your help and support! We’ll email you as new chapters become available. In the meantime, enjoy!

📄 Page 3

A L G O R I T H M I C T H I N K I N G : A P R O B L E M - B A S E D I N T R O D U C T I O N D A N I E L Z I N G A R O Early Access edition, 8/17/20 Copyright © 2020 by Daniel Zingaro. ISBN-13: 978-1-7185-0080-8 (print) ISBN-13: 978-1-7185-0081-5 (ebook) Publisher: William Pollock Executive Editor: Barbara Yien Developmental Editor: Alex Freed Production Editor: Kassie Andreadis Cover Illustration: Rob Gale Technical Reviewer: Larry Zhang Copyeditor: David Couzens Proofreader: James Fraleigh 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 trade- marked 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. 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 informa- tion storage or retrieval system, without the prior written permission of the copyright owner and the publisher. 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.

📄 Page 4

C O N T E N T S Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi Chapter 1: Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chapter 2: Trees and Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Chapter 3: Memoization and Dynamic Programming . . . . . . . . . . . . 71 Chapter 4: Graphs and Breadth-First Search . . . . . . . . . . . . . . . . . 119 Chapter 5: Shortest Paths in Weighted Graphs . . . . . . . . . . . . . . . 165 Chapter 6: Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Chapter 7: Heaps and Segment Trees . . . . . . . . . . . . . . . . . . . . . 241 Chapter 8: Union-Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Afterword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 Appendix A: Algorithm Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 339 Appendix B: Because I Can’t Resist . . . . . . . . . . . . . . . . . . . . . . . 345 Appendix C: Problem Credits . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 The chapters in red are included in this Early Access PDF.

📄 Page 5

INTRODUCT ION I’m assuming that you’ve learned to use a programming language such as C, C++, Java, or Python . . . and I’m hoping that you’re hooked. It’s hard to explain to nonprogram- mers why solving problems through programming is so rewarding and fun. I’m also hoping that you’re ready to take your programming skill to the next level. I have the privilege of helping you do that. I could start by teaching you some fancy new techniques, telling you why they’re useful, and comparing them to other fancy techniques, but I won’t. That material would lay inert, holding on for a little, waiting for the opportu- nity to spring into action—if in fact some opportunity ever did present itself. Instead, what I do throughout this book is pose problems: hard prob- lems. These are problems that I hope you cannot solve, problems that I hope stymie your current approaches. You’re a programmer. You want to solve problems. Now it’s time for learning those fancy techniques. This book is all about posing hard problems and then solving them by bridging between what you know and what you need. You won’t see traditional textbook problems here. You won’t find an op- timal way to multiply a chain of matrices or compute Fibonacci numbers. I promise: you won’t solve the Towers of Hanoi puzzle. There are many excel- Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 6

lent textbooks out there that do these things, but I suspect that many people are not motivated by those kinds of puzzles. My approach is to use new problems that you haven’t seen before. Ev- ery year, thousands of people participate in programming competitions, and these competitions require new problems to avoid simply measuring which participants can rehash or google the fastest. These problems are fas- cinating, riffing on the classics while adding twists and context to challenge people to find new solutions. There is a seemingly endless stream of pro- gramming and computing knowledge encompassed by these problems. We can learn as much as we like by choosing the right problems. Let’s start with some basics. A data structure is a way to organize data so that desirable operations are fast. An algorithm is a sequence of steps that solves a problem. Sometimes we can make fast algorithms without sophis- ticated data structures; other times, the right data structure can offer a sig- nificant speed boost. My goal is not to turn you into a competitive program- mer, though I’d take that as a happy side benefit. Rather, my goal is to teach you data structures and algorithms using problems from the competitive programming world—and to have fun while doing so. Email me if you have learned. Email me if you have laughed. Who This Book Is For This book is for any programmer who wants to learn how to solve tough problems. You’ll learn many data structures and algorithms, their benefits, the types of problems they can help you solve, and how to implement them. As explored further in the next section, all code in this book is written in the C programming language. However, this isn’t a book on learning C. If your prior programming experience is in C or C++, then jump right in. If instead you’ve programmed in a language such as Java or Python, I sus- pect that you’ll pick up most of what you need by reading, but you may wish to review some C concepts now or on first encounter. In particular, I’ll use pointers and dynamic memory allocation, so, no matter what your prior ex- perience, you may like to brush up on those topics. The best C book I can recommend is C Programming: A Modern Approach, 2nd Edition, by K. N. King. Even if you’re OK with C, read it anyway. It’s that good and a won- derful companion any time you get tripped up by C stuff. The Programming Language I’ve chosen to use C as the programming language for this book, rather than some higher level language such as C++ or Java or Python. I’ll briefly discuss why and also justify a couple of other C-related decisions I’ve made. Why Use C? The primary reason for using C is that I want to teach you data structures and algorithms from the ground up. When we want a hash table, we’ll build xxii Introduction Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 7

it ourselves. There will be no reliance on dictionaries or hashmaps or simi- lar data structures of other languages. When we don’t know the maximum length of a string, we’ll build an extensible array: we won’t let the language handle memory allocation for us. I want you to know exactly what’s going on, with no tricks up my sleeve. Using C helps me toward this goal. Solving programming problems in C, as we do in this book, is a use- ful primer should you decide to continue with C++. If you become serious about competitive programming, then you’ll be happy to know that C++ is the most popular language used by competitive programmers, thanks to its rich standard library and ability to generate code that favors speed. Static Keyword Regular local variables are stored on what’s called the call stack. On each call of a function, some of the call stack memory is used to store local vari- ables. Then, when the function returns, that memory is freed up for other local variables to use later. The call stack is small, though, and isn’t appro- priate for some of the massive arrays that we’ll meet in this book. Enter the static keyword. When used on a local variable, it changes the storage dura- tion from automatic to static, which means that the variable maintains its value between function calls. As a side effect, these variables are not stored in memory along with regular local variables, since then their values would be lost when a function terminated. Consequently, they’re stored in their own, separate segment of memory, where they don’t have to compete with whatever else might be on the call stack. One thing to watch out for with this static keyword is that such local variables are only initialized once! For a quick example, see Listing 1. int f(void) { ¶ static int x = 5; printf("%d\n", x); x++; } int main(void) { f(); f(); f(); return 0; } Listing 1: A local variable with a static keyword I’ve used static on local variable x ¶. Without that, you’d expect 5 to be printed three times. However, since static is there, you should see this output instead: 5 6 Introduction xxiii Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 8

7 Include Files To save space in the boilerplate, I don’t include the #include lines that should be added to the start of C programs. You’ll be safe if you include the follow- ing: #include <stdio.h> #include <stdlib.h> #include <string.h> Freeing Memory Unlike Java or Python, C requires the programmer to free all memory that is manually allocated. The pattern is to allocate memory using malloc, use that memory, and then free the memory using free. For two reasons, though, I do not free memory here. First, freeing mem- ory adds clutter, distracting from the primary teaching purpose of the code. Second, these programs are not long-lived: your program will run on a few test cases, and that’s it. The operating system reclaims all of the unfreed memory on program termination, so there’s nothing to worry about even if you run a program many times. Of course, not freeing memory is quite ir- responsible in practice: no one is happy with a program that consumes more and more memory as it runs. If you’d like to practice freeing memory, you can add calls of free to the programs presented in this book. Topics The fields of data structures and algorithms are too large to be corralled by one book (or by this one author!). I used three criteria to help me decide what topics made the cut. First, I chose topics of broad applicability: each can be used to solve not only the corresponding problems in the book but many other problems as well. In each chapter, I focus on at least two problems. I generally use the first problem to introduce the data structure or algorithm and one of its pro- totypical uses. The other problems are meant to give a sense of what else the data structure or algorithm can do. For example, in Chapter 5, we study Dijkstra’s algorithm. If you google it, you’ll see that Dijkstra’s algorithm is used to find shortest paths. Indeed, in the first problem of the chapter, we use it for that very purpose. However, in the second problem, we go further, tweaking Dijkstra’s algorithm to find not only the shortest path but also the number of shortest paths. I hope that, as you progress through each chap- ter, you learn more and more about the affordances, constraints, and sub- tleties of each technique. xxiv Introduction Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 9

Second, I chose topics whose implementation did not overwhelm the surrounding discussion. I wanted the solution to any problem to top out at around 150 lines. That includes reading the input, solving the problem itself, and producing the output. A data structure or algorithm whose imple- mentation took 200 or 300 lines was for practical reasons not suitable. Third, I chose topics that lend themselves to correctness arguments that I hope are convincing and intuitive. Teaching you specific data structures and algorithms is of course one of my goals, because I am imagining that you’re here to learn powerful problem-solving approaches and how to im- plement them. Meanwhile, I’m also hoping that you’re interested in why what you’re learning works, so I have more quietly pursued another goal: convincing you that the data structure or algorithm is correct. There won’t be formal proofs or anything like that. Nonetheless, if I have succeeded in my secret goal, then you’ll learn about correctness right along with the data structure or algorithm. Don’t be content in merely tracing code and mar- veling that it magically works every time. There is no magic, and the insights that make code tick are within your grasp, just as is the code itself. If you’d like to go beyond the chapters of this book, I recommend check- ing Appendix B. There, I’ve included some additional material related to Chapters 1, 3, 4, 7, and 8. Many readers will benefit by practicing or reading additional material as they progress through the book. The Notes sections at the end of the chapters point to additional resources. Many of them contain further ex- amples and sample problems. There are also online resources that offer a curated, categorized list of problems and their solution strategies. The Meth- ods to Solve page by Steven Halim and Felix Halim is the most comprehensive that I’ve found: see https://cpbook.net/methodstosolve. Judges Each problem that I have chosen is available on a programming-judge web- site. There are many such websites out there, each of which generally con- tains hundreds of problems. I’ve tried to keep the number of judges that we use small but large enough to give me the flexibility to choose the most ap- propriate problems. For each judge website, you’ll require a username and password; it’s worth setting up your accounts now so that you don’t have to stop to do so while working through the book. Here are the judges that we’ll use: Judge URL Codeforces codeforces.com DMOJ dmoj.ca Kattis open.kattis.com POJ poj.org SPOJ spoj.com UVa uva.onlinejudge.org Introduction xxv Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 10

Each problem description begins by indicating the judge website where the problem can be found and the particular problem code that you should use to access it. While some problems on the judge websites are written by individual contributors, others are originally from well-known competitions. Here are some of the competitions from which problems in this book originate: International Olympiad in Informatics (IOI): this is a prestigious an- nual competition for high school students. Each participating country sends up to four participants, but each participant competes individu- ally. The competition runs over two days, with multiple programming tasks on each day. Canadian Computing Competition (CCC) and Canadian Comput- ing Olympiad (CCO): these annual competitions are for high school students and are organized by the University of Waterloo. CCC (also known as stage 1) takes place at individual schools, with the top per- formers moving on to take the CCO (also known as stage 2) at the Uni- versity of Waterloo. The top performers in stage 2 represent Canada at the IOI. When I was a high school student, I participated in the CCC, but I never made it to the CCO—I wasn’t even close. DWITE: this was an online programming contest designed to help students practice for annual competitions. Unfortunately, DWITE is no longer running, but the old problems—and they are good ones!—are still available. ACM East Central North America (ECNA) Regional Programming Contest: this is an annual competition for university students. The top performers are invited to the annual ACM International Collegiate Pro- gramming Contest (ICPC) world finals. Unlike the other competitions here, where students compete individually, ECNA and the world finals competitions are team competitions. South African Programming Olympiad (SAPO): this competition is offered in three rounds per year. The rounds increase in difficulty, from Round 1 to Round 2 to the Final Round. Performance is used to select students to represent South Africa at the IOI. Croatian Open Competition in Informatics (COCI): this online com- petition is offered many times per year. Performance is used to deter- mine the Croatian IOI team. USA Computing Olympiad (USACO): this online competition is of- fered several times per year, the most challenging of which is the US Open competition. In each competition, you’ll encounter four levels of problems: bronze (easiest), silver, gold, and platinum (hardest). Perfor- mance is used to determine the American IOI team. See Appendix C for the source of each problem in the book. When you submit code for a problem, the judge compiles your program and runs it on test cases. If your program passes all test cases, and does so xxvi Introduction Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 11

within the allotted time, then your code is accepted as correct; judges show AC for accepted solutions. If your program fails one or more test cases, then your program is not accepted; judges show WA (for “Wrong Answer”) in these cases. A final popular outcome is for when your program is too slow, in which case judges show TLE (“Time-Limit Exceeded”) here. Note that TLE does not mean that your code is otherwise correct: if your code times out, the judges do not run any further test cases, so there may be some WA bugs hidden behind the TLE. At the time of publication, my solution for each problem passes all test cases within the allotted time with the specified judge. Within those base re- quirements, my aim has been to make the code readable and to choose clar- ity over speed. This is a book about teaching data structures and algorithms, not squeezing further performance out of a program that otherwise gets the job done. Anatomy of a Problem Description Before solving a problem, we must be precise about what we are being asked to do. This precision is required not only in understanding the task itself but also in the way that we should read input and produce output. For this rea- son, each problem begins with a problem description of three components: The Problem Here, I provide the context for the problem and what we are being asked to do. It’s important to read this material carefully so that you know exactly what problem we’re solving. Sometimes, mis- reading or misinterpreting seemingly small words can lead to incorrect solutions. For example, one of our problems asks us to buy “at least” a certain number of apples: if you instead buy “exactly” that many apples, your program will fail some of the test cases. Input The author of the problem provides test cases, all of which must be passed for a submission to be deemed correct. It’s our responsibility to read each test case from the input so that we can process it. How do we know how many test cases there are? What is on each line of each test case? If there are numbers, what are their ranges? If there are strings, how long can they be? All of this information is provided here. Output It can be very frustrating to have a program that produces the correct answer but fails test cases because it does not output answers in the correct format. The output portion of a problem description dic- tates exactly how we should produce output. For example, it will tell us how many lines of output to produce for each test case, what to put on each line, whether blank lines are required between or after test cases, and so on. In addition, I provide the time limit for the problem: if the program does not output the solution for all test cases within the time limit, then the program does not pass. I have rewritten the text of each problem from the official description, so that I can maintain a consistent presentation throughout. Despite these Introduction xxvii Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 12

tweaks, my description will convey the same information as the official de- scription. For most problems in this book, we’ll read input from standard input and write output to standard output. (There are only two problems where standard input and output are not involved; they are in Chapter 6.) This means we should use C functions such as scanf, getchar, printf, and so on and not explicitly open and close files. Problem: Food Lines Let’s familiarize ourselves with a sample problem description. I’ll provide some commentary in parentheses along the way, directing your attention to the important bits. Once we understand the problem, I can think of noth- ing better to do than solve it. Unlike the other problems in the book, we’ll be able to do so with programming constructs and ideas that I hope you al- ready know. If you solve the problem on your own, or work through my so- lution with little or no trouble, then I think you’re ready for what’s to come. If you get seriously stuck, then you may wish to revisit programming funda- mentals and/or solve a few other starter problems before continuing. This is DMOJ problem lkp18c2p1. (You might like to go now to the DMOJ website and search for this problem, so that you’re ready to submit once we solve it.) The Problem There are n lines of people waiting for food, and the number of people wait- ing in each line is known. Then, each of m new people will arrive, and they will join the shortest line (the line with the fewest number of people). Our task is to determine the number of people in each line that each of the m people joins. (Spend a little time interpreting the above paragraph. There’s an exam- ple coming next, so if anything is unclear, try to remedy it with the combina- tion of the above paragraph and the example below.) Suppose that there are three lines, with three people in line 1, two peo- ple in line 2, and five people in line 3. Then, four new people arrive. (Try to work out what happens for this case before reading the rest of this para- graph.) The first person joins a line with two people, line 2; now line 2 has three people. The second person joins a line with three people, line 1 or line 2—let’s say line 1; line 1 now has four people. The third person joins a line with three people, line 2; line 2 now has four people. The fourth and final person joins a line with four people, line 1 or line 2—let’s say line 1; line 1 now has five people. Input The input contains one test case. The first line contains two positive inte- gers, n and m, giving the number of lines and number of new people, respec- tively. n and m are at most 100. The second line contains n positive integers, xxviii Introduction Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 13

giving the number of people in each line before the new people arrive. Each of these integers is at most 100. Here’s the input for the above test case: 3 4 3 2 5 (Note how there is exactly one test case here. Therefore, we should ex- pect to read exactly two lines of input.) Output For each of the m new people, output a line containing the number of peo- ple in the line that they join. Valid output for the above test case is 2 3 3 4 The time limit for solving the test case is three seconds. (Given that we have to handle at most 100 new people for each test case, three seconds is a long time. We won’t need any fancy data structures or algorithms.) Solving the Problem For problems involving data structures that are difficult to build by hand, I may start by reading the input. Otherwise, I tend to save that code for last. The reason for this is that we can generally test the functions we’re writing by calling them with sample values; there is no need to worry about parsing the input until we’re ready to solve the whole problem. The key data that we need to maintain are the number of people in each line. The appropriate storage technique is an array, using one index per line. I use a variable named lines for that array. Each new person that arrives chooses to join the shortest line, so we’ll need a helper function to tell us which line that is. That helper function is given in Listing 2. int shortest_line_index(int lines[], int n) { int j; int shortest = 0; for (j = 1; j < n; j++) if (lines[j] < lines[shortest]) shortest = j; return shortest; } Listing 2: Index of the shortest line Introduction xxix Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 14

Now, given a lines array and n and m, we can solve a test case, the code for which is given in Listing 3. void solve(int lines[], int n, int m) { int i, shortest; for (i = 0; i < m; i++) { shortest = shortest_line_index(lines, n); printf("%d\n", lines[shortest]); ¶ lines[shortest]++; } } Listing 3: Solving the problem For each iteration of the outer for loop, we call our helper function to grab the index of the shortest line. We then print the length of that short- est line. This person then joins that line: that’s why we must increment the number of people by one ¶. All that’s left is to read the input and call solve; that’s done in Listing 4. #define MAX_LINES 100 int main(void) { int lines[MAX_LINES]; int n, m, i; scanf("%d%d", &n, &m); for (i = 0; i < n; i++) scanf("%d", &lines[i]); solve(lines, n, m); return 0; } Listing 4: The main function Putting together our shortest_line_index, solve, and main functions and adding the required #include lines at the top gives us a complete solution that we can submit to the judge. When doing so, be sure to choose the cor- rect programming language: for the programs in this book, you want to find GCC, or C99, or C11, or however the judge refers to a compiler for C. If you want to test your code locally before submitting it to the judge, then you have a few options. Since our programs read from standard input, one thing you can do is run the program and type a test case by hand. That’s a reasonable thing to do for small test cases, but its tedious doing that over and over and especially for large test cases. A better option is to store the in- put in a file and then use input redirection from the command prompt to have the program read from that file instead of the keyboard. For example, if you store a test case for the present problem in file food.txt, and your compiled program is called food, then try: $ food < food.txt xxx Introduction Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 15

This makes it easy to change the test case: just change what’s in food.txt and then run the program with input redirection again. Congratulations! That’s your first problem solved. Moreover, you now know the game plan for each problem in the book, as they all follow the same structure I have given here. Notes Food Lines is originally from the 2018 LKP Contest 2, hosted by DMOJ. Introduction xxxi Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 16

Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 17

1 HASH TABLES In this chapter, we’ll solve two problems whose solutions hinge on being able to per- form efficient searches. The first problem is determining whether or not all snowflakes in a collection are identical. The second is determining which words are compound words. We want to solve these problems correctly, but we’ll see that some cor- rect approaches are simply too slow. We’ll be able to achieve enormous performance increases using a data structure known as a hash table, which we’ll explore at length. We’ll end the chapter by looking at a third problem: determining how many ways a letter can be deleted from one word to arrive at another. Here we’ll see the risks of uncritically using a new data structure—when learning something new, it’s tempting to try to use it everywhere! Problem 1: Unique Snowflakes This is DMOJ problem cco07p2. Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 18

The Problem We’re given a collection of snowflakes, and we have to determine whether any of the snowflakes in the collection are identical. A snowflake is represented by six integers, where each integer gives the length of one of the snowflake’s arms. For example, this is a snowflake: 3, 9, 15, 2, 1, 10 Snowflakes can also have repeated integers, such as 8, 4, 8, 9, 2, 8 What does it mean for two snowflakes to be identical? Let’s work up to that definition through a few examples. First we’ll look at these two snowflakes: 1, 2, 3, 4, 5, 6 and 1, 2, 3, 4, 5, 6 These are clearly identical because the integers in one snowflake match the integers in their corresponding positions in the other snowflake. Here’s our second example: 1, 2, 3, 4, 5, 6 and 4, 5, 6, 1, 2, 3 These are also identical. We can see this by starting at the 1 in the sec- ond snowflake and moving right. We see the integers 1, 2, and 3 and then, wrapping around to the left, we see 4, 5, and 6. These two pieces together give us the first snowflake. We can think of each snowflake as a circle. These two snowflakes are identical because we can choose a starting point for the second snowflake and follow it to the right to get the first snowflake. Let’s try a trickier example: 1, 2, 3, 4, 5, 6 and 3, 2, 1, 6, 5, 4 From what we’ve seen so far, we would deduce that these are not identi- cal. If we start with the 1 in the second snowflake and move right (wrapping around to the left when we hit the right end), we get 1, 6, 5, 4, 3, 2. That’s not even close to the 1, 2, 3, 4, 5, 6 in the first snowflake. 2 Chapter 1 Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 19

However, if we begin at the 1 in the second snowflake and move left in- stead of right, then we do get exactly 1, 2, 3, 4, 5, 6! Moving left from the 1 gives us 1, 2, 3, and wrapping around to the right, we can proceed leftward to collect 4, 5, 6. That’s our third way for two snowflakes to be identical: two snowflakes are called identical if they match when we move leftward through the numbers. Putting it all together, we can conclude that two snowflakes are identi- cal if they are the same, if we can make them the same by moving rightward through one of the snowflakes, or if we can make them the same by moving leftward through one of the snowflakes. Input The first line of input is an integer n, which gives the number of snowflakes that we’ll be processing. The value n will be between 1 and 100,000. Each of the following n lines represents one snowflake: each line has six integers, where each integer is at least zero and at most 10,000,000. Output Our output will be a single line of text: • If there are no identical snowflakes, print exactly No two snowflakes are alike. • If there are at least two identical snowflakes, print exactly Twin snowflakes found. The time limit for solving the test cases is two seconds. Simplifying the Problem One general strategy for solving competitive programming challenges is to first work with a simpler version of the problem. Let’s warm up by eliminat- ing some of the complexity from this problem. Suppose that instead of working with snowflakes made of multiple in- tegers, we’re working with single integers. We have a collection of integers, and we want to know whether any are identical. We can test whether two in- tegers are identical with C’s == operator. We can test all pairs of integers, and if we find even one pair of identical integers, we’ll stop and output Twin integers found. If no identical integers are found, we’ll output No two integers are alike. Let’s make an identify_identical function with two nested loops to com- pare pairs of integers, as shown in Listing 1-1. Hash Tables 3 Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro

📄 Page 20

void identify_identical(int values[], int n) { int i, j; for (i = 0; i < n; i++) { ¶ for (j = i+1; j < n; j++) { if (values[i] == values[j]) { printf("Twin integers found.\n"); return; } } } printf("No two integers are alike.\n"); } Listing 1-1: Finding identical integers We feed the integers to the function through the values array. We also pass in n, the number of integers in the array. Notice that we start the inner loop at i + 1 and not 0 ¶. If we started at 0, then eventually j would equal i, and we’d compare an element to itself, giving us a false positive result. Let’s test identify_identical using this small main function: int main(void) { int a[5] = {1, 2, 3, 1, 5}; identify_identical(a, 5); return 0; } Run the code and you will see from the output that our function cor- rectly identified a matching pair of 1s. In general, I won’t provide much test code in this book, but it’s important that you play with and test the code yourself as we go along. Solving the Core Problem Let’s take our identify_identical function and try to modify it to solve the Snowflake problem. To do so, we need to make two extensions to our code: 1. We have to work with six integers at a time, not one. A two- dimensional array should work nicely here: each row will be a snowflake with six columns (one column per element). 2. As we saw earlier, there are three ways for two snowflakes to be identical. Unfortunately, this means we can’t just use == to compare snowflakes. We need to take into account our “moving right” and “moving left” criteria (not to mention that == in C doesn’t compare arrays anyway!). Correctly comparing snowflakes will be the major update to our algorithm. 4 Chapter 1 Algorithmic Thinking (Early Access), © 2020 by Daniel Zingaro