7c. Prof. Rosenthal’s Review

7c. Prof. Rosenthal’s Review#

A review of Chapter 7: Iteration and Search, for students who have already studied the chapter. Use the two lists under Concepts covered as a checklist (click a list’s title to hide it), then work through the Questions, which go from easy to hard. Each question has a suggested answer under Answer. Try the question first, then open the Answer.

Run this page on Colab

Concepts covered#

Python Syntax and Semantics

Looping through a string

This runs the body once for each character of the string, in order, with the loop variable referring to that character:
```
for LOOP_VARIABLE in STRING:
    BODY
```
For example, this displays G, a, d on separate lines:
```
for letter in 'Gad':
    print(letter)
```
print(VALUE, end=' ') displays the value followed by a space instead of a newline, so the next print continues on the same line.

Updating variables

A new assignment makes an existing variable refer to a new value. x = x + 1 is an update: it computes the right side with the current value of x, then assigns the result to x.
Updating a variable that does not exist yet, such as z = z + 1, is a NameError. Initialize it first, for example with z = 0.
Augmented assignment: x += N is the same as x = x + N. Likewise x -= N and x *= N.

A counter is a variable initialized to 0 before a loop and incremented inside it:

count = 0
for LOOP_VARIABLE in SEQUENCE:
    if CONDITION:
        count += 1

The in operator and string methods

STRING1 in STRING2 is True if STRING1 appears in STRING2: 'e' in 'Gadsby' is False, and 'ads' in 'Gadsby' is True. Uppercase and lowercase letters are different: 'g' in 'Gadsby' is False.
A method is a function associated with a value, called with a dot: VALUE.METHOD_NAME(ARGUMENTS).
STRING.lower() returns a new string with the letters in lowercase: 'Gadsby'.lower() is 'gadsby'. It does not change the original string; to keep the result, assign it, as in word = word.lower().
STRING.strip() returns a new string without the whitespace (spaces, tabs and newlines) at its beginning and end: ' hi \n'.strip() is 'hi'.

Reading files

open(FILE_NAME) returns a file object for reading the file.
FILE_OBJECT.readline() returns the next line of the file as a string, including the newline at its end ('\n'). The file object keeps track of where it is, so each call returns the next line.

This runs the body once for each line of the file:

for line in open(FILE_NAME):
    word = line.strip()
    BODY

Linear search

A linear search loops through a sequence and returns as soon as it finds what it is looking for; if the loop ends without finding it, the function returns after the loop:
```
def has_e(word):
    for letter in word:
        if letter == 'e':
            return True
    return False
```
The return False must be after the loop, not in an else inside it: otherwise the function returns after checking only the first letter.

Doctests

A docstring can contain tests: a line starting with >>> followed by an expression, and on the next line the value the expression should have:

def FUNCTION_NAME(PARAMETERS):
    """WHAT THE FUNCTION DOES

    >>> FUNCTION_NAME(ARGUMENTS)
    EXPECTED_VALUE
    """
    BODY

run_docstring_examples(FUNCTION, globals(), name=FUNCTION.__name__), after from doctest import run_docstring_examples, runs a function’s doctests. It displays nothing if all of them pass; for each test that fails, it displays the example, the expected value and the value it got.

Definitions, etc.

Definitions

DEFINITION: A loop variable is the variable defined in the header of a for loop.
DEFINITION: A file object is a value that represents an open file and keeps track of which parts of it have been read.
DEFINITION: A method is a function associated with a value (an object), called using the dot operator, as in word.lower().
DEFINITION: An update is an assignment that gives a new value to a variable that already exists, often computed from its old value.
DEFINITION: To initialize a variable is to create it and give it a first value.
DEFINITION: To increment a variable is to increase its value; to decrement it is to decrease its value.
DEFINITION: An augmented assignment operator, such as +=, -= or *=, updates a variable concisely.
DEFINITION: A counter is a variable used to count something, usually initialized to zero and then incremented.
DEFINITION: A linear search is a pattern that goes through a sequence of elements one at a time and stops when it finds what it is looking for.
DEFINITION: A doctest is a test written in a docstring: an expression after >>> and the value it should have.
DEFINITION: A test passes if it runs and the result is as expected; otherwise it fails.

Other ideas

Give the loop variable a name that says what it refers to, such as letter or line.
A function that loops through a string and returns True or False can often be simplified with the in operator.
Converting strings with lower before comparing them makes a function work with any combination of uppercase and lowercase letters.
Doctests document what a function does and test it at the same time. When all tests pass, no news is good news.

Questions#

The questions use for loops over strings, counters, the in operator, string methods and doctests. One question reads words.txt, a list of about 114,000 English words, one per line, in alphabetical order (the first two are aa and aah).

The setup cell below downloads words.txt.

from os.path import basename, exists

def download(url):
    filename = basename(url)
    if not exists(filename):
        from urllib.request import urlretrieve

        local, _ = urlretrieve(url, filename)
        print("Downloaded " + str(local))
    return filename

download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');

Question 1 (easy): what is displayed?#

Predict what this code displays, then open the Answer to check.

for letter in 'hi':
    print(letter * 2)
for letter in 'code':
    print(letter, end=' ')

Answer

hh
ii
c o d e 

The loop variable letter refers to each character of the string in turn. end=' ' makes print display a space instead of a newline after each letter, so the letters of 'code' are on one line.

Question 2 (easy): what is displayed?#

x = 5
x = x + 1
x += 2
x *= 3
x -= 4
print(x)

Answer

The value of x is 5, then 6, then 8, then 24, then 20. x += 2 means x = x + 2, x *= 3 means x = x * 3, and x -= 4 means x = x - 4.

Question 3 (easy): what is displayed?#

word = 'Gadsby'
print('e' in word, 'G' in word, 'g' in word)
print('ads' in word)
print(word.lower(), word)

Answer

False True False
True
gadsby Gadsby

in checks whether one string appears in another. Uppercase and lowercase letters are different, so 'g' is not in 'Gadsby'. It also works for longer strings: 'ads' appears in 'Gadsby'. lower returns a new string; word itself does not change.

Question 4 (easy): write a function#

Write a function called exclaim_letters that takes a string word and displays each of its letters followed by !, one per line.

Start from this header (replace ... with the body):

def exclaim_letters(word):
    ...

Examples

exclaim_letters('hi')

h!
i!

exclaim_letters('yes')

y!
e!
s!

Answer

def exclaim_letters(word):
    for letter in word:
        print(letter + '!')

Then try: exclaim_letters('hi').

print(letter, '!') would put a space between the letter and the !, so join them with + instead.

Question 5 (medium): what is displayed?#

count = 0
total = 0
for letter in 'Mississippi':
    total += 1
    if letter == 's':
        count += 1
print(count, total)

Answer

4 11

total is incremented for every letter, so it counts all 11 letters. count is incremented only for the letter s, which appears 4 times. Both counters are initialized to 0 before the loop.

Question 6 (medium): what is displayed?#

word = 'Hello'
word.lower()
print(word)
word = word.lower()
print(word)

Answer

Hello
hello

lower does not change the string it is called on: it returns a new string. On the second line, that new string is not assigned to anything, so it is thrown away. On the fourth line, it is assigned to word, so word now refers to 'hello'.

Question 7 (medium): what is displayed?#

line = '  hello world \n'
print(len(line), len(line.strip()))
print(line.strip() + '!')

Answer

15 11
hello world!

line has 2 spaces, the 11 characters of hello world, a space and a newline (\n is one character): 15 in all. strip removes the whitespace at the beginning and end (spaces and the newline), but not the space between the words.

Question 8 (medium): what happens?#

for letter in 'abc':
    num_letters = num_letters + 1
print(num_letters)

Answer

This is a NameError.

      1 for letter in 'abc':
----> 2     num_letters = num_letters + 1
      3 print(num_letters)

NameError: name 'num_letters' is not defined

To compute num_letters + 1, Python needs the current value of num_letters, but the variable has never been assigned. Initialize it before the loop:

num_letters = 0
for letter in 'abc':
    num_letters = num_letters + 1
print(num_letters)

This displays 3.

Question 9 (medium): reading a file#

words.txt has one word per line; its first two lines are aa and aah. Predict what this code displays.

file_object = open('words.txt')
first = file_object.readline()
second = file_object.readline()
print(len(first), len(second.strip()))
print(second.strip())

Answer

3 3
aah

readline returns the next line including its newline, so first is 'aa\n', which has 3 characters. The file object remembers where it is, so the second call returns the second line, 'aah\n'; after strip it is 'aah', with 3 characters.

Question 10 (medium): write a function#

Write a function called count_vowels that takes a string and returns the number of vowels (a, e, i, o, u, uppercase or lowercase) in it.

Start from this header (replace ... with the body):

def count_vowels(word):
    ...

Examples

print(count_vowels('banana'))

print(count_vowels('Python'), count_vowels('AEIOU'), count_vowels('rhythm'))

1 5 0

Answer

A counter, and the in operator to check each letter:

def count_vowels(word):
    count = 0
    for letter in word.lower():
        if letter in 'aeiou':
            count += 1
    return count

Then try: print(count_vowels('banana')).

Calling lower first makes uppercase vowels count too. Without lower, check both cases:

def count_vowels(word):
    count = 0
    for letter in word:
        if letter in 'aeiouAEIOU':
            count = count + 1
    return count

Question 11 (medium): write a function#

Write a function called first_vowel that takes a string and returns its first vowel (a, e, i, o or u, lowercase), or None if it has none.

Start from this header (replace ... with the body):

def first_vowel(word):
    ...

Examples

print(first_vowel('python'), first_vowel('strength'))

o e

print(first_vowel('rhythm'))

None

Answer

A linear search: return the first letter that is a vowel; if the loop ends, there is none.

def first_vowel(word):
    for letter in word:
        if letter in 'aeiou':
            return letter
    return None

Then try: print(first_vowel('python'), first_vowel('strength')).

A function that ends without return also returns None, so the last line could be left out, but writing it makes the intention clear.

Question 12 (hard): what is displayed?#

def uses_any_wrong(word, letters):
    for letter in word:
        if letter in letters:
            return True
        else:
            return False

print(uses_any_wrong('nab', 'n'), uses_any_wrong('banana', 'n'))

Answer

True False

The function is supposed to return True if word uses any of the letters, but it returns after checking only the first letter of word: 'n' is in 'n', so the first call returns True, but 'b' is not, so the second returns False even though banana has an n. The return False belongs after the loop:

def uses_any(word, letters):
    for letter in word:
        if letter in letters:
            return True
    return False

print(uses_any('nab', 'n'), uses_any('banana', 'n'))

True True

Question 13 (hard): what is displayed?#

count = 0
for a in 'ab':
    line = ''
    for b in 'xyz':
        line += a + b
        count += 1
    print(line)
print(count)

Answer

axayaz
bxbybz
6

For each letter a of 'ab', the inner loop runs through all three letters of 'xyz'. line is set back to the empty string at the start of each outer loop, and count is incremented 2 times 3 = 6 times in all. += works with strings too: line += a + b adds two letters to the end of line.

Question 14 (hard): doctests#

run_doctests runs the tests in a function’s docstring (you can ignore how it works: globals() and __name__ are explained later). Predict what the last line displays. What is wrong with count_e, and how do you fix it?

Run this cell to define run_doctests.

from doctest import run_docstring_examples

def run_doctests(func):
    run_docstring_examples(func, globals(), name=func.__name__)

def count_e(word):
    """Count the letter e (or E) in word.

    >>> count_e('Eerie')
    3
    >>> count_e('sky')
    0
    """
    count = 0
    for letter in word:
        if letter == 'e':
            count += 1
    return count

run_doctests(count_e)

Answer

The first test fails, and the second one passes (a test that passes displays nothing). The output is something like this (the line number may differ):

**********************************************************************
File "__main__", line 4, in count_e
Failed example:
    count_e('Eerie')
Expected:
    3
Got:
    2

