6
ALGORITHMS
Algorithms are ancient concepts. An algorithm is nothing more than a set of instructions, much like a cooking recipe. However, the role algorithms play in society is increasing drastically in importance: algorithms and algorithmic decision-making are ubiquitous as computers become a larger and larger part of our lives.
A 2018 study highlights that “Data, in the form of observations about our world, permeate modern society. . . . This information can in turn be used to make informed—and in some cases even fully automated—decisions. . . . It seems likely that such algorithms will interface with human decision-making, a development necessary to gain societal acceptance and thus wide-scale use.”
NOTE
For more information on this study, see “The Growing Ubiquity of Algorithms in Society: Implications, Impacts, and Innovations” by S. C. Olhede and P. J. Wolfe at https://royalsocietypublishing.org/doi/full/10.1098/rsta.2017.0364#d2696064e1.
As society undergoes major trends in automation, artificial intelligence, and ubiquitous computing, the societal gap between those who understand algorithms and those who don’t grows rapidly. For example, the logistics sector undergoes a major trend toward automation—with self-driving cars and trucks on the rise—and professional drivers face the fact that algorithms take over their jobs.
The constantly shifting landscape of sought-after skills and jobs in the 21st century makes it imperative for young people to understand, control, and manipulate basic algorithms. While the only constant is change, the concepts and basics of algorithms and algorithmic theory form the basis upon which much of the upcoming changes are built. Roughly speaking, understand algorithms and you’ll be well equipped to thrive in the upcoming decades.
This chapter aims to improve your understanding of algorithms, focusing more on your intuition and a well-rounded understanding of concepts and practical implementations than on theory. While algorithmic theory is as important as practical implementations and conceptual understanding, many great books focus on the theory part. After reading this chapter, you will intuitively understand some of the most popular algorithms in computer science—and improve your practical Python implementation skills. This may provide you a strong foundation for the upcoming technological breakthroughs.
NOTE
The book Introduction to Algorithms by Thomas Cormen et al. (MIT Press, 2009) is an excellent follow-up resource on algorithmic theory.
Let’s start with a small algorithm to solve a simple problem that is relevant for programmers who want to find good jobs.
Finding Anagrams with Lambda Functions and Sorting
Anagrams are a popular topic in programming interviews to test your computer science vocabulary and how good you are at developing your own simple algorithms. In this section, you’ll learn about a simple algorithm to find anagrams in Python.
The Basics
Two words are anagrams if they consist of the same characters and if every character of the first word appears in the second word exactly once. This is illustrated in Figure 6-1 and in the following examples:
- “listen” → “silent”
- “funeral ” → “real fun”
- “elvis” → “lives”
Figure 6-1: The word elvis is an anagram of the word lives.
We’ll now work on this problem and arrive at a concise Pythonic solution to figuring out whether two words are anagrams. Let’s start coding.
The Code
Our goal is to write a function is_anagram() that takes two strings x1 and x2 and returns True if those are anagrams! Before you read on, pause for a moment and think about the problem. How would you approach it in Python? Listing 6-1 shows one solution.
## One-Liner
➊ is_anagram = lambda x1, x2: sorted(x1) == sorted(x2)
## Results
print(is_anagram("elvis", "lives"))
print(is_anagram("elvise", "livees"))
print(is_anagram("elvis", "dead"))
This code prints three lines. What are they?
How It Works
Two strings are anagrams if they have the same sorted character sequence, so our method is to sort both strings and then make an element-wise comparison. It’s that easy. There is no need for external dependencies. You simply create a function is_anagram() ➊ by using the lambda function definition (see Chapter 1) with two arguments x1 and x2. The function returns the result of the expression sorted(x1) == sorted(x2), which is True if the sorted character sequences consist of the same characters. Here’s the output of the two sorted character sequences:
print(sorted("elvis"))
# ['e', 'i', 'l', 's', 'v']
print(sorted("lives"))
# ['e', 'i', 'l', 's', 'v']
Both strings 'elvis' and 'lives' consist of the same characters, so the sorted list representation is the same. The result of the three print statements is the following:
## Results
print(is_anagram("elvis", "lives")) # True
print(is_anagram("elvise", "livees")) # True
print(is_anagram("elvis", "dead")) # False
As a small side note for advanced coders: the runtime complexity of sorting a sequence of n elements in Python grows asymptotically like the function n log(n). That means our one-liner algorithm is more efficient than the naive solution of checking whether every character exists in both strings and removing the character if this is the case. The naive algorithm grows asymptotically like the quadratic function n**2.
However, there’s another efficient way, called histogramming, whereby you create a histogram for both strings that counts the number of occurrences of all characters in that string, and then compare the two histograms. Assuming a constant-sized alphabet, the runtime complexity of histogramming is linear; it grows asymptotically like the function n. Feel free to implement this algorithm as a small exercise!
Finding Palindromes with Lambda Functions and Negative Slicing
This section introduces another computer science term that’s popular in interview questions: palindromes. You’ll use a one-liner to check whether two words are palindromes of each other.
The Basics
First things first: what is a palindrome? A palindrome can be defined as a sequence of elements (for example, a string or a list) that reads the same backward as it does forward. Here are a few fun examples that are palindromes if you take out the whitespace:
- “Mr Owl ate my metal worm”
- “Was it a car or a cat I saw?”
- “Go hang a salami, I’m a lasagna hog”
- “Rats live on no evil star”
- “Hannah”
- “Anna”
- “Bob”
Our one-liner solution will require your basic understanding of slicing. As you know from Chapter 2, slicing is a Python-specific concept for carving out a range of values from sequence types such as lists or strings. Slicing uses the concise notation [start:stop:step] to slice a sequence starting at index start (inclusive) and ending at index stop (exclusive). The third parameter step allows you to define the step size, which is how many characters from the original sequence your slice will skip before taking the next character (for example, step=2 means that your slice will consist of only every other character). When using a negative step size, the string is traversed in reverse order.
This is everything you need to know to come up with a short and concise one-liner solution in Python.
The Code
When given a string, you want your code to check whether the reverse sequence of characters equals the original sequence, to determine whether the string is a palindrome. Listing 6-2 shows the solution.
## One-Liner
is_palindrome = lambda phrase: phrase == phrase[::-1]
## Result
print(is_palindrome("anna"))
print(is_palindrome("kdljfasjf"))
print(is_palindrome("rats live on no evil star"))
How It Works
The simple one-liner solution does not depend on any external library. You define a lambda function that takes a single argument phrase—the string to be tested—and returns a Boolean value that says whether the sequence of characters remains unchanged when reversed. To reverse the string, you use slicing (see Chapter 2).
The result of the one-liner code snippet is the following:
## Result
print(is_palindrome("anna")) # True
print(is_palindrome("kdljfasjf")) # False
print(is_palindrome("rats live on no evil star")) # True
The first and third strings are palindromes, but the second isn’t. Next let’s dive into another popular computer science concept: permutations.
Counting Permutations with Recursive Factorial Functions
This section explains a simple and effective way of computing the factorial in a single line of code to figure out the maximum number of possible permutations in a data set.
The Basics
Consider the following problem: England’s Premier League has 20 soccer teams, each of which can reach any of the 20 ranks at the end of the season. Given 20 fixed teams, you can calculate how many possible versions of these rankings exist. Note that the question is not how many rankings a single team can achieve (the answer would be 20) but how many total rankings of all teams exist. Figure 6-2 shows just three possible rankings.
Figure 6-2: Three possible rankings of the soccer teams in England’s Premier League
In computer science terminology, you would denote each ranking as a permutation, defined as a specific order of set elements. Our goal is to find the number of possible permutations of a given set. The number of those permutations has important implications for programs involved in betting applications, match prediction, and game analysis. For example, if each of 100 different rankings has the same initial probability, the probability of a specific ranking is 1/100 = 1 percent. This can be used as a base probability (a priori probability) for game-prediction algorithms. Under these assumptions, a randomly guessed ranking has a 1 percent probability of being the correct outcome after one season.
To calculate the number of permutations of a given set of n elements, you can use the factorial function n!. In the next few paragraphs, you’ll learn why this is the case. The factorial is defined as follows:
n! = n × (n – 1) × (n – 2) × . . . × 1
For example:
1! = 1
3! = 3 × 2 × 1 = 6
10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3,628,800
20! = 20 × 19 × 18 × . . . × 3 × 2 × 1 = 2,432,902,008,176,640,000
Let’s take a look at how this works. Say you have a set of 10 elements S = {s0, s1, s2, . . . , s9} and 10 buckets B = {b0, b1, b2, . . . , b9}. You want to place exactly one element from S into each bucket. In the soccer example, the 20 teams are the elements, and the 20 table ranks are the buckets. To get one specific permutation of S, you simply place all elements into all buckets. The number of different ways of assigning elements to buckets is the total number of permutations of elements in S.
The following algorithm determines the number of permutations for a set with 10 elements (which need to be placed into 10 buckets):
- Take the first element from the set S. There are 10 empty buckets so you have 10 options for where you can place the element. You place one element in a bucket.
- Now one bucket is occupied. Take the second element from the set. There now remain 9 empty buckets so you have 9 options.
- Finally, take the 10th (last) element from the set. Nine buckets are now occupied. There is only one empty bucket, so you have one option.
In total, you have 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 10! options. Each potential placement of an element in a bucket represents one permutation of the set elements. The number of permutations of a set with n elements is therefore n!.
Recursively, the factorial function can also be defined as follows:
n! = n × (n – 1)!
The recursion base cases are defined as shown here:
1! = 0! = 1
The intuition behind these base cases is that a set with one element has one permutation, and a set with zero elements has one permutation (there is one way of assigning zero elements to zero buckets).
The Code
The one-liner in Listing 6-3 will compute the number of permutations n! of a set with n elements.
## The Data
n = 5
## The One-Liner
factorial = lambda n: n * factorial(n-1) if n > 1 else 1
## The Result
print(factorial(n))
Try figuring out what the output of this code would be.
How It Works
In the code, you use the recursive definition of the factorial. Let’s quickly improve our intuitive understanding of recursion. Stephen Hawking came up with a concise way to explain recursion: “To understand recursion, one must first understand recursion.”
The Merriam-Webster dictionary defines recursion as “a computer programming technique involving the use of a . . . function . . . that calls itself one or more times until a specified condition is met, at which time the rest of each repetition is processed from the last one called to the first.” At the heart of this definition is the recursive function, which is simply a function that calls itself. But if the function keeps calling itself, it would never stop.
For this reason, we set a certain base case. When the base case is met, the last function call terminates and returns a solution to the second-to-last function call. The second-to-last function call also returns the solution to the third-to-last function call. This causes a chain reaction of propagating the results to the higher recursion level until the first function call returns the final result. This may feel difficult to grasp in a few lines of English text, but stay with me: we will discuss this with the aid of the given one-liner example next.
In general, you create a recursive function f in four steps:
- Break the original problem into smaller problem instances.
- Take the smaller problem instances as the input of function f (which will then break the smaller input into even smaller problem instances and so on).
- Define a base case, which is the smallest possible input that can be solved directly without any further call of the function f.
- Specify how you can recombine the obtained smaller solutions into the larger solution.
You create a lambda function with one argument n and assign the lambda function to the name factorial. Finally, you call the named function factorial(n-1) to calculate the result of the function call factorial(n). The value n could be the number of soccer teams in the Premier League (n=20) or any other value such as the one in Listing 6-3 (n=5).
Roughly speaking, you can use the simpler solution for factorial(n-1) to construct the solution of the harder problem factorial(n) by multiplying the former with the input argument n. As soon as you reach the recursion base case n <= 1, you simply return the hardcoded solution factorial(1) = factorial(0) = 1.
This algorithm shows how you can often find a simple, concise, and efficient way of solving problems by thoroughly understanding the problem first. Choosing the simplest solution idea is one of the most important things you can do when creating your own algorithms. Beginners often find they write cluttered and unnecessarily complicated code.
In this case, the recursive (one-liner) definition of the factorial is shorter than an iterative (one-liner) definition without recursion. As an exercise, try rewriting this one-liner without using a recursive definition and without external libraries—it’s not trivial and certainly not that concise!
Finding the Levenshtein Distance
In this section, you’ll learn about an important practical algorithm to calculate the Levenshtein distance. Understanding this algorithm is more complicated than previous algorithms, so you’ll also train yourself to think through a problem clearly.
The Basics
The Levenshtein distance is a metric to calculate the distance between two strings; in other words, it’s used to quantify the similarity of two strings. Its alternate name, the edit distance, describes precisely what it measures: the number of character edits (insertions, removals, or substitutions) needed to transform one string into another. The smaller the Levenshtein distance, the more similar the strings.
The Levenshtein distance has important applications in things like the autocorrection functionality on your smartphone. If you type helo in your WhatsApp messenger, your smartphone detects a word outside its library and selects several high-probability words as potential replacements, and then sorts them by Levenshtein distance. For example, the word with minimal Levenshtein distance and, hence, maximal similarity is the string 'hello', so your phone may automatically correct helo to hello.
Let’s consider an example with the two less similar strings 'cat' and 'chello'. Knowing that the Levenshtein distance computes the minimal number of edits required to reach the second string starting from the first string, Table 6-1 shows the minimal sequence.
Table 6-1: The Minimal Sequence Needed to Change 'cat' to 'chello'
Current word |
Edit made |
cat |
— |
cht |
Replace a with h |
che |
Replace t with e |
chel |
Insert l at position 3 |
chell |
Insert l at position 4 |
chello |
Insert o at position 5 |
Table 6-1 transforms the string 'cat' to the string 'chello' in five editing steps, meaning the Levenshtein distance is 5.
The Code
Now let’s write a Python one-liner that calculates the Levenshtein distance of strings a and b, a and c, and b and c (see Listing 6-4).
## The Data
a = "cat"
b = "chello"
c = "chess"
## The One-Liner
ls = ➊lambda a, b: len(b) if not a else len(a) if not b else min(
➋ ls(a[1:], b[1:])+(a[0] != b[0]),
➌ ls(a[1:], b)+1,
➍ ls(a, b[1:])+1)
## The Result
print(ls(a,b))
print(ls(a,c))
print(ls(b,c))
Based on what you know so far, try to calculate the output before running the program.
How It Works
Before diving into the code, let’s quickly explore an important Python trick heavily used in this one-liner. In Python, every object has a truth value and is either True or False. Most objects are in fact True and, intuitively, you can probably guess the few objects that are False:
- The numerical value 0 is False.
- The empty string '' is False.
- The empty list [] is False.
- The empty set set() is False.
- The empty dictionary {} is False.
As a rule of thumb, Python objects are considered False if they are empty or zero. Equipped with this information, let’s look at the first part of the Levenshtein function: you create a lambda function that takes two strings a and b and returns the number of edits required to transform string a into string b ➊.
There are two trivial cases: if string a is empty, the minimal edit distance is len(b), since you would just need to insert each character of string b. Similarly, if string b is empty, the minimal edit distance is len(a). That means if either string is empty, you can directly return the correct edit distance.
Let’s say both strings are non-empty. You can simplify the problem by calculating the Levenshtein distance of smaller suffixes of the original strings a and b, as shown in Figure 6-3.
Figure 6-3: Calculating the Levenshtein distance of the words 'cat' and 'chello' recursively by solving the smaller problem instances first
To compute the Levenshtein distance between the strings 'cat' and 'chello' in a recursive manner, you solve the easier problems first (recursively):
- You calculate the distance between the suffixes at and hello because if you know how to transform at into hello, you can easily transform cat into chello by modifying the first character (or by keeping the first character if both strings start with the same character). Assuming this distance is 5, you can now conclude that the distance between cat and chello is also at most 5 because you can reuse the exact same sequence of edits (both words begin with the character c and you don’t have to edit this character).
- You calculate the distance between at and chello. Assuming this distance is 6, you can now conclude that the distance between cat and chello is at most 6 + 1 = 7 because you can simply remove the character c at the beginning of the first word (one additional operation). From there, you can reuse the exact same solution to come from at to chello.
- You calculate the distance between cat and hello. Assuming this distance is 5, you can now conclude that the distance between cat and chello is at most 5 + 1 because you need to insert the character c at the beginning of the second word (one additional operation).
As these are all possible cases of what you can do with the first character (substitution, removal, insertion), the Levenshtein distance between cat and chello is the minimum of the three cases 1, 2, and 3. Let’s now further examine the three cases in Listing 6-4.
First, you calculate the edit distance from a[1:] to b[1:] in a recursive manner ➋. If the leading characters a[0] and b[0] are different, you have to fix it by replacing a[0] by b[0], so you increment the edit distance by one. If the leading characters are the same, the solution of the simpler problem ls(a[1:], b[1:]) is also a solution to the more complex problem ls(a, b), as you’ve seen in Figure 6-3.
Second, you calculate the distance from a[1:] to b in a recursive manner ➌. Say you know the result of this distance (going from a[1:] to b)—how can you calculate the distance one step further from a to b? The answer is to simply remove the first character a[0] from the beginning of a, which is one additional operation. With this, you have reduced the more complicated problem to the easier one.
Third, you calculate the distance from a to b[1:] in a recursive manner ➍. Say you know the result of this distance (going from a to b[1:]). How can you calculate the distance from a to b? In this case, you can simply go one step further (from a to b[1:] to b) by inserting the character b[0] at the beginning of the word b[1:], which would increment the distance by one.
Finally, you simply take the minimum edit distance of all three results (replace the first character, remove the first character, insert the first character).
This one-liner solution demonstrates once again the importance of training your recursion skills. Recursion may not come naturally to you, but rest assured that it will after studying many recursive problems like this one.
Calculating the Powerset by Using Functional Programming
In this section, you’ll learn about an important mathematical concept known as the powerset: the set of all subsets. You’ll need powersets in statistics, set theory, functional programming, probability theory, and algorithmic analysis.
The Basics
The powerset is the set of all subsets of the given set s. It includes the empty set {}, the original set s, and all other possible subsets of the original set. Here are a few examples.
Example 1:
- Given set: s = {1}
- Powerset: P = {{},{1}}
Example 2:
- Given set: s = {1, 2}
- Powerset: P = {{},{1},{2},{1,2}}
Example 3:
- Given set: s = {1, 2, 3}
- Powerset: P = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
To calculate a powerset P_{n} of a set s with n elements, you use the smaller powerset P_{n}_{–1} of a subset of s with (n – 1) elements. Say you want to calculate the powerset of set s = {1, 2, 3}.
- Initialize the powerset P_{0} with zero elements as P_{0} = {{}}. In other words, this is the powerset of the empty set. It contains only the empty set itself.
- To create the powerset P_{n} with n elements from the powerset P_{n}_{–1} with (n – 1) elements, you take one (arbitrary) element x from the set s and incorporate all arising subsets into the larger powerset P_{n} by using the following procedure:
- Go over all sets p in P_{n}_{–1} and create a new subset that consists of the union of x and p. This results in a new temporary set of sets T. For example, if P_{2} = {{}, {1}, {2}, {1,2}}, you’ll create the temporary set of sets T = {{3}, {1,3}, {2,3}, {1,2,3}} by adding the element x = 3 to all sets in P_{2}.
- Merge the new set of sets T with the powerset P_{n}_{–1} to obtain powerset P_{n}. For example, you obtain powerset P_{3} by merging the temporary set T with the powerset P_{2} as follows: P_{3} = T union P_{2}.
- Go to 2 until original set s is empty.
I’ll explain this strategy in more detail in the following section.
The reduce() Function
But first, you need to properly understand an important Python function that you’ll use in the one-liner: the reduce() function. The reduce() function is built into Python 2, but the developers decided it was used little enough that they didn’t include it in Python 3, so you’ll need to import it first from the functools library.
The reduce() function takes three arguments: reduce(function, iterable, initializer). The function arguments define how two values x and y are reduced to a single value (for example, lambda x, y: x + y). This way, you can iteratively reduce two values of an iterable (the second argument) to a single value—until only a single value is left in the iterable. The initializer argument is optional—if you don’t set it, Python assumes the first value of the iterable as a default.
For example, calling reduce(lambda x, y: x + y, [0, 1, 2, 3]) performs the following computation: (((0 + 1)+ 2)+ 3) = 6. In other words, you first reduce the two values x=0 and y=1 to the sum x + y = 0 + 1 = 1. Then, you use this result of the first call of the lambda function as input to the second call of the lambda function: x=1 and y=2. The result is the sum x + y = 1 + 2 = 3. Finally, we use the result of this second call of the lambda function as input to the third call of the lambda function by setting x=3 and y=3. The result is the sum x + y = 3 + 3 = 6.
In the last example, you have seen that the value x always carries the result of the previous (lambda) function. The argument x serves as the accumulated value, while the argument y serves as the update value from the iterable. This is the intended behavior to iteratively “reduce” all values in the iterable argument to a single one. The optional third parameter initializer specifies the initial input for x. This allows you to define a sequence aggregator as shown in Listing 6-5.
List Arithmetic
Before diving into the one-liner, you need to understand two more list operators. The first is the list concatenation operator +, which glues together two lists. For example, the result of the expression [1, 2] + [3, 4] is the new list [1, 2, 3, 4]. The second is the union operator |, which performs a simple union operation on two sets. For example, the result of the expression {1, 2} | {3, 4} is the new set {1, 2, 3, 4}.
The Code
Listing 6-5 provides a one-liner solution that calculates the powerset of a given set s.
# Dependencies
from functools import reduce
# The Data
s = {1, 2, 3}
# The One-Liner
ps = lambda s: reduce(lambda P, x: ➊P + [subset | {x} for subset in P], s, ➋[set()])
# The Result
print(ps(s))
Guess the output of this code snippet!
How It Works
The idea of this one-liner is to start the powerset as an empty set ➋ and repeatedly add subsets to it ➊ until no more subsets can be found.
Initially, the powerset contains only the empty set. In each step, you take one element x out of the data set s and create new subsets that naturally emerge by adding x to all subsets that are already in the powerset ➋. As you’ve seen in the introduction of this section, the size of the powerset therefore doubles each time you consider an additional element x from the data set s. In this way, you can grow the powerset with n subsets one data set element at a time (but by n subsets at a time). Note that the powerset grows exponentially: for any new data set element x, you double the size of the powerset. This is an inherent property of powersets: they quickly overwhelm any storage capacity—even for relatively small data sets with only a few dozen of elements.
You use the reduce() function to maintain the current powerset in the variable P (which initially contains only the empty set). Using list comprehension, the reduce() function creates new subsets—one for each existing subset—and adds them to the powerset P. In particular, it adds the value x from the data set to each subset and thus doubles the size of the powerset (containing the subsets with and without the data set element x). In this way, the reduce() function repeatedly “merges” two elements: the powerset P and an element x from the data set.
Hence, the result of the one-liner is the following:
# The Result
print(ps(s))
# [set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}]
This one-liner nicely demonstrates how important it is that you have a thorough understanding of lambda functions, list comprehension, and set operations.
Caesar’s Cipher Encryption Using Advanced Indexing and List Comprehension
In this section, you’ll learn about an ancient encryption technique called Caesar’s cipher, used by Julius Caesar himself to obfuscate his private conversations. Unfortunately, Caesar’s cipher is extremely simple to crack and offers no real protection, but it’s still used for fun and obfuscation of forum content that should be protected from naive readers’ eyes.
The Basics
Caesar’s cipher is based on the idea of shifting characters to be encrypted by a fixed number of positions in the alphabet. We’ll look at a particular case of Caesar’s cipher called the ROT13 algorithm.
The ROT13 algorithm is a simple encryption algorithm used in many forums (for example, Reddit) to prevent spoilers or hide the semantics of a conversation from newbies. The ROT13 algorithm is easy to decrypt—an attacker can crack your code by running a probabilistic analysis on the distribution of the letters in your encrypted text—even if the attacker doesn’t know by how many positions you shifted each character. You should never rely on this algorithm to actually encrypt your messages! Still, there are many light applications of the ROT13 algorithm:
- Obscure the result of puzzles in online forums.
- Obscure possible spoilers for movies or books.
- Make fun of other weak encryption algorithms: “56-bit DES is at least stronger than ROT13.”
- Obscure email addresses on websites against 99.999 percent of email spam bots.
So ROT13 is more of a popular running gag in internet culture and an educational tool than a serious cipher.
The algorithm can be explained in one sentence: ROT13 = Rotate the string to be encrypted by 13 positions (modulo 26) in the alphabet of 26 characters (see Figure 6-4).
Figure 6-4: The table shows how each character in the alphabet is encrypted and decrypted under the ROT13 algorithm.
In other words, you shift each character by 13 positions in the alphabet. When shifting over the last character, z, you start over at the first position in the alphabet, a.
The Code
Listing 6-6 creates a one-liner to encrypt the string s by using the ROT13 algorithm!
## Data
abc = "abcdefghijklmnopqrstuvwxyz"
s = "xthexrussiansxarexcoming"
## One-Liner
rt13 = lambda x: "".join([abc[(abc.find(c) + 13) % 26] for c in x])
## Result
print(rt13(s))
print(rt13(rt13(s)))
Use Figure 6-4 to crack this code: what’s the output of this code snippet?
How It Works
The one-liner solution encrypts each character separately by moving it 13 positions to the right in the alphabet stored in abc, and then creates a list of these encrypted characters and joins the elements in this list to get the encrypted phrase x.
Let’s take a closer look at how to encrypt each character. You use list comprehension (see Chapter 2) to create the list of encrypted characters by replacing each character c with the character 13 positions to the right in the alphabet. It’s crucial to prevent overshooting for all characters in the alphabet with index >= 13. For instance, when shifting character z with index 25 by 13 positions, you obtain index 25 + 13 = 38, which is not a valid index of the alphabet. To fix this, you use the modulo operator to ensure that when shifting a character beyond the maximum index 25 for character z, you restart our calculation of the final position of the character to be encrypted with index == 0 (character a). Then, you proceed shifting to the right for the remaining of the 13 positions that have not already been applied before the restart (see Figure 6-5). For example, character z is shifted by 13 positions to index 38 modulo 26 (in Python code: 38%26), which is index 12 or character m.
Figure 6-5: Preventing overshooting by restarting the shift operation at index 0, which results in the following shift sequence: 25 > 0 > 1 > . . . > 12
Here’s the critical part of the code that shows exactly how each character c is shifted by 13 positions:
abc[(abc.find(c) + 13) % 26]
First, you find character c’s index in the alphabet abc. Second, you shift the index by adding the integer 13 to character c’s index in the alphabet abc considering our modulo 26 trick (as explained in the previous paragraphs).
The result of the one-liner code snippet is the following:
## Result
print(rt13(s))
# kgurkehffvnafknerkpbzvat
print(rt13(rt13(s)))
# xthexrussiansxarexcoming
To summarize, you’ve learned the special variant of Caesar’s cipher, the ROT13 algorithm, which shifts each character in a string by 13 positions in the alphabet. Shifting it twice by 13 + 13 = 26 index positions results in the original character, meaning encryption and decryption use the same algorithm.
Finding Prime Numbers with the Sieve of Eratosthenes
Finding prime numbers is of critical importance for practical applications such as cryptography. Many public-key methods are safe (from a cryptographic point of view) only because computation of prime factors of large numbers is generally inefficient and slow. We’ll make a one-liner that uses an ancient algorithm to root out all prime numbers from a range of numbers.
The Basics
A prime number n is an integer that’s not divisible without a remainder by any other integer, except for i and n. In other words, for a prime number, there are no two integers a>1 and b>1 whose product equals the prime number: a^{b}=n.
Say you want to check whether your given number n is a prime number. Let’s start with a naive algorithm to determine prime numbers (see Listing 6-7).
def prime(n):
➊ for i in range(2,n):
➋ if n % i == 0:
return False
return True
print(prime(10))
# False
print(prime(11))
# True
print(prime(7919))
# True
The algorithm checks all numbers between 2 and n-1 ➊ to see whether the number n will divide evenly into it with no remainders ➋. For example, when determining whether number n = 10 is a prime number, the algorithm quickly realizes that the expression n % i == 0 evaluates to True for i = 2. It has found a number i that is a divisor of n, so n cannot be a prime number. In this case, the algorithm aborts any further computation and returns False.
The time complexity for checking a single number is the same as the input n: in the worst case, the algorithm needs n loop iterations to check whether number n is a prime number.
Say you want to calculate all prime numbers from 2 to a certain maximal number m. You could simply repeat the prime test from Listing 6-7 m-1 times (see Listing 6-8). However, this comes at huge processing cost.
# Find all prime numbers <= m
m = 20
primes = [n for n in range(2,m+1) if prime(n)]
print(primes)
# [2, 3, 5, 7, 11, 13, 17, 19]
Here we use list comprehension (see Chapter 2) to create a list with all prime numbers smaller than m. We introduce a for loop, meaning the algorithm requires m function calls of is_prime(n) and so the time complexity is bounded by m**2. The number of operations grows quadratically with the input m. To find all prime numbers smaller than m = 100 takes up to m**2 = 10000 operations!
We’ll build a one-liner to drastically reduce this time cost.
The Code
With this one-liner, we’ll write an algorithm to find all prime numbers up to a maximal integer number m that is more time efficient than our naive implementation. The one-liner in Listing 6-9 is inspired by an ancient algorithm called the Sieve of Eratosthenes, which I’ll explain in this section.
## Dependencies
from functools import reduce
## The Data
n=100
## The One-Liner
primes = reduce(lambda r, x: r - set(range(x**2, n, x)) if x in r else r,
range(2, int(n**0.5) + 1), set(range(2, n)))
## The Result
print(primes)
# {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
# 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
You’ll likely need some additional background knowledge to understand what happens here.
How It Works
To be frank, I was hesitant to include this one-liner in the book. It’s confusing, complex, and unreadable. Still, this is the type of code you face in practice, and with this book, I want to ensure you’re able to understand every single line of code—even if it takes some time. I stumbled upon a version of this one-liner at StackOverflow. It is loosely based on an ancient algorithm called the Sieve of Eratosthenes that was designed to calculate prime numbers.
NOTE
I modified the original StackOverflow one-liner for clarity. The original one-liner can be found at https://stackoverflow.com/questions/10639861/python-prime-generator-in-one-line/ at the time of this writing.
The Sieve of Eratosthenes Algorithm
The algorithm creates (conceptually) a huge array of numbers from 2 to m, the maximal integer number. All the numbers in the array are prime candidates, which means that the algorithm considers them to be prime numbers potentially (but not necessarily). During the algorithm, you sieve out the candidates that cannot be prime. Only the ones that remain after this filtering process are the final prime numbers.
To accomplish this, the algorithm calculates and marks the numbers in this array that are not prime numbers. At the end, all unmarked numbers are prime numbers.
The algorithm repeats the following steps:
- Start with the first number 2 and increment it in every step of the process until you find a prime number x. You know that x is prime if it is unmarked because the fact that x is unmarked means that no smaller number than x is a divisor of x—the definition of a prime number.
- Mark all multiples of number x because they are also not prime: number x is a divisor of all those numbers.
- Perform simple optimization: start marking multiples from number x × x instead of 2x because all numbers between 2x and x × x are already marked. There is a simple mathematical argument for this that I will describe later. For now, know that you can start marking from x × x.
Figures 6-6 to 6-11 explain this algorithm step-by-step.
Figure 6-6: Initializing the Sieve of Eratosthenes algorithm
Initially, all numbers between 2 and m = 100 are unmarked (white cells). The first unmarked number 2 is a prime number.
Figure 6-7: Mark all multiples of 2 because they are not prime. Ignore the marked numbers for the rest of the algorithm.
Figure 6-8: Mark multiples of 3 as “non-prime.”
Increment to the next unmarked number, 3. Because it is unmarked at this point, it is a prime number. Because you have marked all multiples of numbers smaller than the current number 3, no smaller number is a divisor of 3. By definition, number 3 must be prime. Mark all multiples of 3 because they are not prime. Start marking from number 3 × 3 because all multiples of 3 between 3 and 3 × 3 = 9 are already marked.
Figure 6-9: Mark multiples of 5 as “non-prime.”
Go to the next unmarked number, 5 (which is a prime number). Mark all multiples of 5. Start marking from number 5 × 5 because all multiples of 5 between 5 and 5 × 5 = 25 are already marked.
Figure 6-10: Mark multiples of 7 as “non-prime.”
Increment to the next unmarked number, 7 (which is a prime number). Mark all multiples of 7. Start marking from number 7 × 7 because all multiples of 7 between 7 and 7 × 7 = 49 are already marked.
Figure 6-11: Mark multiples of 11 as “non-prime.”
Increment to the next unmarked number, 11 (which is a prime number). Mark all multiples of 11. Because you would start marking from number 11 × 11=121, you realize that this is already larger than our maximal number m = 100. This causes the algorithm to terminate. All remaining unmarked numbers are not divisible by any number and are, therefore, prime numbers.
The Sieve of Eratosthenes is much more efficient than the naive algorithm because the naive algorithm checks each number independently, ignoring all previous computations. The Sieve of Eratosthenes, on the other hand, reuses results from previous computational steps—a common idea in many areas of algorithmic optimization. Each time we cross out multiples of a prime number, we essentially save ourselves the tedious work of checking whether this multiple is a prime number: we already know that it isn’t.
You may wonder why we start marking from the squared prime number instead of the prime number itself. For example, in the algorithm in Figure 6-10, you just found prime number 7 and start marking from number 7 × 7 = 49. The reason is that you already marked all other multiples in previous iterations 7 × 2, 7 × 3, 7 × 4, 7 × 5, 7 × 6 because you marked all multiples of numbers smaller than the current prime number 7: 2, 3, 4, 5, 6.
One-Liner Explained
Equipped with a thorough conceptual understanding of the algorithm, you can now start investigating the one-liner solution:
## The One-Liner
primes = reduce(lambda r, x: r - set(range(x**2, n, x)) if x in r else r,
range(2, int(n**0.5) + 1), set(range(2, n)))
This one-liner uses the reduce() function to remove, one step at a time, all marked numbers from the initial set of all numbers between 2 and n (in the one-liner: set(range(2, n))).
You take this set as the initial value for the set of unmarked values r because, initially, all values are unmarked. Now the one-liner goes over all numbers x between 2 and the square root of n (in the one-liner: range(2, int(n**0.5) + 1)) and removes the multiples of x from the set r (starting at x**2)—but only if the number x is a prime number, known because it is not removed from the set r at the current time.
Spend 5–15 minutes rereading this explanation and study the different parts of the one-liner carefully. I promise you’ll find this exercise worthwhile, as it will significantly improve your Python code understanding skills.
Calculating the Fibonacci Series with the reduce() Function
The popular Italian mathematician Fibonacci (original name: Leonardo of Pisa) introduced the Fibonacci numbers in the year 1202 with the surprising observation that these numbers have significance in fields as various as math, art, and biology. This section will show you how to compute the Fibonacci numbers in a single line of code.
The Basics
The Fibonacci series starts with the numbers 0 and 1, and then, each element that follows is the sum of the two previous series elements. The Fibonacci series has the algorithm built in!
The Code
Listing 6-10 calculates a list of the n first Fibonacci numbers starting with the numbers 0 and 1.
# Dependencies
from functools import reduce
# The Data
n = 10
# The One-Liner
fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (n-2), [0, 1])
# The Result
print(fibs)
Study this code and take a guess at the output.
How It Works
You’ll again use the powerful reduce() function. In general, this function is useful if you want to aggregate state information that’s computed on the fly; for example, when you use the previous two Fibonacci numbers just computed to compute the next Fibonacci number. This is difficult to achieve with list comprehension (see Chapter 2), which can’t generally access the values that have been newly created from the list comprehension.
You use the reduce() function with three arguments that correspond to reduce(function, iterable, initializer) to consecutively add the new Fibonacci number to an aggregator object that incorporates one value at a time from the iterable object as specified by the function.
Here, you use a simple list as the aggregator object with the two initial Fibonacci numbers [0, 1]. Remember that the aggregator object is handed as the first argument to the function (in our example, x).
The second argument is the next element from the iterable. However, you initialized the iterable with (n-2) dummy values in order to force the reduce() function to execute function (n-2) times (the goal is to find the first n Fibonacci numbers—but you already have the first two, 0 and 1) You use the throwaway parameter _ to indicate that you are not interested in the dummy values of the iterable. Instead, you simply append the new Fibonacci number to the aggregator list x, calculated as the sum of the previous two Fibonacci numbers.
AN ALTERNATIVE MULTILINE SOLUTION
Repeatedly summing two Fibonacci numbers was already the simple idea of the one-liner in Listing 6-10. Listing 6-11 gives a beautiful alternative solution.
n = 10
x = [0,1]
fibs = x[0:2] + [x.append(x[-1] + x[-2]) or x[-1] for i in range(n-2)]
print(fibs)
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
This code snippet was submitted by one of my email subscribers (feel free to join us at https://blog.finxter.com/subscribe/) and uses list comprehension with side effects: the variable x is updated n-2 times with the new Fibonacci series element. Note that the append() function has no return value, but returns None, which evaluates to False. Thus, the list comprehension statement generates a list of integers using the following idea:
print(0 or 10)
# 10
It doesn’t seem correct to perform the or operation on two integers, but remember that the Boolean type is based on the integer type. Every integer value other than 0 is interpreted as True. Thus, the or operation simply uses the second integer value as a return value instead of converting it to an explicit Boolean value of True. A fine piece of Python code!
In summary, you’ve improved your understanding of another important pattern for Python one-liners: using the reduce() function to create a list that dynamically uses the freshly updated or added list elements to compute new list elements. You will find this useful pattern quite often in practice.
A Recursive Binary Search Algorithm
In this section, you’ll learn about a basic algorithm every computer scientist must know: the binary search algorithm. Binary search has important practical applications in many implementations of basic data structures such as sets, trees, dictionaries, hash sets, hash tables, maps, and arrays. You use these data structures in every single nontrivial program.
The Basics
In brief, the binary search algorithm searches a sorted sequence of values l for a particular value x by repeatedly reducing the size of the sequence by half until only a single value is left: either it’s the searched value or it doesn’t exist in the sequence. In the following, you will examine this general idea in detail.
For example, say you want to search a sorted list for value 56. A naive algorithm would start with the first list element, check whether it’s equal to the value 56, and move on to the next list element until it has checked all elements or found its value. In the worst case, the algorithm goes over every list element. A sorted list with 10,000 elements would take approximately 10,000 operations to check each list element for equality with the searched value. In algorithmic theory language, we say that the runtime complexity is linear in the number of list elements. The algorithm does not leverage all the available information to achieve the greatest efficiency.
The first piece of useful information is that the list is sorted! Using this fact, you can create an algorithm that touches only a few elements in the list and still knows with absolute certainty whether an element exists in the list. The binary search algorithm traverses only log2(n) elements (logarithm of base 2). You can search the same list of 10,000 elements by using only log2(10,000) < 14 operations!
For a binary search, you assume the list is sorted in an ascending manner. The algorithm starts by checking the middle element. If the middle value is bigger than the value you want, you know that all elements between the middle and the last list elements are larger than the value you want. The value you want won’t exist in this half of the list, so you can immediately reject half of the list elements with a single operation.
Similarly, if the searched value is larger than the middle element, you can reject the first half of the list elements. You then simply repeat the procedure of halving the effective list size of elements to be checked in each step of the algorithm. Figure 6-12 shows a visual example.
Figure 6-12: Example run of the binary search algorithm
If the sublist contains an even number of elements, there’s no obvious middle element. In this case, you round down the index of the middle element.
You want to find the value 56 in the sorted list of eight integer values while touching as few elements as possible. The binary search algorithm checks middle element x (rounding down), then discards the half of the list that 56 cannot possibly be in. There are three general results of this check:
- Element x is larger than 56. The algorithm ignores the right part of the list.
- Element x is smaller than value 56. The algorithm ignores the left part of the list.
- Element x is equal to value 56, as in the last line in Figure 6-12. Congratulations—you have just found desired value!
Listing 6-12 shows a practical implementation of the binary search algorithm.
def binary_search(lst, value):
lo, hi = 0, len(lst)-1
while lo <= hi:
mid = (lo + hi) // 2
if lst[mid] < value:
lo = mid + 1
elif value < lst[mid]:
hi = mid - 1
else:
return mid
return -1
l = [3, 6, 14, 16, 33, 55, 56, 89]
x = 56
print(binary_search(l,x))
# 6 (the index of the found element)
This algorithm takes as arguments a list and a value to search for. It then repeatedly halves the search space by using the two variables lo and hi, which define the interval of possible list elements in which the desired value could exist: lo defines the start index, and hi defines the end index of the interval. You check which of the cases the mid element falls in and adapt the interval of potential elements accordingly by modifying the lo and hi values as described.
While this is a perfectly valid, readable, and efficient implementation of the binary search algorithm, it’s not a one-liner solution, yet!
The Code
Now you’ll implement the binary search algorithm in a single line of code (see Listing 6-13)!
## The Data
l = [3, 6, 14, 16, 33, 55, 56, 89]
x = 33
## The One-Liner
➊ bs = lambda l, x, lo, hi: -1 if lo>hi else \
➋ (lo+hi)//2 if l[(lo+hi)//2] == x else \
➌ bs(l, x, lo, (lo+hi)//2-1) if l[(lo+hi)//2] > x else \
➍ bs(l, x, (lo+hi)//2+1, hi)
## The Results
print(bs(l, x, 0, len(l)-1))
Guess the output of this code snippet!
How It Works
Because binary search lends itself naturally to a recursive approach, studying this one-liner will strengthen your intuitive understanding of this important computer science concept. Note that I’ve broken this one-liner solution into four lines for readability, though you can, of course, write it in a single line of code. In this one-liner, I’ve used a recursive way of defining the binary search algorithm.
You create a new function bs by using the lambda operator with four arguments: l, x, lo, and hi ➊. The first two arguments l and x are variables with the sorted list and the value to search for. The lo and hi arguments define the minimal and the maximal index of the current sublist to be searched for the value x. At each recursion level, the code checks a sublist specified by the indices hi and lo, which becomes smaller and smaller by increasing the index lo and decreasing the index hi. After a finite number of steps, the condition lo>hi holds True. The searched sublist is empty—and you haven’t found the value x. This is the base case of our recursion. Because you haven’t found element x, you return -1, indicating that no such element exists.
You use the calculation (lo+hi)//2 to find the middle element of the sublist. If this happens to be your desired value, you return the index of that mid element ➋. Note that you use integer division to round down to the next integer value that can be used as a list index.
If the mid element is larger than the desired value, it means the elements on the right are also larger, so you call the function recursively but adapt the hi index to consider only list elements on the left of the mid element ➌.
Similarly, if the mid element is smaller than the desired value, there is no need to search all elements on the left of the mid element, so you call the function recursively but adapt the lo index to consider only list elements on the right of the mid element ➍.
When searching for the value 33 in the list [3, 6, 14, 16, 33, 55, 56, 89], the result is the index 4.
This one-liner section has strengthened your general code understanding regarding features such as conditional execution, basic keywords, and arithmetic operations, as well as the important topic of programmatic sequence indexing. More important, you’ve learned how to use recursion to make complex problems easier.
A Recursive Quicksort Algorithm
Now you’ll build a one-liner to use the popular algorithm Quicksort, a sorting algorithm that, as the name suggests, quickly sorts the data.
The Basics
Quicksort is both a popular question in many code interviews (asked by Google, Facebook, and Amazon) and a practical sorting algorithm that’s fast, concise, and readable. Because of its elegance, most introductory algorithm classes cover Quicksort.
Quicksort sorts a list by recursively dividing the big problem into smaller problems and combining the solutions from the smaller problems in a way that it solves the big problem.
To solve each smaller problem, the same strategy is used recursively: the smaller problems are divided into even smaller subproblems, solved separately, and combined, placing Quicksort in the class of Divide and Conquer algorithms.
Quicksort selects a pivot element and then places all elements that are larger than the pivot to the right, and all elements that are smaller than or equal to the pivot to the left. This divides the big problem of sorting the list into two smaller subproblems: sorting two smaller lists. You then repeat this procedure recursively until you obtain a list with zero elements that, being sorted, causes the recursion to terminate.
Figure 6-13 shows the Quicksort algorithm in action.
Figure 6-13: Example run of the Quicksort algorithm
Figure 6-13 shows the Quicksort algorithm on a list of unsorted integers [4, 1, 8, 9, 3, 8, 1, 9, 4]. First, it selects 4 as the pivot element, splits up the list into an unsorted sublist [1, 3, 1, 4] with all elements that are smaller than or equal to the pivot, and an unsorted sublist [8, 9, 8, 9] with all elements that are larger than the pivot.
Next, the Quicksort algorithm is called recursively on the two unsorted sublists to sort them. As soon as the sublists contain maximally one element, they are sorted by definition, and the recursion ends.
At every recursion level, the three sublists (left, pivot, right) are concatenated before the resulting list is handed to the higher recursion level.
The Code
You’ll create a function q that implements the Quicksort algorithm in a single line of Python and sorts any argument given as a list of integers (see Listing 6-14).
## The Data
unsorted = [33, 2, 3, 45, 6, 54, 33]
## The One-Liner
q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else []
## The Result
print(q(unsorted))
Now, can you guess—one last time—the output of the code?
How It Works
The one-liner directly resembles the algorithm we just discussed. First, you create a new lambda function q that takes one list argument l to sort. From a high-level perspective, the lambda function has the following basic structure:
lambda l: q(left) + pivot + q(right) if l else []
In the recursion base case—that is, the case that the list is empty and, therefore, trivially sorted—the lambda function returns the empty list [].
In any other case, the function selects the pivot element as the first element of list l, and divides all elements into two sublists (left and right) based on whether they are smaller or larger than the pivot. To achieve this, you use simple list comprehension (see Chapter 2). As the two sublists are not necessarily sorted, you recursively execute the Quicksort algorithm on them too. Finally, you combine all three lists and return the sorted list. Therefore, the result is as follows:
## The Result
print(q(unsorted))
# [2, 3, 6, 33, 33, 45, 54]
Summary
In this chapter, you’ve learned important algorithms in computer science addressing a wide range of topics including anagrams, palindromes, powersets, permutations, factorials, prime numbers, Fibonacci numbers, obfuscation, searching, and sorting. Many of these form the basis of more advanced algorithms and contain the seeds of a thorough algorithmic education. Advancing your knowledge of algorithms and algorithmic theory is one of the most effective ways to improve as a coder. I would even say that the lack of algorithmic understanding is the number one reason most intermediate coders feel stuck in their learning progress.
To help you get unstuck, I regularly explain new algorithms in my “Coffee Break Python” email series for continuous improvement (visit https://blog.finxter.com/subscribe/). I appreciate you spending your valuable time and effort studying all the one-liner code snippets and explanations, and I hope you can already see how your skills have improved. Based on my experience teaching thousands of Python learners, more than half the intermediate coders struggle with understanding basic Python one-liners. With commitment and persistence, you have a good chance of leaving the intermediate coders behind and becoming a Python master (or at least a top 10 percent coder).