Competitive Programming in Python 128 Algorithms to Develop your Coding Skills (Christoph Dürr, Jill-Jênn Vie) (z-library.sk, 1lib.sk, z-lib.sk)

Competitive Programming in Python Want to kill it at your job interview in the tech industry? Want to win that coding competition? Learn all the algorithmic techniques and programming skills you need from two experienced coaches, problem-setters, and judges for coding competitions. The authors highlight the versatility of each algorithm by considering a variety of problems and show how to implement algorithms in simple and efficient code. What to expect: * Master 128 algorithms in Python. * Discover the right way to tackle a problem and quickly implement a solution of low complexity. * Understand classic problems like Dijkstra’s shortest path algorithm and Knuth–Morris–Pratt’s string matching algorithm, plus lesser-known data structures like Fenwick trees and Knuth’s dancing links. * Develop a framework to tackle algorithmic problem solving, including: Definition, Complexity, Applications, Algorithm, Key Information, Implementation, Variants, In Practice, and Problems. * Python code included in the book and on the companion website. Christoph Dürr is a senior researcher at the French National Center for Scientific Research (CNRS), affiliated with the Sorbonne University in Paris. After a PhD in 1996 at Paris-Sud University, he worked for one year as a postdoctoral researcher at the International Computer Science Institute in Berkeley and one year in the School of Computer Science and Engineering in the Hebrew University of Jerusalem in Israel. He has worked in the fields of quantum computation, discrete tomography and algorithmic game theory, and his current research activity focuses on algorithms and optimisation. From 2007 to 2014, he taught a preparation course for programming contests at the engineering school École Polytechnique, and acts regularly as a problem setter, trainer, or competitor for various coding competitions. In addition, he loves carrot cake. Jill-Jênn Vie is a research scientist at Inria in machine learning. He is an alumnus from École normale supérieure Paris-Saclay, where he founded the algorithmic club of Paris-Saclay (CAPS) and coached several teams for the International Collegiate Programming Contest (ICPC). He published a book in theoretical computer science to help students prepare for prestigious French competitive exams such as Grandes Écoles or agrégation, and directed a television show “Blame the Algorithm” about the algorithms that govern our lives. He is part of the advisory board of the French Computer Science Society (SIF), itself a member of the International Federation for Information Processing (IFIP).

Competitive Programming in Python 128 Algorithms to Develop Your Coding Skills CHR ISTOPH DÜRR CNRS, Sorbonne University J I LL-JÊNN V IE Inria Translated by Greg Gibbons and Danièle Gibbons

University Printing House, Cambridge CB2 8BS, United Kingdom One Liberty Plaza, 20th Floor, New York, NY 10006, USA 477 Williamstown Road, Port Melbourne, VIC 3207, Australia 314–321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre, New Delhi – 110025, India 79 Anson Road, #06–04/06, Singapore 079906 Cambridge University Press is part of the University of Cambridge. It furthers the University’s mission by disseminating knowledge in the pursuit of education, learning, and research at the highest international levels of excellence. www.cambridge.org Information on this title: www.cambridge.org/9781108716826 DOI: 10.1017/9781108591928 © Cambridge University Press 2021 Translation from the French language edition: Programmation efficace - 128 algorithmes qu’il faut avoir compris et codés en Python au cour de sa vie By Christoph Dürr & Jill-Jênn Vie Copyright © 2016 Edition Marketing S.A. www.editions-ellipses.fr All Rights Reserved This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2021 Printed in the United Kingdom by TJ Books Limited, Padstow Cornwall A catalogue record for this publication is available from the British Library. Library of Congress Cataloging-in-Publication Data Names: Dürr, Christoph, 1969– author. | Vie, Jill-Jênn, 1990– author. | Gibbons, Greg, translator. | Gibbons, Danièle, translator. Title: Competitive programming in Python : 128 algorithms to develop your coding skills / Christoph Dürr, Jill-Jênn Vie ; translated by Greg Gibbons, Danièle Gibbons. Other titles: Programmation efficace. English Description: First edition. | New York : Cambridge University Press, 2020. | Includes bibliographical references and index. Identifiers: LCCN 2020022774 (print) | LCCN 2020022775 (ebook) | ISBN 9781108716826 (paperback) | ISBN 9781108591928 (epub) Subjects: LCSH: Python (Computer program language) | Algorithms. Classification: LCC QA76.73.P98 D8713 2020 (print) | LCC QA76.73.P98 (ebook) | DDC 005.13/3–dc23 LC record available at https://lccn.loc.gov/2020022774 LC ebook record available at https://lccn.loc.gov/2020022775 ISBN 978-1-108-71682-6 Paperback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

