1 06-Loops

Previous: 05-Branches.html

Q: **How did the programmer die in the shower?**
A: **The shampoo bottle instructions said: **
   **Lather. Rinse. Repeat.**

**Ask**: What is the above construct?

1.1 Screencasts

Password for the Vimeo videos is in Zulip chat.
https://vimeo.com/510882133
Tip: If anyone want to speed up the lecture videos a little, inspect the page, go to the browser console, and paste this in:
document.querySelector('video').playbackRate = 1.2

1.2 Reading

Extra reading 1:
* http://scipy-lectures.org/intro/language/control_flow.html
* https://automatetheboringstuff.com/2e/chapter2/
* https://books.trinket.io/pfe/05-iterations.html
* https://docs.python.org/3/tutorial/controlflow.html#for-statements
* https://inventwithpython.com/invent4thed/chapter3.html
* http://inventwithpython.com/invent4thed/chapter5.html
* https://python.swaroopch.com/control_flow.html
* https://www.learnpython.org/en/Loops
* https://www.python-course.eu/python3_loops.php
* https://www.python-course.eu/python3_for_loop.php
* https://www.tutorialspoint.com/python3/python_loops.htm

1.3 Control flow part 2: loops

Branching was the first major part of control flow, and loops are the second major part:
https://en.wikipedia.org/wiki/Control_flow#Loops

1.4 Loops: general intro

Loops and computation
* Being able to repeat an operation of any kind is the last capability that we need to complete a fully functional toolbox for computing!
* A loop lets you repeat a block of code (a.k.a, the loop body), and each repetition is known as an iteration.
* In every programming language there are structures for repetition (mostly looping, but also recursion).
* In general, there are two kinds of loops:
1. sentinel loop has a sentinel value that triggers the termination of the looping, and are preferred when you don’t know how many iterations the problem will take.
2. counting loops are used when you know a-priori how many times you wish the loop body to repeat.

There are two primary sentinel loops:
1. while loop
2. do-while loop
There is one primary counting loop, with several variations:
1. for loop
  - C-style
  - for-each style

General loop:
06-Loops/loop_architecture.png

General loop
06-Loops/loop_control.png

1.4.1 Loop control variable

Reminder: Variable re-assignment
It is possible to make more than one assignment to the same variable.
~~~
x = 5 # 5
x = 7 # 7
x = x + 1 # 8
~~~

A new assignment makes an existing variable refer to a new value (object), and stop referring to the old value (object).
The old object may be garbage collected (deleted), if there was only one variable referencing it, which is then gone.

In every loop, sentinel or counting, there is in some form of a Loop Control Variable (LCV).
There are also statement(s) to perform the following actions:
1. initialize the LCV
2. evaluate/check value of LCV
3. update the LCV
  If any of these three components are left out of your code for the loop, then you run the risk of having a loop that either:
does nothing, or
does something far more loopy, an “infinite loop”!

Note:
* In python and other languages, while loops handle LCVs explicitly
* In python, for-each loops handle LCVs implicitly.
* In other languages, C-style for loops manage LCVs explicitly.

++++++++++++++++
Cahoot-06.1
https://mst.instructure.com/courses/58101/quizzes/55535

1.4.2 Infinite loops

https://en.wikipedia.org/wiki/Infinite_loop
(in any language)

An infinite loop (or endless loop) is a sequence of instructions in a computer program which loops endlessly, either due to:
1. the loop having no terminating condition,
2. having a termination condition that can never be met, or
3. code that causes the loop to start over.
If you find yourself with an infinite loop in Linux/Unix/MacOS, key in ctrl-c (push the 'ctrl’ and 'c’ buttons simultaneously).
- This will usually kill the process (at the Linux command line).
General ways to exit a loop include methods like:
- loop test statement (natural exit)
- return statement
- break statement
- exit statement
- goto statement
- an exception being thrown
- the user killing the program (ctrl-c)
- More on some of these to come later!
Sometimes we write infinite loops on purpose??
- Programs that run until the user decides to stop them sometimes intentionally use an infinite loop along with a return, break, or exit statement to terminate the loop.
- It is common to see this kind of infinite loop in web-server applications that run continuously, with the purpose of servicing web requests.

++++++++++++++++
Cahoot-06.2
https://mst.instructure.com/courses/58101/quizzes/55536

1.4.3 Exiting loops early

In most languages we can exit a loop early.

1.4.3.1 break

Some languages provides the break statement to implement middle-exiting control logic.
The break statement causes the immediate exit from the body of the loop.
When a program’s execution encounters a break statement inside a loop, it skips the rest of the body of the loop and exits the loop.

1.4.3.2 continue

The continue statement is similar to the break statement, except the continue statement does not necessarily exit the loop.
The continue statement skips the rest of the body of the loop, and immediately checks the loop’s condition.
If the loop’s condition remains true, then the loop’s execution resumes at the top of the loop.

1.4.3.3 return

In many languages, return statements can be anywhere, rather than just at the end of a function (more to come later when we cover functions).

1.4.4 How to debug loops

One way to debug an infinite loop (or other potentially bad code) is to place simple output messages in your code at appropriate places.
- Where is an appropriate place??
First, try to reason how much of the code is being executed before the problem occurs.
Then around where you think the error is, insert statements like this, often INSIDE a loop:

x = 0
y = 0
while x < 10 and y != 37:
    print("Loop control variable values are")
    print(x, y)
    x = x + 1
    y = y + 1
    # The rest of your code here

If that message is displayed to the screen, you know the problem is after that point in the code.
Keep doing this until you have narrowed it down.
Printing the LCV can help you determine the iteration on which your problem exists.

1.4.5 While loop

https://en.wikipedia.org/wiki/While_loop
06-Loops/while_loop.png

The syntax for the while is:
~~~
while expression
statement(s)
~~~

The while-loop simply repeats statement(s) while ‘expression’ is true.
Under the while expression (in Python), the sequence of statements to be executed is tabbed over 4 spaces.
- In other languages, scope is indicated differently, often using brackets.
After every execution of loop body, the expression condition is checked, and if it is found to be True, then the loop body is executed again.
When/if condition check comes out to be False, the loop body will not be executed.

Requirements
* while is a reserved word.
* ‘condition’ is any valid expression that evaluates to True or False or a numerical value (which True and False are in python).
* can be a simple or compound expression
* A while loop is a pre-test loop, which means that the condition in expression is checked before the body of the while loop (statement) might possibly be executed.
* This implies that the body of the loop might never be executed, if the expression were false before the loop.

Evaluation
1. expression is evaluated.
2. If it is true, the body (statement) is executed, and control passes back up to expression to be evaluated again.
3. If it is false, control passes out of the loop statement.

Loop control variables
* To execute a certain number of times, use a loop variable, often called a counter.
* A loop variable is usually an integer variable that is declared for the sole purpose of counting how many times a loop has executed.
* Loop variables are often given simple names, such as i or j.
* i and j are easily confusible, especially in small font sizes.
* I’ve spent hours assuming i was j, the only bug in a big program…
* If you want to know where in your program a loop variable is used, and you use the search function on i or j, the search function will return half your program! Many words have an i or j in them.
* Consequently, a better idea is to use “iii”, “jjj”, or even better, “thing_counter” as your loop variable names.
* Because these names are more unique, this makes searching for loop variables much easier, and helps them stand out as loop variables.
* You may often want to ctrl-f for these loop control variables.
* If you don’t name them uniquely, then it makes your loop ctrl-f’ing awful…

Scope
* Each time a loop executes, it is called an iteration.
* In many languages, because the loop body is typically a block, and because that block is entered and exited with each iteration, any variables declared inside the loop body are created and then destroyed with each iteration.

1.4.6 Do while loop

https://en.wikipedia.org/wiki/Do_while_loop (not in Python)

If the while loop condition is initially false, the body of the loop will not execute at all.
We may want a loop to execute at least once, such as when displaying a menu.
A do-while loop is similar to a while loop, except that a do-while loop is guaranteed to execute at least one time.
- Ultimately, we can do this with a while or for loop too, but it’s just convenience.
The do-while loop is usually preferred over a while-loop when the statement needs to be executed at least once, such as when the condition that is checked to end the loop is determined within the loop statement itself.

1.4.6.1 Diagram

1.4.6.2 Syntax

do statement evaluates the body of the loop first, and at the end, the condition is checked using while statement.
General format of do-while loop is

do
   statement(s)
while condition

1.4.7 For loop

https://en.wikipedia.org/wiki/For_loop

1.4.7.1 Diagrams

General
06-Loops/for1.png

1.4.7.2 Syntax

For loop is used to execute a set of statement(s) repeatedly until a particular condition is satisfied.
Like the while-loop, this loop repeats statement while condition is true.
It is useful to use counter variables as a condition.

1.4.7.2.1 For each loop (Python)

https://en.wikipedia.org/wiki/Foreach_loop
~~~
for item in iterable_container_of_items
statement(s) optionally including access to item
~~~

1.4.7.2.2 C-style (not Python)

for initialize(s); condition; increment(s)/decrement(s)
   statement(s)

for is a reserved word.
statement is a valid simple or compound C++ statement.
field 1 initializes the LCV.
field 2 checks the LCV.
field 3 updates the LCV.
exactly two semicolons, one after initialization and second after condition.

Sequence of operations
A for statement is evaluated in 3 parts (ORDER MATTERS!)
1. The init-statement is evaluated.
* Typically, the init-statement consists of variable definitions and initialization.
* This statement is only evaluated once, when the loop is first executed.
2. The condition-expression is evaluated.
* If this evaluates to false, the loop terminates immediately.
* If this evaluates to true, the statement is executed.
3. After the statement is executed, the end-expression is evaluated.
* Typically, this expression is used to increment or decrement the variables declared in the init-statement.
* After the end-expression has been evaluated, the loop returns to step 2.

1.4.8 Nested loops

Loops of any kind can be arbitrarily nested
~~~
while expression:
while expression:
for initialize(s); condition; increment(s)/decrement(s)
statement(s)
~~~

Ask: How deep can we nest?
Many programming languages allow hundreds of levels
Python is 20…

++++++++++++++++
Cahoot-06.3
https://mst.instructure.com/courses/58101/quizzes/55537

1.5 Python loops

1.5.1 While

General
~~~
while [condexpr]:
[substatements]
~~~

Example while loop:
06-Loops/loops_00_while_pos.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

user_input: int = int(input())

while 0 < user_input:
    print(user_input)
    user_input = int(input())

Tracing code is very helpful for learning loops (especially c-style for, when you get there later).
Use programmatic debuggers that can step through code (C++: cgdb, Python3: pudb, etc.)!!!

06-Loops/loops_01_squared.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# A while loop construct executes its sub-statements
# while its condition is true.
# Below, while x > 0, the loop outputs x’s square.
# input array should end in -1

user_input: int = int(input())

while 0 < user_input:
    x_squared = user_input * user_input
    # Could also do this:
    # xSquared *= x
    print(x_squared)
    user_input = int(input())V

1.5.2 For

for item in iterable:
    [substatements]

Example for-each loop:
06-Loops/loops_02_for_each.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# A for loop construct iterates a specified number
# of times. The below for loop iterates with
# counter being 0, 1, 2, 3, then 4.

for counter in [0, 1, 2, 3, 4]:
    print(counter)

range() generates an iterable sequence of numbers:
06-Loops/loops_03_range.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# A for loop construct iterates a specified number
# of times. The below for loop iterates with
# counter being 0, 1, 2, 3, then 4.

for counter in range(0, 5):
    print(counter)

1.6 Example problems

1.6.1 Exponentiation

https://en.wikipedia.org/wiki/Exponentiation
This is a very common operation in computer science, particularly with powers of 2!
Why?

06-Loops/loops_04_exponents.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

print("Enter base, hit enter, then exponent")
base: int = int(input())
exponent: int = int(input())
total: int = 1

for counter in range(0, exponent):
    total = total * base

print("Base ", base)
print(" to the power of ", exponent)
print(" is ", total)

06-Loops/loops_04_exponents_cfg.svg
Ask:
* For input of 0, how many times does the loop execute?
* For input of 1, how many times does the loop execute?
* For input of 2, how many times does the loop execute?
* For input of 3, how many times does the loop execute?
* ….
* For input of n, how many times does the loop execute?

Mention: that n+1 idea is the basis of algorithm analysis.

1.6.2 Prime numbers

https://en.wikipedia.org/wiki/Prime_number
https://en.wikipedia.org/wiki/Primality_test
https://en.wikipedia.org/wiki/Trial_division
http://inventwithpython.com/cracking/chapter22.html

A prime number is an integer greater than one, whose only factors (also called divisors), are one and itself.
For example, 29 is a prime number (only 1 and 29 divide into it with no remainder), but 28 is not (2, 4, 7, and 14 are factors of 28).
Prime numbers were once merely an intellectual curiosity of mathematicians, but now they play an important role in cryptography and computer security.

The simplest primality test is trial division:
* Given an input number n, check whether any prime integer m, from 2 to sqrt(n) evenly divides n (the division leaves no remainder).
* If n is divisible by any m, then n is composite, otherwise it is prime.
* For example, to test the primality of 100 by trial division, consider all the integer divisors of 100:
2, 4, 5, 10, 20, 25, 50

The possible largest factor is 100 / 2 = 50.
This is true for all n:
- all divisors are necessarily less than or equal to n / 2.
Inspecting the divisors, it is determined that some of them are redundant.
The list of divisors may be written as:
100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2
which demonstrates the redundancy.
There are inefficiencies in the below primality test/enumeration program.
What could be improved to speed it up?
06-Loops/loops_05_trial_division.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# smallest prime is 2, how odd...
value: int = 2

max_value: int = int(input("Display primes up to what value?"))

while value <= max_value:
    is_prime: bool = True
    trial_factor: int = 2

    while trial_factor < value:
        if value % trial_factor == 0:
            is_prime = False
        trial_factor = trial_factor + 1

    if is_prime == True:
        print(value, " is prime")
    else:
        print(value, " is not prime")

    value = value + 1

06-Loops/loops_05_trial_division_cfg.svg
Ask:
* For input of 0, how many times does the loop execute?
* For input of 1, how many times does the loop execute?
* For input of 2, how many times does the loop execute?
* For input of 3, how many times does the loop execute?
* ….
* For input of n, how many times does the loop execute?

1.6.3 Practice

Think:
* What is the starting condition?
* What is the termination condition?
* Do changes happen before or after a print statement?

++++++++++++++++
Cahoot-06.4
https://mst.instructure.com/courses/58101/quizzes/55538

06-Loops/loops_06_binary_down.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

x: int = 256

while x != 0:
    x //= 2
    print(x)

06-Loops/loops_06_binary_down_cfg.svg
Ask:
* For x of 256, how many times does the loop execute?
* For input of 0, how many times does the loop execute?
* For input of 1, how many times does the loop execute?
* For input of 2, how many times does the loop execute?
* For input of 3, how many times does the loop execute?
* ….
* For input of n, how many times does the loop execute?

++++++++++++++++
Cahoot-06.5
https://mst.instructure.com/courses/58101/quizzes/55539

06-Loops/loops_07_binary_up.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

x: int = 0

while x < 256:
    x *= 2
    print(x)

06-Loops/loops_07_binary_up_cfg.svg
Ask:
* For a limit of 256, how many times does the loop execute?
* For input of 0, how many times does the loop execute?
* For input of 1, how many times does the loop execute?
* For input of 2, how many times does the loop execute?
* For input of 3, how many times does the loop execute?
* ….
* For input of n, how many times does the loop execute?

1.6.4 Caesar extended

Can we build in variable length message processing?
Last time, we did not have loops.
- Do they help us here?
We can now translate a whole word with one run of the program, though just one character at a time, which is not as user-friendly as it could potentially be.

1.6.4.1 Key generation (correct)

06-Loops/loops_09_caesar_keygen.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import random

print("Your randomly chosen Caesar cipher key is: ")
print(random.randint(1, 25))
print("\n Share securily with your communication partner, and don't tell anyone else\n")

1.6.4.2 Encryption and decryption (bug fixed, missing features)

Can be programmed with a for loop: 06-Loops/loops_09_caesar_for.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

key: int = int(input("\nEnter your Caesar key in numeric form (1-25): "))
mode: int = int(input("\nEnter 1 for encryption, and 0 for decryption: "))

length: int = int(input("Enter the number of characters in your message: "))
for counter in range(0, length):
    character = int(
        input("\nEnter the Caesar encoding of the next character to translate: ")
    )
    print("\tYour letter translated to:")
    # Does using a loop help here? If yes, why? If no, why?
    if mode == 1:
        # 26 is the symbol set size (# letters in alphabet)
        print("\t", (character + key) % 26)
    else:
        print("\t", (character - key) % 26)

