# 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 **for loop**.

*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.

We can nest `for`

statements. For example, suppose we have a matrix represented as a

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()

**Exercise**

Suppose you have imported a function `file_bug_report`

with two parameters: `id`

and `description`

. Suppose also that you have a `dict`

called `bugs`

whose keys are ids and whose values are strings representing descriptions. Write a loop which performs the action of filing each bug report in the dictionary.

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)

**Exercise**

Write a `factorial`

which takes a positive integer `n`

as an argument and returns its factorial.

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()

*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

17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

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`

.

**Exercise**

Newton's algorithm for finding the square root of a number `n`

starts from 1 and repeatedly applies the function . For example, applying this algorithm to approximate , we get

1, 3/2, 17/12, 577/408, ...

This algorithm converges very fast: 577/408 approximates with a relative error of about 0.00015%.

Write a function `newtonsqrt`

which takes as an argument the value `n`

to square root and applies Newton's algorithm until the relative difference between consecutive iterates drops below .

Note that can be represented in Python using scientific notation `1e-8`

.

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

## Exercises

**Exercise**

Write a function which prints an checkerboard pattern of `x`

's and `o`

's.

*Note*: `\n`

in a string literal represents the "newline" character. You'll need to print this character after each row you've printed.

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")

**Exercise**

Write a function which prints Pascal's triangle up to the $n$th row, where the top row counts as row zero. You might want to use a helper function `print_row(n,row)`

to manage the responsibility of printing each row, as well as a helper function `next_row(row)`

to calculate each row from the previous one.

Example output, for `n = 4`

:

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

*Note*: there's no solution to this one, but you can do it on your own!

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 """