Contents Preface page ix 1 Introduction 1 1.1 Programming Competitions 1 1.2 Python in a Few Words 5 1.3 Input-Output 13 1.4 Complexity 17 1.5 Abstract Types and Essential Data Structures 20 1.6 Techniques 28 1.7 Advice 37 1.8 A Problem: ‘Frosting on the Cake’ 39 2 Character Strings 42 2.1 Anagrams 42 2.2 T9—Text on 9 Keys 43 2.3 Spell Checking with a Lexicographic Tree 46 2.4 Searching for Patterns 48 2.5 Maximal Boundaries—Knuth–Morris–Pratt 49 2.6 Pattern Matching—Rabin–Karp 56 2.7 Longest Palindrome of a String—Manacher 59 3 Sequences 62 3.1 Shortest Path in a Grid 62 3.2 The Levenshtein Edit Distance 63 3.3 Longest Common Subsequence 65 3.4 Longest Increasing Subsequence 68 3.5 Winning Strategy in a Two-Player Game 70 4 Arrays 72 4.1 Merge of Sorted Lists 73 4.2 Sum Over a Range 74 4.3 Duplicates in a Range 74 4.4 Maximum Subarray Sum 75

vi Contents 4.5 Query for the Minimum of a Range—Segment Tree 75 4.6 Query the Sum over a Range—Fenwick Tree 77 4.7 Windows with k Distinct Elements 80 5 Intervals 82 5.1 Interval Trees 82 5.2 Union of Intervals 85 5.3 The Interval Point Cover Problem 85 6 Graphs 88 6.1 Encoding in Python 88 6.2 Implicit Graphs 90 6.3 Depth-First Search—DFS 91 6.4 Breadth-First Search—BFS 93 6.5 Connected Components 94 6.6 Biconnected Components 97 6.7 Topological Sort 102 6.8 Strongly Connected Components 105 6.9 2-Satisfiability 110 7 Cycles in Graphs 113 7.1 Eulerian Tour 113 7.2 The Chinese Postman Problem 116 7.3 Cycles with Minimal Ratio of Weight to Length—Karp 117 7.4 Cycles with Minimal Cost-to-Time Ratio 120 7.5 Travelling Salesman 120 7.6 Full Example: Menu Tour 121 8 Shortest Paths 124 8.1 Composition Property 124 8.2 Graphs with Weights 0 or 1 126 8.3 Graphs with Non-negative Weights—Dijkstra 127 8.4 Graphs with Arbitrary Weights—Bellman–Ford 130 8.5 All Source–Destination paths—Floyd–Warshall 132 8.6 Grid 133 8.7 Variants 135 9 Matchings and Flows 138 9.1 Maximum Bipartite Matching 139 9.2 Maximal-Weight Perfect Matching—Kuhn–Munkres 145 9.3 Planar Matching without Crossings 151 9.4 Stable Marriages—Gale–Shapley 153

Contents vii 9.5 Maximum Flow by Ford–Fulkerson 155 9.6 Maximum Flow by Edmonds–Karp 158 9.7 Maximum Flow by Dinic 159 9.8 Minimum s − t Cut 162 9.9 s − t Minimum Cut for Planar Graphs 163 9.10 A Transport Problem 165 9.11 Reductions between Matchings and Flows 165 9.12 Width of a Partial Order—Dilworth 167 10 Trees 171 10.1 Huffman Coding 172 10.2 Lowest Common Ancestor 174 10.3 Longest Path in a Tree 178 10.4 Minimum Weight Spanning Tree—Kruskal 179 11 Sets 182 11.1 The Knapsack Problem 182 11.2 Making Change 184 11.3 Subset Sum 185 11.4 The k-sum Problem 187 12 Points and Polygons 189 12.1 Convex Hull 190 12.2 Measures of a Polygon 193 12.3 Closest Pair of Points 195 12.4 Simple Rectilinear Polygon 198 13 Rectangles 200 13.1 Forming Rectangles 200 13.2 Largest Square in a Grid 201 13.3 Largest Rectangle in a Histogram 202 13.4 Largest Rectangle in a Grid 204 13.5 Union of Rectangles 205 13.6 Union of Disjoint Rectangles 212 14 Numbers and Matrices 214 14.1 GCD 214 14.2 Bézout Coefficients 214 14.3 Binomial Coefficients 215 14.4 Fast Exponentiation 216 14.5 Prime Numbers 217 14.6 Evaluate an Arithmetical Expression 218

viii Contents 14.7 System of Linear Equations 221 14.8 Multiplication of a Matrix Sequence 225 15 Exhaustive Search 227 15.1 All Paths for a Laser 227 15.2 The Exact Cover Problem 231 15.3 Problems 237 15.4 Sudoku 238 15.5 Enumeration of Permutations 240 15.6 Le Compte est Bon 243 16 Conclusion 245 16.1 Combine Algorithms to Solve a Problem 245 16.2 For Further Reading 245 16.3 Rendez-vous on tryalgo.org 246 Debugging tool 247 References 248 Index 251

Preface Algorithms play an important role in our society, solving numerous mathematical problems which appear in a broad spectrum of situations. To give a few examples, think of planning taxi routes given a set of reservations (see Section 9.12); assigning students to schools in a large urban school district, such as New York (see Section 9.4); or identifying a bottleneck in a transportation network (see Section 9.8). This is why job interviews in the IT (Information Technology) industry test candidates for their problem-solving skills. Many programming contests are organised by companies such as Google, Facebook and Microsoft to spot gifted candidates and then send them job offers. This book will help students to develop a culture of algorithms and data structures, so that they know how to apply them properly when faced with new mathematical problems. Designing the right algorithm to solve a given problem is only half of the work; to complete the job, the algorithm needs to be implemented efficiently. This is why this book also emphasises implementation issues, and provides full source code for most of the algorithms presented. We have chosen Python for these implementations. What makes this language so enticing is that it allows a particularly clear and refined expression, illustrating the essential steps of the algorithm, without obscuring things behind burdensome notations describing data structures. Surprisingly, it is actually possible to re-read code written several months ago and even understand it! We have collected here 128 algorithmic problems, indexed by theme rather than by technique. Many are classic, whereas certain are atypical. This work should prove itself useful when preparing to solve the wide variety of problems posed in programming contests such as ICPC, Google Code Jam, Facebook Hacker Cup, Prologin, France-ioi, etc. We hope that it could serve as a basis for an advanced course in programming and algorithms, where even certain candidates for the ‘agrégation de mathématiques option informatique’ (French competitive exam for the highest teacher’s certification) will find a few original developments. The website tryalgo.org, maintained by the authors, contains links to the code of this book, as well as to selected problems at various online contests. This allows readers to verify their freshly acquired skills. This book would never have seen the light of day without the support of the authors’ life partners. Danke, Hương. Merci, 智子. The authors would also like to thank the students of the École polytechnique and the École normale supérieure of Paris-Saclay, whose practice, often nocturnal, generated a major portion of the

x Preface material of this text. Thanks to all those who proofread the manuscript, especially René Adad, Evripidis Bampis, Binh-Minh Bui-Xuan, Stéphane Henriot, Lê Thành Dũng Nguyễn, Alexandre Nolin and Antoine Pietri. Thanks to all those who improved the programs on GitHub: Louis Abraham, Lilian Besson, Ryan Lahfa, Olivier Marty, Samuel Tardieu and Xavier Carcelle. One of the authors would especially like to thank his past teacher at the Lycée Thiers, Monsieur Yves Lemaire, for having introduced him to the admirable gem of Section 2.5 on page 52. We hope that the reader will pass many long hours tackling algorithmic problems that at first glance appear insurmountable, and in the end feel the profound joy when a solution, especially an elegant solution, suddenly becomes apparent. Finally, we would like to thank Danièle and Greg Gibbons for their translation of this work, even of this very phrase. Attention, it’s all systems go!

1 Introduction You, my young friend, are going to learn to program the algorithms of this book, and then go on to win programming contests, sparkle during your job interviews, and finally roll up your sleeves, get to work, and greatly improve the gross national product! Mistakenly, computer scientists are still often considered the magicians of modern times. Computers have slowly crept into our businesses, our homes and our machines, and have become important enablers in the functioning of our world. However, there are many that use these devices without really mastering them, and hence, they do not fully enjoy their benefits. Knowing how to program provides the ability to fully exploit their potential to solve problems in an efficient manner. Algorithms and programming techniques have become a necessary background for many professions. Their mastery allows the development of creative and efficient computer-based solutions to problems encountered every day. This text presents a variety of algorithmic techniques to solve a number of classic problems. It describes practical situations where these problems arise, and presents simple implementations written in the programming language Python. Correctly implementing an algorithm is not always easy: there are numerous traps to avoid and techniques to apply to guarantee the announced running times. The examples in the text are embellished with explanations of important implementation details which must be respected. For the last several decades, programming competitions have sprung up at every level all over the world, in order to promote a broad culture of algorithms. The prob- lems proposed in these contests are often variants of classic algorithmic problems, presented as frustrating enigmas that will never let you give up until you solve them! 1.1 Programming Competitions In a programming competition, the candidates must solve several problems in a fixed time. The problems are often variants of classic problems, such as those addressed in this book, dressed up with a short story. The inputs to the problems are called instances. An instance can be, for example, the adjacency matrix of a graph for a shortest path problem. In general, a small example of an instance is provided, along with its solution. The source code of a solution can be uploaded to a server via

2 Introduction a web interface, where it is compiled and tested against instances hidden from the public. For some problems the code is called for each instance, whereas for others the input begins with an integer indicating the number of instances occurring in the input. In the latter case, the program must then loop over each instance, solve it and display the results. A submission is accepted if it gives correct results in a limited time, on the order of a few seconds. Figure 1.1 The logo of the ICPC nicely shows the steps in the resolution of a problem. A helium balloon is presented to the team for each problem solved. To give here a list of all the programming competitions and training sites is quite impossible, and such a list would quickly become obsolete. Nevertheless, we will review some of the most important ones. ICPC The oldest of these competitions was founded by the Association for Computing Machinery in 1977 and supported by them up until 2017. This contest, known as the ICPC, for International Collegiate Programming Contest, is organised in the form of a tournament. The starting point is one of the regional competitions, such as the South-West European Regional Contest (SWERC), where the two best teams qualify for the worldwide final. The particularity of this contest is that each three-person team has only a single computer at their disposal. They have only 5 hours to solve a maximum number of problems among the 10 proposed. The first ranking criterion is the number of submitted solutions accepted (i.e. tested successfully against a set of unknown instances). The next criterion is the sum over the submitted problems of the time between the start of the contest and the moment of the accepted submission. For each erroneous submission, a penalty of 20 minutes is added. There are several competing theories on what the ideal composition of a team is. In general, a good programmer and someone familiar with algorithms is required, along with a specialist in different domains such as graph theory, dynamic programming, etc. And, of course, the team members need to get along together, even in stressful situations! For the contest, each team can bring 25 pages of reference code printed in an 8-point font. They can also access the online documentation of the Java API and the C++ standard library. Google Code Jam In contrast with the ICPC contest, which is limited to students up to a Master’s level, the Google Code Jam is open to everyone. This more recent annual competition is for individual contestants. Each problem comes in

1.1 Programming Competitions 3 general with a deck of small instances whose resolution wins a few points, and a set of enormous instances for which it is truly important to find a solution with the appropriate algorithmic complexity. The contestants are informed of the acceptance of their solution for the large instances only at the end of the contest. However, its true strong point is the possibility to access the solutions submitted by all of the participants, which is extremely instructive. The competition Facebook Hacker Cup is of a similar nature. Prologin The French association Prologin organises each year a competition targeted at students up to twenty years old. Their capability to solve algorithmic problems is put to test in three stages: an online selection, then regional competitions and concluding with a national final. The final is atypically an endurance test of 36 hours, during which the participants are confronted with a problem in Artificial Intelligence. Each candidate must program a “champion” to play a game whose rules are defined by the organisers. At the end of the day, the champions are thrown in the ring against each other in a tournament to determine the final winner. The website https://prologin.org includes complete archives of past problems, with the ability to submit algorithms online to test the solutions. France-IOI Each year, the organisation France-IOI prepares junior and senior high school students for the International Olympiad in Informatics. Since 2011, they have organised the ‘Castor Informatique’ competition, addressed at students from Grade 4 to Grade 12 (675,000 participants in 2018). Their website http://france-ioi.org hosts a large number of algorithmic problems (more than 1,000). Numerous programming contests organised with the goal of selecting candidates for job offers also exist. The web site www.topcoder.com, for example, also includes tutorials on algorithms, often very well written. For training, we particularly recommend https://codeforces.com, a well- respected web site in the community of programming competitions, as it proposes clear and well-prepared problems. 1.1.1 Training Sites A number of websites propose problems taken from the annals of competitions, with the possibility to test solutions as a training exercise. This is notably the case for Google Code Jam and Prologin (in French). The collections of the annals of the ICPC contests can be found in various locations. Traditional online judges The following sites contain, among others, many problems derived from the ICPC contests. uva http://uva.onlinejudge.org icpcarchive http://icpcarchive.ecs.baylor.edu, http://livearchive .onlinejudge.org

4 Introduction Chinese online judges Several training sites now exist in China. They tend to have a purer and more refined interface than the traditional judges. Nevertheless, sporadic failures have been observed. poj http://poj.org tju http://acm.tju.edu.cn (Shut down since 2017) zju http://acm.zju.edu.cn Modern online judges Sphere Online Judge http://spoj.com and Kattis http://open.kattis.com have the advantage of accepting the submission of solutions in a variety of languages, including Python. spoj http://spoj.com kattis http://open.kattis.com zju http://acm.zju.edu.cn Other sites codechef http://codechef.com codility http://codility.com gcj http://code.google.com/codejam prologin http://prologin.org slpc http://cs.stanford.edu/group/acm Throughout this text, problems are proposed at the end of each section in rela- tion to the topic presented. They are accompanied with their identifiers to a judge site; for example [spoj:CMPLS] refers to the problem ‘Complete the Sequence!’ at the URL www.spoj.com/problems/CMPLS/. The site http://tryalgo.org contains links to all of these problems. The reader thus has the possibility to put into practice the algorithms described in this book, testing an implementation against an online judge. The languages used for programming competitions are principally C++ and Java. The SPOJ judge also accepts Python, while the Google Code Jam contest accepts many of the most common languages. To compensate for the differences in execution speed due to the choice of language, the online judges generally adapt the time limit to the language used. However, this adaptation is not always done carefully, and it is sometimes difficult to have a solution in Python accepted, even if it is correctly written. We hope that this situation will be improved in the years to come. Also, certain judges work with an ancient version of Java, in which such useful classes as Scanner are not available. 1.1.2 Responses of the Judges When some code for a problem is submitted to an online judge, it is evaluated via a set of private tests and a particularly succinct response is returned. The principal response codes are the following:

1.2 Python in a Few Words 5 Accepted Your program provides the correct output in the allotted time. Congrat- ulations! Presentation Error Your program is almost accepted, but the output contains extraneous or missing blanks or end-of-lines. This message occurs rarely. Compilation Error The compilation of your program generates errors. Often, clicking on this message will provide the nature of the error. Be sure to compare the version of the compiler used by the judge with your own. Wrong Answer Re-read the problem statement, a detail must have been over- looked. Are you sure to have tested all the limit cases? Might you have left debugging statements in your code? Time Limit Exceeded You have probably not implemented the most efficient algorithm for this problem, or perhaps have an infinite loop somewhere. Test your loop invariants to ensure loop termination. Generate a large input instance and test locally the performance of your code. Runtime Error In general, this could be a division by zero, an access beyond the limits of an array, or a pop() on an empty stack. However, other situations can also generate this message, such as the use of assert in Java, which is often not accepted. The taciturn behaviour of the judges nevertheless allows certain information to be gleaned from the instances. Here is a trick that was used during an ICPC / SWERC contest. In a problem concerning graphs, the statement indicated that the input con- sisted of connected graphs. One of the teams doubted this, and wrote a connectivity test. In the positive case, the program entered into an infinite loop, while in the negative case, it caused a division by zero. The error code generated by the judge (Time Limit Exceeded ou Runtime Error) allowed the team to detect that certain graphs in the input were not connected. 1.2 Python in a Few Words The programming language Python was chosen for this book, for its readability and ease of use. In September 2017, Python was identified by the website https:// stackoverflow.com as the programming language with the greatest growth in high- income countries, in terms of the number of questions seen on the website, notably thanks to the popularity of machine learning.1 Python is also the language retained for such important projects as the formal calculation system SageMath, whose critical portions are nonetheless implemented in more efficient languages such as C++ or C. Here are a few details on this language. This chapter is a short introduction to Python and does not claim to be exhaustive or very formal. For the neophyte reader we recommend the site python.org, which contains a high-quality introduction as well as exceptional documentation. A reader already familiar with Python can profit 1 https://stackoverflow.blog/2017/09/06/incredible-growth-python/

6 Introduction enormously by studying the programs of David Eppstein, which are very elegant and highly readable. Search for the keywords Eppstein PADS. Python is an interpreted language. Variable types do not have to be declared, they are simply inferred at the time of assignment. There are neither keywords begin/end nor brackets to group instructions, for example in the blocks of a function or a loop. The organisation in blocks is simply based on indentation! A typical error, difficult to identify, is an erroneous indentation due to spaces used in some lines and tabs in others. Basic Data Types In Python, essentially four basic data types exist: Booleans, integers, floating-point numbers and character strings. In contrast with most other programming languages, the integers are not limited to a fixed number of bits (typically 64), but use an arbi- trary precision representation. The functions—more precisely the constructors: bool, int, float, str—allow the conversion of an object to one of these basic types. For example, to access the digits of a specific integer given its decimal representation, it can be first transformed into a string, and then the characters of the string can be accessed. However, in contrast with languages such as C, it is not possible to directly modify a character of a string: strings are immutable. It is first necessary to convert to a list representation of the characters; see below. Data Structures The principal complex data structures are dictionaries, sets, lists and n-tuples. These structures are called containers, as they contain several objects in a structured manner. Once again, there are functions dict, set, list and tuple that allow the conversion of an object into one of these structures. For example, for a string s, the function list(s) returns a list L composed of the characters of the string. We could then, for example, replace certain elements of the list L and then recreate a string by concatenating the ele- ments of L with the expression ‘’.join(L). Here, the empty string could be replaced by a separator: for example, ‘-’.join([’A’,’B’,’C’]) returns the string “A-B-C”. 1.2.1 Manipulation of Lists, n-tuples, Dictionaries Note that lists in Python are not linked lists of cells, each with a pointer to its successor in the list, as is the case in many other languages. Instead, lists are arrays of elements that can be accessed and modified using their index into the array. A list is written by enumerating its elements between square brackets [ and ], with the elements separated by commas. Lists The indices of a list start with 0. The last element can also be accessed with the index −1, the second last with −2 and so on. Here are some examples of operations to extract elements or sublists of a list. This mechanism is known as slicing, and is also available for strings.

1.2 Python in a Few Words 7 The following expressions have a complexity linear in the length of L, with the exception of the first, which is in constant time. L[i] the ith element of L L[i:j] the list of elements with indices starting at i and up to (but not including) j L[:j] the first j elements L[i:] all the elements from the ith onwards L[-3:] the last three elements of L L[i:j:k] elements from the ith up to (but not including) the jth, taking only every kth element L[::2] the elements of L with even indices L[::-1] a reverse copy of L The most important methods of a list for our usage are listed below. Their complexity is expressed in terms of n, the length of the list L. A function has constant amortised complexity if, for several successive calls to it, the average complexity is constant, even if some of these calls take a time linear in n. len(L) returns the number of elements of the list L O(1) sorted(L) returns a sorted copy of the list L O(n log n) L.sort() sorts L in place O(n log n) L.count(c) the number of occurrences of c in L O(n) c in L is the element c found in L? O(n) L.append(c) append c to the end of L amortised O(1) L.pop() extracts and returns the last element of L amortised O(1) Thus a list has all the functionality of a stack, defined in Section 1.5.1 on page 20. n-tuple An n-tuple behaves much like a list, with a difference in the usage of parentheses to describe it, as in (1, 2) or (left, ’X’, right). A 1-tuple, composed of only one element, requires the usage of a comma, as in (2,). A 0-tuple, empty, can be written as (), or as tuple(), no doubt more readable. The main difference with lists is that n-tuples are immutable, just like strings. This is why an n-tuple can serve as a key in a dictionary. Dictionaries Dictionaries are used to associate objects with values, for example the words of a text with their frequency. A dictionary is constructed as comma-separated key:value pairs between curly brackets, such as {’the’: 4, ’bread’: 1, ’is’: 6}, where the keys and values are separated by a colon. An empty dictionary is obtained with {}. A membership test of a key x in a dictionary dic is written x in dic. Behind a dictionary there is a hash table, hence the complexity of the expressions x in dic, dic[x], dic[x] = 42 is in practice constant time, even if the worst-case complexity is linear, a case obtained in the improbable event of all keys having the same hash value. If the keys of a dictionary are all the integers between 0 and n− 1, the use of a list is much more efficient.

8 Introduction A loop in Python is written either with the keyword for or with while. The nota- tion for the loop for is for x in S:, where the variable x successively takes on the values of the container S, or of the keys of S in the case of a dictionary. In contrast, while L: will loop as long as the list L is non-empty. Here, an implicit conversion of a list to a Boolean is made, with the convention that only the empty list converts to False. At times, it is necessary to handle at the same time the values of a list along with their positions (indices) within the list. This can be implemented as follows: for index in range(len(L)): value = L[index] # ... handling of index and value The function enumerate allows a more compact expression of this loop: for index, value in enumerate(L): # ... handling of index and value For a dictionary, the following loop iterates simultaneously over the keys and values: for key, value in dic.items(): # ... handling of key and value 1.2.2 Specificities: List and Dictionary Comprehension, Iterators List and Dictionary Comprehension The language Python provides a syntax close to the notation used in mathematics for certain objects. To describe the list of squares from 0 to n2, it is possible to use a list comprehension: >>> n = 5 >>> squared_numbers = [x ** 2 for x in range(n + 1)] >>> squared_numbers [0, 1, 4, 9, 16, 25] which corresponds to the set {x2|x = 0, . . . ,n} in mathematics. This is particularly useful to initialise a list of length n: >>> t = [0 for _ in range(n)] >>> t [0, 0, 0, 0, 0]

1.2 Python in a Few Words 9 or to initialise counters for the letters in a string: >>> my_string = "cowboy bebop" >>> nb_occurrences = {letter: 0 for letter in my_string} >>> nb_occurrences {’c’: 0, ’o’: 0, ’w’: 0, ’b’: 0, ’y’: 0, ’ ’: 0, ’e’: 0, ’p’: 0} The second line, a dictionary comprehension, is equivalent to the following: nb_occurrences = {} for letter in my_string: nb_occurrences[letter] = 0 Ranges and Other Iterators To loop over ranges of integers, the code for i in range(n): can be used to run over the integers from 0 to n− 1. Several variants exist: range(k, n) from k to n− 1 range(k, n, 2) from k to n− 1 two by two range(n - 1, -1, -1) from n− 1 to 0 (−1 excluded) in decreasing order. In early versions of Python, range returned a list. Nowadays, for efficiency, it returns an object known as an iterator, which produces integers one by one, if and when the for loop claims a value. Any function can serve as an iterator, as long as it can produce elements at different moments of its execution using the keyword yield. For example, the following function iterates over all pairs of elements of a given list:. def all_pairs(L): n = len(L) for i in range(n): for j in range(i + 1, n): yield (L[i], L[j]) 1.2.3 Useful Modules and Packages Modules Certain Python objects must be imported from a module or a package with the command import. A package is a collection of modules. Two methods can be used; the second avoids potential naming collisions between the methods in different modules: