CHAPTER 5

Execution Control Structures

5.1 Decision Control and the if Statement

5.2 for Loop and Iteration Patterns

5.3 More on Lists: Two-Dimensional Lists

5.4 while Loop

5.5 More Loop Patterns

5.6 Additional Iteration Control Statements

Chapter Summary

Solutions to Practice Problems

Exercises

Problems

THIS CHAPTER COVERS, in more depth, the Python statements and techniques that provide control over what code blocks will be executed when, and how often.

We start the discussion with the Python decision control structure, the if statement. The if statement was introduced in Chapter 3 in its one-way and two-way formats. We introduce here the general format: a multiway decision control structure that allows an arbitrary number of conditions and associated alternative code blocks to be defined.

We provide next an in-depth coverage of the Python iteration control structures and techniques. Two Python statements provide the ability to execute a block of code repeatedly: the for loop and the while loop. Both are used in many different ways. The bulk of this chapter is spent on the different iteration patterns, and when and how to use them.

Understanding different iteration patterns is really about understanding different approaches to breaking up problems and solving them iteratively. This chapter is thus fundamentally about problem solving.

5.1 Decision Control and the if Statement

The if statement is the fundamental decision control structure that enables alternative code blocks to be executed based on some conditions. In Chapter 3 we introduced the Python if statement. We first saw it in its simplest form, the one-way decision format:

if <condition>:
   <indented code block>
<non-indented statement>

The statements in <indented code block> are executed only if <condition> is True; if <condition> is False, no alternative code block is executed. Either way, execution resumes with the statement <non-indented statement> that is below and with the same indentation as the if statement.

The two-way decision format of the if statement is used when two alternative code blocks have to be executed depending on a condition:

if <condition>:
    <indented code block 1>
else:
    <indented code block 2>
<non-indented statement>

If condition is true, <indented code block 1> is executed; otherwise, <indented code block 2> is executed. Note that the conditions under which the two code blocks get executed are mutually exclusive. In either case, execution again resumes with the statement <non-indented statement>.

Three-Way (and More!) Decisions

The most general format of the Python if statement is the multiway (three or more) decision control structure:

if <condition1>:
    <indented code block 1>
elif <condition2>:
    <indented code block 2>
elif <condition3>:
    <indented code block 3>
else:                 # there could be more elif statements
    <indented code block last>
<non-indented statement>

This statement is executed in this way:

• If <condition1> is true, then <indented code block 1> is executed.
• If <condition1> is false but <condition2> is true, then <indented code block 2> is executed.
• If <condition1> and <condition2> are false but <condition3> is true, then <indented code block 3> is executed.
• If no condition is true, then <indented code block last> is executed.

In all cases, the execution will resume with the statement <non-indented statement>.

The elif keyword stands for “else if”. An elif statement is followed by a condition just like the if statement. An arbitrary number of elif statements can follow one if statement, and an else statement may follow them all (but is optional). Associated with every if and elif statement, and also with the optional else statement, is an indented code block. Python will execute the code block of the first condition that evaluates to True; no other code block is executed. If no condition evaluates to True and an else statement exists, the code block of the else statement is executed.

In function temperature() shown next, we expand the temperature example from Chapter 3 to illustrate the three-way if statement:

Module: ch5.py

1  def temperature(t):
2      ‘prints message based on temperature value t’
3      if t > 86:
4          print(‘It  is hot!’)
5      elif t > 32:
6          print(‘It  is cool.’)
7     else:                         # t <= 32
8          print(‘It  is freezing!’)

For a given value of t, the indented code block of the first condition that is true is executed; if neither the first nor second condition is true, then the indented code corresponding to the else statement is executed:

>>> temperature(87)
It is hot!
>>> temperature(86)
It is cool.
>>> temperature(32)
It is freezing!

The flowchart of the possible executions of this function is shown in Figure 5.1.

Figure 5.1 Flowchart of function temperature(). First checked is the condition t > 86. If true, then the statement print(‘It is hot!’) is executed. If false, then the condition t > 32 is checked. If true, then the statement print(‘It is cool!’) is executed. If false, then the statement print(‘It is freezing!’) is executed.

Ordering of Conditions

There is an issue with multiway decision structures that does not exist with one- or twoway if statements. The order in which the conditions appear in a multiway if statement is important. To see this, try to figure out what is wrong with the order of the conditions in the next implementation of the function temperature().

def temperature(t):
    if t > 32:
        print(‘It is cool.’)
    elif t > 86:
        print(‘It is hot!’)
    else:
        print(‘It is freezing!’)

The problem with this implementation is that ‘It is cool’ will be printed for all values of t greater than 32. So, if t is 104, what is printed is ‘It is cool.’. In fact, ‘It is hot!’ will never get printed, no matter how high the value of t is. The issue is that conditions t > 32 and t > 86 are not mutually exclusive, as conditions corresponding to code blocks in a two-way decision structure are.

One way to fix the wrong implementation is to make the conditions mutually exclusive explicitly:

def temperature(t):
    if 32 < t <= 86:       # add t <= 86 condition
        print(‘It is cool.’)
    elif t > 86:
        print(‘It is hot!’)
    else:                        t <= 32
        print(‘It is freezing!’)

However, explicitly making the conditions mutually exclusive can make the code unnecessarily complicated. Another way to fix the wrong implementation is by implicitly making the conditions mutually exclusive, as we did in the original implementation of function temperature(). Let's explain this.

The temperature() application should have three distinct code blocks, each corresponding to a particular temperature range: t > 86°, 32° < t ≤ 86°, and t ≤ 32°. One of these ranges must become the first condition of the three-way if statement, say t > 86.

Any subsequent condition in a three-way if statement will be tested only if the first condition fails (i.e., the value of t is no more than 86). Therefore, any subsequent condition includes, implicitly, condition t <= 86. So, the explicit second condition t > 32 is really 32 < t <= 86. Similarly, the implicit condition for the else statement is t <= 32 because it is executed only if t is at most 32.

>>> myBMI(190, 75)
Normal
>>> myBMI(140, 75)
Underweight

5.2 for Loop and Iteration Patterns

In Chapter 3, we introduced the for loop. In general, the for loop has this structure:

for <variable> in <sequence>:
    <indented code block>
<non-indented statement>

The variable <sequence> must refer to an object that is a string, list, range, or any container type that can be iterated over—we will see what this means in Chapter 8. When Python runs the for loop, it assigns successive values in <sequence> to <variable> and executes the <indented code block> for every value of <variable>. After the <indented code block> has been executed for the last value in <sequence>, execution resumes with statement <non-indented statement> that is below the indented block and has the same indentation as the first line of the for loop statement.

The for loop, and loops in general, have many uses in programming, and there are different ways to use loops. In this section, we describe several basic loop usage patterns.

Loop Pattern: Iteration Loop

So far in this book, we have used the for loop to iterate over the items of a list:

>>> l = [‘cat’, ‘dog’, ‘chicken’]
>>> for animal in l:
        print(animal)

cat
dog
chicken

We have used it to iterate over the characters of a string:

>>> s = ‘cupcake’
>>> for c in s:
        if c in ‘aeiou’:
                print(c)

u
a
e

Iterating through an explicit sequence of values and performing some action on each value is the simplest usage pattern for a for loop. We call this usage pattern the iteration loop pattern. This is the loop pattern we have used most so far in this book. We include, as our final example of an iteration loop pattern, the code from Chapter 4 that reads a file line by line and prints each line in the interactive shell:

>>> infile = open(‘test.txt’, ‘r’)
>>> for line in infile:
        print(line, end=‘’)

In this example, the iteration is not over characters of a string or items of a list but over the lines of the file-like object infile. Even though the container is different, the basic iteration pattern is the same.

Loop Pattern: Counter Loop

Another loop pattern we have been using is iterating over a sequence of integers specified with the function range():

>>> for i in range(10):
        print(i, end=‘ ’)

0 1 2 3 4 5 6 7 8 9

We use this pattern, which we name the counter loop pattern, when we need to execute a block of code for every integer in some range. For example, we may want to find (and print) all even numbers from 0 up to some integer n:

>>> n = 10
>>> for i in range(n):
        if i % 2 == 0:
            print(i, end = ‘ ’)

0 2 4 6 8

>>> powers(6)
2 4 8 16 32 64

A very common reason to iterate over a sequence of consecutive integers is to generate the indexes of a sequence, whether the sequence is a list, string, or other. We illustrate this with a new pets list.

>>> pets = [‘cat’, ‘dog’, ‘fish’, ‘bird’]

We can print the animals in the list using the iteration loop pattern:

>>> for animal in pets:
        print(animal)

cat
dog
fish
bird

Instead of iterating through the items of list pets, we could also iterate through the indexes of list pets and achieve the same result:

>>> for i in range(len(pets)): # i is assigned 0, 1, 2,…
        print(pets[i])         # print object at index i

cat
dog
fish
bird

Note how the range() and len() functions work in tandem to generate the indexes 0, 1, 2, and 3 of list pets. The execution of the loop is illustrated in Figure 5.2.

Figure 5.2 Counter pattern. In the for loop, variable i is successively assigned values 0, 1, 2, and 3. For every value of i, the list object pets[i] is printed: string ‘cat’ when i is 0, ‘dog’ when i is 1, and so on.

The second approach, using iteration through list indexes, is more complicated and less intuitive than the approach that iterates through list items. Why would one use it?

Well, there are situations when it is necessary to iterate through a sequence by index rather than by value. For example, consider the problem of checking whether a list lst of numbers is sorted in increasing order. To do this it suffices to check that each number in the list is smaller than the next one—if there is a next one. Let's try to implement this approach by iterating through the items of the list:

for item in lst:
    # now compare item with the next object in list lst

We're stuck. How do we compare a list item with the one following it? The problem is that we do not really have a way to access the object in list lst that is after object item.

If we iterate through the list by list index rather than by list item, we do have a way: The object that follows the item at index i must be at index i + 1:

for i in range(len(lst)):
    # compare lst[i] and lst[i+1]

The next question to resolve is how to compare lst[i] and lst[i+1]. If condition lst[i] < lst[i+1] is true, we do not need to do anything but go check the next adjacent pair in the next iteration of the loop. If the condition is false—that is, lst[i] >= lst[i+1] is true—then we know that list lst cannot be in increasing order and we can immediately return false. So, we only need a one-way if statement inside the loop:

for i in range(len(lst)):
    if lst[i] >= lst[i+1]:
        return False

In this loop, variable i gets assigned indexes of list lst. For every value of i, we check whether the object at position i is greater than or equal to the object at position i+1. If that is the case, we can return False. If the for loop terminates, that means that every consecutive pair of objects in list lst is in increasing order and therefore the whole list is increasing.

It turns out that we have made mistake in this code. Note that we compare list items at index 0 and 1, 1 and 2, 2 and 3, all the way to items at index len(lst)-1 and len(lst). But there is no item at index len(lst). In other words, we do not need to compare the last list item with the “next item” in the list. What we need to do is shorten the range over which the for loop iterates by 1.

Here is our final solution in the form of a function that takes as input a list and returns True if the list is sorted in increasing order and False otherwise:

Module: ch5.py

1  def sorted(lst):
2      ‘returns True if sequence lst is increasing, False otherwise’
3      for i in range(0, len(lst)-1): # i =  0, 1,  2,…, len(lst)-2
4          if lst[i] > lst[i+1]:
5              return False
6      return True

>>> arithmetic([3, 6, 9, 12, 15])
True
>>> arithmetic([3, 6, 9, 11, 14])
False
>>> arithmetic([3])
True

Loop Pattern: Accumulator Loop

A common pattern in loops is to accumulate “something” in every iteration of the loop. Given a list of numbers numList, for example, we might want to sum the numbers up. To do this using a for loop, we first need to introduce a variable mySum that will hold the sum. This variable is initialized to 0; then a for loop can be used to iterate through the numbers in numList and add them to mySum. For example:

>>> numList = [3, 2, 7, -1, 9]
>>> mySum = 0                   # initializing the accumulator
>>> for num in numList:
        mySum = mySum + num     # adding to the accumulator

>>> mySum                       # the sum of numbers in numList
20

Figure 5.3 Accumulator pattern. The for loop iterates over the numbers in list numList. In every iteration, the current number is added to the accumulator mySum using the assignment mySum = mySum + num.

The execution of the previous for loop example is illustrated in Figure 5.3. The variable mySum serves as the accumulator. In this case, it is an integer accumulator initialized to 0 because we are summing integers and 0 is the identity for addition (i.e., 0 doesn't affect addition). Every value of num is added to the accumulator with the assignment

mySum = mySum + num

In the expression to the right of the assignment operator =, the value of num and the current value of the accumulator mySum are added together. The assignment then puts the result of this addition back into the accumulator mySum. We say that mySum is incremented by the value of num. This operation is so common that there is a shortcut for it:

mySum += num

Let's recompute the sum using this shortcut:

>>> mySum = 0
>>> for num in numList:
        mySum += num

We refer to the pattern of this for loop as the accumulator loop pattern.

Accumulating Different Types

We illustrate the accumulator pattern with several more examples. Recall that in Chapter 2, we introduced the built-in function sum() that can be used to add up the values in a list:

>>> sum(numList)
20

So, writing a for loop to sum up the numbers in a list was not really necessary. Usually, however, a built-in function is not available. What if, for example, we wanted to multiply all the numbers in the list? An approach similar to the one we used for the sum might work:

>>> myProd = 0                   # initializing the product
>>> for num in numList:          # num gets values from numList
        myProd = myProd * num    # myProd is multiplied by num
>>> myProd                       # what went wrong?
0

What went wrong? We initialized the accumulator product myProd to 0; the problem is that 0 times anything is 0. When we multiply myProd by every value in numList, we will always get 0 back. The value 0 was a good choice for initializing a sum because 0 is the identity for the addition operator. The identity value for the product operator is 1:

>>> myProd = 1
>>> for num in numList:
    myProd = myProd * num

>>> myProd
-378

>>> factorial(0)
1
>>> factorial(3)
6
>>> factorial(5)
120

In our first two examples of accumulator patterns, the accumulators were of a number type. If we accumulate (concatenate) characters into a string, the accumulator should be a string. What string value should the accumulator be initialized to? It has to be a value that is the identity for string concatenation (i.e., has the property: When concatenated with some character, the resulting string should just be the character). The empty string ‘’ (not the blank space!) is thus the identity for string concatenation.

>>> acronym(‘Random access memory’)
‘RAM’
>>> acronym(‘central processing unit’)
‘CPU’

If we accumulate objects into a list, the accumulator should be a list. What is the identity for list concatenation? It is the empty list [].

>>> divisors(1)
[1]
>>> divisors(6)
[1, 2, 3, 6]
>>> divisors(11)
[1, 11]

Loop Patterns: Nested Loop

Suppose we would like to develop a function nested() that takes one positive integer n as input and prints, on the screen, these n lines:

0 1 2 3 … n-1
0 1 2 3 … n-1
0 1 2 3 … n-1
…
0 1 2 3 … n-1

For example:

>>> n = 5
>>> nested(n)
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4

As we have seen, in order to print one line, it suffices to do:

>>> for i in range(n):
        print(i,end=‘ ’)

0 1 2 3 4

In order to get n such lines (or 5 lines in this case), all we need to do is repeat the loop n times (or 5 times in this case). We can do that with an additional outer for loop, which will repeatedly execute the for loop:

>>> for j in range(n):          # outer loop iterates 5 times
        for i in range(n):          # inner loop prints 0 1 2 3 4
            print(i, end = ‘ ’)

0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

Oops, this is not what we wanted. The statement print(i, end=‘ ’) forces all the numbers in one line. What we want is to start a new line after each sequence 0 1 2 3 4 has been printed. In other words, we need to call function print() with no arguments every

time the inner loop

               for i in range(n):
                   print(i, end = ‘ ’)

has been executed. Here is our final solution:

Module: ch5.py

1 def nested(n):
2     ‘prints n lines each containing value 0 1 2 … n-1’
3     for j in range(n):          # repeat n times:
4         for i in range(n):          # print 0, 1, …, n-1
5             print(i, end = ‘ ’)
6         print()                 # move cursor to next line

Note that we needed to use a variable name in the outer for loop different from the variable name in the inner for loop (i).

In this program, a loop statement is contained inside another loop statement. We refer to this type of loop pattern as a nested loop pattern. A nested loop pattern may contain more than two nested loops.

>>> xmult([2], [1, 5])
[2, 10]
>>> xmult([2, 3], [1, 5])
[2, 10, 3, 15]
>>> xmult([3, 4, 1], [2, 0])
[6, 0, 8, 0, 2, 0]

Suppose now we would like to write another function, nested2(), that takes one positive integer n and prints, on the screen, these n lines:

0
0 1
0 1 2
0 1 2 3
…
0 1 2 3 … n-1

For example:

>>> nested2(5)
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4

What needs to be changed in function nested() to create this output? In nested(), the complete line 0 1 2 3… n-1 is printed for every value of variable j. What we now want is to:

• Print 0 when j is 0.
• Print 0 1 when j is 1.
• Print 0 1 2 when j is 2, and so on.

Inner loop variable i needs to iterate not over range(n) but over values 0, 1, 2,…, j, that is, over range(j+1). This suggests this solution:

Module: ch5.py

1  def nested2(n):
2      ‘prints n lines 0 1 2 … j for j = 0, 1, …, n-1’
3      for j in range(n):       # j =  0, 1,  …, n-1
4          for i in range(j+1):     #  print 0 1 2  …  j
5              print(i, end =  ‘ ’)
6      print()                      # move to next line

>>> lst = [3, 1, 7, 4, 9, 2, 5]
>>> bubblesort(lst)
>>> lst
[1, 2, 3, 4, 5, 7, 9]

5.3 More on Lists: Two-Dimensional Lists

Lists we have seen so far can be viewed as one-dimensional tables. For example, the list

>>> l = [3, 5, 7]

can be viewed as the table

A one-dimensional table can easily be represented in Python as a list. But what about two-dimensional tables like the next one?

A two-dimensional table such as this is represented in Python as a list of lists, also referred to as a two-dimensional list.

Two-Dimensional Lists

A two-dimensional table can be viewed as consisting of a bunch of rows (or one-dimensional tables). That is exactly how two-dimensional tables are represented in Python: a list of list elements, with each list element corresponding to a row of the table. For example, the preceding two-dimensional table is represented in Python as:

>>> t = [[4, 7, 2, 5], [5, 1, 9, 2], [8, 3, 6, 6]]
>>> t
[[4, 7, 2, 5], [5, 1, 9, 2], [8, 3, 6, 6]]

List t is illustrated in Figure 5.4; note that t[0] corresponds to the first row of the table, t[1] corresponds to the second row, and t[2] corresponds to the third row. We check this:

>>> t[0]
[4, 7, 2, 2]
>>> t[1]
[5, 1, 9, 2]

So far there really is nothing new here: We knew that a list could contain another list. What is special here is that each list element is of the same size. Now, how do we access (read or write) individual table items? An item in a two-dimensional table is typically accessed by using its “coordinates” (i.e., its row index and column index). For example, the value 8 in the table is in row 2 (counting from the topmost row and starting with index 0) and column 0 (counting from the leftmost column). In other words, 8 is located at index 0 of of list t[2], or at t[2][0] (see Figure 5.4). In general, the item located in row i and column j of a two-dimensional list t is accessed with the expression t[i][j]:

Figure 5.4 Two-dimensional list. List t represents a 2D table. The first row of the table is t[0], the second is t[1], and the third is t[2]. The items in the first row are t[0][0], t[0][1], t[0][2], and t[0][3]. The items in the second row are t[1][0], t[1][1], t[1][2], t[1][3], and so on.

>>> t[2][0]           # the element in row 2, column 0
8
>>> t[0][0]           # the element in row 0, column 0
4
>>> t[1][2]           # the element in row 1, column 2
9

To assign a value to the entry in row i and column j, we simply use the assignment statement. For example:

>>> t[2][3] = 7

The entry in row 2 and column 3 of t is now 7:

>>> t
[[4, 7, 2, 5], [5, 1, 9, 2], [8, 3, 6, 7]]

Sometimes we need to access all entries of a two-dimensional list in some order and not just a single entry at a specified row and column. To visit entries of a two-dimensional list systematically, the nested loop pattern is used.

Two-Dimensional Lists and the Nested Loop Pattern

When we printed the value of two-dimensional list t, the output we got was a list of lists rather than a table with rows in different lines. Often it is nice to print the content of a two-dimensional list so it looks like a table. The next approach uses the iteration pattern to print each row of the table in a separate line:

>>> for row in t:
        print(row)

[4, 7, 2, 5]
[5, 1, 9, 2]
[8, 3, 6, 7]

Suppose that instead of printing each row of the table as a list, we would like to have a function print2D() that prints the items in t as shown next:

>>> print2D(t)
4 7 2 5
5 1 9 2
8 3 6 7

We use the nested loop pattern to implement this function. The outer for loop is used to generate the rows, while the inner for loop iterates over the items in a row and prints them:

Module: ch5.py

1  def print2D(t):
2      ‘prints values in 2D list t as a 2D table’
3      for row in t:
4          for item in row:         # print item followed by
5              print(item, end=‘ ’)     # a blank space
6          print()                  # move to next line

Let's consider one more example. Suppose we need to develop function incr2D() that increments the value of every number in a two-dimensional list of numbers:

>>> print2D(t)
4 7 2 5
5 1 9 2
8 3 6 7
>>> incr2D(t)
>>> print2D(t)
5 8 3 6
6 2 10 3
9 4 7 8

Clearly, the function incr2D() will need to execute:

t[i][j] += 1

for every row index i and column index j of an input two-dimensional list t. We can use the nested loop pattern to generate all combinations of row and column index.

The outer loop should generate the row indexes of t. To do this we need to know the number of rows in t. It is simply len(t). The inner loop should generate the column indexes of t. We are hitting a snag here. How do we find out how many columns t has? Well, it is actually the number of items in a row, and since we assume that all rows have the same number of items, we can arbitrarily pick the first row to obtain the number of columns: len(l[0]). Now we can implement the function:

Module: ch5.py

1  def incr2D(t):
2      ‘increments each number in 2D list of numbers t’
3      nrows = len(t)                   # number of rows
4      ncols = len(t[0])                # number of columns
5
6      for i in range(nrows):           # i is the row index
7          for j in range(ncols):           #j is the column index
8              t[i][j] += 1

The nested loop pattern is used in this program to access the items of two-dimensional list t row by row, from left to right, top to bottom. First accessed are the items in row 0—t[0][0], t[0][1], t[0][2], and t[0][3], in that order—as illustrated in Figure 5.5. After that, items in row 1 are accessed, from left to right, and then items in row 2, and so on.

Figure 5.5 Nested loop pattern. The outer for loop generates row indexes. The inner for loop generates column indexes. The arrow illustrates the execution of the inner for loop for the first-row index (0).

>>> t = [[4, 7, 2, 5], [5, 1, 9, 2], [8, 3, 6, 6]]
>>> s = [[0, 1, 2, 0], [0, 1, 1, 1], [0, 1, 0, 0]]
>>> add2D(t,s)
>>> for row in t:
        print(row)

[4, 8, 4, 5]
[5, 2, 10, 3]
[8, 4, 6, 6]

5.4 while Loop

In addition to for loops, there is another, more general iteration control structure in Python: the while loop. In order to understand how the while loop works, we start by reviewing how a one-way if statement works:

if <condition>:
    <indented code block>
<non-indented statement>

Recall that the <indented code block> is executed when <condition> is true; after the <indented code block> has been executed, the program execution continues with <non-indented statement>. If <condition> is false, program execution goes straight to <non-indented statement>.

The format of a while statement is essentially identical to the format of a one-way if statement:

while <condition>:
    <indented code block>
<non-indented statement>

Just as for an if statement, in a while statement, the <indented code block> is executed if <condition> is true. But, after the <indented code block> has been executed, program execution goes back to checking whether <condition> is true. If so, then the <indented code block> is executed again. As long as <condition> is true, the <indented code block> keeps getting executed, again and again. When <condition> evaluates to false, then the execution jumps to the <non-indented statement>. The while loop flowchart in Figure 5.6 illustrates the possible execution paths.

When is the while loop useful? We illustrate that with the next problem. Suppose we have the silly idea to compute the first multiple of 73 that is greater than 3,951. One way to solve this problem is to successively generate positive multiples of 73 until we get to a number greater than 3,951. A for loop implementation of this idea would start with:

for multiple in range(73, ???, 73)}:
    …

Figure 5.6 while statement flowchart. The conditional block will repeatedly get executed, as long as the condition evaluates to true. When the condition evaluates to false, the statement that follows the while loop gets executed.

The idea is to use function range() to generate the sequence of multiples of 73: 73, 146, 219,… The problem is that we do not know where to stop (i.e., what to replace ??? with).

A while loop is perfect for situations in which we need to iterate but we do not know how many times. In our case, we need to keep generating multiples of 73 as long as the multiples are ≤ 3,951. In other words, while multiple ≤ 73, we generate the next multiple. Let's translate that into Python:

while multiple <= 3951:
  multiple += 73

The variable multiple needs to be initialized before the while loop. We can initialize it to the first positive multiple of 73, which is 73. In every iteration of the while loop, the condition multiple <= 3951 is checked. If true, multiple is incremented to the next multiple of 73:

>>> bound = 3951
>>> multiple = 73
>>> while multiple <= bound:
        multiple += n

>>> multiple
4015

When the while loop condition evaluates to False, the execution of the loop stops. The value of multiple is then greater than bound. Since the previous value of multiple was not greater, it will have the value we want: the smallest multiple greater than bound.

>>> interest(0.07)
11

5.5 More Loop Patterns

With the while loop in hand, as well as a few additional loop control structures we will introduce, we can develop a few more useful loop patterns.

Iteration Patterns: Sequence Loop

Some problems, particularly coming from science, engineering, and finance, can be solved by generating a sequence of numbers that eventually reaches a desired number. We illustrate this pattern on the well-known Fibonacci number sequence:

1,1,2,3,5,8,13,21,34,55,89,…

The Fibonacci number sequence starts with integers 1 and 1 and goes on forever by applying this rule: The current number in the sequence is the sum of the previous two numbers in the sequence.

A natural problem is to compute the i th Fibonacci number. Problem 5.32 at the end of this chapter asks you to do just that. Right now we are going to solve a slightly different problem. We would like to compute the first Fibonacci number greater than some given integer bound. We will do that by generating the sequence of Fibonacci numbers and stopping when we reach a number greater than bound. So, if our current Fibonacci number is current, our while loop condition will be

while current <= bound:

If the condition is true, we need to generate the next Fibonacci number or, in other words, the next value of current. To do this, we need keep track of the Fibonacci number that comes before current. So we need to have another variable, say, previous, in addition to a variable current for the current Fibonacci number. Before the while loop, we initialize previous and current to the first and second Fibonacci numbers:

Module: ch5.py

1  def fibonacci(bound):
2      ‘returns the smallest Fibonacci number greater than bound’
3      previous = 1        # first Fibonacci number
4      current = 1         # second Fibonacci number
5      while current <= bound:
6          # current becomes previous, and new current is computed
7          previous, current = current, previous+current
8      return current

Note the use of the parallel assignment statement to compute the new values for current and previous.

In function fibonacci(), the loop is used to generate a sequence of numbers until a condition is satisfied. We refer to this loop pattern as the sequence loop pattern. In the next problem, we apply the sequence loop pattern to approximate the value of the mathematical constant e, called the Euler constant.

>>> approxE(0.01)
2.7166666666666663
>>> approxE(0.000000001)
2.7182818284467594

Loop Pattern: Infinite Loop

The while loop can be used to create an infinite loop, which is a loop that runs “forever”:

while True:
    <indented code block>

Because True is always true, <indented code block> will get executed again and again.

Infinite loops are useful when the program is meant to provide a service indefinitely. A web server (i.e., a program that serves web pages) is an example of a program that provides a service. It repeatedly receives web page requests from your—and other people's—web browser and sends back the requested web page. The next example illustrates the use of the infinite loop pattern in a much simpler “greeting service.”

We would like to write a function hello2() that repeatedly requests users to input their name and then, when users have done so and pressed , greets them:

>>> hello2()
What is your name? Sam
Hello Sam
What is your name? Tim
Hello Tim

Here is a straightforward implementation that uses the infinite loop pattern:

Module: ch5.py

1  def hello2():
2      ‘‘‘a greeting service; it repeatedly requests the name
3         of the user and then greets the user’’’
4      while True:
5          name = input(‘What is your name? ’)
6          print(‘Hello {}’.format(name))

How do you stop a program that use the infinite loop pattern? Any running program, including one that runs an infinite loop, can be broken—more precisely, interrupted—from outside the program (externally) by typing (simultaneously) on the keyboard. That is how you should stop the execution of the above hello2() function.

Loop Pattern: Loop and a Half

A while loop should also be used when a program must repeatedly process some input values until a flag is reached. (A flag is an arbitrary value that is chosen to indicate the end of the input.)

More specifically, consider the problem of developing a function cities() that repeatedly requests city names (i.e., strings) from the user and accumulates them in a list. The user indicates the end of the input by entering the empty string, at which point the function should return the list of all cities entered by the user. Here is the behavior we expect to see:

>>> cities()
Enter city: Lisbon
Enter city: San Francisco
Enter city: Hong Kong
Enter city:
[‘Lisbon’, ‘San Francisco’, ‘Hong Kong’]
>>>

If the user enters no city, the empty list should be returned:

>>> cities()
Enter city:
[]

Clearly, function cities() should be implemented using a loop that interactively asks the user to enter a city in every iteration. Since the number of iterations is not known, we need to use a while loop. The condition of this while loop should check whether the user entered the empty string. That means that the user should be asked to enter the first city before even entering the while loop. We will, of course, also need to ask the user to enter a city in every iteration of the while loop:

Module: ch5.py

 1  def cities():
 2      ‘‘‘returns the list of cities that are interactively entered
 3         by the user; the empty string ends the interactive input’’’
 4      lst = []
 5
 6      city = input(‘Enter city: ’)   # ask user to enter first city
 7
 8      while city != ‘’:             # if city is not the flag value
 9          lst.append(city)          # append city to list
10          city = input(‘Enter city: ’)  # and ask user once again
11
12      return lst

Note that the function uses the accumulator loop pattern to accumulate the cities into a list.

In function cities(), there are two input() function calls: one before the while loop statement and one inside the while loop code block. A way to eliminate one of those “redundant” statements and make the code more intuitive is to use an infinite loop and an if statement inside the body of the while loop. The if statement would test whether the user entered the flag value:

Module: ch5.py

 1  def cities2():
 2      ‘‘‘returns the list of cities that are interactively entered
 3         by the user; the empty string ends the interactive input’’’
 4      lst = []
 5
 6      while True:                  # forever repeat:
 7          city = input(‘Enter city: ’) # ask user to enter city
 8
 9          if city == ‘’ :              # if city is the flag value
10            return lst                   # return list
11
12          lst.append(city)             # append city to list

When executing function cities2(), the last iteration of the while loop is the one during which the user enters the empty string. In this iteration, only “half” of the body of the for loop is executed; the statement lst.append(city) is skipped. For this reason, the loop pattern in cities2() is commonly referred to as the loop-and-a-half pattern.

http://max.cs.kzoo.edu/patterns/Repetition.shtml

5.6 Additional Iteration Control Statements

We end this chapter by introducing several Python statements that provide further control over iteration. We use simple examples so that we can clearly illustrate how they work.

break Statement

The break statement can be added to the code block of a loop (whether a for loop or a while loop). When it is executed, the current loop iteration is stopped and the loop is exited. Execution then resumes with the statement that follows the loop statement. If the break statement appears in the code block of a loop of a nested loop pattern, only the innermost loop containing the break is exited.

To illustrate the usage of the break statement, we start with another implementation of the function that prints the numbers in a two-dimensional list of numbers in a 2D table format:

Module: ch5.py

1  def print2D2(table):
2      ‘prints values in 2D list of numbers t as a 2D table’
3      for row in table:
4          for num in row:
5              print(num, end=‘ ’)
6          print()

Let's test the code:

>>> table = [[2, 3, 0, 6], [0, 3, 4, 5], [4, 5, 6, 0]]
>>> print2D2(table)
2 3 0 6
0 3 4 5
4 5 6 0

Suppose that instead of printing the complete row, we want to print only those numbers in the row up to, and not including, the first 0 entry in the row. A function before0() doing this would behave as follows:

>>> before0(table)
2 3

4 5 6

To implement before0(), we modify the implementation of print2D() by adding an if statement, inside the inner for loop code block, that checks whether the current value of num is 0. If so, the break statement is executed. This will terminate the inner for loop. Note that the break statement does not terminate the outer for loop; execution thus resumes at the next row of the table.

Module: ch5.py

 1  def before0(table):
 2      ‘‘‘prints values in 2D list of numbers t as a 2D table;
 3         only values in row up to first 0 are printed’’’
 4      for row in table:
 5
 6          for num in row:      # inner for loop
 7              if num == 0:         # if num is 0
 8                  break            # terminate inner for loop
 9              print(num, end=‘ ’)  # otherwise print num
10
11      print()                  # move cursor to next line

The break statement does not affect the outer for loop, which will iterate through all the rows of the table regardless of whether the break statement has been executed.

continue Statement

The continue statement can be added to the code block of a loop, just like the break statement. When the continue statement is executed, the current, innermost loop iteration is stopped, and execution resumes with the next iteration of the current, innermost loop statement. Unlike the break statement, the continue statement does terminate the innermost loop; it only terminates the current iteration of the innermost loop.

To illustrate the usage of the continue statement, we modify the print2D2() function to skip the printing of 0 values in the table. The modified function, which we call ignore0(), should behave like this:

>>> table = [[2, 3, 0, 6], [0, 3, 4, 5], [4, 5, 6, 0]]
>>> ignore0(table)
2 3 6
3 4 5
4 5 6

Note that the 0 values in the table are ignored. Let's implement ignore0():

Module: ch5.py

 1  def ignore0(table):
 2      ‘‘‘prints values in 2D list of numbers t as a 2D table;
 3         0 values are no printed’’’
 4  for row in table:
 5
 6      for num in row:         # inner for loop
 7          if num == 0:            # if num is 0, terminate
 8              continue            # current inner loop iteration
 9          print(num, end=‘ ’)     # otherwise print num
10
11      print()                 # move cursor to next line

pass Statement

In Python, every function definition def statement, if statement, or for or while loop statement must have a body (i.e., a nonempty indented code block). A syntax error while parsing the program would occur if the code block is missing. In the rare occasion when the code in the blocks really doesn't have to do anything, we still have to put some code in it. For this reason Python provides the pass statement, which does nothing but is still a valid statement.

In the next example we illustrate its usage, in a code fragment that prints the value of n only if the value of n is odd.

if n % 2 == 0:
    pass      # do nothing for even number n
else:
    print(n)  # print odd number n only

If the value of n is even, the first code block is executed. The block is just a pass statement, which does nothing.

The pass statement is used when the Python syntax requires code (bodies of functions and execution control statements). The pass statement is also useful when a code body has not yet been implemented.

Chapter Summary

This key chapter covers the Python control flow structures in depth.

We start by revisiting the if control flow construct introduced in Chapter 2. We describe its most general format, the multiway decision structure that uses the elif statement. While one- and two-way conditional structures are defined with only one condition, multiway conditional structures have, in general, multiple conditions. If the conditions are not mutually exclusive, the order in which the conditions appear in the multiway if statement is important, and care must be taken to ensure that the order will give the desired behavior.

The bulk of this chapter describes the different ways that iteration structures are used. First covered are the fundamental iteration, counter, accumulator, and nested loop patterns. These are not only the most common loop patterns, but they are also the building blocks for more advanced loop patterns. The nested loop pattern is particularly useful for processing two-dimensional lists, which we introduce in this chapter.

Before describing more advanced iteration patterns, we introduce another Python loop construct, the while loop. It is more general than the for loop construct and can be used to implement loops that would be awkward to implement using the for loop. Using the while loop construct, we describe the sequence, infinite, interactive, and loop-and-a-half loop patterns.

At the end of the chapter, we introduce several more iteration control statements (break, continue, and pass) that give a bit more control over iteration structures and code development.

The decision and iteration control flow structures are the building blocks used to describe algorithmic solutions to problems. How to effectively apply these structures when solving a problem is one of the fundamental skills of a computing professional. Mastering multiway conditional structures and understanding when and how to apply the iteration patterns described in this chapter is the first step toward the development of this skill.

Solutions to Practice Problems

5.1 After computing the BMI, we use a multiway if statement to decide what to print:

def myBMI(weight, height):
  ‘prints BMI report’
  bmi = weight * 703 / height**2
  if bmi < 18.5:
    print(‘Underweight’)
  elif bmi < 25:
    print(‘Normal’)
  else:                       # bmi >= 25
    print(‘Overweight’)

5.2 We need to print 2¹, 2², 2³,…,2ⁿ (i.e., 2ⁱ for all integers i from 1 to n). To iterate over the range from 1 up to (and including) n, we use function call range(1, n+1):

def powers(n):
  ‘prints 2**i for i = 1, 2, …, n’
  for i in range(1, n+1):
    print(2**i, end=‘ ’)

5.3 We need to check that the difference between adjacent list values are all the same. One way to do this is to check that they are all equal to the difference between the first two list items, l[0] and l[1]. So, we need to check that l[2]-l[1], l[3]-l[2],…, l[n-1]-l[n-2], where n is the size of list l, are all equal to diff = l[1] - l[0]. Or, to put it another way, we need to check that l[i+1] - l[i] = diff for i = 1, 2,…, n 2, values obtained by iterating through range(1, len(l)-1):

def arithmetic(lst):
    ‘‘‘returns True if list lst contains an arithmetic sequence,
       False otherwise’’’
    if len(lst) < 2: # a sequence of length < 2 is arithmetic
        return True
    # checking that difference between successive items is equal
    # to the difference between the first two numbers
    diff = l[1] - l[0]
    for i in range(1, len(l)-1):
    if l[i+1] - l[i] != diff:
        return False
return True

5.4 We need to multiply (accumulate) integers 1, 2, 3,…, n. The accumulator res is initialized to 1, the identity for multiplication. Then we iterate over sequence 2, 3, 4,…, n and multiply res by each number in the sequence:

def factorial(n):
    ‘returns n! for input integer n’
    res = 1
    for i in range(2,n+1):
        res *= i
    return res

5.5 In this problem we would like to iterate over the words of the phrase and accumulate the first letter in every word. So we need to break the phrase into a list of words using the string split() method and then iterate over the words in this list. We will add the first letter of every word to the accumulator string res.

def acronym(phrase):
    ‘returns the acronym of the input string phrase’
    # splits phrase into a list of words
    words = phrase.split()
    # accumulate first character, as an uppercase, of every word
    res = ‘’
    for w in words:
        res = res + w[0].upper()
    return res

5.6 Divisors of n include 1, n, and perhaps more numbers in between. To find them, we can iterate over all integers given by range(1, n+1) and check each integer whether it is a divisor of n.

def divisors(n):
    ‘returns the list of divisors of n’
    res = []
    for i in range(1, n+1):
        if n % i == 0:
            res.append(i)
return res

5.7 We will use the nested loop pattern to multiply every integer in the first list with every integer in the second list. The outer for loop will iterate over the integers in the first list. Then, for every such integer i, the inner for loop will iterate over the integers of the second list, and each such integer is multiplied by i; the product is accumulated into a list accumulator.

def xmult(l1, l2):
    ‘‘‘returns the list of products of items in list l1
       with items in list l2’’’
    l = []
    for i in l1:
        for j in l2:
            l.append(i*j)
    return l

5.8 As discussed in the problem statement, in the first pass you need to successively compare items at indexes 0 and 1, 1 and 2, 2 and 3,…, up to len(lst)-2 and len(lst)-1. We can do this by generating the sequence of integers from 0 up to but not including len(lst)-1.

In the second pass, we can stop the pairwise comparisons with the pair of items at indexes len(lst)-3 and len(lst)-2, so the indexes we need in the second pass go from 0 up to but not including len(lst)-2. This suggests that we should use the outer loop to generate the upper bounds len(lst)-1 for pass 1, len(lst)-2 for pass 2, down to 1 (when the final comparison between the first two list items is made).

The inner loop implements a pass that compares adjacent list items up to items at indexes i-1 and i and swaps improperly ordered items:

def bubblesort(lst):
    ‘sorts list lst in nondecreasing order’
    for i in range(len(lst)-2, 0, -1):
        # perform pass that ends at
        # i = len(lst)-2, len(lst)-1, …, 0
        for j in range(i):
            # compare items at index j and j+1
            # for every j = 0, 1, …, i-1
            if lst[j] > lst[j+1]:
                # swap numbers at index j and j+1
                lst[j], lst[j+1] = lst[j+1], lst[j]

5.9 We use the nested loop pattern to generate all pairs of column and row indexes and add up the corresponding entries:

def add2D(t1, t2):
    ‘‘‘t1 and t2 are 2D lists with the same number of rows and
       same number of equal sized columns

       add2D increments every item t1[i][j] by t2[i][j]’’’
    nrows = len(t1)                # number of rows
    ncols = len(t1[0])             # number of columns
    for i in range(nrows):         # for every row index i
        for j in range(ncols):         # for every column index j
            t1[i][j] += t2[i][j]

5.10 First note that the number of years required for an investment to double in value does not depend on the amount invested. So we can assume the original investment is $100. We use a while loop to add the yearly interest to the investment x. The while loop condition will check whether x < 200. What the problem asks is how many times we have executed the while loop. To count it, we use the counter loop pattern:

def interest(rate):
    ‘‘‘returns the number of years for investment
       to double for the given rate’’’
    amount = 100                 # initial account balance
    count = 0
    while amount < 200:
        # while investment not doubled in value
        count += 1               # add one more year
        amount += amount*rate    # add interest
    return count

5.11 We start by assigning the first approximation (1) to prev and the second (2) to current. The while loop condition is then current - prev > error. If the condition is true, then we need to generate new value for prev and current. The value of current becomes previous and the new current value is then previous + 1/factorial(???). What should ??? be? In the first iteration, it should be 2, because the third approximation is the value of the second . In the next iteration, it should be 3, then 4, and so on. We obtain this solution:

def approxE(error):
    ‘returns approximation of e within error’
    prev = 1                        # approximation 0
    current = 2                     # approximation 1
    i = 2                           # index of next approximation
    while current-prev > error:
        # while difference between current and previous
        # approximation is too large
                                    # current approximation
        prev = current              # becomes previous
                                    # compute new approximation
        current = prev + 1/factorial(i) # based on index i
        i += 1                      # index of next approximation
   return current

Exercises

5.12 Implement function test() that takes as input one integer and prints ‘Negative’, ‘Zero’, or ‘Positive’ depending on its value.

>>> test(-3)
Negative
>>> test(0)
Zero
>>> test(3)
Positive

5.13 Read every exercise 5.14 to 5.22 and decide what loop pattern should be used in each.

5.14 Write function mult3() that takes as input a list of integers and prints only the multiples of 3, one per line.

>>> mult3([3, 1, 6, 2, 3, 9, 7, 9, 5, 4, 5])
3
6
3
9
9

5.15 Implement the function vowels() that takes as input a string and prints the indexes of all vowels in the string. Hint: A vowel can be defined as any character in string ‘aeiouAEIOU’

>>> vowels(‘Hello WORLD’)
1
4
7

5.16 Implement function indexes() that takes as input a word (as a string) and a one-character letter (as a string) and returns a list of indexes at which the letter occurs in the word.

>>> indexes(‘mississippi’, ‘s’)
[2, 3, 5, 6]
>>> indexes(‘mississippi’, ‘i’)
[1, 4, 7, 10]
>>> indexes(‘mississippi’, ‘a’)
[]

5.17 Write function doubles() that takes as input a list of integers and outputs the integers in the list that are exactly twice the previous integer in the list, one per line.

>>> doubles([3, 0, 1, 2, 3, 6, 2, 4, 5, 6, 5])
2
6
4

5.18 Implement function four_letter() that takes as input a list of words (i.e., strings) and returns the sublist of all four letter words in the list.

>>> four_letter([‘dog’, ‘letter’, ‘stop’, ‘door’, ‘bus’, ‘dust’])
[‘stop’, ‘door’, ‘dust’]

5.19 Write a function inBoth() that takes two lists and returns True if there is an item that is common to both lists and False otherwise.

>>> inBoth([3, 2, 5, 4, 7], [9, 0, 1, 3])
True

5.20 Write a function intersect() that takes two lists, each containing no duplicate values, and returns a list containing values that are present in both lists (i.e., the intersection of the two input lists).

>>> intersect([3, 5, 1, 7, 9], [4, 2, 6, 3, 9])
[3, 9]

5.21 Implement the function pair() that takes as input two lists of integers and one integer n and prints the pairs of integers, one from the first input list and the other from the second input list, that add up to n. Each pair should be printed.

>>> pair([2, 3, 4], [5, 7, 9, 12], 9)
2 7
4 5

5.22 Implement the function pairSum() that takes as input a list of distinct integers lst and an integer n, and prints the indexes of all pairs of values in lst that sum up to n.

>>> pairSum([7, 8, 5, 3, 4, 6], 11)
0 4
1 3
2 5

Problems

5.23 Write function pay() that takes as input an hourly wage and the number of hours an employee worked in the last week. The function should compute and return the employee's pay. Overtime work should be paid in this way: Any hours beyond 40 but less than or equal 60 should be paid at 1.5 times the regular hourly wage. Any hours beyond 60 should be paid at 2 times the regular hourly wage.

>>> pay(10, 35)
350
>>> pay(10, 45)
475
>>> pay(10, 61)
720

5.24 Write function case() that takes a string as input and returns ‘capitalized’, ‘not capitalized’, or ‘unknown’, depending on whether the string starts with an uppercase letter, lowercase letter, or something other than a letter in the English alphabet, respectively.

>>> case(‘Android’)
‘capitalized’
>>> case(‘3M’)
‘unknown’

5.25 Implement function leap() that takes one input argument—a year—and returns True if the year is a leap year and False otherwise. (A year is a leap year if it is divisible by 4 but not by 100, unless it is divisible by 400 in which case it is a leap year. For example, 1700, 1800 and 1900 are not leap years but 1600 and 2000 are.)

>>> leap(2008)
True
>>> leap(1900)
False
>>> leap(2000)
True

5.26 Rock, Paper, Scissors is a two-player game in which each player chooses one of three items. If both player choose the same item, the game is tied. Otherwise, the rules that determine the winner are:

1. Rock always beats Scissors (Rock crushes Scissors)
2. Scissors always beats Paper (Scissors cut Paper)
3. Paper always beats Rock (Paper covers Rock)

Implement function rps() that takes the choice (‘R’, ‘P’, or ‘S’) of player 1 and the choice of player 2, and returns -1 if player 1 wins, 1 if player 2 wins, or 0 if there is a tie.

>>> rps(‘R’, ‘P’)
1
>>> rps(‘R’, ‘S’)
-1
>>> rps(‘S’, ‘S’)
0

5.27 Write function letter2number() that takes as input a letter grade (A, B, C, D, F, possibly with a - or +) and returns the corresponding number grade. The numeric values for A, B, C, D, and F are 4, 3, 2, 1, 0. A + increases the number grade value by 0.3 and a decreases it by 0.3.

>>> letter2number(‘A-’)
3.7
>>> letter2number(‘B+’)
3.3
>>> letter2number(‘D’)
1.0

5.28 Write function geometric() that takes a list of integers as input and returns True if the integers in the list form a geometric sequence. A sequence a₀, a₁, a₂, a₃, a₄,…, a_n 2, a_n 1 is a geometric sequence if the ratios a₁/a₀, a₂/a₁, a₃/a₂, a₄/a₃,…, a_{n 1} 1/a_{n 2} are all equal.

>>> geometric([2, 4, 8, 16, 32, 64, 128, 256])
True
>>> geometric([2, 4, 6, 8])
False

5.29 Write function lastfirst() that takes one argument—a list of strings of the format <LastName, FirstName>—and returns a list consisting two lists:

1. A list of all the first names
2. A list of all the last names

>>> lastfirst([‘Gerber, Len’, ‘Fox, Kate’, ‘Dunn, Bob’])
[[‘Len’, ‘Kate’, ‘Bob’], [‘Gerber’, ‘Fox’, ‘Dunn’]]

5.30 Develop the function many() that takes as input the name of a file in the current directory (as a string) and outputs the number of words of length 1, 2, 3, and 4. Test your function on file sample.txt.

File: sample.txt

>>> many(‘sample.txt’)
Words of length 1 : 2
Words of length 2 : 5
Words of length 3 : 1
Words of length 4 : 10

5.31 Write a function subsetSum() that takes as input a list of positive numbers and a positive number target. Your function should return True if there are three numbers in the list that add up to target. For example, if the input list is [5, 4, 10, 20, 15, 19] and target is 38, then True should be returned since 4 + 15 + 19 = 38. However, if the input list is the same but the target value is 10, then the returned value should be False because 10 is not the sum of any three numbers in the given list.

>>> subsetSum([5, 4, 10, 20, 15, 19], 38)
True
>>> subsetSum([5, 4, 10, 20, 15, 19], 10)
False

5.32 Implement function fib() that takes a nonnegative integer n as input and returns the nth Fibonacci number.

>>> fib(0)
1
>>> fib(4)
5
>>> fib(8)
34

5.33 Implement a function mystery() that takes as input a positive integer n and answers this question: How many times can n be halved (using integer division) before reaching 1? This value should returned.

>>> mystery(4)
2
>>> mystery(11)
3
>>> mystery(25)
4

5.34 Write a function statement() that takes as input a list of floating-point numbers, with positive numbers representing deposits to and negative numbers representing withdrawals from a bank account. Your function should return a list of two floating-point number; the first will be the sum of the deposits, and the second (a negative number) will be the sum of the withdrawals.

>>> statement([30.95, -15.67, 45.56, -55.00, 43.78])
[-70.67, 120.29]

5.35 Implement function pixels() that takes as input a two-dimensional list of nonnegative integer entries (representing the values of pixels of an image) and returns the number of entries that are positive (i.e., the number of pixels that are not dark). Your function should work on two-dimensional lists of any size.

