DEV Community: David Amos

The Truth About Algorithms and Data Structures

David Amos — Fri, 23 Sep 2022 19:18:25 +0000

You can do a lot with very little.

Modern, high-level languages abstract away lots of details. You don’t need to know the difference between selection sort, bubble sort, merge sort, and quicksort, for instance, to use Python’s sorted() function. It just works.

Do you really need to learn how to use data structures and algorithms?

Well… I've got news for you:

You're already using algorithms and data structures

Ever used a string? That’s a data structure. Written a for loop? That’s an algorithm.

Algorithms and data structures are the building blocks of computer programs — even “Hello, World!” Over time, programmers recognize useful patterns they can apply to a broad range of problems. Language designers bake the most commonly used patterns into easy-to-use interfaces.
You don’t have to know how they’re implemented to reap the benefits.

New coders, especially, need to avoid falling off the deep end.

Focusing on data structures and algorithms too early is a mistake

Let’s be realistic.

You can solve most coding problems without any deep knowledge of algorithms and data structures. Beginners need to focus on learning syntax and getting proficient at translating ideas expressed in a human language into code. You don't want to spend all of your energy on something with little immediate impact.

But here’s the rub:

Ignoring algorithms and data structures is risky

You could end up with your hands tied.

You may write code that works fine in small settings but screeches to a halt on larger workloads. You have a scalability problem. Or you may become so dependent on third-party packages that you can’t solve problems that hit edge cases. You have a specialization problem.

Not everyone that drives a car needs to be a mechanic, though. So how do you know it’s time to take the plunge?

Sometimes data structures and algorithms are crucial

Will your code need to:

Scale to millions of users?
Process enormous amounts of data?
Run on a system with tight memory constraints?

In each of these scenarios, data structures and algorithms are vital. Not because you’ll need to write everything from scratch — although, you might — but because you’ll need tools to evaluate and compare solutions. For some projects, it can be the difference between success and failure.

But there's another reason to learn algorithms and data structures.

One that every coder should know:

Algorithms and data structures are beautiful

One of my favorite quotes about art is from the English painter David Hockney:

Art has to move you, design does not, unless it’s a good design for a bus.

A good algorithm is a work of art. The ingenuity of its inner workings, the cleverness with which it skirts constraints, can elevate an algorithm from the mundane to the downright magical.

Yes, studying algorithms and data structures may be necessary for your career.

Then again, it might not.

But not everything worth learning has to be immediately useful.

Here are some of my favorite books on algorithms and data structures:

For the curious beginner:

Grokking Algorithms by Aditya Bhargava
The Recursive Book of Recursion by Al Sweigart

For folks who want to dig deeper:

Advanced Algorithms and Data Structures by Marcello La Rocca
A Programmer's Guide to Computer Science, Vol. 1 by Dr. William Springer
A Programmer's Guide to Computer Science, Vol. 2 by Dr. William Springer

For folks who want all the details:

Introduction to Algorithms, 3rd Edition by Thomas Cormen, et al

Become a better coder in 5 minutes.

One email, every Saturday, with one actionable tip. Always less than 5 minutes of your time.

Subscribe here →

The Right Way To Compare Floats in Python

David Amos — Mon, 21 Mar 2022 20:07:34 +0000

Floating-point numbers are a fast and efficient way to store and work with numbers, but they come with a range of pitfalls that have surely stumped many fledgling programmers — perhaps some experienced programmers, too! The classic example demonstrating the pitfalls of floats goes like this:



>>> 0.1 + 0.2 == 0.3
False

Seeing this for the first time can be disorienting. But don't throw your computer in the trash bin. This behavior is correct!

This article will show you why floating-point errors like the one above are common, why they make sense, and what you can do to deal with them in Python.

Prefer videos? Here’s the video version of this article:

Your Computer is a Liar (Sort Of)

You've seen that 0.1 + 0.2 is not equal to 0.3 but the madness doesn't stop there. Here are some more confounding examples:



>>> 0.2 + 0.2 + 0.2 == 0.6
False

>>> 1.3 + 2.0 == 3.3
False

>>> 1.2 + 2.4 + 3.6 == 7.2
False

The issue isn't restricted to equality comparisons, either:



>>> 0.1 + 0.2 <= 0.3
False

>>> 10.4 + 20.8 > 31.2
True

>>> 0.8 - 0.1 > 0.7
True

So what's going on? Is your computer lying to you? It sure looks like it, but there's more going on beneath the surface.

When you type the number 0.1 into the Python interpreter, it gets stored in memory as a floating-point number. There's a conversion that takes place when this happens. 0.1 is a decimal in base 10, but floating-point numbers are stored in binary. In other words, 0.1 gets converted from base 10 to base 2.

The resulting binary number may not accurately represent the original base 10 number. 0.1 is one example. The binary representation is 0.000110011…. That is, 0.1 is an infinitely repeating decimal when written in base 2. The same thing happens when you write the fraction ⅓ as a decimal in base 10. You end up with the infinitely repeating decimal 0.333….

Computer memory is finite, so the infinitely repeating binary fraction representation of 0.1 gets rounded to a finite fraction. The value of this number depends on your computer's architecture (32-bit vs. 64-bit). One way to see the floating-point value that gets stored for 0.1 is to use the .as_integer_ratio() method for floats to get the numerator and denominator of the floating-point representation:



>>> numerator, denominator = (0.1).as_integer_ratio()
>>> f"0.1 ≈ {numerator} / {denominator}"
'0.1 ≈ 3602879701896397 / 36028797018963968'

Now use format() to show the fraction accurate to 55 decimal places:



>>> format(numerator / denominator, ".55f")
'0.1000000000000000055511151231257827021181583404541015625'

So 0.1 gets rounded to a number slightly larger than its true value.

