Welcome to this workbook! Before you get started, I want to briefly outline what you can expect when reading it.
This book covers a broad range of practice-relevant topics, represented by exercises of different levels of difficulty. The exercises are (for the most part) independent of each other and can be solved in any order, depending on your mood or interest.
Besides the exercises, you will find the corresponding answers, including a short description of the algorithm used for the solution and the actual source code, which is commented on at essential points.
1.1 Structure of the Chapters
Each chapter shares the same structure, so you will quickly find your way around.
1.1.1 Introduction
Each chapter begins with an introduction to the topic to get you familiar with the subject area or get you in the right mood for the tasks that follow.
1.1.2 Exercises
The introduction is succeeded by a bunch of exercises and the following structure:
Task Each exercise first will have an assignment. In it, the desired functionality to be realized is described in a few sentences. Often a function signature is already included as a clue to the solution.
Examples Supplementary examples are almost always given for clarification with inputs and expected results. For some quite simple tasks, which mainly serve to get to know an API, examples are sometimes omitted.
Input A | Input B | Result |
---|---|---|
[1, 2, 4, 7, 8] | [2, 3, 7, 9] | [2, 7] |
“AB” represents textual specifications.
True/False stands for Boolean values.
123 represent numeric values.
[ value1, value2, .... ] represents collections like sets or lists, but also arrays.
{ key1 : value1, key2 : value2, ... } describes dictionaries.
1.1.3 Solutions
The part of solutions follows the structure described below.
Task definition and examples First, you find the task description again so that you don’t have to constantly flip back and forth between tasks and solutions. Instead, the description of solutions is self-contained.
Algorithm A description of the chosen algorithm follows. For didactics, I sometime present an erroneous way or a not-very-optimal solution to then uncover pitfalls and iteratively come to an improvement. In fact, one or the other brute force solution is sometimes even usable but offers optimization potentials. I then present corresponding, sometimes astonishingly simple, but often very effective improvements.
Python shortcut Sometimes the task explicitly excludes certain Python standard functionality for realizing the solution in order to penetrate a problem algorithmically. In practice, however, you should use the defaults. In the separate short section named “Python shortcut” I show how to make the solution shorter and more concise.
Examination Some of the tasks are quite easy or only serve to get used to syntax or API functionality. For this, it often seems sufficient to execute a few calls directly in the Python command line interpreter. That’s why I don’t use unit tests for this. The same applies for a graphical presentation of a solution, such as displaying a Sudoku board and if the corresponding unit test would probably be more difficult to understand.
However, the more complicated the algorithms become, the more sources of errors exist, such as wrong index values, an accidental or omitted negation, or an overlooked edge case. For this reason, it makes sense to check functionality with the help of unit tests. In this book, for reasons of space, this is only accomplished for important inputs. The companion resources contain over 80 unit tests with roughly 600 test cases, a pretty good start. Nevertheless, in practice, the amount of unit tests and test cases should be even more voluminous if possible.
1.2 Basic Structure of the PyCharm Project
The included PyCharm project closely follows the structure of the book. It offers a separate folder for each relevant chapter (those with exercises), such as ch02_math or ch08_recursion_advanced.
Some of the source code snippets from the respective introductions are located in the subfolder intro. The provided (sample) solutions are collected in their own subfolder named solutions and the modules are named according to the task as follows: ex<no>_<taskdescription>.py.
Utility modules All the useful utility functions developed in the respective chapters are included in the provided PyCharm project in the form of utility modules. They are combined into a module xyz_utils, which resides in its own subdirectory util—for the chapter about mathematical tasks in the subdirectory ch02_math.util. The same applies to the other chapters and topics.
1.3 Basic Framework for Unit Tests with Pytest
In addition to the import needed, this example shows parameterized tests that are extensively used since they allow testing multiple combinations of values in a simple way. For details, please see Appendix A.
1.4 Note on Programming Style
During discussions while writing this book the question came up if certain things should be made more compact. This is why I would like to mention in advance something about the programming style used in this book.
1.4.1 Thoughts on Source Code Compactness
The most important things for me when programming and especially for the implementations in this book are easy comprehensibility and a clear structure. This leads to simplified maintainability and changeability. Therefore, the shown implementations are programmed as understandable as possible. I like to favor this aspect in this book. In practice, it is often easier to live with a bit more verbosity than with bad maintainability but more compact programming.
1.4.2 Example 1
Think briefly about in which of the two methods you feel safe making subsequent changes. And what if you want to add unit tests? How do you find suitable value sets?
1.4.3 Example 2
Let’s bring in another example to illustrate my point. It concerns the following function count_substrings() which is modeled after the standard count() function. The later counts the number of occurrences of one string in another, and for the two inputs “hellohe” and “he,” it returns the result 2.
Would you prefer to change this function or the one shown before?
By the way, the lower one still contains a subtle functional deviation! For the inputs of “XXXX” and “XX” the first variant always consumes the characters and finds two occurrences. The lower, however, moves only one character at a time and thus finds three occurrences.
Further, integrating the previously realized functionality of advancing by the whole search string into the second variant will lead to more obscure source code. On the other hand, you can easily shift by only one character by simply adjusting the upper text[len(value_to_find):] call and then even pull this functionality out of the if.
1.4.4 Decorators and Sanity Checks at the Beginning of Functions
To ensure stable programs, it is often a good idea to check the parameters of central functions for validity. These checks are adequate in the form of simple if statements. In Python, however, this can often be accomplished more elegantly with the help of decorators. To get started, please have a look at Appendix B.
1.4.5 Block Comments in Listings
1.4.6 PEP 8 and the Zen of Python
PEP 8 Coding Standard (PEP = Python Enhancement Proposal)
The Zen of Python—thoughts about Python
PEP 8 Coding Standard
The official coding standard is available online at www.python.org/dev/peps/pep-0008/ as PEP 8 . This is intended to help write clean, consistent, and understandable Python code. There is a tendency in the Python community to put more emphasis on pretty source code than in other languages. In general, make it work somehow is not a sustainable strategy, as I have also motivated.
However, there are a few things about which opinions may differ, for example the limitation of the line length to 79 characters. With today’s HiDPI monitors and resolutions beyond Full-HD, longer lines of around 120 characters are certainly possible. But a line should also not be too long—especially if you want to compare two versions of a file with each other; this can otherwise be annoying.
I may violate indentation hints for split lines to favor readability when optically appropriate. Additionally, I occasionally name lambdas, which usually encapsulate only a tiny piece of functionality and thus should not be named, for a better insight into how things work or express more clearly what was intended. The latter is reported as E731 do not assign a lambda expression, use a def. Please find more info in a moment.
The Zen of Python
Tooling As mentioned, PyCharm offers itself as IDE and provides various hints for style and improvement possibilities directly in the editor. A configuration is possible under Preferences > Editor > Code Style > Python as well as Preferences > Editor > Inspections > Python. In particular, the latter gives you the option to enable PEP8 coding style violation.
E501 line too long (80 > 79 characters: As already stated, 79 characters per line are pretty few these days.
F811 redefinition of unused ‘...’ from line ...: Samples sometimes redefine variables and functions.
E126 continuation line over-indented for hanging indent: Minor deviations from the standard to achieve a nicer layout.
E127 continuation line over-indented for visual indent: Minor deviations from the standard to achieve a nicer layout.
W504 line break after binary operator: Minor deviations from the standard to achieve a nicer layout.
There are other tools for checking your sources. Although somewhat more complex, for larger projects it is recommended to perform a static source code analysis using Sonar. For this, you must install Sonar and a Sonar Runner. In return, though, you get a nice overview as well as a history so that you can quickly recognize both positive and negative trends and take countermeasures if necessary.
1.4.7 More Information
Python Tricks: A Buffet of Awesome Python Features by Dan Bader [Bad17]
Mastering Python by Rick van Hattern [vH16]
1.5 Note on the Exercises
When solving the tasks, the goal is to deal with the appropriate algorithms and data structures. Python offers an extensive collection of functionalities, for example for calculating sums and minimums of lists or even more complex things like computing permutations.
Some of the tasks can be solved with the ready-made standard functionalities in a few lines. However, this is not the goal within this book, because the exercises serve the algorithmic understanding and the extension of your problem-solving strategies. By exploring and solving this yourself, you learn a lot in the process. Developing things yourself is only for training, not for practical use: please keep in mind that in real projects the standard functionality of Python should always be preferred and you should not dream of inventing something yourself for which there is already a ready-made solution. That’s why I often point out in a separate short section named “Python shortcut” a solution that uses standard Python functionality.
1.6 Trying Out the Examples and Solutions
Basically, I prefer to use as comprehensible constructs as possible instead of fancy syntax or API features of special Python versions. In many cases, you can simply copy the source code snippets shown into the Python command line interpreter and execute them. Alternatively, all relevant sources are provided in the PyCharm project that comes with the book. There, the programs may be launched by a main() function or checked by corresponding unit tests that are often available.
1.7 Let’s Go: Discovering the Python Challenge
So, enough of the preface! You are probably already excited about the first challenges through the exercises. I hope you will enjoy this book and gain some new insights while solving the exercises and experimenting with the algorithms.
If you need a refresher on pytest, decorators, or O-notation, you might want to take a look at the appendices first.