count_e only counts lowercase e, so for 'Eerie' it returns 2, not 3. Fix it by converting the word to lowercase first; then running the tests displays nothing, because they all pass:

def count_e(word):
    """Count the letter e (or E) in word.

    >>> count_e('Eerie')
    3
    >>> count_e('sky')
    0
    """
    count = 0
    for letter in word.lower():
        if letter == 'e':
            count += 1
    return count

run_doctests(count_e)

(nothing is displayed)

Question 15 (hard): searching a file#

What does this code display? Explain what it counts. (You cannot know the number without running it; predict what it means, then open the Answer to see the number.)

count = 0
for line in open('words.txt'):
    word = line.strip()
    if 'q' in word and 'u' not in word:
        count += 1
print(count)

Answer

It counts the words in words.txt that contain a q but no u: only 10 of about 114,000 words. 'u' not in word is the same as not 'u' in word. Each line is stripped first, so that the newline is not part of the word (here it would not change the result, but it would for a test like word == 'qat').

Question 16 (hard): write a function#

A word is abecedarian if its letters are in alphabetical order (repeated letters are allowed), like almost or abbey. Write a function is_abecedarian that takes a lowercase word and returns True if it is abecedarian and False otherwise. Strings can be compared with <: 'a' < 'b' is True, and 'h' < 'e' is False.

Start from this header (replace ... with the body):

def is_abecedarian(word):
    ...

Examples

print(is_abecedarian('almost'), is_abecedarian('abbey'))

True True

print(is_abecedarian('hello'), is_abecedarian('a'))

False True

Answer

A linear search for a letter that comes before the one just before it. A variable remembers the previous letter:

def is_abecedarian(word):
    previous = 'a'
    for letter in word:
        if letter < previous:
            return False
        previous = letter
    return True

Then try: print(is_abecedarian('almost'), is_abecedarian('abbey')).

Starting with previous = 'a' works because no lowercase letter comes before 'a'. As soon as one letter is out of order, the answer is False; only after checking all the letters is it True.

Question 17 (hard): write a function with doctests#

Write a function count_doubles that takes a word and returns the number of times a letter is immediately followed by the same letter. Give it a docstring with at least three doctests, and check that running them displays nothing.

Start from this header (replace ... with the body):

def count_doubles(word):
    ...

Examples

print(count_doubles('bookkeeper'))

print(count_doubles('Mississippi'), count_doubles('cat'), count_doubles('aaa'))

3 0 2

This question uses run_doctests from Question 14.

Answer

Remember the previous letter, as in a search, and count instead of returning:

def count_doubles(word):
    """Count the letters immediately followed by the same letter.

    >>> count_doubles('bookkeeper')
    3
    >>> count_doubles('cat')
    0
    >>> count_doubles('aaa')
    2
    """
    count = 0
    previous = ''
    for letter in word:
        if letter == previous:
            count += 1
        previous = letter
    return count

run_doctests(count_doubles)

Then try: print(count_doubles('bookkeeper')).

previous starts as the empty string, which is not equal to any letter, so the first letter is never counted. In 'aaa' there are two pairs of neighbors, and both are doubles.

Summary and questions by Prof. Y. Rosenthal, based on Think Python: 3rd Edition by Allen B. Downey. Text license: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

7c. Prof. Rosenthal’s Review

Contents

7c. Prof. Rosenthal’s Review#

Concepts covered#

Questions#

Question 1 (easy): what is displayed?#

Question 2 (easy): what is displayed?#

Question 3 (easy): what is displayed?#

Question 4 (easy): write a function#

Question 5 (medium): what is displayed?#

Question 6 (medium): what is displayed?#

Question 7 (medium): what is displayed?#

Question 8 (medium): what happens?#

Question 9 (medium): reading a file#

Question 10 (medium): write a function#

Question 11 (medium): write a function#

Question 12 (hard): what is displayed?#

Question 13 (hard): what is displayed?#

Question 14 (hard): doctests#

Question 15 (hard): searching a file#

Question 16 (hard): write a function#

Question 17 (hard): write a function with doctests#