🐍 Learn more about number methods like .as_integer_ratio() in my article 3 Things You Might Not Know About Numbers in Python.

This error, known as floating-point representation error , happens way more often than you might realize.

Representation Error is Really Common

There are three reasons that a number gets rounded when represented as a floating-point number:

The number has more significant digits than floating points allow.
The number is irrational.
The number is rational but has a non-terminating binary representation.

64-bit floating-point numbers are good for about 16 or 17 significant digits. Any number with more significant digits gets rounded. Irrational numbers, like π and e, can't be represented by any terminating fraction in any integer base. So again, no matter what, irrational numbers will get rounded when stored as floats.

These two situations create an infinite set of numbers that can't be exactly represented as a floating-point number. But unless you're a chemist dealing with tiny numbers, or a physicist dealing with astronomically large numbers, you're unlikely to run into these problems.

What about non-terminating rational numbers, like 0.1 in base 2? This is where you'll encounter most of your floating-point woes, and thanks to the math that determines whether or not a fraction terminates, you'll brush up against representation error more often than you think.

In base 10, a fraction can be expressed as a terminating fraction if its denominator is a product of powers of prime factors of 10. The two prime factors of 10 are 2 and 5, so fractions like ½, ¼, ⅕, ⅛, and ⅒ all terminate, but ⅓, ⅐, and ⅑ do not. In base 2, however, there is only one prime factor: 2. So only fractions whose denominator is a power of 2 terminate. As a result, fractions like ⅓, ⅕, ⅙, ⅐, ⅑, and ⅒ are all non-terminating when expressed in binary.

You can now understand the original example in this article. 0.1, 0.2, and 0.3 all get rounded when converted to floating-point numbers:



>>> # -----------vvvv Display with 17 significant digits
>>> format(0.1, ".17g")
'0.10000000000000001'

>>> format(0.2, ".17g")
'0.20000000000000001'

>>> format(0.3, ".17g")
'0.29999999999999999'

When 0.1 and 0.2 are added, the result is a number slightly larger than 0.3:



>>> 0.1 + 0.2
0.30000000000000004

Since 0.1 + 0.2 is slightly larger than0.3 and 0.3 gets represented by a number slightly smaller than itself, the expression 0.1 + 0.2 == 0.3 evaluates to False.

❗Floating-point representation error is something every programmer in every language needs to be aware of and know how to handle. It's not specific to Python. You can see the result of printing 0.1 + 0.2 in many different languages over at Erik Wiffin's aptly named website 0.30000000000000004.com.

How To Compare Floats in Python

So, how do you deal with floating-point representation errors when comparing floats in Python? The trick is to avoid checking for equality. Never use ==, >=, or <= with floats. Use the math.isclose() function instead:



>>> import math
>>> math.isclose(0.1 + 0.2, 0.3)
True

math.isclose() checks if the first argument is acceptably close to the second argument. But what exactly does that mean? The trick is to examine the distance between the first argument and the second argument, which is equivalent to the absolute value of the difference of both values:



>>> a = 0.1 + 0.2
>>> b = 0.3
>>> abs(a - b)
5.551115123125783e-17

If abs(a - b) is smaller than some percentage of the larger of a or b, then a is considered sufficiently close to b to be "equal" to b. This percentage is called the relative tolerance. You can specify it with the rel_tol keyword argument of math.isclose() which defaults to 1e-9. In other words, if abs(a - b) is less than 0.00000001 * max(abs(a), abs(b)), then a and b are considered "close" to each other. This guarantees that a and b are equal to about nine decimal places.

You can change the relative tolerance if you need to:



>>> math.isclose(0.1 + 0.2, 0.3, rel_tol=1e-20)
False

Of course, the relative tolerance depends on constraints set by the problem you're solving. For most everyday applications, however, the default relative tolerance should suffice.

There's a problem if one of a or b is zero and rel_tol is less than one, however. In that case, no matter how close the nonzero value is to zero, the relative tolerance guarantees that the check for closeness will always fail. In this case, using an absolute tolerance works as a fallback:



>>> # Relative check fails!
>>> # ---------------vvvv Relative tolerance
>>> # ----------------------vvvvv max(0, 1e-10)
>>> abs(0 - 1e-10) < 1e-9 * 1e-10
False

>>> # Absolute check works!
>>> # ---------------vvvv Absolute tolerance
>>> abs(0 - 1e-10) < 1e-9
True

math.isclose() will do this check for you automatically. The abs_tol keyword argument determines the absolute tolerance. However, abs_tol defaults to 0.0So you'll need to set this manually if you need to check how close a value is to zero.

All in all, math.isclose() returns the result of the following comparison, which combines the relative and absolute tests into a single expression:



abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)

math.isclose() was introduced in PEP 485 and has been available since Python 3.5.

When Should You Use `math.isclose()`?

In general, you should use math.isclose() whenever you need to compare floating-point values. Replace == with math.isclose():



>>> # Don't do this:
>>> 0.1 + 0.2 == 0.3
False

>>> # Do this instead:
>>> math.isclose(0.1 + 0.2, 0.3)
True

You also need to be careful with >= and <= comparisons. Handle the equality separately using math.isclose() and then check the strict comparison:



>>> a, b, c = 0.1, 0.2, 0.3

>>> # Don't do this:
>>> a + b <= c
False

>>> # Do this instead:
>>> math.isclose(a + b, c) or (a + b < c)
True

Various alternatives to math.isclose() exist. If you use NumPy, you can leverage numpy.allclose() and numpy.isclose():



>>> import numpy as np

>>> # Use numpy.allclose() to check if two arrays are equal
>>> # to each other within a tolerance.
>>> np.allclose([1e10, 1e-7], [1.00001e10, 1e-8])
False

>>> np.allclose([1e10, 1e-8], [1.00001e10, 1e-9])
True

>>> # Use numpy.isclose() to check if the elements of two arrays
>>> # are equal to each other within a tolerance
>>> np.isclose([1e10, 1e-7], [1.00001e10, 1e-8])
array([True, False])

>>> np.isclose([1e10, 1e-8], [1.00001e10, 1e-9])
array([True, True])

Keep in mind that the default relative and absolute tolerances are not the same as math.isclose(). The default relative tolerance for both numpy.allclose() and numpy.isclose() is 1e-05 and the default absolute tolerance for both is 1e-08.

math.isclose() is especially useful for unit tests, although there are some alternatives. Python's built-in unittest module has a unittest.TestCase.assertAlmostEqual() method. However, that method only uses an absolute difference test. It's also an assertion, meaning that failures raise an AssertionError, making it unsuitable for comparisons in your business logic.

A great alternative to math.isclose() for unit testing is the pytest.approx() function from the pytest package. Unlike math.isclose(), pytest.approx() only takes one argument — namely, the value you expect:



>>> import pytest
>>> 0.1 + 0.2 == pytest.approx(0.3)
True

Just like math.isclose(), pytest.approx() has rel_tol and abs_tol keyword arguments for setting the relative and absolute tolerances. The default values are different, however. rel_tol has a default value of 1e-6 and abs_tol has a default value of 1e-12.

If the first two arguments passed to pytest.approx() are array-like, meaning they're a Python iterable like a list or a tuple, or even a NumPy array, then pytest.approx() behaves like numpy.allclose() and returns whether or not the two arrays are equal within the tolerances:



>>> import numpy as np                                                          
>>> np.array([0.1, 0.2]) + np.array([0.2, 0.4]) == pytest.approx(np.array([0.3, 0.6])) 
True

pytest.approx() will even work with dictionary values:



>>> {'a': 0.1 + 0.2, 'b': 0.2 + 0.4} == pytest.approx({'a': 0.3, 'b': 0.6})
True

Floating-point numbers are great for working with numbers whenever absolute precision isn't needed. They are fast and memory efficient. But if you do need precision, then there are some alternatives to floats that you should consider.

Floating-Point Alternatives That Are Precise

There are two built-in numeric types in Python that offer full precision for situations where floats are inadequate: Decimal and Fraction.

The `Decimal` Type

The Decimaltype can store decimal values exactly with as much precision as you need. By default, Decimal preserves 28 significant figures, but you can change this to whatever you need to suit the specific problem you're solving:



>>> # Import the Decimal type from the decimal module
>>> from decimal import Decimal

>>> # Values are represented exactly so no rounding error occurs
>>> Decimal("0.1") + Decimal("0.2") == Decimal("0.3")
True

>>> # By default 28 significant figures are preserved
>>> Decimal(1) / Decimal(7)
Decimal('0.1428571428571428571428571429')

>>> # You can change the significant figures if needed
>>> from decimal import getcontext
>>> getcontext().prec = 6 # Use 6 significant figures
>>> Decimal(1) / Decimal(7)
Decimal('0.142857')

You can read more about the Decimal type in the Python docs.

The `Fraction` Type

Another alternative to floating-point numbers is the Fraction type. Fraction can store rational numbers exactly and overcomes representation error issues encountered by floating-point numbers:



>>> # import the Fraction type from the fractions module
>>> from fractions import Fraction

>>> # Instantiate a Fraction with a numerator and denominator
>>> Fraction(1, 10)
Fraction(1, 10)

>>> # Values are represented exactly so no rounding error occurs
>>> Fraction(1, 10) + Fraction(2, 10) == Fraction(3, 10)
True

Both Fraction and Decimal offer numerous benefits over standard floating-point values. However, these benefits come at a price: reduced speed and higher memory consumption. If you don't need absolute precision, you're better off sticking with floats. But for things like financial and mission-critical applications, the tradeoffs incurred by Fraction and Decimal may be worthwhile.

Conclusion

Floating-point values are both a blessing and a curse. They offer fast arithmetic operations and efficient memory use at the cost of inaccurate representation. In this article, you learned:

Why floating-point numbers are imprecise
Why floating-point representation error is common
How to correctly compare floating-point values in Python
How to represent numbers precisely using Python's Fraction and Decimal types

If you learned something new, then there might be even more that you don't know about numbers in Python. For example, did you know the int type isn't the only integer type in Python? Find out what the other integer type is and other little-known facts about numbers in my article 3 Things You Might Not Know About Numbers in Python.

Additional Resources

Want to take your Python skills to the next level? I offer private one-on-one coaching for Python programming and technical writing. Click here to learn more.

Why Can't You Reverse A String With a Flag Emoji?

David Amos — Thu, 27 Jan 2022 02:23:53 +0000

What do you think is the output of the following Python code?

>>> flag = "🇺🇸"
>>> reversed_flag = flag[::-1]
>>> print(reversed_flag)

Questions like this make me want to immediately open a Python REPL and try the code out because I think I know what the answer is, but I'm not very confident in that answer.

Here's my line of thinking when I first saw this question:

The flag string contains a single character.
The [::-1] slice reverses the flag string.
The reversal of a string with a single character is the same as the original string.
Therefore, reversed_flag must be "🇺🇸".

That's a perfectly valid argument. But is the conclusion true? Take a look:

>>> flag = "🇺🇸"
>>> reversed_flag = flag[::-1]
>>> print(reversed_flag)
🇸🇺

What in the world is going on here?

Does `"🇺🇸"` Really Contain a Single Character?

When the conclusion of a valid argument is false, one of its premises must be false, too. Let's start from the top:

The flag string contains a single character.

Is that so? How can you tell how many characters a string has?

In Python, you can use the built-in len() function to get the total number of characters in a string:

>>> len("🇺🇸")
2

Oh.

That's weird. You can only see a single thing in the string "🇺🇸" — namely the US flag — but a length of 2 jives with the result of flag[::-1]. Since the reverse of "🇺🇸" is "🇸🇺", this seems to imply that somehow "🇺🇸" == "🇺 🇸".

How Can You Tell What Characters Are In a String?

There are a few different ways that you can see all of the true characters in a string using Python:

>>> # Convert a string to a list
>>> list("🇺🇸")
['🇺', '🇸']

>>> # Loop over each character and print
>>> for character in "🇺🇸":
... print(character)
...
🇺
🇸

The US flag emoji isn’t the only flag emoji with two characters:

>>> list("🇿🇼") # Zimbabwe
['🇿', '🇼']

>>> list("🇳🇴") # Norway
['🇳', '🇴']

>>> list("🇨🇺") # Cuba
['🇨', '🇺']

>>> # What do you notice?

And then there’s the Scottish flag:

>>> list("🏴󠁧󠁢󠁳󠁣󠁴󠁿")
['🏴', '\U000e0067', '\U000e0062', '\U000e0073', '\U000e0063',
 '\U000e0074', '\U000e007f']

OK, what is that all about?

💪🏻 Challenge: Can you find any non-emoji strings that look like a single character but actually contain two or more characters?

The unnerving thing about these examples is that they imply that you can't tell what characters are in a string just by looking at your screen.

Or, perhaps more deeply, it makes you question your understanding of the term character.

What Is a Character, Anyway?

The term character in computer science can be confusing. It tends to get conflated with the word symbol , which, to be fair, is a synonym for the word character as it's used in English vernacular.

In fact, when I googled character computer science, the very first result I got was a link to a Technopedia article that defines a character as:

“[A] display unit of information equivalent to one alphabetic letter or symbol."

— Technopedia, “Character (Char)”

That definition seems off, especially in light of the US flag example that indicates that a single symbol may be comprised of at least two characters.

The second Google result I get is Wikipedia. In that article, the definition of a character is a bit more liberal:

”[A] character is a unit of information that roughly corresponds to a grapheme, grapheme-like unit, or symbol, such as in an alphabet or syllabary in the written form of a natural language.

— Wikipedia, "Character (computing)”

Hmm... using the word "roughly" in a definition makes the definition feel, shall I say, non-definitive.

But the Wikipedia article goes on to explain that the term character has been used historically to "denote a specific number of contiguous bits.”

Then, a significant clue to the question about how a string with one symbol can contain two or more characters:

“A character is most commonly assumed to refer to 8 bits (one byte) today... All [symbols] can be represented with one or more 8-bit code units with UTF-8.”

— Wikipedia, "Character (computing)”

OK! Maybe things are starting to make a little bit more sense. A character is one byte of information representing a unit of text. The symbols that we see in a string can be made up of multiple 8-bit (1 byte) UTF-8 code units.

Characters are not the same as symbols. It seems reasonable now that one symbol could be made up of multiple characters, just like flag emojis.

But what is a UTF-8 code unit?

A little further down the Wikipedia article on characters, there’s a section called Encoding that explains:

“Computers and communication equipment represent characters using a character encoding that assigns each character to something – an integer quantity represented by a sequence of digits, typically – that can be stored or transmitted through a network. Two examples of usual encodings are ASCII and the UTF-8 encoding for Unicode.”

— Wikipedia, "Character (computing)”

There’s another mention of UTF-8! But now I need to know what a character encoding is.

What Exactly Is a Character Encoding?

According to Wikipedia, a character encoding assigns each character to a number. What does that mean?

Doesn’t it mean that you can pair each character with a number? So, you could do something like pair each uppercase letter in the English alphabet with an integer 0 through 25.

You can represent this pairing using tuples in Python:

>>> pairs = [(0, "A"), (1, "B"), (2, "C"), ..., (25, "Z")]
>>> # I'm omitting several pairs here -----^^^

Stop for a moment and ask yourself: “Can I create a list of tuples like the one above without explicitly writing out each pair?"

One way is to use Python’s enumerate() function. enumerate() takes an argument called iterable and returns a tuple containing a count that defaults to 0 and the values obtained from iterating over iterable.

Here’s a look at enumerate() in action:

>>> letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>>> enumerated_letters = list(enumerate(letters))
>>> enumerated_letters
[(0, 'A'), (1, 'B'), (2, 'C'), (3, 'D'), (4, 'E'), (5, 'F'), (6, 'G'),
(7, 'H'), (8, 'I'), (9, 'J'), (10, 'K'), (11, 'L'), (12, 'M'), (13, 'N'),
(14, 'O'), (15, 'P'), (16, 'Q'), (17, 'R'), (18, 'S'), (19, 'T'), (20, 'U'),
(21, 'V'), (22, 'W'), (23, 'X'), (24, 'Y'), (25, 'Z')]

There’s an easier way to make all of the letters, too.

Python’s string module has a variable called ascii_uppercase that points to a string containing all of the uppercase letters in the English alphabet:

>>> import string
>>> string.ascii_uppercase
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

>>> enumerated_letters = list(enumerate(string.ascii_uppercase))
>>> enumerated_letters
[(0, 'A'), (1, 'B'), (2, 'C'), (3, 'D'), (4, 'E'), (5, 'F'), (6, 'G'),
 (7, 'H'), (8, 'I'), (9, 'J'), (10, 'K'), (11, 'L'), (12, 'M'), (13, 'N'),
 (14, 'O'), (15, 'P'), (16, 'Q'), (17, 'R'), (18, 'S'), (19, 'T'),
 (20, 'U'), (21, 'V'), (22, 'W'), (23, 'X'), (24, 'Y'), (25, 'Z')]

OK, so we’ve associated characters to integers. That means we’ve got a character encoding!

But, how do you use it?

To encode the string ”PYTHON” as a sequence of integers, you need a way to look up the integer associated with each character. But, looking things up in a list of tuples is hard. It’s also really inefficient. (Why?)

Dictionaries are good for looking things up. If we convert enumerated_letters to a dictionary, we can quickly look up the letter associated with an integer:

>>> int_to_char = dict(enumerated_letters)

>>> # Get the character paired with 1
>>> int_to_char[1]
'B'

>>> # Get the character paired with 15
>>> int_to_char[15]
'P'

However, to encode the string ”PYTHON” you need to be able to look up the integer associated with a character. You need the reverse of int_to_char.

How do you swap keys and values in a Python dictionary?

One way is use the reversed() function to reverse key-value pairs from the int_to_char dictionary:

>>> # int_to_char.items() is a "list" of key-value pairs
>>> int_to_char.items()
dict_items([(0, 'A'), (1, 'B'), (2, 'C'), (3, 'D'), (4, 'E'), (5, 'F'),
(6, 'G'), (7, 'H'), (8, 'I'), (9, 'J'), (10, 'K'), (11, 'L'), (12, 'M'),
(13, 'N'), (14, 'O'), (15, 'P'), (16, 'Q'), (17, 'R'), (18, 'S'),
(19, 'T'), (20, 'U'), (21, 'V'), (22, 'W'), (23, 'X'), (24, 'Y'),
(25, 'Z')])

>>> # The reversed() function can reverse a tuple
>>> pair = (0, "A")
>>> tuple(reversed(pair))
('A', 0)

You can write a generator expression that reverses all of the pairs in int_to_char.items() and use that generator expression to populate a dictionary:

>>> char_to_int = dict(reversed(pair) for pair in int_to_char.items())
>>> # Reverse the pair-^^^^^^^^^^^^^^
>>> # For every key-value pair--------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>>> # Get the integer associated with B
>>> char_to_int["B"]
1

>>> # Get the integer associated with P
>>> char_to_int["P"]
15

It’s good that you paired each letter with a unique integer. Otherwise, this dictionary reversal wouldn’t have worked. (Why?)

Now you can encode strings as list of integers using the char_to_int dictionary and a list comprehension:

>>> [char_to_int[char] for char in "PYTHON"]
[15, 24, 19, 7, 14, 13]

And you can convert a list of integers into a string of uppercase characters using int_to_char in a generator expression with Python's string .join() method:

>>> "".join(int_to_char[num] for num in [7, 4, 11, 11, 14])
'HELLO'

But, there’s a problem.

Your encoding can’t handle strings with things like punctuation, lowercase letters, and whitespace:

>>> [char_to_int[char] for char in "monty python!"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <listcomp>
KeyError: 'm'
>>> # ^^^^^^^-----char_to_int has no "m" key

One way to fix this is to create an encoding using a string containing all of the lowercase letters, punctuation marks, and whitespace characters that you need.

But, in Python, there’s almost always a better way. Python’s string module contains a variable called printable that gives you a string containing a whole bunch of printable characters:

>>> string.printable
'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c'

Would you have included all of those characters if you were making your own string from scratch?

Now you can make new dictionaries for encoding and decoding the characters in string.printable:

>>> int_to_printable = dict(enumerate(string.printable))
>>> printable_to_int = dict(reversed(item) for item in int_to_printable.items())

You can use these dictionaries to encode and decode more complicated strings:

>>> # Encode the string "monty python!"
>>> encoded_string = [printable_to_int[char] for char in "monty python!"]
>>> encoded_string
[22, 24, 23, 29, 34, 94, 25, 34, 29, 17, 24, 23, 62]

>>> # Decode the encoded string
>>> decoded_string = "".join(int_to_printable[num] for num in encoded_string)
>>> decoded_string
'monty python!'

You’ve now made two different character encodings! And they really are different. Just look at what happens when you decode the same list of integers using both encodings:

>>> encoded_string = [15, 24, 19, 7, 14, 13]

>>> # Decode using int_to_char (string.ascii_uppercase)
>>> "".join(int_to_char[num] for num in encoded_string)
'PYTHON'

>>> # Decode using int_to_printable(string.printable)
>>> "".join(int_to_printable[num] for num in encoded_string)
'foj7ed'

Not even close!

So, now we know a few things about character encodings:

A character encoding pairs characters with unique integers.
Some character encodings exclude characters that are included in other character encodings.
Two different character encodings may decode the same integers into two different strings.

What does any of this have to do with UTF-8?

What Is UTF-8?

Wikipedia's article on characters mentions two different character encodings:

“Two examples of usual encodings are ASCII and the UTF-8 encoding for Unicode.”

— Wikipedia, "Character (computing)”

OK, so ASCII and UTF-8 are specific kinds of character encoding.

According to the Wikipedia article on ASCII:

ASCII was the most common character encoding on the World Wide Web until December 2007, when UTF-8 encoding surpassed it; UTF-8 is backward compatible with ASCII.

— Wikipedia, "ASCII”

UTF-8 isn’t just the dominant character encoding for the web. It’s also the primary character encoding for Linux and macOS operating systems and is even the default for Python code.

In fact, you can see how UTF-8 encodes characters as integers using the .encode() method on Python string objects. But .encode() doesn't return a list of integers. Instead, encode() returns a bytes object:

>>> encoded_string = "PYTHON".encode()

>>> # The encoded string *looks* like a string still,
>>> # but notice the b in front of the first quote
>>> encoded_string
b'PYTHON'

>>> # b stands for bytes, which is the type of
>>> # object returned by .encode()
>>> type(encoded_string)
<class 'bytes'>

The Python docs describe a bytes object as “an immutable sequence of integers in the range 0 <= x < 256.” That seems a little weird considering that the encoded_string object displays the characters in the string “PYTHON” and not a bunch of integers.

But let’s accept this and see if we can tease out the integers somehow.

The Python docs say that bytes is a "sequence," and Python's glossary defines a sequence as “[a]n iterable which supports efficient element access using integer indices.”

So, it sounds like you can index a bytes object the same way that you can index a Python list object. Let's try it out:

>>> encoded_string[0]
80

Aha!

What happens when you convert encoded_string to a list?

>>> list(encoded_string)
[80, 89, 84, 72, 79, 78]

Bingo. It looks like UTF-8 assigns the letter ”P” to the integer 80, ”Y” to the integer 89, ”T” to the integer 84, and so on.

Let’s see what happens when we encode the string ”🇺🇸” using UTF-8:

>>> list("🇺🇸".encode())
[240, 159, 135, 186, 240, 159, 135, 184]

Huh. Did you expect ”🇺🇸” to get encoded as eight integers?

”🇺🇸” is made up of two characters, namely “🇺” and ”🇸". Let's see how those get encoded:

>>> list("🇺".encode())
[240, 159, 135, 186]

>>> list("🇸".encode())
[240, 159, 135, 184]

OK, things are making more sense now. Both “🇺” and ”🇸" get encoded as four integers, and the four integers corresponding to “🇺” appear first in the list of integers corresponding to ”🇺🇸”, while the four integers corresponding to ”🇸" appear second.

This raises a question, though.

Why Does UTF-8 Encode Some Characters As Four Integers and Others as One Integer?

The character “🇺” is encoded as a sequence of four integers in UTF-8, while the character ”P” gets encoded as a single integer. Why is that?

There’s a hint at the top of Wikipedia’s UTF-8 article:

UTF-8 is capable of encoding all 1,112,064 valid character code points in Unicode using one to four one-byte (8-bit) code units. Code points with lower numerical values, which tend to occur more frequently, are encoded using fewer bytes.

— Wikipedia, “UTF-8”

OK, so that makes it sound like UTF-8 isn’t encoding characters to integers, but instead to something called a Unicode code point. And each code unit can apparently be one to four bytes.

There are a couple of questions we need to answer now:

What is a byte?
What is a Unicode code point?

The word byte has been floating around a lot, so let’s go ahead and give it a proper definition.

A bit is the smallest unit of information. A bit has two states, on or off, that are usually represented by the integers 0 and 1, respectively. A byte is a sequence of eight bits.

You can interpret bytes as integers by viewing their component bits as expressing a number in binary notation.

Binary notation can look pretty exotic the first time you see it. It's a lot like the usual decimal representation you use to write numbers, though. The difference is that each digit can only be a 0 or a 1, and the value of each place in the number is a power of 2, not a power of 10:

Since a byte contains eight bits, the largest number you can represent with a single byte is 11111111 in binary or 255 in decimal notation.

A character encoding that uses one byte for each character can encode a maximum of 255 characters since the maximum 8-bit integer is 255.

255 characters might be enough to encode everything in the English language. Still, there’s no way that it can handle all of the characters and symbols used in written and electronic communication worldwide.

So what do you do? Allowing characters to be encoded as multiple bytes seems like a reasonable solution, and that’s exactly what UTF-8 does.

UTF-8 is an acronym for Unicode Transformation Format — 8-bit. There's that word Unicode again.

According to the Unicode website:

“Unicode provides a unique number for every character, no matter what the platform, no matter what the program, no matter what the language.”

— Unicode website, “What is Unicode?”

Unicode is massive. The goal of Unicode is to provide a universal representation for all written language. Every character gets assigned to a code point — a fancy word for “integer" with some additional organization — and there are a total of 1,112,064 possible code points.

How Unicode code points actually get encoded depends, though. UTF-8 is just one character encoding implementing the Unicode standard. It divides code points into groups of one to four 8-bit integers.

There are other encodings for Unicode. UTF-16 divides Unicode code points into one or two 16-bit numbers and is the default encoding used by Microsoft Windows. UTF-32 can encode every Unicode code point as a single 21-bit integer.

But wait, UTF-8 encodes symbols as code points using one to four bytes. OK, so… why does the 🇺🇸 symbol get encoded with eight bytes?

>>> list("🇺🇸".encode())
[240, 159, 135, 186, 240, 159, 135, 184]

>>> # There are eight integers in the list, a total of eight bytes!

Remember, two characters make up the US flag emoji: 🇺 and 🇸. These characters are called regional indicator symbols. There are twenty-six regional indicators in the Unicode standard representing A–Z English letters. They’re used to encode ISO 3166-1 two-letter country codes.

Here’s what Wikipedia has to say about regional indicator symbols:

These were defined in October 2010 as part of the Unicode 6.0 support for emoji, as an alternative to encoding separate characters for each country flag. Although they can be displayed as Roman letters, it is intended that implementations may choose to display them in other ways, such as by using national flags. The Unicode FAQ indicates that this mechanism should be used and that symbols for national flags will not be directly encoded.

— Wikipedia, “Regional indicator symbol”

In other words, the 🇺🇸 symbol — indeed, the symbol for any country's flag — is not directly supported by Unicode. Operating systems, web browsers, and other places where digital text is used, may choose to render pairs of regional indicators as flags.

Let’s take stock of what we know so far:

Strings of symbols get converted to sequences of integers by a character encoding, usually UTF-8.
Some characters are encoded as a single 8-bit integer by UTF-8, and others require two, three, or four 8-bit integers.
Some symbols, such as flag emojis, are not directly encoded by Unicode. Instead, they are renders of sequences of Unicode characters and may or may not be supported by every platform.

So, when you reverse a string, what gets reversed? Do you reverse the entire sequence of integers in the encoding, or do you reverse the order of the code points, or something different?

How Do You Actually Reverse A String?

Can you think of a way to answer this question with a code experiment rather than trying to look up the answer?

You saw earlier that UTF-8 encodes the string ”PYTHON” as a sequence of six integers:

>>> list("PYTHON".encode())
[80, 89, 84, 72, 79, 78]

What happens if you encode the reversal of the string ”PYTHON”?

>>> list("PYTHON"[::-1].encode())
[78, 79, 72, 84, 89, 80]

In this case, the order of the integers in the list was reversed. But what about other symbols?

Earlier, you saw that the “🇺" symbol is encoded as a sequence of four integers. What happens when you encode its reversal?

>>> list("🇺".encode())
[240, 159, 135, 186]

>>> list("🇺"[::-1].encode())
[240, 159, 135, 186]

Huh. The order of the integers in both lists is the same!

Let’s try reversing the string with the US flag:

>>> list("🇺🇸".encode())
[240, 159, 135, 186, 240, 159, 135, 184]
>>> # ^^^^^^^^^^^^^^---Code point for 🇺
>>> # ^^^^^^^^^^^^^^^^^^---Code point for 🇸

>>> # The code points get swapped!
>>> list("🇺🇸"[::-1].encode())
[240, 159, 135, 184, 240, 159, 135, 186]
>>> # ^^^^^^^^^^^^^^---Code point for 🇸
>>> # ^^^^^^^^^^^^^^^^^^---Code point for 🇺

The order of the integers isn’t reversed! Instead, the groups of four integers representing the Unicode code points for 🇺and 🇸get swapped. The orders of the integers in each code point stay the same.

What Does All Of This Mean?

The title of this article is a lie! You can reverse a string with a flag emoji. But the reversing symbols composed of multiple code points can have surprising results. Especially if you've never heard of things like character encodings and code points before.

Why Is Any Of This Important?

There are a couple of important lessons to take away from this investigation.

First, if you don't know which character encoding was used to encode some text, you can't guarantee that the decoded text accurately represents the original text.

Second, although UTF-8 is widely adopted, there are still many systems that use different character encodings. Keep this in mind when reading text from a file, especially when shared from a different operating system or across international borders. Be explicit and always indicate which encoding is being used to encode or decode text.

For example, Python’s open() function has an encoding parameter that specifies the character encoding to use when reading or writing text to a file. Make use of it.

Where Do You Go From Here?

We’ve covered a lot of ground, but there are still a lot of questions left unanswered. So write down some of the questions you still have and use the investigative techniques you saw in this article to try and answer them.

💡 This article was inspired by a question posed by Will McGugan on Twitter. Check out Will's thread for a whole bunch of characacter encoding craziness.

Here are some questions you might want to explore:

When you convert ”🏴󠁧󠁢󠁳󠁣󠁴󠁿” to a list, you end up with a bunch of strings that start with ”\U”. What are those strings, and what do they represent?
The UTF-8 encoding for ”🏴󠁧󠁢󠁳󠁣󠁴󠁿” contains a whopping 28 bytes of information. What makes 🏴󠁧󠁢󠁳󠁣󠁴󠁿 different from 🇺🇸? What other flags get encoded as 28 bytes?
Are there any flag emojis that get encoded as a single code point?
Many platforms support colored emojis, such as a thumbs-up emoji that can be rendered with different skin tones. How does the same symbol with different colors get encoded?
How can you check if a string containing emojis is a palindrome?

Thanks for reading! Stay curious out there!

Join my free weekly newsletter "Curious About Code" to get curiosity-inducing content in your inbox every Friday.

How To Stay Curious as a Coder

David Amos — Sat, 22 Jan 2022 18:04:00 +0000

Cover photo by Wil Stewart on Unsplash.

It's easy to be complacent about curiosity. Our lives are filled with stress. We craft routines around that stress. Sometimes those routines turn life into an inescapable turnstile. It isn't easy to be curious when your life depends on keeping the wheel turning.

I spend a lot of my time solving problems with Python. Problem-solving demands creativity. Curiosity breeds creativity. The demand for creative software solutions is constant, but curiosity comes and goes.

When your curiosity wanes, don't resign yourself to the idea that some people are naturally more curious about things and that perhaps you're not one of them. Curiosity is not an immutable trait. You can learn how to be more curious.

How To Cultivate Curiosity

Curiosity is contagious. Follow curious people, and you'll likely catch the bug. Once your mind is infected with a framework for curiosity, you instinctively apply that framework to everything.

Mystery is the key to curiosity. Embrace feeling puzzled because puzzles are everywhere. Question absolutes and axioms, even the ones in this article. Devise experiments to test premises.

Learn to recognize when your curiosity ebbs. I know that my curiosity is critically low whenever I stop reading consistently. I'm not talking about reading code —— I mean reading anything. It's a case of intellectual malnutrition, and the cure is a content-rich diet.

Consume Content Voraciously

Get into a habit of passive consumption. Listen to podcasts during your commute or household chores. Watch documentaries during your lunch break. If your mind wanders, let it. Don't focus on one topic. A diverse content diet is more likely to reveal a mystery that stirs you.

Actively consume content about mysteries that particularly draw your attention. Read long-form articles and books. Listen intently and take notes. But refrain from forcing yourself into active consumption. Forced activity stifles joy.

🦁 Key Takeaway: Consume content the same way a lion consumes prey. Spend most of your time passively observing the stream of information before you. When hunger strikes, ferociously stalk your curiosity.

Dive Deeply Into Things That Interest You Right Now

Unlike diets that nourish our bodies, a curiosity-inducing content diet has no plan and no schedule. Explore topics haphazardly, but also explore them deeply. Don't delay your curiosity. Pursue topics that interest you right now.

Get lost in rabbit holes, but avoid ones generated algorithmically. Algorithms have a knack for surfacing similar content. Actively search for answers to questions that arise.

💦 Key takeaway: Curiosity moves like water pulled upwards through a tree's xylem by capillary action. Surrender to the twists and turns. Allow the final destination to be a mystery.

Embrace Learning as a Conversation

Curiosity is a tug-of-war between selfishness and humility. You're compelled by a primal urge to know more. Yet learning requires you to expose a gap in your understanding, to recognize that there is still more to be known.

Learning is a conversation. Participate in that conversation. Ask questions. A good question synthesizes existing knowledge and addresses an acknowledged gap in understanding.

♻️ Key takeaway: Curiosity is like a REPL:

Read: Consume content.

Evaluate: Think critically, ask questions, and discover solutions.

Print: Share what you've learned

Loop: Interpret feedback and start over.

How To Practice Curiosity as a Coder

Getting better at being curious requires practicing curiosity. Fortunately, coding is full of puzzles. There are packages and tools to discover, languages to learn, and implementation details to explore.

Here are two techniques I've used to practice curiosity while coding.

Use Things In Ways They Weren't Intended to Be Used

Push boundaries and perform experiments.

I once worked as a programmer for a commercial audio/visual installation company. On one job, we installed a distributed video switching system controlled by an app. The app sent TCP packets from an iPad to a network switch and used VLAN untagging to connect video receivers on the network to broadcasts streamed by transmitters.

The app was incompatible with the latest switch firmware. The IT department refused to downgrade the firmware, and the app developer couldn't deliver a patch until well after the project deadline. But I could configure the app to send commands to any IP address.

I could write a TCP server to accept commands from the app, convert them to the network switch's protocol, and forward them to the switch. I needed a machine to host the script. The audio processing unit (APU) was a Linux box with plenty of storage and memory. Installing a custom script would void the warranty.

The APU was programmed by a drag-and-drop visual coding interface. One of the available "blocks" could run Lua scripts inside the application's sandbox. But, could a script running in the sandbox receive commands from the app and communicate with the network switch?

There were no documented restrictions, so I ran an experiment. It worked! Even better, script blocks automatically started whenever the APU booted. Video switching worked effortlessly even after reboots from power outages and other incidents.

My curiosity paid off. We completed the job on time. My discoveries created new solutions for clients and spawned internal tools that saved time and money on installations.

Try To Break Things

Destruction can be productive.

I enjoy finding ways to "break" a language. It isn't about finding bugs. It's about finding code examples that exhibit surprising behavior. It always starts with a question.

"How does a Python set determine if two objects are distinct?"

Knowing where to start looking for answers is a crucial skill. The Python docs on sets are pretty good.

"Oh, ok. Sets use an algorithm that checks if two objects have the same hash value and compare equal to each other. If both checks are true, then those objects are indistinguishable from each other, and the set can only contain one of them."

A little bit of knowledge opens the door to new questions.

"Can you 'trick' a set into thinking two different objects are nondistinct?"

Now there's a fun little puzzle. Think about it. An integer hashes to its value. You can control a custom object's hash value with the .__hash__() method. That means you can create an object that hashes to the same value as the integer 1:

class NotOne:
    def __hash__(self):
        return 1

To confuse a set into thinking NotOne instances are equal to 1, you need them to compare equal to 1. You can make NotOne objects compare equal to any object by implementing an .__eq__() method that always returns True:

class NotOne:
    def __hash__(self):
        return 1

    def __eq__(self, other):
        return True

Now see what happens when you create a set containing 1 and an instance of NotOne:

>>> n = NotOne()

>>> # Create a set S containing 1 and n
>>> S = {1, n}

>>> # S only contains 1
>>> S
{1}

>>> # But somehow n is in S!
>>> n in S
True

n is very much a distinct object from 1. n isn't even a number. It doesn't support arithmetic operations. But you'll never be able to put n and 1 in a set together because they fail to meet a set's criteria for distinctness. It feels weird that any set containing 1 also contains n.

"That's pretty weird. I wonder if there's a way to trick a set into thinking two nondistinct objects are distinct from each other?"

For such a thing to be possible requires an object that doesn't compare equal to itself. If you've ever worked with IEEE 754 NaN objects before, you know they fit the bill.

"What happens when you try to put several NaN values into a Python set?"

Let's find out.

>>> S = {float("nan"), float("nan"), float("nan")}
>>> S
{nan, nan, nan}

"Ok, that is weird. But surely you can verify that the set contains a NaN object. Right?"

Behold:

>>> float("nan") in S
False

I love examples like this. In all honesty, nothing is broken - except maybe my brain for a little bit. Seeking out and understanding examples like these strengthens your intuition about code and surfaces new ideas for solving problems.

Where To Go From Here

Start practicing curiosity today. Ask more questions and do more experiments. Be thankful that it's impossible to know everything. There's always a new puzzle to be solved. There are always new things to wonder about.

Continue Learning

Here are five resources to help you learn more about the science of curiosity and cultivate more of it for yourself:

How to become more curious by Scott H. Young. More on the science of curiosity and tips for cutlivating more of it.
This is your brain on curiosity by Matthias Gruber. Explore curiosity's role in how well we remember information.
The psychology and neuroscience of curiosity by Celeste Kidd and Benjamin Y. Haden. A survey of research into curiosity.
Finding curiosity by Steve Mould. In the autumn of 1989 Steve found out that his brain was weird and it changed the course of his life. In a good way. This is the story of his growing passion for education and his quest to find out how people learn.
What the f*ck Python! Here's a fun project attempting to explain what exactly is happening under the hood for some counter-intuitive snippets and lesser-known features in Python.

Practice curiosity with me each week by subscribing to my "Curious About Code" newsletter.