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. [CS230] 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: Multiplication Tables

Write a multiplication table of dimension yRows * xCols where yRows represents the number of rows in the table and xCols represents the number of columns in the table.

multTable(4, 4)

1 2 3 4 

2 4 6 8 

3 6 9 12 

4 8 12 16

multTable(3, 5)

1 2 3 4 5 

2 4 6 8 10 

3 6 9 12 15

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.

Hint: Remember also that in Python you can print one line at a time moving from left to right. This means you can't print each full column as you go. This will be important when you decide what role the inner for loop and outer for loop should play.

In [11]:
def multTable(yRows, xCols):
    for y in range(1, yRows + 1):
        for x in range(1, xCols + 1):
            print(x * y, end = ' ')
        print('\n')
        
In [12]:
multTable(4, 4)
1 2 3 4 

2 4 6 8 

3 6 9 12 

4 8 12 16 

In [13]:
multTable(3, 5)
1 2 3 4 5 

2 4 6 8 10 

3 6 9 12 15 

You may notice that when you call multTable with arguments larger than 4 or 5 that the table starts to become noticeably misaligned.

In [14]:
multTable(9, 9)
1 2 3 4 5 6 7 8 9 

2 4 6 8 10 12 14 16 18 

3 6 9 12 15 18 21 24 27 

4 8 12 16 20 24 28 32 36 

5 10 15 20 25 30 35 40 45 

6 12 18 24 30 36 42 48 54 

7 14 21 28 35 42 49 56 63 

8 16 24 32 40 48 56 64 72 

9 18 27 36 45 54 63 72 81 

In lab, you will learn how to align the columns so that your multiplication table is more aesthetically pleasing.

5. Nested loops for accumulation

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

In [15]:
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 [16]:
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 [17]:
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 [18]:
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

In this exercise, we will create the grid of circles shown in the pictures below.

Circle Grid with Light Sky Blue Circle Grid with Random Colors

First lets start out by importing the necessary turtle functions into Python.

In [19]:
from turtle import *
from turtleBeads import *

We will also want to define some criteria about our grid. Let's say that each circle should be a radius of 50 and the grid should have 5 x 5 circles. This means that we will have x positions of -200, -100, 0, 100, 200 and y positions of -200, -100, 0, 100, 200. Notice how we need the same coordinates for both the x and y positions.

In [20]:
radius = 50

Next we will generate a sequence of coordinates to represent the x and y positions of each circle

Step 1: Generate a sequence of coordinates with range

Remember, you can use range with three arguments to create a sequence of desired values where the third argument provides a step value.

In [21]:
# use range to create coordinates -200, -100, 0, 100, 200
coords = range(-200, 300, 2*radius)
coords
Out[21]:
range(-200, 300, 100)

Step 2: 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 should look like this:

-200 -200  
-200 -100
-200 0
-200 100
-200 200
-100 -200
etc...

The above results are generated using a nested loop where the outer loop controls the x coordinate and the inner loop controls the y coordinate. In this case, it doesn't matter which loop controls the x or y coordinate because all coordinates will be generated, just in a different order. Either way will work but you may have different results than the ones shown above.

Also it is perfectly acceptable to reuse the same sequence in different for loops. Hint: Don't be afraid to use coords twice!

In [22]:
# Your code here
for x in coords:
    for y in coords:
        print(x, y)
-200 -200
-200 -100
-200 0
-200 100
-200 200
-100 -200
-100 -100
-100 0
-100 100
-100 200
0 -200
0 -100
0 0
0 100
0 200
100 -200
100 -100
100 0
100 100
100 200
200 -200
200 -100
200 0
200 100
200 200

Step 3: draw the circles within the nested loops

Now use a nested loop to create coordinates for each point and draw circles at those locations using a nested loop. Make sure to use the variables coords and radius from above. Make the color of each circle "LightSkyBlue".

In [23]:
reset()
noTrace()

# your code here.  Use a nested loop to produce circles of color "LightSkyBlue" at each coordinate.
for x in coords:
    for y in coords:
        teleport(x, y)
        color("LightSkyBlue")
        begin_fill()
        drawCircle(radius)
        end_fill()
        
showPicture()

Step 4: draw the circles with random colors

Now make your grid randomly select the color of each circle from a list of colors. To perform this task, first import random.

In [24]:
import random

To randomly select from a list of colors, we can use the function random.choice(sequence) where sequence is any sequence like a list, range, or string.

In [25]:
random.choice([1, True, -4.5])
Out[25]:
1
In [26]:
random.choice(range(100, 104))
Out[26]:
103
In [27]:
random.choice("fun")
Out[27]:
'u'

Now let's define a list of colors below:

In [28]:
colors = ["LightSkyBlue", "LightPink", "LightSeaGreen", "PaleVioletRed"]

Below, create a grid of circles but now with a randomly chosen color from the list above.

In [29]:
reset()
noTrace()

# your code here.  Use a nested loop to produce circles of randomly chosen colors at each coordinate.
for x in coords:
    for y in coords:
        teleport(x, y)
        color(random.choice(colors))
        begin_fill()
        drawCircle(radius)
        end_fill()
        
showPicture()

8. [CS230] 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 code below? Think about it before you run the code below!

In [30]:
reset()
noTrace()

for x in coords:
    for y in coords:
        if y <= x:
            teleport(x, y)
            color(random.choice(colors))
            begin_fill()
            drawCircle(radius)
            end_fill()

showPicture()

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

Answers

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

  • For UpperRightTriangleOfCircles, change y <= x to x + y >= 0

  • For LowerLeftTriangleOfCircles, change y <= x to x + y <= 0

9. [CS230] Swapping values

The following code will not swap the values correctly:

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

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

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

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

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

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

10. [CS230] 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 [33]:
a, b = 0, 1
a + b
Out[33]:
1
In [34]:
a, b, c = 1, 2, 3
print(c, a, b)
3 1 2
In [35]:
a, b = "AB"
print(a, b)
A B
In [36]:
a, b = [10, 20]
print(a + b, a * b)
30 200
In [37]:
a, b = (15, 25)
print(b - a)
10
In [38]:
a, b, c, d = [1, 2, 3, 4]
print(a*b*c*d)
24
In [39]:
a, b = 10
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-39-9aefcd17cdb2> in <module>
----> 1 a, b = 10

TypeError: cannot unpack non-iterable int object
In [40]:
a, b = (1, 2, 4)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-40-ed6d19501eae> 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 [41]:
nums = [3, 2, 1, 4]
nums[0], nums[1] = nums[1], nums[0]
nums
Out[41]:
[2, 3, 1, 4]
In [42]:
a, b = 0, 1
print(a, b)
a, b = b, a
print(a, b)
0 1
1 0

Optional: The example of GCD from Lecture Slide 19

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