Class 8

While Loops

Objectives for today

Use relational operators to compare values
Describe the execution of for and while loops and differentiate between them
Use break and continue keywords to further control iterative algorithms
Appropriately choose between for and while loops for a computational problem

Non-boolean types that can be used as booleans

Will the following print statement get executed?

if "a string?":
    print("Do I get executed?")

Yes. Most values can be used in a boolean context. In Python, 0, 0.0, None, empty sequences (e.g. "") and a few other values evaluate as False (often termed “falsy”) and everything else is True (often termed “truthy”).

In general, I don’t recommend using this “implicit” type conversion as it just increases the chances for difficult-to-find bugs.

Now that we know about implicit booleans, though, we can resolve a common bug. In a previous in-class question, the solution was a == b or a == 5. Can we simplify that expression as a == b or 5 (i.e., is == distributive)? No, that expression is evaluated as a (a == b) or 5, which is not the same (and will always evaluate to True as 5 evaluates as True). What about a == (b or 5)? No, equality is not distributive. Instead if b is truthy, the above expression simplifies to a == b, if not, it simplifies to a == 5. If a and b are both 0, we should get True, but will get False.

Short circuit evaluation

Let’s think about a and b. If a evaluates to False do I need to evaluate b? Similarly if in a or b a evaluates to True do I need to evaluate b?

No. Python (and many other languages) “short-circuit” the evaluation of logical expressions. Doing so can both improve efficiency (we don’t perform computations we don’t need) and help us manage potentially problematic situations. For example in the following, we only ever execute dangerous_operation if is_valid(input) evaluates to True.

is_valid(input) and dangerous_operation(input)

Comparing strings and other non-numeric types

We can also apply relational operators, i.e. <, ==, etc., to other types; most notably strings. For example:

'Aardvark' < 'Zebra'
'aardvark' < 'Zebra'

True

False

That second one doesn’t seem to make much sense… Just as + has different meaning for strings than integers, the < a meaning specific to strings. Python compares strings using lexicographic ordering, i.e., it compares the ordering of corresponding characters. The first characters are compared, if equal, then the 2nd characters are compared and so on. If one string is a substring of the other, it is lexicographically less than, e.g.,

>>> "abc" < "abcdef"
True

This is not the same as a case-insensitive alphabetical ordering. When two letters are being compared, that comparison is based on their underlying numeric encoding. In the character encoding used by Python (and lots of other software), all upper case letters are less than lower case letters. Hence “aardvark” is “greater than” “Zebra”. You can access this numerical encoding with the ord function, e.g.,

ord("A")
ord("a")

Some more examples:

"test" == "test"
"test" == "testing"[0:4]
"test" == "TEST"

True

True

False

If we wanted to ensure that a string comparison was case insensitive, how could be we do so? Use the upper or lower methods to ensure consistent case.

`while` loops

We previously used for loops to execute a block of code for a specific number of repetitions. What if we don’t know how many iterations are needed? What might be such a situation? Obtaining a valid input from a user. We don’t know how many tries it will take someone to provide a valid input.

This is where we apply while loops. The general structure of a while loop is:

while <bool expression>:
    statement1
    statement2
    ...
    statementn

The statements in the loop body (i.e. statement1 … statementn) will be executed repeatedly until the boolean expression, the loop conditional, evaluates to False.

Here is a concrete example. What will this code print?

x = 5
while x > 0:
    print(x)
    x = x-1

What is the necessary implication of while loops? That some statement(s) within the body of the while loop will change the loop conditional (or otherwise terminate the loop). What happens if that is not the case, e.g.

while True:
    print("How many times will this string get printed?")

Hit Ctrl-C (Ctrl and C simultaneously) or hover over the name of the terminal in VS Code and click the button that looks like a trash can to stop execution. This is called an infinite loop and is a common problem. You will likely need to use Ctrl-C or the stop sign button at some point.

What about the following loop? Will it terminate?

i = 0
while i < 10:
    print("How many times will this string get printed?")
    i = i - 1

No. Because i starts at 0 and only gets smaller it will always be less than 10. What about this loop?

from random import randint
i = randint(1, 20)
while i < 10:
    print("How many times will this string get printed?")
    i = i + 1

Yes. If the value is less than 10, the loop with terminate after some number of iterations. If the value is greater than or equal to 10, the loop won’t execute at all.

In addition to changing the loop conditional we can also explicitly terminate the loop with the break statement. As its name suggests, break terminates the loop and begins executing the first statement after the loop. Although break is most commonly used with while loops, it can also be used to end for loops “early” (i.e., only perform a subset of the iterations).

Random Guessing Game

Let’s implement a guessing game in which Python picks a random integer from 1-20 (inclusive), and keeps asking the user to guess the number until they get it right. To help the user, the game should give hints “higher”, or “lower”.

What would be some key elements in such a program?

Generate a random integer
Accept input from the user
Conditional to check if guess was correct, and print success or hint messages
Loop that repeatedly prompts user for input and performs the above comparison