l = [[0, 156, 0, 0], [34, 0, 0, 0], [23, 123, 0, 34]]
>>> pixels(l)
5
>>> l = [[123, 56, 255], [34, 0, 0], [23, 123, 0], [3, 0, 0]]
>>> pixels(l)
7

5.36 Implement function prime() that takes a positive integer as input and returns True if it is a prime number and False otherwise.

>>> prime(2)
True
>>> prime(17)
True
>>> prime(21)
False

5.37 Write function mssl() (minimum sum sublist) that takes as input a list of integers. It then computes and returns the sum of the maximum sum sublist of the input list. The maximum sum sublist is a sublist (slice) of the input list whose sum of entries is largest. The empty sublist is defined to have sum 0. For example, the maximum sum sublist of the list

    [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
is [5, -2, 7, 7, 2] and the sum of its entries is 19.

    >>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
    >>> mssl(l)
    19
    >>> mssl([3,4,5])
    12
    >>> mssl([-2,-3,-5])
    0

In the last example, the maximum sum sublist is the empty sublist because all list items are negative.

5.38 Write function collatz() that takes a positive integer x as input and prints the Collatz sequence starting at x. A Collatz sequence is obtained by repeatedly applying this rule to the previous number x in the sequence:

Your function should stop when the sequence gets to number 1. Note: It is an open question whether the Collatz sequence of every positive integer always ends at 1.

>>> collatz(10)
10
5
16
8
4
2
1

5.39 Write function exclamation() that takes as input a string and returns it with this modification: Every vowel is replaced by four consecutive copies of itself and an exclamation mark (!) is added at the end.

>>> exclamation(‘argh’)
‘aaaargh!’
>>> exclamation(‘hello’)
‘heeeelloooo!’

5.40 The constant π is an irrational number with value approximately 3.1415928… The precise value of π is equal to this infinite sum:

We can get a good approximation of π by computing the sum of the first few terms. Write a function approxPi() that takes as input a float-value error and approximates constant π within error by computing the preceding sum, term by term, until the difference between the current sum and the previous sum (with one less term) is no greater than error. The function should return the new sum.

>>> approxPi(0.01)
3.1611986129870506
>>> approxPi(0.0000001)
3.1415928535897395

5.41 A polynomial of degree n with coefficients a₀, a₁, a₂, a₃,…, a_n is the function

This function can be evaluated at different values of x. For example, if p(x) = 1 + 2x + x², then p(2)= 1 + 2 * 2 + 2² = 9. If p(x)= 1 + x² + x⁴, then p(2)= 21 and p(3)= 91.

Write a function poly() that takes as input a list of coefficients a₀, a₁, a₂, a₃,…, a_n of a polynomial p(x) and a value x. The function will return p(x), which is the value of the polynomial when evaluated at x. Note that the usage below is for the three examples shown.

>>> poly([1, 2, 1], 2)
9
>>> poly([1, 0, 1, 0, 1], 2)
21
>>> poly([1, 0, 1, 0, 1], 3)
91

5.42 Implement function primeFac() that takes as input a positive integer n and returns a list containing all the numbers in the prime factorization of n. (The prime factorization of a positive integer n is the unique list of prime numbers whose product is n.)

>>> primeFac(5)
[5]
>>> primeFac(72)
[2, 2, 2, 3, 3]

5.43 Implement function evenrow() that takes a two-dimensional list of integers and returns True if each row of the table sums up to an even number and False otherwise (i.e., if some row sums up to an odd number).

>>> evenrow([[1, 3], [2, 4], [0, 6]])
True
>>> evenrow([[1, 3], [3, 4], [0, 5]])
False
>>> evenrow([[1, 3, 2], [3, 4, 7], [0, 6, 2]])
True
>>> evenrow([[1, 3, 2], [3, 4, 7], [0, 5, 2]])
False

5.44 A substitution cipher for the digits 0, 1, 2, 3,…, 9 substitutes each digit in 0, 1, 2, 3,…, 9 with another digit in 0, 1, 2, 3,…, 9. It can be represented as a 10-digit string specifying how each digit in 0, 1, 2, 3,…, 9 is substituted. For example, the 10-digit string ‘3941068257’ specifies a substitution cipher in which digit 0 is substituted with digit 3, 1 with 9, 2 with 4, and so on. To encrypt a nonnegative integer, substitute each of its digits with the the digit specified by the encryption key.

Implement function cipher() that takes as input a 10-digit string key and a digit string (i.e., the clear text to be encrypted) and returns the encryption of the clear text.

>>> encrypt(‘3941068257’, ‘132’)
‘914’
>>> encrypt(‘3941068257’, ‘111’)
‘999’

5.45 The function avgavg() takes as input a list whose items are lists of three numbers. Each three-number list represents the three grades a particular student received for a course. For example, here is an input list for a class of four students:

[[95,92,86], [66,75,54],[89, 72,100],[34,0,0]]

The function avgavg() should print, on the screen, two lines. The first line will contain a list containing every student's average grade. The second line will contain just one number: the average class grade, defined as the average of all student average grades.

>>> avgavg([[95, 92, 86], [66, 75, 54],[89, 72, 100], [34, 0, 0]])
[91.0, 65.0, 87.0, 11.333333333333334]
63.5833333333

5.46 An inversion in a sequence is a pair of entries that are out of order. For example, the characters F and D form an inversion in string ‘ABBFHDL’ because F appears before D; so do characters H and D. The total number of inversions in a sequence (i.e., the number of pairs that are out of order) is a measure of how unsorted the sequence is. The total number of inversions in ‘ABBFHDL’ is 2. Implement function inversions() that takes a sequence (i.e., a string) of uppercase characters A through Z and returns the number of inversions in the sequence.

>>> inversions(‘ABBFHDL’)
2
>>> inversions(‘ABCD’)
0
>>> inversions(‘DCBA’)
6

5.47 Write function d2x() that takes as input a nonnegative integer n (in the standard decimal representation) and an integer x between 2 and 9 and returns a string of digits that represents the base-x representation of n.

>>> d2x(10, 2)
‘1010’
>>> d2x(10, 3)
‘101’
>>> d2x(10, 8)
‘12’

5.48 Let list1 and list2 be two lists of integers. We say that list1 is a sublist of list2 if the elements in list1 appear in list2 in the same order as they appear in list1, but not necessarily consecutively. For example, if list1 is defined as

[15, 1, 100]

and list2 is defined as

[20, 15, 30, 50, 1, 100]

then list1 is a sublist of list2 because the numbers in list1 (15, 1, and 100) appear in list2 in the same order. However, list

[15, 50, 20]

is not a sublist of list2.

Implement function sublist() that takes as input lists list1 and list2 and returns True if list1 is a sublist of list2, and False otherwise.

>>> sublist([15, 1, 100], [20, 15, 30, 50, 1, 100])
True
>>> sublist([15, 50, 20], [20, 15, 30, 50, 1, 100])
False

5.49 The Heron method is a method the ancient Greeks used to compute the square root of a number n. The method generates a sequence of numbers that represent better and better approximations for . The first number in the sequence is an arbitrary guess; every other number in the sequence is obtained from the previous number prev using the formula

Write function heron() that takes as input two numbers: n and error. The function should start with an initial guess of 1.0 for and then repeatedly generate better approximations until the difference (more precisely, the absolute value of the difference) between successive approximations is at most error.

>>> heron(4.0, 0.5)
2.05
>>> heron(4.0, 0.1)
2.000609756097561