1. Review: sumBetween with iteration table

We have added two print statements in the function, to print the iteration table,
which shows how the three state variables change from one iteration step to the next.

In [1]:
def sumBetween(lo, hi):
    """Returns the sum of the integers from lo to hi
    (inclusive). Assume lo and hi are integers.
    """
    sumSoFar = 0          # initialize accumulator
   
    # Print initial values of state variables, before entering loop the first time
    print('lo:', lo, '| hi:', hi, '| sumSoFar:', sumSoFar)
    
    while lo <= hi:  
        sumSoFar += lo    # update accumulator
        lo += 1
        # Print updated values of state variables before start of next iteration of loop 
        print('lo:', lo, '| hi:', hi, '| sumSoFar:', sumSoFar)
        
    return sumSoFar       # return accumulator
In [2]:
sumBetween(4, 8)
lo: 4 | hi: 8 | sumSoFar: 0
lo: 5 | hi: 8 | sumSoFar: 4
lo: 6 | hi: 8 | sumSoFar: 9
lo: 7 | hi: 8 | sumSoFar: 15
lo: 8 | hi: 8 | sumSoFar: 22
lo: 9 | hi: 8 | sumSoFar: 30
Out[2]:
30

2. Using iteration tables to design loops: replaceVowelSequences

When given an iteration problem, it's usually a very bad idea to start by writing Python code. You'll often waste a lot of time implementing and debugging an approach that may be far from correct.

Instead, we recommend that you begin every iteration problem by creating iteration tables for several concrete examples for that problem, and use these to figure out the state variables and iteration rules for the problem. Then you can translate the state variables and iteration rules into Python code.

Here we will illustrate this strategy in the context of a function that appeared on a previous midterm exam.

replaceVowelSequences function specification

Define a function replaceVowelSequences that takes a string as its single input, and returns a version of the string in which each sequence of consecutive vowels is replaced by the asterisk character, '*'. The following table shows the output of replaceVowelSequences for some input strings:

Input Output
`'section'` `'s*ct*n'`
`'conscientious'` `'c*nsc*nt*s'`
`'audacious'` `'*d*c*s'`
`'amnesia'` `'*mn*s*'`
`'strengths'` `'str*ngths'`
`'wryly'` `'wryly'`

Some sample iteration tables for replaceVowelSequences

In the following iteration tables, explain:

  • State Variables: What are the meanings of the state variables resultSoFar and inVowelSequence?

    Answer:

    • resultSoFar is the prefix of the final result string determined by the characters processed so far.
    • inVowelSequence indicates whether the current char is a vowel. It is helpful, because it can be used in the next row to determine if the previous character was a value.
  • Iteration Rules:

    • How is resultSoFar in a row determined from (1) char in that row (2) resultSoFar from the previous row and (3) inVowelSequence from the previous row?

      Answer:

      • If char is a vowel:
        • If the previous inVowelSequence is False, add '*' to the end of resultSoFar
        • If the previous inVowelSequence is True, resultSoFar is unchanged
      • If char is not a vowel, add char to the end of resultSoFar
    • How is inVowelSequence in a row determined from char in that row?

      Answer: inVowelSequence is True if char is a vowel and False otherwise.

char resultSoFar inVowelSequence
`''` `False`
`'s'` `'s'` `False`
`'e'` `'s*'` `True`
`'c'` `'s*c'` `False`
`'t'` `'s*ct'` `False`
`'i'` `'s*ct*'` `True`
`'o'` `'s*ct*'` `True`
`'n'` `'s*ct*n'` `False`

char resultSoFar inVowelSequence
`''` `False`
`'a'` `'*'` `True`
`'u'` `'*'` `True`
`'d'` `'*d'` `False`
`'a'` `'*d*'` `True`
`'c'` `'*d*c'` `False`
`'i'` `'*d*c*'` `True`
`'o'` `'*d*c*'` `True`
`'u'` `'*d*c*'` `True`
`'s'` `'*d*c*s'` `False`

Translating the iteration tables into a Python function for replaceVowelSequences

Now translate the state variables and iteration rules from above into a Python definition for replaceVowelSequences

In [3]:
def isVowel(char):
    return char.lower() in 'aeiou'

def replaceVowelSequences(word):
    resultSoFar = ''
    inVowelSequence = False
    for char in word:
        if isVowel(char):
            if not inVowelSequence:
                resultSoFar += '*'
            inVowelSequence = True
        else:
            resultSoFar += char
            inVowelSequence = False
    return resultSoFar
In [4]:
def testReplaceVowelSequences(words):
    for word in words:
        print("replaceVowelSequences('" + word + "') => '" + replaceVowelSequences(word) + "'")
        
testReplaceVowelSequences('section conscientious audacious amensia strenghts wryly'.split())
replaceVowelSequences('section') => 's*ct*n'
replaceVowelSequences('conscientious') => 'c*nsc*nt*s'
replaceVowelSequences('audacious') => '*d*c*s'
replaceVowelSequences('amensia') => '*m*ns*'
replaceVowelSequences('strenghts') => 'str*nghts'
replaceVowelSequences('wryly') => 'wryly'

An alternative definition of replaceVowelSequences without the inVowelSequence state variable

It is possible to determine the value of inVowelSequence by looking at resultSoFar from the previous row. How?

Use this observation to define an alternative definition of replaceVowelSequences without the inVowelSequence state variable

In [5]:
def replaceVowelSequences(word):
    resultSoFar = ''
    for char in word:
        if isVowel(char):
            if (resultSoFar == '' # Careful! Must have this test for case 
                                  # where word begins with vowel!
                or resultSoFar[-1] != '*'):
                resultSoFar += '*'
        else:
            resultSoFar += char
    return resultSoFar
In [6]:
testReplaceVowelSequences('section conscientious audacious amensia strenghts wryly'.split())
replaceVowelSequences('section') => 's*ct*n'
replaceVowelSequences('conscientious') => 'c*nsc*nt*s'
replaceVowelSequences('audacious') => '*d*c*s'
replaceVowelSequences('amensia') => '*m*ns*'
replaceVowelSequences('strenghts') => 'str*nghts'
replaceVowelSequences('wryly') => 'wryly'

3. Nested for loops for printing

A simple example of two nested for loops to generate the multiplication table.

In [7]:
for i in range(2, 6): # This is called the "outer loop"
    for j in range(2, 6): # This is called the "inner loop"
        print(i, 'x', j, '=', i*j)
2 x 2 = 4
2 x 3 = 6
2 x 4 = 8
2 x 5 = 10
3 x 2 = 6
3 x 3 = 9
3 x 4 = 12
3 x 5 = 15
4 x 2 = 8
4 x 3 = 12
4 x 4 = 16
4 x 5 = 20
5 x 2 = 10
5 x 3 = 15
5 x 4 = 20
5 x 5 = 25

What happens if we add conditionals in the outer and/or inner loop? Predict the output of the following examples:

In [8]:
for i in range(2, 6): 
    for j in range(2, 6): 
        if i <= j: 
            print(i, 'x', j, '=', i*j)
2 x 2 = 4
2 x 3 = 6
2 x 4 = 8
2 x 5 = 10
3 x 3 = 9
3 x 4 = 12
3 x 5 = 15
4 x 4 = 16
4 x 5 = 20
5 x 5 = 25
In [9]:
for i in range(2, 6): 
    if i % 2 == 0: 
        for j in range(2, 6): 
            if i <= j: 
                print(i, 'x', j, '=', i*j)
2 x 2 = 4
2 x 3 = 6
2 x 4 = 8
2 x 5 = 10
4 x 4 = 16
4 x 5 = 20

As another simple example of nested loops, this one to print words. Predict the words that will be printed, in order.

In [10]:
for letter in ['b','d','r','s']:
    for suffix in ['ad', 'ib', 'ump']: 
        print(letter + suffix)
bad
bib
bump
dad
dib
dump
rad
rib
rump
sad
sib
sump

4. Exercise 1: Print patterns with nested loops

Write a function with 4 parameters that can create patterns like below.
Yes, these patterns can be created with a single for loop and string concatenation, but try to do it with nested loops.

printPattern(5, 10, 3, '+')

| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |

printPattern(3, 6, 2, '&')

| && && && && && && |
| && && && && && && |
| && && && && && && |

Hint: In Python, you can change print() to end with something other than the newline character (i.e., '\n') by changing its default argument. To do so, simply write print('a', end = ''). The parameter end sets how you should conclude printing. By default, it is '\n'. Now it is '', allowing the programmer to continue printing on the same line.

In [11]:
def printPattern(numRows, numCols, size, symbol):
    # Flesh out this function body
    for i in range(numRows):
        print("|", end = ' ')                 # Change default end from '\n' to ' '
        for j in range(numCols):
            print(size * symbol, end = ' ')   
        print("|")                            # Here we use the default end to create a newline
        
In [12]:
printPattern(5, 10, 3, '+')
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
| +++ +++ +++ +++ +++ +++ +++ +++ +++ +++ |
In [13]:
printPattern(3, 6, 2, '&')
| && && && && && && |
| && && && && && && |
| && && && && && && |

5. Nested loops for accumulation

A common reason to use nested loops is to accumulate values for every element of a sequence:

In [14]:
def isVowel(char):
    return char.lower() in 'aeiou'

verse = "Two roads diverged in a yellow wood"
for word in verse.split():
    counter = 0
    for letter in word:
        if isVowel(letter):
            counter += 1
    print('Vowels in "' + word + '" =>', counter)
Vowels in "Two" => 1
Vowels in "roads" => 2
Vowels in "diverged" => 3
Vowels in "in" => 1
Vowels in "a" => 1
Vowels in "yellow" => 2
Vowels in "wood" => 2

Experiment!

In the code above change the position of the statement counter = 0.

  1. take it outside the outer loop
  2. put it inside the inner loop

how can you explain these results?

Experiment 1: take counter outside the outer loop

In [15]:
def isVowel(char):
    return char.lower() in 'aeiou'

verse = "Two roads diverged in a yellow wood"
counter = 0

for word in verse.split():
    for letter in word:
        if isVowel(letter):
            counter += 1
    print('Vowels in "' + word + '" =>', counter)
Vowels in "Two" => 1
Vowels in "roads" => 3
Vowels in "diverged" => 6
Vowels in "in" => 7
Vowels in "a" => 8
Vowels in "yellow" => 10
Vowels in "wood" => 12

Explanation: Here counter is accumulating the vowels across all words in the sentence, thus, at the end it contains the total number of vowels.

Experiment 2: put counter inside the inner loop

In [16]:
def isVowel(char):
    return char.lower() in 'aeiou'

verse = "Two roads diverged in a yellow wood"

for word in verse.split():
    for letter in word:
        counter = 0           # counter inside the inner loop
        if isVowel(letter):
            counter += 1
    print('Vowels in "' + word + '" =>', counter)
Vowels in "Two" => 1
Vowels in "roads" => 0
Vowels in "diverged" => 0
Vowels in "in" => 0
Vowels in "a" => 1
Vowels in "yellow" => 0
Vowels in "wood" => 0

Explanation: Here counter is set to 0 every time we enter the inner loop and it forget about vowels that it has seen before.

6. Avoiding nested loops with functions

Since nested loops can be challenging to think about, it's nice to try to avoid them when possible.

One strategy is to capture the inner loop in a separate function. In the above vowel-counting example, this is easy to do with the countVowels function we defined in a previous lecture:

In [17]:
def isVowel(char):
    return char.lower() in 'aeiou'

def countVowels(word):
    counter = 0
    for letter in word:
        if isVowel(letter):
            counter += 1
    return counter

def countVowelsInVerse(verse):
    for word in verse.split():
        print('Vowels in "' + word + '" =>', countVowels(word))

countVowelsInVerse("Two roads diverged in a yellow wood")
Vowels in "Two" => 1
Vowels in "roads" => 2
Vowels in "diverged" => 3
Vowels in "in" => 1
Vowels in "a" => 1
Vowels in "yellow" => 2
Vowels in "wood" => 2

By "hiding" the inner loop in the countVowels function, we end up thinking about two independent non-nested loops!

7. Exercise 2: Nested loops with graphics

Write the function drawGrid that will create the grid of circles shown in the picture below.
It uses the class Color from cs1graphics to generate random colors: Color.randomColor().

Let's start by the defining what we know about the problem:

In [18]:
from cs1graphics import *

cWidth = 800 # canvas width
cHeight = 600 # canvas height
radius = 50 # circle radius

paper = Canvas(cWidth, cHeight, 'white', 'Circle Grid')

Step 1: Generate the list of all x values for the centers with range

Remember, you can use range with three arguments to create a list of desired values.

In [19]:
# use range to create the list: [50, 150, ..., 750] using variable names
range(radius, cWidth, 2*radius)
Out[19]:
range(50, 800, 100)

Step 2: Generate the list of all y values for the centers with range

In [20]:
# use range to create the list: [50, 150, ..., 550] using variable names
range(radius, cHeight, 2*radius)
Out[20]:
range(50, 600, 100)

Step 3: use nested loops to create all pairs (x, y)

Make use of the two range expressions from Step 1 and Step 2. The pairs you'll create look like this: (50, 50) (50, 150) (50, 250) (50, 350), ...

In [21]:
for x in range(radius, cWidth, 2*radius):
    for y in range(radius, cHeight, 2*radius):
        print(x, y)
50 50
50 150
50 250
50 350
50 450
50 550
150 50
150 150
150 250
150 350
150 450
150 550
250 50
250 150
250 250
250 350
250 450
250 550
350 50
350 150
350 250
350 350
350 450
350 550
450 50
450 150
450 250
450 350
450 450
450 550
550 50
550 150
550 250
550 350
550 450
550 550
650 50
650 150
650 250
650 350
650 450
650 550
750 50
750 150
750 250
750 350
750 450
750 550

Step 4: draw the circles within the nested loops

You can use the syntax: Circle(radius, Point(x,y)) to generate each circle directly at its desired location.
Don't forget to set the fill color to Color.randomColor() as well as add the circles to the canvas.

In [22]:
for x in range(radius, cWidth, 2*radius):
    for y in range(radius, cHeight, 2*radius):
        circ = Circle(radius, Point(x,y))
        circ.setFillColor(Color.randomColor())
        paper.add(circ)
In [23]:
paper.close()

8. Exercise 3: Triangles of Circles

Suppose we want to generate triangular patterns of circles that touch two sides of a square:

UpperLeftTriangleOfCircles UpperRightTriangleOfCircles
LowerLeftTriangleOfCircles LowerRightTriangleOfCircles

Which of the above four patterns is generated by the following drawTriangleOfCircles function?

In [24]:
def drawTriangleOfCircles(numCirclesOnSide, radius):  
    
    # Create a square canvas than can fit numCirclesOnSide on one side. 
    cSide = 2*radius*numCirclesOnSide # side length of canvs
    canvas = Canvas(cSide, cSide, 'white', 'TriangleOfCircles')
    
    # Populate the canvas with circles in a triangular pattern
    for x in range(radius, cSide, 2*radius):
        for y in range(radius, cSide, 2*radius):
            if y <= x: 
                circ = Circle(radius, Point(x,y))
                circ.setFillColor(Color.randomColor())
                canvas.add(circ)
   
    # Return the final canvas    
    return canvas 
In [25]:
canv = drawTriangleOfCircles(5, 50)

drawTriangleOfCircles adds only circles whose y-centers are less than or equal to the x-centers, which is the pattern for UpperRightTriangleOfCircles

In [26]:
canv.close()

Question What (small) changes can we make to drawTriangleOfCircles to draw the other three patterns?

Answers

  • For LowerLeftTriangleOfCircles, change y <= x to y >= x

  • For UpperLeftTriangleOfCircles, change y <= x to x + y <= cSide

  • For LowerRightTriangleOfCircles, change y <= x to x + y >= cSide

9. Swapping values

The following code will not swap the values correctly:

In [27]:
nums = [3, 2, 1, 4]

# swapping values?
nums[0] = nums[1]
nums[1] = nums[0]
nums
Out[27]:
[2, 2, 1, 4]

What works instead is the use of a so-called temporary variable to hold one of the values temporarily:

In [28]:
nums = [3, 2, 1, 4]

oldNumsSub0 = nums[0] # oldNumSub0 is a temporary variable
nums[0] = nums[1]
nums[1] = oldNumsSub0 

nums
Out[28]:
[2, 3, 1, 4]

10. Simultaneous assignment

Simulataneous assignment is another name for the notion of tuple assignment introduced near the end of lecture called Iteration1.

Try to guess the result of each cell without running it, then test your guess.

In [29]:
a, b = 0, 1
a + b
Out[29]:
1
In [30]:
a, b, c = 1, 2, 3
print(c, a, b)
3 1 2
In [31]:
a, b = "AB"
print(a, b)
A B
In [32]:
a, b = [10, 20]
print(a + b, a * b)
30 200
In [33]:
a, b = (15, 25)
print(b - a)
10
In [34]:
a, b, c, d = [1, 2, 3, 4]
print(a*b*c*d)
24
In [35]:
a, b = 10
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-35-8dd506a19743> in <module>()
----> 1 a, b = 10

TypeError: 'int' object is not iterable
In [36]:
a, b = (1, 2, 4)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-36-01d9c0c9819e> in <module>()
----> 1 a, b = (1, 2, 4)

ValueError: too many values to unpack (expected 2)

Swapping variables in one line

Using tuple assignment, we can swap values in Python in one statement:

In [37]:
nums = [3, 2, 1, 4]
nums[0], nums[1] = nums[1], nums[0]
nums
Out[37]:
[2, 3, 1, 4]
In [38]:
a, b = 0, 1
print(a, b)
a, b = b, a
print(a, b)
0 1
1 0

The example of GCD from Lecture Slide 19

In [39]:
def gcdFixed3(a, b):
    while b != 0:
        a, b = b, a % b # tuple (simultaneous) assignment                      
    return a 
In [40]:
gcdFixed3(84, 60)
Out[40]:
12