print("\nend of Caesar encoded message\n")

06-Loops/loops_09_caesar_for_cfg.svg
Ask:
* For input of 0, how many times does the loop execute?
* For input of 1, how many times does the loop execute?
* For input of 2, how many times does the loop execute?
* For input of 3, how many times does the loop execute?
* ….
* For input of n, how many times does the loop execute?

Can also be programmed with a while loop: 06-Loops/loops_10_caesar_while.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

key: int = int(input("\nEnter your Caesar key in numeric form (1-25): "))
mode: int = int(input("\nEnter 1 for encryption, and 0 for decryption: "))

character: int = int(
    input("\nEnter the Caesar encoding of the first character of your message: ")
)
while character != -1:
    print("\tYour letter translated to:")
    # Does using a loop help here? If yes, why? If no, why?
    if mode == 1:
        # 26 is the symbol set size (# letters in alphabet)
        print("\t", (character + key) % 26)
    else:
        print("\t", (character - key) % 26)
    character = int(
        input("\nEnter the Caesar encoded next character, or -1 for done: ")
    )

print("\nend of Caesar encoded message\n")

06-Loops/loops_10_caesar_while_cfg.svg
Ask:
* For input of 0, how many times does the loop execute?
* For input of 1, how many times does the loop execute?
* For input of 2, how many times does the loop execute?
* For input of 3, how many times does the loop execute?
* ….
* For input of n, how many times does the loop execute?

Ask:
* Which version was better?
* Which version was easier to understand?
* Was either more efficient?
* What remaining structure do we need to be able to enter a whole sentence at once, and then encrypt it to be printed out all at once?

What about bad users who don’t read, or make a typo?
Add a while loop to insist on ‘str’.isdigit() input!
06-Loops/loops_10_caesar_while_check.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

key: int = int(input("\nEnter your Caesar key in numeric form (1-25): "))
mode: int = int(input("\nEnter 1 for encryption, and 0 for decryption: "))

character_str: str = input(
    "\nEnter the Caesar encoding of the first character of your message: "
)

while not character_str.isnumeric():
    character_str = input(
        "\nEnter the Caesar encoded INTEGER corresponding to yoru next character: "
    )

character = int(character_str)

while True:
    print("\tYour letter translated to:")
    # Does using a loop help here? If yes, why? If no, why?
    if mode == 1:
        # 26 is the symbol set size (# letters in alphabet)
        print("\t", (character + key) % 26)
    else:
        print("\t", (character - key) % 26)

    character_str = input("\nEnter the Caesar encoded next character, or -1 for done: ")
    if character_str == "-1":
        break
    while not character_str.isnumeric():
        character_str = input(
            "\nEnter the Caesar encoded INTEGER corresponding to your next character: "
        )
    character = int(character_str)

print("\nend of Caesar encoded message\n")

06-Loops/loops_10_caesar_while_check_cfg.svg
Notice the while True and the break statement!

1.6.5 Guess the number game

We’ll start tracing games in python now, and continue with more complicated games as the semester progresses.
http://inventwithpython.com/invent4thed/chapter3.html

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# This is a Guess the Number game.
import random

number = random.randint(1, 20)
myName = input("Hello! What is your name? ")
print("Well, " + myName + ", I am thinking of a number between 1 and 20.")
print("You have 6 guesses before you lose!")
guessesTaken = 0

for guessesTaken in range(6):
    guess = int(input("Take a guess: "))
    if guess < number:
        print("Your guess is too low.")
    if guess > number:
        print("Your guess is too high.")
    if guess == number:
        break

if guess == number:
    guessesTaken = guessesTaken + 1
    print(
        "Good job, "
        + myName
        + "! You guessed my number in "
        + str(guessesTaken)
        + " guesses!"
    )
else:
    print("Nope. The number I was thinking of was " + str(number) + ".")

06-Loops/loops_11_guess_cfg.svg

Q: What is the most rational way to play this game, assuming a uniform distribution between 0 and n?
A: This will be an interesting search algorithm later on!

1.7 Language focus

To be stepped through in the python3-spyder IDE and/or python3-pudb debugger:
06-Loops/loops_12_overview.py

Next: 07-Containers.html