CS111 Lecture: Iteration I¶
Table of Contents
1. Computer Password Checker¶
Let's try and build a simple password checker using the tools we know. The general idea of a password checker is that the user needs to keep trying passwords until they get the correct password. At this point, the user is logged in. What are the key steps we need to build this program? Let's make an outline.
- Create a password to be checked
- Ask the user for their password guess and keep asking the user for their password until they guess the correct one
- Perform whatever action once the user has logged in
There are several key elements that we need to identify. The most important is that there will be some code that we have to repeat potentially if the user keeps guessing incorrectly. Eventually, we use loops to help us. Loops repeat code. Second, we need to keep repeating until some condition is met, namely the user has entered in their password correctly. Formally, we call this a continuation condition. It is the condition that determines whether we need to repeat or to move on to someother code.
Manual Implementation¶
It turns out that without loops we do not have the means to implement this program. However, we can simulate what we should do by reexecuting certain code cells.
The password¶
password = "12345"
Keep asking until they get the right password¶
Here, we need to continually execute the cell until we are no longer prompted to enter a password. We will have to do this manually with the tools we know. This is the moment though where we will need a loop because we want to repeat this block of code until some condition is met (i.e., the password is entered correctly).
# prompt the user
prompt = "Please enter your password: "
suppliedPassword = input(prompt)
# check the password
if password != suppliedPassword:
print("Please re-execute this cell and enter in the correct password.")
else:
print("You have logged in correctly!")
Log In Code¶
This is the code that would execute once the user has guessed the correct password.
print("Welcome")
2. Introducing while loops¶
A while loop is a control flow statement, that repeats a body of code until some condition is met. This is perfect for our password checker! The condition is called a continuation condition. If the continuation condition is True, then we will continue to execute the code body one more time. If the continuation condition is False, then we will not continue and move on to the next statement. The chart below details the control flow of a while loop outlined with the dotted dashes.
Below is our first example of a while loop to implement our password checker.
password = "12345"
# prompt the user
prompt = "Please enter your password: "
suppliedPassword = input(prompt)
# Keep asking the user until password is correct
# continuation condition: password != suppliedPassword
# if continuation condition is True, keep asking for password because they are not equal
# if continuation condition is False, do not execute the body and ask for age because password is correct
while password != suppliedPassword: # continuation condition
print("Your password is incorrect. Please re-enter the correct password.")
suppliedPassword = input(prompt)
# we can only have arrived her is password == suppliedPassword
print("You have logged in successfully!")
3. Other examples of while loops¶
A while loop for counting up¶
i = 0
while i < 10:
print(i)
i += 1
Another example of a while loop that depends on user input¶
prompt = 'Please enter your name (type quit to exit): '
name = input(prompt)
while (name.lower() != 'quit'):
print('Hi,', name)
name = input(prompt)
print('Goodbye')
Example of a while loop that depends on argument value¶
def printHalves(n):
while n > 0:
print(n)
n = n//2
printHalves(100)
printHalves(22)
printHalves(75)
4. Gotcha: Infinite Loops¶
We sometimes might wrongly write an infinite loop, one that never ends. In these cases, use Ctrl+C to break out of the loop.
def printHalves2(n):
"""Attempts to print positive successive halves of n.
"""
while n > 0:
print(n)
n = n//2
NOTE: In the Notebook, it might not be possible sometimes to break the loop, even with Kernel|Interrupt. In this case, close the tab and open it again.
printHalves2(22)
5. The Accumulating Pattern¶
It is common to use a while loop in conjunction with one or more accumulators = variables that accumulate results from processing the elements of a sequence.
All accumulation patterns follow these three steps:
- Define an accumulation variable
- Iterate to accumulate
- Return the accumulation variable
Here is a sumHalves function that takes an nonnegative integer and returns the sum of the values printed by printHalves.
def sumHalves(n):
"""Accumulates the sum of elements that are halves of the preceding numbers.
"""
sumSoFar = 0
while n > 0:
sumSoFar += n
n = n//2
return sumSoFar
sumHalves(22)
6. Printing the iteration table¶
We can understand the execution of a loop by an iteration table whose columns are state variables that change during the loop and where each row indicates the values of the state variables at a particular point in time.
Here is an iteration table for sumHalves(22):
| n | sumSoFar |
|---|---|
| 22 | 0 |
| 11 | 22 |
| 5 | 33 |
| 2 | 38 |
| 1 | 40 |
| 0 | 41 |
You can get a Python loop to display the rows of an iteration table by adding two print statements:
- Add one
printstatement right before thewhileloop. This statement is executed once, before the loop execution begins. - Add a second
printstatement as the last statement in the loop body. This statement is executed for each iteration of the loop.
def sumHalvesTable(n):
sumSoFar = 0
print('n:', n, '| sumSoFar:', sumSoFar) # First print is executed once
while n > 0:
sumSoFar += n # or sumSoFar = sumSoFar + n
n = n//2
print('n:', n, '| sumSoFar:', sumSoFar) # Second print may be executed multiple times (including zero)
return sumSoFar
sumHalvesTable(22)
Does the sumHalves2 function have the same input/output behavior as sumHalves? Create an iteration table that predicts the output of sumHalves2(22), and test your prediction below:
Here is an iteration table for sumHalves2(22):
| n | sumSoFar |
|---|---|
| 22 | 0 |
| 11 | 11 |
| 5 | 16 |
| 2 | 18 |
| 1 | 19 |
| 0 | 19 |
def sumHalves2(n):
'''Prints positive successive halves of n'''
sumSoFar = 0
while n > 0:
n = n//2
sumSoFar = sumSoFar + n
return sumSoFar
sumHalves2(22)
Moral of the story: the order of updates to state variables can affect how the loop behaves!
7. Another Motivating Example: counting vowels¶
Assume we are given different words, such as "Wellesley", "Boston", "abracadbra", "osteoarthritis", and so on, and want to count the number of vowels in each word, or to count how many times a particular letter occurs in the word.
How do we do that? First, we'll need our "old friend", isVowel as a predicate that we can use in conditional statements.
Old friend: isVowel¶
def isVowel(char):
"""Predicate that returns true only when a letter is a vowel."""
return char.lower() in "aeiou"
def testIsVowel(char):
"""Helper function to test isVowel"""
print("isVowel('" + char + "')", "=>", isVowel(char))
testIsVowel('d')
testIsVowel('D')
testIsVowel('a')
testIsVowel('E')
testIsVowel('i')
testIsVowel('O')
testIsVowel('u')
testIsVowel('y')
Use indices to access elements in a string¶
We can access each character (or element) in a string word by using indices. These are integers from 0 to len(word)-1
word = "Boston"
word[0]
len(word)
word[1]
word[3]
Question: Will the following expression work?
word[6]
Question: What about this one, will this work?
word[-1]
Question: Can you access the character "s" by using a negative index? Write it below to test:
word[-4]
Sequential vs. Chained conditionals¶
How can we count the vowels in a word? We can use isVowel and the indices to test each character and keep track of vowels through a counter variable.
But, how do we write the conditionals to test for each character?
Scenario 1: A series of if statements¶
Can you predict the result?
word = 'Boston'
counter = 0
if isVowel(word[0]):
counter += 1
if isVowel(word[1]):
counter += 1
if isVowel(word[2]):
counter += 1
if isVowel(word[3]):
counter += 1
if isVowel(word[4]):
counter += 1
if isVowel(word[5]):
counter += 1
print(counter)
Scenario 2: Chained conditionals¶
Can you predict the result?
word = 'Boston'
counter = 0
if isVowel(word[0]):
counter += 1
elif isVowel(word[1]):
counter += 1
elif isVowel(word[2]):
counter += 1
elif isVowel(word[3]):
counter += 1
elif isVowel(word[4]):
counter += 1
elif isVowel(word[5]):
counter += 1
print(counter)
Try the code with another word¶
We always strive to write code that is generic, what will happen when we run it with a new string?
word = 'Lynn'
counter = 0
if isVowel(word[0]):
counter += 1
if isVowel(word[1]):
counter += 1
if isVowel(word[2]):
counter += 1
if isVowel(word[3]):
counter += 1
if isVowel(word[4]):
counter += 1
if isVowel(word[5]):
counter += 1
print(counter)
Using a While Loop¶
Remember a while loop is used to repeat a block of code. What code do we want to repeat? We want to repeat the conditional for each index in the string. Here we can use a while loop to start at index 0 and repeat until we reach the last index of the string. We will need two accumulation variables. One to increment the counter and one to increment the index.
word = "Boston"
counter = 0
index = 0
while index < len(word): # continuation condition
if isVowel(word[index]):
counter += 1
index += 1
print(word + ' has ' + str(counter) + ' vowels')
word = "Manchester-by-the-Sea"
counter = 0
index = 0
while index < len(word):
if isVowel(word[index]):
counter += 1
index += 1
print(word + ' has ' + str(counter) + ' vowels')
8. Challenge Exercise: countChar¶
Define a function countChar that takes two arguments -- a character and a word -- and returns the number of times that character appears in the word.
# Your code here
def countChar(char, word):
counter = 0
index = 0
while index < len(word):
if word[index] == char:
counter += 1
index += 1
return counter
def testCountChar(char, word):
"""Helper function to test countChar"""
print("countAllVowels('" + char + "', '" + word + "')", "=>", countChar(char, word))
testCountChar('i', 'Mississippi')
testCountChar('p', 'Mississippi')
testCountChar('M', 'Mississippi')
testCountChar('m', 'Mississippi')
testCountChar('-', 'Manchester-by-the-Sea')
testCountChar('t', 'To be or not to be')
testCountChar(' ', 'To be or not to be')