CHAPTER 6

Containers and Randomness

6.1 Dictionaries

6.2 Other Built-In Container Types

6.3 Character Encodings and Strings

6.4 Module random

6.5 Case Study: Games of Chance

Chapter Summary

Solutions to Practice Problems

Exercises

Problems

THE FOCUS OF THIS CHAPTER are the other built-in container classes available in Python. While lists are useful general-purpose containers, there are situations when they are awkward or inefficient to use. For this reason, Python provides other built-in container classes.

In a dictionary container, values stored in the container can be indexed using user-specified indexes we call keys. Dictionaries have many different uses, including counting, and they are general-purpose containers just as list containers are. In addition to dictionaries, we also explain when and how to use the tuple and set built-in container classes.

We also come back to strings one more time and look at them as containers of characters. In today's interconnected world, text is created in one place and read in another, and computers have to be able to deal with encoding and decoding characters from different writing systems. We introduce Unicode as the current standard for encoding characters.

In order to introduce a whole new class of problems and applications, including computer games, we end this chapter with a discussion of how to generate “random” numbers. Then, in this chapter's case study, we use randomness to develop a simple blackjack game.

6.1 Dictionaries

We start the chapter by introducing the very important dictionary container built-in type.

User-Defined Indexes as Motivation for Dictionaries

Suppose we need to somehow store employee records for a company with 50,000 employees. Ideally, we would like to be able to access each employee's record using only the employee's Social Security Number (SSN) or ID number, like this:

>>> employee[987654321]
[‘Yu’, ‘Tsun’]
>>> employee[864209753]
[‘Anna’, ‘Karenina’]
>>> employee[100010010]
[‘Hans’, ‘Castorp’]

At index 987654321 of container named employee is stored the the first and last name of the employee with SSN 987-65-4321, Yu Tsun. The first and last name are stored in a list, which could contain additional information, such as address, date of birth, position, and so on. At index 864209753 and 100010010 will be stored the records for [‘Anna’, ‘Karenina’] and [‘Hans’, ‘Castorp’]. In general, stored at index i will be the record (first and last name) of the employee with SSN i.

If employee were a list, it would have to be a very big list. It would need to be larger than the integer value of the largest employee SSN. Since SSNs are 9-digit numbers, employee would need to be as large as 1,000,000,000. That's big. Even if our system can accommodate a list so large, it would be a huge waste: Most of the list will be empty. Only 50,000 list positions will be used. There is one more problem with lists: SSNs are not really integer values since they are typically denoted using dashes, such as 987-65-4321, and can start with a 0, such as 012-34-5678. Values like 987-65-4321 and 012-34-5678 are better represented as string values ‘012-34-5678’ or ‘987-65-4321’.

The issue is that list items are meant to be accessed using an integer index that represents the item's position in a collection. What we want is something else: We would like to access items using “user-defined indexes,” such as ‘012-34-5678’ or ‘987-65-4321’, as illustrated in Figure 6.1.

Figure 6.1 Motivation for a dictionary. A dictionary is a container that stores items that are accessible using “user-specified” indexes.

Python has a built-in container type called a dictionary that enables us to use “userdefined indexes”. Here is how we can define a dictionary named employee that behaves as we would like:

>>> employee = {
        ‘864-20-9753’: [‘Anna’, ‘Karenina’],
        ‘987-65-4321’: [‘Yu’, ‘Tsun’],
        ‘100-01-0010’: [‘Hans’, ‘Castorp’]}

We wrote the assignment statement using multiple lines to clearly emphasize that “index” ‘864-20-9753’ corresponds to value [‘Anna’, ‘Karenina’], index ‘987-65-4321’ corresponds to value [‘Yu’, ‘Tsun’], and so on. Let's check that the dictionary employee works as we want:

>>> employee[‘987-65-4321’]
[‘Yu’, ‘Tsun’]
>>> employee[‘864-20-9753’]
[‘Anna’, ‘Karenina’]

The dictionary employee differs from a list in that an item in a dictionary is accessed using a user-specified “index” rather than the index representing the items position in the container. We discuss this more precisely next.

Dictionary Class Properties

The Python dictionary type, denoted dict, is a container type, just like list and str. A dictionary contains (key, value) pairs. The general format of the expression that evaluates to a dictionary object is:

{<key 1>:<value 1>, <key 2>:<value 2>, …, <key i>:<value i>}

This expression defines a dictionary containing i key:value pairs. The key and the value are both objects. The key is the “index” that is used to access the value. So, in our dictionary employee, ‘100-01-0010’ is the key and [‘Hans’, ‘Castorp’] is the value.

The (key, value) pairs in a dictionary expression are separated by commas and enclosed in curly braces (as opposed to square brackets, [], used for lists.) The key and value in each (key, value) pair are separated by a colon (:) with the key being to the left and the value to the right of the colon. Keys can be of any type as long as the type is immutable. So string and number objects can be keys while objects of type list cannot. The value can be of any type.

We often say that a key maps to its value or is the index of the value. Because dictionaries can be viewed as a mapping from keys to values, they are often referred to as maps. For example, here is a dictionary mapping day abbreviations ‘Mo’, ‘Tu’, ‘We’, and ‘Th’ (the keys) to the corresponding days ‘Monday’, ‘Tuesday’, ‘Wednesday’, and ‘Thursday’ (the values):

>>> days = {‘Mo’:‘Monday’, ‘Tu’:‘Tuesday’, ‘We’:‘Wednesday’,
        ‘Th’:‘Thursday’}

The variable days refers to a dictionary, illustrated in Figure 6.2, with four (key, value) pairs. The (key, value) pair ‘Mo’:‘Monday’ has key ‘Mo’ and value ‘Monday’, the (key, value) pair ‘Tu’:‘Tuesday’ has key ‘Tu’ and value ‘Tuesday’, etc.

Figure 6.2 Dictionary days. The dictionary maps string keys ‘Mo’, ‘Tu’, ‘We’, and ‘Th’ to string values ‘Monday’, ‘Tuesday’, and so on.

Values in the dictionary are accessed by key, not index (or offset). To access value ‘Wednesday’ in dictionary days, we use key ‘We’

>>> days[‘We’]
‘Wednesday’

and not index 2

   >>> days[2]
   Traceback (most recent call last):
     File “<pyshell#27>”, line 1, in <module>
       days[2]
   KeyError: 2

The KeyError exception tells us that we are using an illegal, in this case undefined, key.

The (key, value) pairs in the dictionary are not ordered, and no ordering assumption can be made. For example, we could define a dictionary d as:

>>> d = {‘b’:23, ‘a’:34, ‘c’:12}

However, when we evaluate d, we may not get the (key, value) pairs in the order in which they were defined:

>>> d
{‘a’: 34, ‘c’: 12, ‘b’: 23}

Dictionaries are mutable, like lists. A dictionary can be modified to contain a new (key, value) pair:

>>> days[‘Fr’] = ‘friday’
>>> days
{‘Fr’: ‘friday’, ‘Mo’: ‘Monday’, ‘Tu’: ‘Tuesday’,
‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’}

This implies that dictionaries have dynamic size. The dictionary can also be modified so an existing key refers to a new value:

>>> days[‘Fr’] = ‘Friday’
>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘Tu’: ‘Tuesday’,
‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’}

An empty dictionary can be defined using the default dict() constructor or simply as:

>>> d = {}

{‘Barack Hussein Obama II’:‘Hawaii’,
 ‘George Walker Bush’:‘Connecticut’,
 ‘William Jefferson Clinton’:‘Arkansas’,
 ‘George Herbert Walker Bush’:‘Massachussetts’,
 ‘Ronald Wilson Reagan’:‘Illinois’,
 ‘James Earl Carter, Jr’:‘Georgia’}

>>> birthState(‘Ronald Wilson Reagan’)
‘Illinois’

Dictionary Operators

The dictionary class supports some of the same operators that the list class supports. We already saw that the indexing operator ([]) can be used to access a value using the key as the index:

>>> days[‘Fr’]
‘Friday’

The indexing operator can also be used to change the value corresponding to a key or to add a new (key, value) pair to the dictionary:

>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘Tu’: ‘Tuesday’,
‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’}
>>> days[‘Sa’] = ‘Sat’
>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘Tu’: ‘Tuesday’,
‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’, ‘Sa’: ‘Sat’}

The length of a dictionary (i.e., the number of (key, value) pairs in it) can be obtained using the len function:

>>> len(days)
6

The in and not in operators are used to check whether an object is a key in the dictionary:

>>> ‘Fr’ in days
True
>>> ‘Su’ in days
False
>>> ‘Su’ not in days
True

Table 6.1 shows some of the operators that can be used with dictionaries.

Table 6.1 Class dict operators. The usage and explanation for commonly used dictionary operators are shown.

There are operators that the list class supports but the class dict does not. For example, the indexing operator [] cannot be used to get a slice of a dictionary. This makes sense: A slice implies an order, and there is no order in a dictionary. Also not supported are operators +, *, max(), min(), and sum(), among others.

>>> rphonebook = {‘(123)456-78-90’:[‘Anna’,‘Karenina’],
                  ‘(901)234-56-78’:[‘Yu’, ‘Tsun’],
                  ‘(321)908-76-54’:[‘Hans’, ‘Castorp’]}
>>> rlookup(rphonebook)
Enter phone number in the format (xxx)xxx-xx-xx: (123)456-78-90
(‘Anna’, ‘Karenina’)
Enter phone number in the format (xxx)xxx-xx-xx: (453)454-55-00
The number you entered is not in use.
Enter phone number in the format (xxx)xxx-xx-xx:

Dictionary Methods

While the list and dict class share quite a few operators, there is only one method that they share: pop(). This method takes a key, and if the key is in the dictionary, it removes the associated (key, value) pair from the dictionary and returns the value:

>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘Tu’: ‘Tuesday’,
‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’, ‘Sa’: ‘Sat’}
>>> days.pop(‘Tu’)
‘Tuesday’
>>> days.pop(‘Fr’)
‘Friday’
>>> days
{‘Mo’: ‘Monday’, ‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’,
‘Sa’: ‘Sat’}

We now introduce some more dictionary methods. When dictionary d1 calls method update() with input argument dictionary d2, all the (key, value) pairs of d2 are added to d1, possibly writing over (key, value) pairs of d1. For example, suppose we have a dictionary of our favorite days of the week:

>>> favorites = {‘Th’:‘Thursday’, ‘Fr’:‘Friday’,‘Sa’:‘Saturday’}

We can add those days to our days dictionary:

>>> days.update(favorites)
>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘We’: ‘Wednesday’,
‘Th’: ‘Thursday’, ‘Sa’: ‘Saturday’}

The (key, value) pair ‘Fr’:‘Friday’ has been added to days and the (key, value) pair ‘Sa’:‘Saturday’ has replaced the pair ‘Sa’:‘Sat’, originally in dictionary days. Note that only one copy of (key, value) pair ‘Th’:‘Thursday’ can be in the dictionary.

Particularly useful dictionary methods are keys(), values(), and items(): They return the keys, values, and (key, value) pairs, respectively, in the dictionary. To illustrate how to use these methods, we use dictionary days defined as:

>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘We’: ‘Wednesday’,
‘Th’: ‘Thursday’, ‘Sa’: ‘Saturday’}

The method keys() returns the keys of the dictionary:

>>> keys = days.keys()
>>> keys
dict_keys([‘Fr’, ‘Mo’, ‘We’, ‘Th’, ‘Sa’])

The container object returned by method keys() is not a list. Let's check its type:

>>> type(days.keys())
<class ‘dict_keys’>

OK, it's a type we have not seen before. Do we really have to learn everything there is to know about this new type? At this point, not necessarily. We only really need to understand its usage. So, how is the object returned by the keys() method used? It is typically used to iterate over the keys of the dictionary, for example:

>>> for key in days.keys():
        print(key, end=‘ ’)

Fr Mo We Th Sa

Thus, the dict_keys class supports iteration. In fact, when we iterate directly over a dictionary, as in:

>>> for key in days:
        print(key, end=‘ ’)

Fr Mo We Th Sa

the Python interpreter translates the statement for key in days to the statement for key in days.keys() before executing it.

Table 6.2 lists some of the commonly used methods that the dictionary class supports; as usual, you can learn more by looking at the online documentation or by typing

>>> help(dict)
…

in the interpreter shell. The dictionary methods values() and items() shown in Table 6.2 also return objects that we can iterate over. The method values() is typically used to iterate over the values of a dictionary:

>>> for value in days.values():
        print(value, end=‘, ’)

Friday, Monday, Wednesday, Thursday, Saturday,

Table 6.2 Methods of the dict class. Listed are some commonly used methods of the dictionary class. d refers to a dictionary.

The method items() is typically used to iterate over the (key, value) pairs of the dictionary:

>>> for item in days.items():
        print(item, end=‘; ’)

(‘Fr’, ‘Friday’); (‘Mo’, ‘Monday’); (‘We’, ‘Wednesday’);
(‘Th’, ‘Thursday’); (‘Sa’, ‘Saturday’);

The (key, value) pairs in the container obtained by evaluating days.items() are shown in a format we have not seen before. This format is a representation of a container object of type tuple, which we introduce in the next section.

>>> days
{‘Fr’: ‘Friday’, ‘Mo’: ‘Monday’, ‘We’: ‘Wednesday’,
‘Th’: ‘Thursday’, ‘Sa’: ‘Saturday’}
>>> keys = days.keys()
>>> keys
dict_keys([‘Fr’, ‘Mo’, ‘We’, ‘Th’, ‘Sa’])

>>> del(days[‘Mo’])
>>> days
{‘Fr’: ‘Friday’, ‘We’: ‘Wednesday’, ‘Th’: ‘Thursday’,
‘Sa’: ‘Saturday’}

>>> keys
dict_keys([‘Fr’, ‘We’, ‘Th’, ‘Sa’])

The container objects returned by keys(), value(), and items() have types that also support various setlike operations, like union and intersection. These operations allow us to, say, combine the keys of two dictionaries or find the values common to both dictionaries. We discuss those operations in more detail in Section 6.2, when we cover the set built-in type.

A Dictionary as a Substitute for Multiway Condition

When we introduced dictionaries at the start of this section, our motivation was the need for a container with user-defined indexes. We now show alternate uses for dictionaries.

Suppose we would like to develop a small function, named complete(), that takes the abbreviation of a day of week, such as ‘Tu’, and returns the corresponding day, which for input ‘Tu’ would be ‘Tuesday’:

>>> complete(‘Tu’)
‘Tuesday’

One way to implement the function would be to use a multiway if statement:

def complete(abbreviation):
    ‘returns day of the week corresponding to abbreviation’
    if abbreviation == ‘Mo’:
        return ‘Monday’
    elif abbreviation == ‘Tu’:
       return ‘Tuesday’
    elif …
         …
    else: # abbreviation must be Su
       return ‘Sunday’

We omit part of the implementation, because it is long, because you should be able to finish it, and also because it is tedious to read and write. We also omit it because it is not an effective way to implement the function.

The main problem with the implementation is that it simply overkill to use a seven-way if statement to implement what is really a “mapping” from day abbreviations to the corresponding days. We now know how to implement such as mapping using a dictionary. Here is a better implementation of function complete():

Module: ch6.py

1  def complete(abbreviation):
2      ‘returns day of the week corresponding to abbreviation’
3
4      days = {‘Mo’: ‘Monday’, ‘Tu’:‘Tuesday’, ‘We’: ‘Wednesday’,
5              ‘Th’: ‘Thursday’, ‘Fr’: ‘Friday’, ‘Sa’: ‘Saturday’,
6              ‘Su’:‘Sunday’}
7
8      return days[abbreviation]

Dictionary as a Collection of Counters

An important application of the dictionary type is its use in computing the number of occurrences of “things” in a larger set. A search engine, for example, may need to compute the frequency of each word in a web page in order to calculate its relevance with respect to search engine queries.

On a smaller scale, suppose that we would like to count the frequency of each name in a list of student names such as:

>>> students = [‘Cindy’, ‘John’, ‘Cindy’, ‘Adam’, ‘Adam’,
                ‘Jimmy’, ‘Joan’, ‘Cindy’, ‘Joan’]

More precisely, we would like to implement a function frequency() that takes a list such as students as input and computes the number of occurrences of each distinct list item.

As usual, there are different ways to implement function frequency(). However, the best way is to have a counter for each distinct item in the list and then iterate over the items in the list: For each visited item, the corresponding counter is incremented. In order for this to work, we need to answer three questions:

Figure 6.3 Dynamically created counters. Counters are created dynamically, in the course of iterating over the list students. When the first item, ‘Cindy’, is visited, a counter for string ‘Cindy’ is created. When second item, ‘John’, is visited, a counter for ‘John’ is created. When the third item, ‘Cindy’, is visited, the counter corresponding to ‘Cindy’ is incremented.

1. How do we know how many counters we need?
2. How do we store all the counters?
3. How do we associate a counter with a list item?

The answer to the first question is not to worry about how many counters we need but to create them dynamically, as needed. In other words, we create a counter for an item only when, in the course of iterating over the list, we encounter the item for the first time. Figure 6.3 illustrates the states of the counters after visiting the first, second, and third name in list students.

Figure 6.3 gives us an insight on how to answer the second question: We can use a dictionary to store the counters. Each item counter will be a value in the dictionary, and the item itself will be the key corresponding to the value. For example, the string ‘Cindy’ would be the key and the corresponding value would be its counter. The dictionary mapping of keys to values also answers the third question.

Now we can also decide what the function frequency() should return: a dictionary mapping each distinct item in the list to the number of times it occurs in the list. Here is an example usage of this function:

>>> students = [‘Cindy’, ‘John’, ‘Cindy’, ‘Adam’, ‘Adam’,
           ‘Jimmy’, ‘Joan’, ‘Cindy’, ‘Joan’,]
>>> frequency(students)
{‘John’: 1, ‘Joan’: 2, ‘Adam’: 2, ‘Cindy’: 3, ‘Jimmy’: 1}

In the dictionary returned by the call frequency(students), shown in Figure 6.4, the keys are the distinct names in the list students and the values are the corresponding frequencies: so ‘John’ occurs once, ‘Joan’ occurs twice, and so on.

Figure 6.4 Dictionary as a container of counters. This dictionary is the output of running function frequency() on list students.

With all the pieces of the puzzle in place, we can now implement the function:

Module: ch6.py

1  def frequency(itemList):
2      ‘returns frequency of items in itemList’
3      counters = {}            # initialize dictionary of counters
4
5      for item in itemList:
6
7          if item in counters: # counter for item already exists
8              counters[item] += 1  # so increment it
9          else:                # counter for item is created
10             counters[item] = 1   # an initialized to 1
11
12    return counters

The dictionary counters is initialized to an empty dictionary in line 3. The for loop iterates through the list of items itemList, and for every item:

• Either the counter corresponding to the item is incremented,
• Or, if no counter exists yet for the item, a counter corresponding to the item is created and initialized to 1.

Note the use of an accumulator pattern to accumulate frequency counts.

>>> text = ‘all animals are equal but some 
animals are more equal than others’
>>> wordCount(text)
all      appears 1 time.
animals  appears 2 times.
some     appears 1 time.
equal    appears 2 times.
but      appears 1 time.
are      appears 2 times.
others   appears 1 time.
than     appears 1 time.
more     appears 1 time.

6.2 Other Built-In Container Types

In this section, we introduce two more useful container classes: tuple and set.

Class tuple

In Practice Problem 6.2, we defined a dictionary that maps phone numbers to (the first and last name of) individuals:

>>> rphonebook = {‘(123)456-78-90’:[‘Anna’,‘Karenina’],
                  ‘(901)234-56-78’:[‘Yu’, ‘Tsun’],
                  ‘(321)908-76-54’:[‘Hans’, ‘Castorp’]}

We used this dictionary to implement a reverse phone book lookup application: Given a phone number, the app returns the individual that number is assigned to. What if, instead, we wanted to build an app that implements a standard phone book lookup: Given a person's first and last name, the app would return the phone number assigned to that individual.

For the standard lookup app, a dictionary such as rphonebook is not appropriate. What we need is a mapping from individuals to phone numbers. So let's define a new dictionary that is, effectively, the inverse of the mapping of rphonebook:

>>> phonebook = {[‘Anna’,‘Karenina’]:‘(123)456-78-90’,
                 [‘Yu’, ‘Tsun’]:‘(901)234-56-78’,
                 [‘Hans’, ‘Castorp’]:‘(321)908-76-54’}
Traceback (most recent call last):
  File “<pyshell#242>”, line 1, in <module>
    phonebook = {[‘Anna’,‘Karenina’]:‘(123)456-78-90’,
  TypeError: unhashable type: ‘list’

Oops, we have a problem. The problem is that we are trying to define a dictionary whose keys are list objects. Recall that the list type is mutable and that dictionary keys must be of a type that is immutable.

To the rescue comes a Python collection class that behaves like a list in almost every aspect except that it is immutable: the class tuple. A tuple object contains a sequence of values separated by commas and enclosed in parentheses (()) instead of brackets ([ ]):

>>> days = (‘Mo’, ‘Tu’, ‘We’)
>>> days
(‘Mo’, ‘Tu’, ‘We’)

Let's check the type of the object days refers to:

>>> type(days)
<class ‘tuple’>

The parentheses are optional in simple expressions like this assignment:

>>> days = ‘Mo’, ‘Tu’, ‘We’, ‘Th’
>>> days
(‘Mo’, ‘Tu’, ‘We’, ‘Th’)

The indexing operator can be used to access tuple items using the item's offset as the index, just like in list objects:

>>> days[2]
‘We’

However, any attempt to change the tuple object results in a TypeError exception being thrown:

>>> days[4] = ‘th’
Traceback (most recent call last):
  File “<pyshell#261>”, line 1, in <module>
    days[4] = ‘th’
TypeError: ‘tuple’ object does not support item assignment

Also, adding new items to a tuple object is not allowed:

>>> days[5] = ‘Fr’
Traceback (most recent call last):
  File “<pyshell#260>”, line 1, in <module>
    days[5] = ‘Fr’
TypeError: ‘tuple’ object does not support item assignment

So, as in lists, items in tuple containers are ordered and are accessed using an index (offset). Unlike lists, tuple containers are immutable. To learn more about the tuple class, read the online documentation or just use the documentation function help().

tuple Objects Can Be Dictionary Keys

Because tuple objects are immutable, they can be used as dictionary keys. Let's get back to our original goal of constructing a dictionary that maps (the first and last name of) individuals to phone numbers. We can now use tuple objects as keys, instead of list objects:

>>> phonebook = {(‘Anna’,‘Karenina’):‘(123)456-78-90’,
                 (‘Yu’, ‘Tsun’):‘(901)234-56-78’,
                 (‘Hans’, ‘Castorp’):‘(321)908-76-54’}
>>> phonebook
{(‘Hans’, ‘Castorp’): ‘(321)908-76-54’,
(‘Yu’, ‘Tsun’): ‘(901)234-56-78’,
(‘Anna’, ‘Karenina’): ‘(123)456-78-90’}

Let's check that the indexing operator works as we want:

>>> phonebook[(‘Hans’, ‘Castorp’)]
‘(321)908-76-54’

Now you can implement the standard phone book lookup tool.

>>> phonebook = {(‘Anna’,‘Karenina’):‘(123)456-78-90’,
                 (‘Yu’, ‘Tsun’):‘(901)234-56-78’,
                 (‘Hans’, ‘Castorp’):‘(321)908-76-54’}

>>> lookup(phonebook)
Enter the first name: Anna
Enter the last name: Karenina
(123)456-78-90
Enter the first name: Yu
Enter the last name: Tsun
(901)234-56-78

Dictionary Method items(), Revisited

Before moving on, let's go back and take another look at the dictionary method items(). We used it in the previous section to iterate over the (key, value) pairs of dictionary days:

>>> days = {‘Mo’: ‘Monday’, ‘Tu’: ‘Tuesday’, ‘We’: ‘Wednesday’,
            ‘Th’: ‘Thursday’}

The items() dictionary method returns a container that contains tuple objects, one for each (key, value) pair:

>>> days.items()
dict_items([(‘We’, ‘Wednesday’), (‘Mo’, ‘Monday’),
            (‘Th’, ‘Thursday’), (‘Tu’, ‘Tuesday’)])

Each tuple contains two items: the key and the value of the corresponding (key, value) pair.

>>> days = (‘Mo’)

>>> days
‘Mo’
>>> type(days)
<class ‘str’>

>>> t = (3)
>>> t
3
>>> type(3)
<class ‘int’>

>>> (‘Mo’+‘Tu’)*3
‘MoTuMoTuMoTu’
>>> ‘Mo’+(‘Tu’*3)
‘MoTuTuTu’

>>> days = (‘Mo’,)

>>> days
(‘Mo’,)
>>> type(days)
<class ‘tuple’>

Class set

Another built-in Python container type is the set class. The set class has all the properties of a mathematical set. It is used to store an unordered collection of items, with no duplicate items allowed. The items must be immutable objects. The set type supports operators that implement the classical set operations: set membership, intersection, union, symmetric difference, and so on. It is thus useful whenever a collection of items is modeled as a mathematical set. It is also useful for duplicate removal.

A set is defined using the same notation that is used for mathematical sets: a sequence of items separated by commas and enclosed in curly braces: { }. Here is how we would assign the set of three phone numbers (as strings) to variable phonebook1:

>>> phonebook1 = {‘123-45-67’, ‘234-56-78’, ‘345-67-89’}

We check the value and type of phonebook1:

>>> phonebook1
{‘123-45-67’, ‘234-56-78’, ‘345-67-89’}
>>> type(phonebook1)
<class ‘set’>

If we had defined a set with duplicate items, they would be ignored:

>>> phonebook1 = {‘123-45-67’, ‘234-56-78’, ‘345-67-89’,
                  ‘123-45-67’, ‘345-67-89’}
>>> phonebook1
{‘123-45-67’, ‘234-56-78’, ‘345-67-89’}

Using the set Constructor to Remove Duplicates

The fact that sets cannot have duplicates gives us the first great application for sets: removing duplicates from a list. Suppose we have a list with duplicates, such as this list of ages of students in a class:

>>> ages = [23, 19, 18, 21, 18, 20, 21, 23, 22, 23, 19, 20]

To remove duplicates from this list, we can convert the list to a set, using the set constructor. The set constructor will eliminate all duplicates because a set is not supposed to have them. By converting the set back to a list, we get a list with no duplicates:

>>> ages = list(set(ages))
>>> ages
[18, 19, 20, 21, 22, 23]

There is, however, one major caveat: The elements have been reordered.

>>> phonebook2 = {}

>>> type(phonebook2)
<class ‘dict’>

>>> phonebook2 = set()

>>> phonebook2
set()
>>> type(phonebook2)
<class ‘set’>

set Operators

The set class supports operators that correspond to the usual mathematical set operations. Some are operators that can also be used with list, string, and dictionary types. For example, the in and not in operators are used to test set membership:

>>> ‘123-45-67’ in phonebook1
True
>>> ‘456-78-90’ in phonebook1
False
>>> ‘456-78-90’ not in phonebook1
True

The len() operator returns the size of the set:

>>> len(phonebook1)
3

Comparison operators ==, !=, <, <=, >, and >= are supported as well, but their meaning is set-specific. Two sets are “equal” if and only if they have the same elements:

>>> phonebook3 = {‘345-67-89’,‘456-78-90’}
>>> phonebook1 == phonebook3
False
>>> phonebook1 != phonebook3
True

As shown in Figure 6.5, sets phonebook1 and phonebook3 do not contain the same elements.

Figure 6.5 Three phone book sets. The Venn diagram of sets phonebook1, phonebook2, and phonebook3 is shown.

A set is “less than or equal to” another set if it is a subset of it, and a set is “less than another set” if it is a proper subset of it. So, for example:

>>> {‘123-45-67’, ‘345-67-89’} <= phonebook1
True

As Figure 6.5 shows, the set {‘123-45-67’, ‘345-67-89’} is a subset of set phonebook1. However, phonebook1 is not a proper subset of phonebook1:

>>> phonebook1 < phonebook1
False

The mathematical set operations union, intersection, difference, and symmetric difference are implemented as set operators |, &, -, and ^, respectively. Each set operation takes two sets and returns a new set. The union of two sets contains all elements that are in either set:

>>> phonebook1 | phonebook3
{‘123-45-67’, ‘234-56-78’, ‘345-67-89’, ‘456-78-90’}

The intersection of two sets contains all elements that are in both sets:

>>> phonebook1 & phonebook3
{‘345-67-89’}

The difference between two sets contains all elements that are in the first set but not the second one:

>>> phonebook1 - phonebook3
{‘123-45-67’, ‘234-56-78’}

The symmetric difference of two sets contains all elements that are either in the first set or in the second set, but not both:

>>> phonebook1 ^ phonebook3
{‘123-45-67’, ‘234-56-78’, ‘456-78-90’}

Use Figure 6.5 to check that the set operators work as expected.

Before we move on to discussing the set class methods, we summarize in Table 6.3 the commonly used set operators that we just covered.

Table 6.3 Class set operators. Shown are the usage and explanation for commonly used set operators.

set Methods

In addition to operators, the set class supports a number of methods. The set method add() is used to add an item to a set:

>>> phonebook3.add(‘123-45-67’)
>>> phonebook3
{‘123-45-67’, ‘345-67-89’, ‘456-78-90’}

The method remove() is used to remove an item from a set:

>>> phonebook3.remove(‘123-45-67’)
>>> phonebook3
{‘345-67-89’, ‘456-78-90’}

Finally, the method clear() is used to empty a set:

>>> phonebook3.clear()

We check that phonebook3 is indeed empty:

>>> phonebook3
set()

To learn more about the set class, read the online documentation or use the help() documentation function.

>>> phonebook4 = {‘234-56-78’, ‘456-78-90’}
>>> phonebooks = [phonebook1, phonebook2, phonebook3, phonebook4]
>>> sync(phonebooks)
{‘234-56-78’, ‘456-78-90’, ‘123-45-67’, ‘345-67-89’}

6.3 Character Encodings and Strings

The string type, str, is the Python type for storing text values. In Chapters 2 and 4, we have seen how to create string objects and manipulate them using string operators and methods. The assumption then was that we were dealing with string objects containing English text. That assumption helped make string processing intuitive, but it also hid the complexity, and richness, of string representations. We now discuss the complexity of text representations that is due to the huge number of symbols and characters in the world languages we speak and write. We discuss specifically what kind of characters strings can contain.

Character Encodings

String objects are used to store text, that is, a sequence of characters. The characters could be upper- and lowercase letters from the alphabet, digits, punctuation marks, and possibly symbols like the dollar sign ($). As we saw in Chapter 2, in order to create a variable whose value is the text ’An apple costs $0.99!’, we just need to do:

>>> text = ‘An apple costs $0.99!’

The variable text then evaluates to the text:

>>> text
‘An apple costs $0.99!’

While all this may sound very clean and straightforward, strings are somewhat messy. The problem is that computers deal with bits and bytes, and string values need to be somehow encoded with bits and bytes. In other words, each character of a string value needs to be mapped to a specific bit encoding, and this encoding should map back to the character.

But why should we care about this encoding? As we saw in Chapters 2 and 4, manipulating strings is quite intuitive, and we certainly did not worry about how strings are encoded. Most of the time, we do not have to worry about it. However, in a global Internet, documents created in one location may need to be read in another. We need to know how to work with characters from other writing systems, whether they are characters from other languages, such as French, Greek, Arabic, or Chinese, or symbols from various domains, such as math, science, or engineering. As importantly, we need to understand how strings are represented because, as computer scientists, we do like to know what is below the hood.

ASCII

For many years, the standard encoding for characters in the English language was ASCII encoding. The American Standard Code for Information Interchange (ASCII) was developed in the 1960s. It defines a numeric code for 128 characters, punctuation, and a few other symbols common in the American English language. Table 6.4 shows the decimal ASCII codes for the printable characters.

Let's explain what the entries of this table mean. The decimal ASCII code for lowercase a is 97. The & sign is encoded with decimal ASCII code 38. ASCII codes 0 through 32 and 127 include nonprintable characters, such as backspace (decimal code 8), horizontal tab (decimal code 9), and line feed (decimal code 10). You can explore the ASCII encodings using the Python function ord(), which returns the decimal ASCII code of a character:

>>> ord(‘a’)
97

The sequence of characters of a string value (such as ‘dad’) is encoded as a sequence of ASCII codes 100, 97, and 100. What is stored in memory is exactly this sequence of codes. Of course, each code is stored in binary. As ASCII decimal codes go from 0 to 127, they can be encoded with seven bits; because a byte (eight bits) is the smallest memory storage unit, each code is stored in one byte.

For example, the decimal ASCII code for lowercase a is 97, which corresponds to binary ASCII code 1100001. So, in the ASCII encoding, character a is encoded in a single byte with the first bit being a 0 and the remaining bits being 1100001. The resulting byte 01100001 can be described more succinctly using a two-digit hex number 0x61 (6 for the leftmost four bits, 0110, and 1 for the rightmost 4 bits, 0001). In fact, it it common to use hex ASCII codes (as a shorthand for ASCII binary codes).

Table 6.4 ASCII encoding. Printable ASCII characters and their corresponding decimal codes are shown. The character for decimal code 43, for example, is the operator +. The character for decimal code 32 is the blank space, which is displayed as a blank space.

The symbol &, for example, is encoded with decimal ASCII code 38, which corresponds to binary code 0100110 or hex code 0x26.

>>> encoding(‘dad’)
Char Decimal  Hex   Binary
 d       100   64  1100100
 a        97   61  1100001
 d       100   64  1100100

The function chr() is the inverse of function ord(). It take a numeric code and returns the character corresponding to it.

>>> chr(97)
‘a’

>>> char(62, 67)
62 : >
63 : ?
64 : @
65 : A
66 : B
67 : C

Unicode

ASCII is an American standard. As such, it does not provide for characters not in the American English language. There is no French ‘é’, Greek ‘Δ’, or Chinese in ASCII encoding. Encodings other than ASCII were developed to handle different languages or groups of languages. This raises a problem, however: With the existence of different encodings, it is likely that some encodings are not installed on a computer. In a globally interconnected world, a text document that was created on one computer will often need to be read on another, a continent away. What if the computer reading the document does not have the right encoding installed?

Unicode was developed to be the universal character-encoding scheme. It covers all characters in all written languages, modern or ancient, and includes technical symbols from science, engineering, and mathematics, punctuation, and so on. In Unicode, every character is represented by an integer code point. The code point is not necessarily the actual byte representation of the character, however; it is just the identifier for the particular character.

For example, the code point for lowercase ‘k’ is the integer with hex value 0x006B, which corresponds to decimal value 107. As you can see in Table 6.4, 107 is also the ASCII code for letter ‘k’. Unicode conveniently uses a code point for ASCII characters that is equal to their ASCII code.

How do you incorporate Unicode characters into a string? To include character ‘k’, for example, you would use the Python escape sequence u006B:

>>> ‘u006B’
‘k’

In the next example, the escape sequence u0020 is used to denote the Unicode character with code point 0x0020 (in hex, corresponding to decimal 32). This is, of course, the blank space (see Table 6.4):

>>> ‘Hellou0020World !’
‘Hello World !’

We now try a few examples in several different languages. Let's start with my name in Cyrillic:

Here is ‘Hello World!’ in Greek:

Finally, let's write ‘Hello World!’ in Chinese:

>>> ‘u0020’ > ‘u0409’
False
>>> ‘u0020’ < ‘u0409’
True

Let's check that the basic string operators work on this string.

String operators work regardless of the alphabet used in the string. Now let's see whether the ord() and chr() functions extend from ASCII to Unicode:

They do! Note that 19990 is the decimal value of hex value 0x4e16, which is of course the Unicode code point of character [uni4E16]. Thus, the built-in function ord() really takes a Unicode character and outputs the decimal value of its Unicode code point, and chr() does the inverse. The reason they both also work for ASCII characters is that the Unicode code points for ASCII characters are, by design and as noted, the ASCII codes.

UTF-8 Encoding for Unicode Characters

A Unicode string is a sequence of code points that are numbers from 0 to 0x10FFFF. Unlike ASCII codes, however, Unicode code points are not what is stored in memory. The rule for translating a Unicode character or code point into a sequence of bytes is called an encoding.

There is not just one but several Unicode encodings: UTF-8, UTF-16, and UTF-32. UTF stands for Unicode Transformation Format, and each UTF-x defines a different way to map a Unicode code point to a byte sequence. UTF-8 has become the preferred encoding for e-mail, web pages, and other applications where characters are stored or sent across a network. In fact, the default encoding when you write Python 3 programs is UTF-8. One of the features of UTF-8 is: Every ASCII character (i.e., every symbol in Table 6.4) has a UTF-8 encoding that is exactly the 8-bit (1-byte) ASCII encoding. This means that an ASCII text is a Unicode text encoded with the UTF-8 encoding.

In some situations, your Python program will receive text without a specified encoding. This happens, for example, when the program downloads a text document from the World Wide Web (as we will see in Chapter 11). In that case, Python has no choice but to treat the “text” as a sequence of raw bytes stored in an object of type bytes. This is because files downloaded from the web could be images, video, audio, and not just text.

Consider this content of a text file downloaded from the web:

>>> content
b‘This is a text document
posted on the
WWW.
’

Variable content refers to an object of type bytes. As you can verify, the letter b in the front of the “string” indicates that:

>>> type(content)
<class ‘bytes’>

To decode it to a string encoded using the UTF-8 Unicode encoding, we need to use the decode() method of the bytes class:

>>> content.decode(‘utf-8’)
‘This is a text document
posted on the
WWW.
’

If the method decode() is called without arguments, the default, platform-dependent encoding is used, which is UTF-8 for Python 3 (or ASCII for Python 2).

6.4 Module random

Random numbers are useful for running simulations in science, engineering, and finance. They are needed in modern cryptographic protocols that provide computer security, communication privacy, and authentication. They also are a necessary component in games of chance, such as poker or blackjack, and help make computer games less predictable.

Truly random numbers are not easy to obtain. Most computer applications that require random numbers use numbers generated by a pseudorandom number generator instead. The “pseudo” in “pseudorandom” means fake, or not real. Pseudorandom number generators are programs that produce a sequence of numbers that “look” random and are good enough for most applications that need a random numbers.

In Python, pseudorandom number generators and associated tools are available through the random module. As usual, if we need to use functions in the random module, we need to import it first:

>>> import random

Next we describe a few functions in the random module that are particularly useful.

Choosing a Random Integer

We start with function randrange(), which takes a pair of integers a and b and returns some number in the range from—and including—a up to—and not including—b with each number in the range equally likely. Here is how we would use this function to simulate several (six-sided) die tosses:

>>> random.randrange(1,7)
2
>>> random.randrange(1,7)
6
>>> random.randrange(1,7)
5
>>> random.randrange(1,7)
1
>>> random.randrange(1,7)
2

>>> guess(100)
Enter your guess: 50
Too low.
Enter your guess: 75
Too high.
Enter your guess: 62
Too high.
Enter your guess: 56
Too low.
Enter your guess: 59
Too high.
Enter your guess: 57
You got it!

Choosing a Random “Real”

Sometimes what we need in an application is not a random integer but a random number chosen from a given number interval. The function uniform() takes two numbers a and b and returns a float number x such that a ≤ x ≤ b (assuming a ≤ b), with each float value in the range equally likely. Here is how we would use it to obtain several random numbers between 0 and 1:

>>> random.uniform(0,1)
0.9896941090637834
>>> random.uniform(0,1)
0.3083484771618912
>>> random.uniform(0,1)
0.12374451518957152

>>> approxPi(1000)
3.028
>>> approxPi(100000)
3.1409600000000002
>>> approxPi(1000000)
3.141702
>>>

Shuffling, Choosing, and Sampling at Random

Let's illustrate a few more functions from the random module. The function shuffle() shuffles, or permutes, the objects in a sequence not unlike how a deck of cards is shuffled prior to a card game like blackjack. Each possible permutation is equally likely. Here is how we can use this function to shuffle a list twice:

>>> lst = [1,2,3,4,5]
>>> random.shuffle(lst)
>>> lst
[3, 4, 1, 5, 2]
>>> random.shuffle(lst)
>>> lst
[1, 3, 2, 4, 5]

The function choice() allows us to choose an item from a container uniformly at random. Given list

>>> lst = [‘cat’, ‘rat’, ‘bat’, ‘mat’]

here is how we would choose a list item uniformly at random:

>>> random.choice(lst)
‘mat’
>>> random.choice(lst)
‘bat’
>>> random.choice(lst)
‘rat’
>>> random.choice(lst)
‘bat’

If, instead of needing just one item, we want to choose a sample of size k, with every sample equally likely, we would use the sample() function. It takes as input the container and the number k.

Here is how we would choose random samples of list lst of size 2 or 3:

>>> random.sample(lst, 2)
[‘mat’, ‘bat’]
>>> random.sample(lst, 2)
[‘cat’, ‘rat’]
>>> random.sample(lst, 3)
[‘rat’, ‘mat’, ‘bat’]

6.5 Case Study: Games of Chance

Games of chance such as poker and blackjack have transitioned to the digital age very successfully. In this case study, we show how to develop a blackjack application. As we develop this application, we will make use of several concepts introduced in this chapter: sets, dictionaries, Unicode characters, and of course randomness through card shuffling.

Blackjack

Blackjack can be played with a standard deck of 52 cards. In a one-person blackjack game, the player plays against the house (i.e., the dealer). The house deals the cards, plays using a fixed strategy, and wins in case of a tie. Our blackjack application will simulate the house. The player (i.e., the user of the application) is trying to beat the house.

Let's illustrate with a few examples how we want the blackjack application to work. When you start the app, the house should deal two cards to you and two to itself:

The house dealt a 6 and a 10 of spades to you and a 7 of spades and an ace of heart to itself. The house then asks you whether you want to hit. Suppose you hit:

You receive an 8 of clubs; since your hand value is 10 + 8 + 6 > 21, you lose. Let's try another example:

After getting your first two cards, you decide to hit and receive a 9 of clubs. With a hand value of 19, you decide to stand. The house then hits once and gets an ace. With an ace value of 11, the house's total is 5+7+11=23, so the ace value of 1 is used instead, making the house's hand value 5 + 7 + 1 = 13. Since 13 < 17, the house must hit again and gets a 5. With a hand value of 18, the house must stand and the player wins.

In this final example, the house loses because it went over:

Rather than develop the blackjack application as a single function, we develop it in modular fashion, using several small functions. The modular approach has two main benefits. One is that smaller functions are easier to write, test, and debug. Another is that some of the functions may be reused in some other card-playing game app. In fact, the first function we implement returns a shuffled deck, which is useful in most card games.

Creating and Shuffling the Deck of Cards

The game starts with a shuffled deck of 52 cards. Each card is defined by its rank and suit, and every combination of rank and suit defines a card. To generate all 52 combinations of rank and suit, we first create a set of ranks and a set of suits (using Unicode suit characters). Then we use a nested loop pattern to generate every combination of rank and suit. Finally, we use the shuffle() function of the random module to shuffle the deck:

Module: blackjack.py

1  def shuffledDeck():
2      ‘returns shuffled deck’
3
4      # suits is a set of 4 Unicode symbols: black spade and club,
5      # and white diamond and heart
6      suits = {‘u2660’, ‘u2661’, ‘u2662’, ‘u2663’}
7      ranks = {‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’,‘10’,‘J’,‘Q’,‘K’,‘A’}
8      deck = []
9
10     # create deck of 52 cards
11      for suit in suits:
12          for rank in ranks:             # card is the concatenation
13              deck.append(rank+‘ ’+suit) # of suit and rank
14
15     # shuffle the deck and return
16     random.shuffle(deck)
17     return deck

A list is used to hold the cards in the shuffled deck because a list defines an ordering on the items it contains. A blackjack hand, however, does not need to be ordered. Still, we choose lists to represent the player's and the house's hands. Next we develop a function that deals a card to either the player or the house.

Dealing a Card

The next function is used to deal the top card in a shuffled deck to one of the blackjack participants. It also returns the card dealt.

Module: blackjack.py

1 def dealCard(deck, participant):
2     ‘deals single card from deck to participant’
3     card = deck.pop()
4     participant.append(card)
5     return card

Note that this function can also be reused in other card game apps. The next function, however, is blackjack specific.

Computing the Value of a Hand

Next we develop the function total() that takes a blackjack hand (i.e., a list of cards) and uses the best assignment of values to aces to return the best possible value for the hand. Developing this function makes sense, not because it can be reused in other card games but because it encapsulates a very specific and somewhat complex computation.

The mapping of cards to their blackjack values is somewhat tricky. Therefore, we use a dictionary to map the assignments of values to the ranks (dictionary keys) with the ace being assigned 11. The hand value is computed with these assignments using an accumulator loop pattern. In parallel, we also count the number of aces, in case we want to switch the value of an ace down to 1.

If the hand value obtained is 21 or below, it is returned. Otherwise, the value of each ace in the hand, if any and one by one, is converted to 1 until the hand value drops below 21.

Module: blackjack.py

 1   def total(hand):
 2       ‘returns the value of the blackjack hand’
 3       values = {‘2’:2, ‘3’:3, ‘4’:4, ‘5’:5, ‘6’:6, ‘7’:7, ‘8’:8,
 4                 ‘9’:9, ‘1’:10, ‘J’:10, ‘Q’:10, ‘K’:10, ‘A’:11}
 5       result = 0
 6       numAces = 0
 7
 8       # add up the values of the cards in the hand
 9       # also add the number of aces
10       for card in hand:
11           result += values[card[0]]
12           if card[0] == ‘A’:
13               numAces += 1
14
15      # while value of hand is > 21 and there is an ace
16      # in the hand with value 11, convert its value to 1
17      while result > 21 and numAces > 0:
18          result -= 10
19          numAces -= 1
20
21      return result

Comparing the Player's and the House's Hands

Another part of the blackjack implementation that we can develop as a separate function is the comparison between the player's hand and the house's. Blackjack rules are used to determine, and announce, the winner.

Module: blackjack.py

 1  def compareHands(house, player):
 2      ‘compares house and player hands and prints outcome’
 3
 4      # compute house and player hand total
 5      houseTotal, playerTotal = total(house), total(player)
 6
 7      if houseTotal > playerTotal:
 8          print(‘You lose.’)
 9      elif houseTotal < playerTotal:
10          print(‘You win.’)
11      elif houseTotal == 21 and 2 == len(house) < len(player):
12          print(‘You lose.’) # house wins with a blackjack
13      elif playerTotal == 21 and 2 == len(player) < len(house):
14          print(‘You win.’) # players wins with a blackjack
15      else:
16          print(‘A tie.’)

Main Blackjack Function

We now implement the main function, blackjack(). The functions we have developed so far make the program easier to write and easier to read as well.

Module: blackjack.py

1  def blackjack()
2      ‘simulates the house in a game of blackjack’
3
4      deck = shuffledDeck()     # get shuffled deck
5
6      house = []  # house hand
7      player = [] # player hand
8
9      for i in range(2):        # dealing initial hands in 2 rounds
10         dealCard(deck, player)    # deal to player first
11         dealCard(deck, house)     # deal to house second
12
13     # print hands
14     print(‘House:{:>7}{:>7}’.format(house[0], house[1]))
15     print(‘ You:{:>7}{:>7}’.format(player[0], player[1]))
16
17     # while user requests an additional card, house deals it
18     answer = input(‘Hit or stand? (default: hit): ’)
19     while answer in {‘’, ‘h’, ‘hit’}:
20         card = dealCard(deck, player)
21         print(‘You got{:>7}’.format(card))
22
23     if total(player) > 21:         # player total is > 21
24         print(‘You went over… You lose.’)
25         return
26
27     answer = input(‘Hit or stand? (default: hit): ’)
28
29     # house must play the “house rules”
30     while total(house) < 17:
31         card = dealCard(deck, house)
32         print(‘House got{:>7}’.format(card))
33
34         if total(house) > 21: # house total is > 21
35             print(‘House went over… You win.’)
36             return
37
38    # compare house and player hands and print result
39    compareHands(house, player)

In lines 6 and 7, the shuffled deck is used to deal the initial hands, which are then printed. In lines 18 to 25, the interactive loop pattern is used to implement the player's requests for additional cards. After each card is dealt, the value of the player's hand is checked. Lines 30 to 36 implement the house rule for completing the house hand.

Chapter Summary

This chapter starts by introducing several built-in Python container classes that complement the string and list classes we have been using so far.

The dictionary class dict is a container of (key, value) pairs. One way to view a dictionary is to see it as as container that stores values that are accessible through user-specified indexes called keys. Another is to see it as a mapping from keys to values. Dictionaries are as useful as lists in practice. A dictionary can be used, for example, as a substitute for a multiway conditional structure or as a collection of counters.

In some situations, the mutability of lists is a problem. For example, we cannot use lists as keys of a dictionary because lists are mutable. We introduce the built-in class tuple, which is essentially an immutable version of class list. We use tuple objects when we need an immutable version of a list.

The last built-in container class covered in this boo is the class set that implements a mathematical set, that is, a container that supports mathematical set operations, such as union and intersection. As all elements of a set must be distinct, sets can be used to easily remove duplicates from other containers.

In this chapter, we also complete the coverage of Python's built-in string type str that we started in Chapter 2 and continued in Chapter 4. We describe the range of characters that a string object can contain. We introduce the Unicode character encoding scheme, the default in Python 3 (but not Python 2), which enables developers to work with strings that use non-American English characters.

Finally, this chapter introduces the Standard Library module random. The module supports functions that return pseudorandom numbers, which are needed in simulations and computer games. We also introduce random module functions shuffle(), choice(), and sample() that enable us to do shuffling and sampling on container objects.

Solutions to Practice Problems

6.1 The function takes a president's name (president) as input. This name maps to a state. The mapping of presidents’ names to states is best described using a dictionary. After the dictionary is defined, the function simply returns the value corresponding to key president:

def birthState(president):
    ‘returns the birth state of the given president’

states = {‘Barack Hussein Obama II’:‘Hawaii’,
          ‘George Walker Bush’:‘Connecticut’,
          ‘William Jefferson Clinton’:‘Arkansas’,
          ‘George Herbert Walker Bush’:‘Massachussetts’,
          ‘Ronald Wilson Reagan’:‘Illinois’,
          ‘James Earl Carter, Jr’:‘Georgia’}

return states[president]

6.2 The reverse lookup service is implemented with an infinite, interactive loop pattern. In each iteration of this loop, the user is requested to enter a number. The phone number entered by the user is mapped, using the phone book, to a name. This name is then printed.

def rlookup(phonebook):
    ‘‘‘implements an interactive reverse phone book lookup service
       phonebook is a dictionary mapping phone numbers to names’’’
    while True:
       number = input(‘Enter phone number in the
                       format (xxx)xxx-xx-xx: ’)
       if number in phonebook:
           print(phonebook[number])
       else:
           print(‘The number you entered is not in use.’)

6.3 See Figure 6.7.

Figure 6.7 Counters states. When string ‘Adam’ is visited, (key, value) pair (‘Adam’, 1) is added to the dictionary. When another string ‘Adam’ is visited, the value in this same (key, value) pair is incremented by one. Another (key, value) pair is added when visiting string ‘Jimmy’.

6.4 The first thing to do is split the text and obtain a list of words. Then the standard pattern for counting using a dictionary of counter is used.

def wordCount(text):
    ‘prints frequency of each word in text’
    wordList = text.split()  # split text into list of words
    counters ={}             # dictionary of counters
    for word in wordList:
        if word in counters: # counter for word exists
            counters[word] += 1
        else:                # counter for word doesn't exist
            counters[word] = 1
    for word in counters:    # print word counts
        if counters[word] == 1:
           print(‘{:8} appears {} time.’.format(word,
                                                counters[word]))
        else:
           print(‘{:8} appears {} times.’.format(word,
                                                counters[word]))

6.5 The infinite loop pattern is used to provide a long-running service. In every iteration, the user is asked to enter a first and a last name, which are then used to build a tuple object. This object is used as a key for the phone book dictionary. If the dictionary contains a value corresponding to this key, the value is printed; otherwise, an error message is printed.

def lookup(phonebook):
    ‘‘‘implements interactive phone book service using the input
       phonebook dictionary’’’
    while True:
        first = input(‘Enter the first name: ’)
        last = input(‘Enter the last name: ’)

        person = (first, last)    # construct the key

        if person in phonebook:   # if key is in dictionary
            print(phonebook[person]) # print value
        else:                     # if key not in dictionary
            print(‘The name you entered is not known.’)

6.6 The goal is to obtain the union of all the sets appearing in a list. The accumulator pattern is the right loop pattern for doing this. The accumulator should be a set that is initialized to be empty:

def sync(phonebooks):
    ‘returns the union of sets in phonebooks’
    res = set() # initialize the accumulator

    for phonebook in phonebooks:
        res = res | phonebook    # accumulate phonebook into res
    return res

6.7 The iteration pattern is used to iterate over the characters of the string. In each iteration, the ASCII code of the current character is printed:

def encoding(text):
    ‘prints ASCII codes of characters in S, one per line’
    print(‘Char Decimal Hex Binary’) # print column headings

    for c in text:
        code = ord(c) # compute ASCII code
        # print character and its code in decimal, hex, and binary
        print(‘ {} {:7} {:4x} {:7b}’.format(c,code,code,code))

6.8 We use a counter loop pattern to generate integers from low to high. The character corresponding to each integer is printed:

def char(low,high):
    ‘‘‘prints the characters with ASCII codes
       in the range from low to high’’’
    for i in range(low, high+1):
        # print integer ASCII code and corresponding character
        print(‘{} : {}’.format(i, chr(i)))

6.9 The randrange() function of the random module is used to generate the secret number to be guessed. An infinite loop and a loop-and-a-half pattern are used to implement the interactive service:

import random	
def guess(n):	
    ‘an interactive number guessing game’
    secret = random.randrange(0,n)   # generate secret number

    while True:
        # user enters a guess
        guess = eval(input(‘Enter you guess: ’))
        if guess == secret:	
            print(‘You got it!’)
            break
        elif guess < secret:
            print(‘Too low.’)
        else: # guess > secret
            print(‘Too high.’)

6.10 Each random dart throw hit is simulated by choosing, uniformly at random, an x and a y coordinate between 1 and 1. If the resulting point (x, y) is within distance 1 from the origin (0,0) (i.e., the center of the dartboard) the point represents a hit. An accumulator loop pattern is used to add up all the “hits.”

import random
def approxPi(total):
    ‘return approximate value of pi based on “dart throwing”’
    count = 0                # counts darts hitting dartboard
    for i in range(total):
        x = random.uniform(-1,1) # x-coordinate of dart
        y = random.uniform(-1,1) # y coordinate of dart
        if x**2+y**2 <= 1:       # if dart hit dartboard
            count += 1               # increment count
    return 4*count/total

Exercises

6.11 Implement function easyCrypto() that takes as input a string and prints its encryption defined as follows: Every character at an odd position i in the alphabet will be encrypted with the character at position i + 1, and every character at an even position i will be encrypted with the character at position i 1. In other words, ‘a’ is encrypted with ‘b’, ‘b’ with ‘a’, ‘c’ with ‘d’, ‘d’ with ‘c’, and so on. Lowercase characters should remain lowercase, and uppercase characters should remain uppercase.

>>> easyCrypto(‘abc’)
bad
>>> easyCrypto(‘Z00’)
YPP

6.12 Redo Problem 5.27 using a dictionary instead of a multiway if statement.

6.13 Define a dictionary called agencies that stores a mapping of acronyms CCC, FCC, FDIC, SSB, WPA (the keys) to federal government agencies ‘Civilian Conservation Corps’, ‘Federal Communications Commission’, ‘Federal Deposit Insurance Corporation’, ‘Social Security Board’, and ‘Works Progress Administration’ (the values) created by President Roosevelt during the New Deal. Then:

1. Add the map of acronym SEC to ‘Securities and Exchange Commission’.
2. Change the value the value of key SSB to ‘Social Security Administration’.
3. Remove the (key, value) pairs with keys CCC and WPA.

6.14 Repeat Exercise 6.13 with this change: Before making changes to agencies, define acronyms to be the view of its keys. After making the changes, evaluate acronyms.

6.15 The dictionary used in Practice Problem 6.5 assumes that only one person can have a certain first and last name. In a typical phone book, however, there can be more than one person with the same first and last name. A modified dictionary that maps a (last name, first name) tuple to a list of phone numbers could be used to implement a more realistic phone book. Reimplement the lookup() function from Practice Problem 6.5 so it can take such a dictionary (i.e., with list values) as input and return all the numbers that a (last name, first name) tuple maps to.

6.16 Using a counter loop pattern, construct sets mult3, mult5, and mult7 of nonnegative multiples of 3, 5, and 7, respectively, less than 100. Then, using these three sets, write set expressions that return

1. Multiples of 35
2. Multiples of 105
3. Multiples of 3 or 7
4. Multiples of 3 or 7, but not both
5. Multiples of 7 that are not multiples of 3

6.17 Write a function hexASCII() that prints the correspondence between the lowercase characters in the alphabet and the hexadecimal representation of their ASCII code. Note: A format string and the format string method can be used to represent a number value in hex notation.

>>> hexASCII()
a:61 b:62 c:63 d:64 e:65 f:66 g:67 h:68 i:69 j:6a k:6b l:6c m:6d
n:6e o:6f p:70 q:71 r:72 s:73 t:74 u:75 v:76 w:77 x:78 y:79 z:7a

6.18 Implement function coin() that returns ‘Heads’ or ‘Tails’ with equal probability.

>>> coin()
‘Heads’
>>> coin()
‘Heads’
>>> coin()
‘Tails’

6.19 Using an online translator such as Google Translate, translate the phrase ‘My name is Ada’ into Arabic, Japanese, and Serbian. Then copy and paste the translations into your interactive shell and assign them as strings to variable names arabic, japanese, and serbian. Finally, for each string, print the Unicode code point of each character in the string using an iteration loop pattern.

Problems

6.20 Write function reverse() that takes as input a phone book, that is, a dictionary mapping names (the keys) to phone numbers (the values). The function should return another dictionary representing the reverse phone book mapping phone numbers (the keys) to the names (the values).

>>> phonebook = {‘Smith, Jane’:‘123-45-67’,
             ‘Doe, John’:‘987-65-43’,‘Baker,David’:‘567-89-01’}
>>> reverse(phonebook)
{‘123-45-67’: ‘Smith, Jane’, ‘567-89-01’: ‘Baker,David’,
‘987-65-43’: ‘Doe, John’}

6.21 Write function ticker() that takes a string (the name of a file) as input. The file will contain company names and stock (ticker) symbols. In this file, a company name will occupy a line and its stock symbol will be in the next line. Following this line will be a line with another company name, and so on. Your program will read the file and store the name and stock symbol in a dictionary. Then it will provide an interface to the user so the user can obtain the stock symbol for a given company. Test your code on the NASDAQ 100 list of stock given in file nasdaq.txt.

File: nasdaq.txt

>>> ticker(‘nasdaq.txt’)
Enter Company name: YAHOO
Ticker symbol: YHOO
Enter Company name: GOOGLE INC
Ticker symbol: GOOG
…

6.22 The mirror image of string vow is string wov, and the mirror image wood is string boow. The mirror image of string bed cannot be represented as a string, however, because the mirror image of e is not a valid character.

Develop function mirror() that takes a string and returns its mirror image but only if the mirror image can be represented using letters in the alphabet.

>>> mirror(‘vow’)
‘wov’
>>> mirror(‘wood’)
‘boow’
>>> mirror(‘bed’)
‘INVALID’

6.23 You would like to produce a unique scary dictionary but have a hard time finding the thousands of words that should go into such a dictionary. Your brilliant idea is to write a function scaryDict() that reads in an electronic version of a scary book, say Frankenstein by Mary Wollstonecraft Shelley, picks up all the words in it, and writes them in alphabetical order in a new file called dictionary.txt. You can eliminate one- and two-letter words because none of them are scary.

You will notice that punctuation in the text makes this exercise a bit more complicated. You can handle it be replacing punctuation with blanks or empty strings.

File: frankenstein.txt

>>> scaryDict(‘frankenstein.txt’)
abandon
abandoned
abbey
abhor
abhorred
abhorrence
abhorrent
…

6.24 Implement function names() that takes no input and repeatedly asks the user to enter the first name of a student in a class. When the user enters the empty string, the function should print for every name the number of students with that name.

>>> names()
Enter next name: Valerie
Enter next name: Bob
Enter next name: Valerie
Enter next name: Amelia
Enter next name: Bob
Enter next name:
There is 1 student named Amelia
There are 2 students named Bob
There are 2 students named Valerie

6.25 Write function different() that takes a two-dimensional table as input and returns the number of distinct entries in the table.

>>> t = [[1,0,1],[0,1,0]]
>>> different(t)
2
>>> t = [[32,12,52,63],[32,64,67,52],[64,64,17,34],[34,17,76,98]]
>>> different(t)
10

6.26 Write function week() that takes no arguments. It will repeatedly ask the user to enter an abbreviation for a day of the week (Mo, Tu, We, Th, Fr, Sa, or Su) and then print the corresponding day.

>>> week()
Enter day abbreviation: Tu
Tuesday
Enter day abbreviation: Su
Sunday
Enter day abbreviation: Sa
Saturday
Enter day abbreviation:

6.27 At the end of this and other textbooks, there usually is an index that lists the pages where a certain word appears. In this problem, you will create an index for a text but, instead of page number, you will use the line numbers.

You will implement function index() that takes as input the name of a text file and a list of words. For every word in the list, your function will find the lines in the text file where the word occurs and print the corresponding line numbers (where the numbering starts at 1). You should open and read the file only once.

File: raven.txt

>>> index(‘raven.txt’, [‘raven’, ‘mortal’, ‘dying’, ‘ghost’,
          ‘ghastly’, ‘evil’,‘demon’])
ghost     9
dying     9
demon     122
evil      99, 106
ghastly   82
mortal    30
raven     44, 53, 55, 64, 78, 97, 104, 111, 118, 120

6.28 Implement function translate() that provides a rudimentary translation service. The function input is a dictionary mapping words in one language (the first language) to corresponding words in another (the second language). The function provides a service that lets users type a phrase in the first language interactively and then obtain a translation into the second language, by pressing the key. Words not in the dictionary should be translated as _ _ _ _.

6.29 In your class, many students are friends. Let's assume that two students sharing a friend must be friends themselves; in other words, if students 0 and 1 are friends and students 1 and 2 are friends, then students 0 and 2 must be friends. Using this rule, we can partition the students into circles of friends.

To do this, implement a function networks() that takes two input arguments. The first is the number n of students in the class. We assume students are identified using integers 0 through n 1. The second input argument is a list of tuple objects that define friends. For example, tuple (0,2) defines students 0 and 2 as friends. Function networks() should print the partition of students into circles of friends as illustrated:

>>> networks(5, [(0, 1), (1, 2), (3, 4)])
Social network 0 is {0, 1, 2}
Social network 1 is {3, 4}

6.30 Implement function simul() that takes as input an integer n and simulates n rounds of Rock, Paper, Scissors between players Player 1 and Player 2. The player who wins the most rounds wins the n-round game, with ties possible. Your function should print the result of the game as shown. (You may want to use your solution to Problem 5.26.)

>>> simul(1)
Player 1
>>> simul(1)
Tie
>>> simul(100)
Player 2

6.31 Craps is a dice-based game played in many casinos. Like blackjack, a player plays against the house. The game starts with the player throwing a pair of standard, six-sided dice. If the player rolls a total of 7 or 11, the player wins. If the player rolls a total of 2, 3, or 12, the player loses. For all other roll values, the player will repeatedly roll the pair of dice until either she rolls the initial value again (in which case she wins) or 7 (in which case she loses)

1. Implement function craps() that takes no argument, simulates one game of craps, and returns 1 if the player won and 0 if the player lost.

   >>> craps()
   0
   >>> craps()
   1
   >>> craps()
   1

2. Implement function testCraps() that takes a positive integer n as input, simulates n games of craps, and returns the fraction of games the player won.

   >>> testCraps(10000)
   0.4844
   >>> testCraps(10000)
   0.492

6.32 You may know that the streets and avenues of Manhattan form a grid. A random walk through the grid (i.e., Manhattan) is a walk in which a random direction (N, E, S, or W) is chosen with equal probability at every intersection. For example, a random walk on a 5 × 11 grid starting (5,2) could visit grid points (6, 2), (7, 2), (8, 2), (9, 2), (10, 2), back to (9, 2) and then back to (10, 2) before leaving the grid.

Write function manhattan() that takes the number of rows and columns in the grid, simulates a random walk starting in the center of the grid, and computes the number of times each intersection has been visited by the random walk. Your function should print the table line by line once the random walk moves outside the grid.

>>> manhattan(5, 11)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

6.33 The two-player card game War is played with a standard deck of 52 cards. A shuffled deck is evenly split among the two players who keep their decks face-down. The game consists of battles until one of the players runs out of cards. In a battle, each player reveals the card on top of their deck; the player with the higher card takes both cards and adds them face-down to the bottom of her stack. If both cards have the same value, a war occurs.

In a war, each player lays, face-down, their top three cards and picks one of them. The player who picks the higher valued card adds all eight cards to the bottom of their deck. In case of another tie, wars are repeated until a player wins and collects all cards on the table. If a player runs out of cards before laying down three cards in a war, they are allowed to complete the war, using their last card as their pick.

In War, the value of a number card is its rank, and the values of cards with rank A, K, Q, and J are 14, 13, 12, and 11, respectively.

1. Write a function war() that simulates one game of war and returns a tuple containing the number of battles, wars, and two-round wars in the game. Note: When adding cards to the bottom of a player's deck, make sure to shuffle the cards first to add additional randomness to the simulation.
2. Write a function warStats() that takes a positive integer n as input, simulates n games of war, and computes the average number of battles, wars, and two-round wars.

6.34 Develop a simple game that teaches kindergartners how to add single-digit numbers. Your function game() will take an integer n as input and then ask n single-digit addition questions. The numbers to be added should be chosen randomly from the range [0,9] (i.e., 0 to 9 inclusive). The user will enter the answer when prompted. Your function should print ‘Correct’ for correct answers and ‘Incorrect’ for incorrect answers. After n questions, your function should print the number of correct answers.

>>> game(3)
8 + 2 =
Enter answer: 10
Correct.
6 + 7 =
Enter answer: 12
Incorrect.
7 + 7 =
Enter answer: 14
Correct.
You got 2 correct answers out of 3

6.35 The Caesar cipher is an encryption technique in which every letter of the message is replaced by the letter that is a fixed number of positions down the alphabet. This “fixed number” is referred to as the key, which can have any value from 1 to 25. If the key is 4, for example, then letter A would be replaced by E, B by F, C by G, and so on. Characters at the end of the alphabet, W, X, Y, and Z would be replaced by A, B, C, and D.

Write function caesar that takes as input a key between 1 and 25 and a text file name (a string). Your function should encode the file content with a Caesar cipher using the input key and write the encrypted content into a new file cipher.txt (as well as print it on the screen).

File: clear.txt

>>> caesar(3,‘clear.txt’)
”Vsb Pdqxdo (Wrs vhfuhw)

1. Dozdbv zhdu d gdun frdw.
2. Dozdbv
zhdu brxu djhqfb'v edgjh rq brxu frdw.
”

6.36 George Kingsley Zipf (1902–1950) observed that the frequency of the k th most common word in a text is roughly proportional to 1/k. This means that there is a constant value C such that for most words w in the text the following is true:

If word w is k th most common then freq(w)k ≈ C

Here, by frequency of word w, freq(w), we mean the number of times the word occurs in the text divided by the total number of words in the text.

Implement function zipf() that takes a file name as input and verifies Zipf's observation by printing the value freq(w)k for the first 10 most frequent words w in the file. Ignore capitalization and punctuation when processing the file.

File: frankenstein.txt

>>> zipf(‘frankenstein.txt’)
0.0557319552019
0.0790477076165
0.113270715149
0.140452498306
0.139097394747
0.141648177917
0.129359248582
0.119993091629
0.122078888284
0.134978942754