Check out guessing_game.py which implements one way to make this game. Currently, a boolean variable correct is used to track if the user answered correctly. But there are other strategies we could use:

break out of a “while True” loop on a correct answer
Compare the user response to the desired answered in the loop conditional

We’ll investigate these strategies together which will then be posted here after class.

Additionally, note the use of the input function for reading user inputs. input prints its prompt argument then waits for and returns the string the user typed before hitting Enter/Return. input returns a string and so we need to convert the result to an int for use in our game.

help(input)

Help on built-in function input in module builtins:

input(prompt='', /)
    Read a string from standard input.  The trailing newline is stripped.

    The prompt string, if given, is printed to standard output without a
    trailing newline before reading input.

    If the user hits EOF (*nix: Ctrl-D, Windows: Ctrl-Z+Return), raise EOFError.
    On *nix systems, readline is used if available.

`while` vs `for` loops

Often we can implement the same functionality with both a for loop and a while loop. In fact, in Python any for loop can be readily implemented with a while loop. The reverse is trickier. There are tricks that would enable us to make a for loop behave like a while loop in some situations, but they are exactly that – tricks. So for our purposes we should think of while loops as a superset of for loops.

As an example, how could we write a for loop to print the even numbers from 1-10 inclusive?

for i in range(2, 11, 2):
    print(i)

And the same with a while loop?

i = 2
while i <= 10:
    print(i)
    i += 2

We can see the clear correspondence between the while loop and the for loop. Here we effectively re-implemented the range within the while loop by setting the initial value, the end condition and the increment. What are some other ways we could have achieved the same result? One is to iterate through all integers in the range [1,10], but use an if statement, e.g., if i % 2 == 0: to identify and print the even values.

There is yet another way to implement this, and another keyword we can use called continue. When the interpreter sees continue it will skip the rest of the expressions in the current iteration and skip ahead to the next iteration.

For example, we can produce an equivalent loop to those above using:

for i in range(2, 11):
    if i % 2 == 1:
        continue
    print(i)

When to use `for` vs. `while`?

So when do we use a for loop and when do we use a while loop?

We use a for loop when

The number of iterations is known before the loop and does not depend on the statements in the loop body. That doesn’t mean the number of iterations is a fixed number (like the 4 sides of a square), just that we know the number of iterations before the loop starts.
The increment to the loop variable is the same on every iteration

As an example, iterating over all the elements in a sequence, e.g. a string, is an example of a situation where the number of iterations is known at the initiation of the loop (number of elements in sequence) and the increment is consistent (increment one element each iteration).

We would use a while loop in other settings, such as

The number of iterations is not known beforehand
The increments to loop variable are different, e.g. depend on a computation in the loop body

This an example where “style” matters but there are not necessarily clear “rules”. Often one approach or the other is more appropriate. The right choice will make the code more elegant, easier to reason about (and easier to debug).

`while` loops in action

A better way to design the snake game from last class

The for-loop used in our snake game from last class isn’t a very natural choice, though it works fine for a game that is limited to a certain amount of time. For indefinite games, however, we won’t know how many times to iterate, so this is a better candidate for a while loop.

Instead, we can replace the for-loop with a while loop that uses a condition based on whether the game is over. This “game over” function can also be encapsulated in a function:

def game_over():
    """
    Determines if the game is over.
    """
    # Here, we just determine if the player is on the screen, but other options could be:
    # 1. Use a time limit on the game.
    # 2. Check if the snake somehow intersected itself, which may not be allowed.
    return not inbounds()

The while loop for running the game can then be:

while not game_over():
  ...

Algorithms that “converge”

Many algorithms in computational mathematics need to iterate until some criterion is met which is most naturally achieved with a while loop.

For example, consider trying to calculate the square root of some number (e.g. if you were writing your own version of math.sqrt).

In AD 60, Heron described a technique to do this in an iterative way. If we want to calculate the square root of some number \(x\), the idea is to start with a guess \(y_0\) (and \(n = 0\)) and iteratively calculate:

\[ y_{n+1} = \frac{1}{2}\left(y_n + \frac{x}{y_n}\right) \]

until some convergence criterion is met. This criterion can be based on the difference between subsequent guesses, i.e. the difference between \(y_n\) and \(y_{n+1}\). Another option is to measure the difference between \(y_n^2\) and \(x\). When either of these is “small enough”, the algorithm has converged and we’re done.

Let’s implement our own DIY sqrt function called diy_sqrt using this technique.

Solution to diy_sqrt(x)

TOLERANCE = 1e-12 # scientific notation for 10 ** (-12)
def diy_sqrt(x):
  """
  Calculates the square root of some number x using Heron's method.

  Args:
    x: number to calculate the square root of. MUST BE >= 0.

  Returns:
    Square-root of x.
  """
  y_n = x
  while abs(y_n * y_n - x) > TOLERANCE:
    y_n = 0.5 * (y_n + x / y_n)
  return y_n

Another iterative method for computing the square-root of a number is known as the Bakhshali method and here is a possible implementation: