Programming in PythonIteration

We have already seen one way of doing something to each element in a collection: the list comprehension.

smallest_factor = {2: 2, 3: 3, 4: 2, 5: 5,
                 6: 2, 7: 7, 8: 2, 9: 3}
[v for (k,v) in smallest_factor.items()]

In this list comprehension, we iterate over the pairs of the dictionary to produce a new list. Although list comprehensions are very useful, they are not flexible enough to cover all our iteration needs. A much more flexible tool is the for loop.

Continue

For statements

The code above could also be rewritten as follows:

smallest_factor = {2: 2, 3: 3, 4: 2, 5: 5,
                 6: 2, 7: 7, 8: 2, 9: 3}
vals = []
for (k,v) in smallest_factor.items():
    vals.append(v)
vals

The statement for item in collection: works as follows: the first element of collection is assigned to item, and the block indented below the for statement is executed. Then, the second element of collection is assigned to item, the indented block is executed again, etc., until the end of the collection is reached.

Continue

We can nest for statements. For example, suppose we have a matrix represented as a list of lists, and we want to sum all of the matrix entries. We can do that by iterating over the rows and then iterating over each row:

def sum_matrix_entries(M):
    """
    Return the sum of the entries of M
    """
    s = 0
    for row in M:
        for entry in row:
            s = s + entry
    return s

def test_sum():
    M = [[1,2,3],[4,5,6],[7,8,9]]
    assert sum_matrix_entries(M) == 45
    return "Test passed!"

test_sum()

Continue

def file_bug_report(id, description):
    "A dummy function which represents filing a bug report"
    print(f"bug {id} ({description}) successfully filed")


bugs = {"07cc242a":
          "`trackShipment` hangs if `trackingNumber` is missing",
        "100b359a":
          "customers not receiving text alerts"}

Solution. We loop over the items:

for id, desc in bugs.items():
    file_bug_report(id, desc)

Continue

def factorial(n):
    "Return n!"
    # add code here

def test_factorial():
    assert factorial(3) == 6
    assert factorial(0) == 1
    assert factorial(20) == 2432902008176640000
    return "Tests passed!"

test_factorial()

Solution. We loop through range(1, n+1) and multiply as we go.

def factorial(n):
    "Return n!"
    product = 1
    for k in range(1, n+1):
        product = k * product
    return product


def test_factorial():
    assert factorial(3) == 6
    assert factorial(0) == 1
    assert factorial(20) == 2432902008176640000
    return "Tests passed!"

test_factorial()

Continue

While statements

The Collatz conjecture is one of the easiest-to-state unsolved problems in mathematics. Starting from any given positive integer, we halve it if it's even and triple it and add one if it's odd. The Collatz conjecture states that repeatedly applying this rule always gets us to the number 1 eventually. For example, the Collatz sequence starting from 17 is

If we want to write a Python function which returns the Collatz sequence for any given starting number, we face a problem: we don't know from the start how many steps it will take to reach 1, so it isn't clear how we could use a for loop. What we want to do is execute a block of code until a given condition is met. Python provides the while loop for this purpose.

def collatz_sequence(n):
    "Return the Collatz sequence starting from n"
    sequence = [n]
    while n > 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3*n + 1
        sequence.append(n)
    return sequence

def test_collatz():
    assert collatz_sequence(17) == [17, 52, 26, 13,
                                40, 20, 10, 5,
                                16, 8, 4, 2, 1]
    return "Test passed!"

test_collatz()

The expression which appears immediately following the while keyword is called the condition, and the block indented below the while statement is the body of the loop. The rules of the language stipulate the following execution sequence for a while statement: the condition is evaluated, and if it's true, then the body is executed, then condition is evaluated again, and so on. When the condition returns False, the loop is exited. An exit can also be forced from within the body of the while loop with the keyword break.

def newtonsqrt(n):
    """Use Newton's algorithm to approximate √n"""
    # add code here

def test_newton():
    assert abs(newtonsqrt(2) - 1.4142135623730951) < 1e-6
    assert abs(newtonsqrt(9) - 3) < 1e-6
    return "Tests passed!"

test_newton()

Solution. We keep up with two separate variables, which we call x and old_x, to compare the most recent two iterates:

def newtonsqrt(n):
    """Use Newton's algorithm to approximate √n"""
    x = 1
    while True:
        old_x = x
        x = 1/2 * (x + n/x)
        if abs(x - old_x)/old_x < 1e-8:
            return x

Continue

Exercises

def checkerboard(n):
    """
    Prints an n × n checkerboard, like:
      
    xoxo
    oxox
    xoxo
    oxox
    """

Solution. We loop through the rows and use an if statement to print a different output depending on whether the row is even-numbered or odd-numbered.

def checkerboard(n):
    "Prints an n × n checkerboard"
    for i in range(n):
        if i % 2 == 0:
            print("xo" * (n//2))
        else:
            print("ox" * (n//2))
        print("\n")

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

def print_row(n,row):
    """
    Prints the nth row (`row`) of Pascal's triangle
    with appropriate spacing.
    """

def next_row(row):
    """
    Returns the next row in Pascal's triangle.
    Example: next_row([1,3,3,1]) == [1,4,6,4,1]
    """

def pascals_triangle(n):
    """
    Print the first n rows of Pascal's triangle
    """