0. Preamble

Notebook Authors:

New book Algorithms: Competitive Programming, co-authored by Antonio, is just published! The book helps you prepare for your incoming programming contest or coding interview. This book contains detailed explanations and source code for algorithms used in competitive programing.

PRIZE: You can get a free digital copy if you get a final score of 85% in the exercises.

1. Review: While Loop

The while loop is used to make an indefinite iteration. That is, the loop repeats an unknown number of times apriori. A while loop ends when the condition for the while loop is false.

Note: a for loop iterates for a definite number of times. For example, for i in range(5) repeats 5 times.

Example: Finding the nearest square of a number.

Given an integer number limit, find the largest square number less than that integer limit. A square number is a number with a square root, that is, the product of an integer with itself.

For instance, 36 is a square number because 36 = 6 x 6.

40 # this is not a square number 49 = 7 * 7 # is a square number

limit = 40 number = 3 number * number

# Problem: how do we find the largest square number less than a limit? limit = 40 # Strategy: we try the square of every integer and stop when the square is greater than the limit number = 1 # TODO: while loop here while (number + 1) **2 < limit: number += 1 # get the result result = number * number print("The largest square number less than {} is {}.".format(limit, result))

2. Review: For Loop

When to use for loop vs while loop:

use for loop when the number of iterations is known or finite
use while loop when the iterations need to continue until a certain condition is met

For loops are used for definite iteration. That is, the loop body is run a predetermined number of times. In a while loop, however, the loop repeats an unknown number of times and ends only when some condition is met. This is called indefinite iteration.

For example, if you have an iterable (e.g. list, set, tuple, or dictionary), use for loop. If you want to use comparison operator to break the loop, consider using the while loop instead. For more information, see https://wiki.python.org/moin/WhileLoop

If we need more control over when a loop should be ended or skipped, we can use the break and continue keywords, respectively.

break terminates a loop
continue skips one iteration of a loop

number = 5 i = 4 if number %i == 0: print("{} is not a prime number because it is divisible by {}".format(number, i))

list(range(2, 6))

# Example: check for prime number # Prime numbers have only two multiplication factors: one and the number itself. # For example, 7 is a prime number because its multiplication factors are 7 and 1. # 6 is not a prime number because its multiplication factors are 1, 2, 3, and 6. # Given a number, we want to check if it is prime. number = 6 for i in range(2, number): if number % i == 0: # if the number is divisible by i, it is not a prime number print("{} is not a prime number because it is divisible by {}".format(number, i)) break if i == number - 1: print("{} is a prime number".format(number))

# now instead of checking a single number, I want you to check a list of numbers # check if the numbers below are prime or not number_list = [26, 39, 51, 53, 57, 79, 85] for number in number_list: # another outer loop for i in range(2, number): # the original loop is now an inner loop if number % i == 0: # if the number is divisible by i, it is not a prime number print("{} is not a prime number because it is divisible by {}".format(number, i)) break if i == number - 1: # if the number is not divisible by any number less than itself, it is a prime print("{} is a prime number".format(number))

3. Python Pro Tools for Looping

We will discuss two handy built-in functions and one trick to elegantly handle loops: zip, enumerate, and list comprehension.

zip returns an iterator that combines multiple iterables into one sequence of tuples. Each tuple contains the elements in that position from all the iterables.
enumerate returns an iterator of tuples containing indices and values of a list. You will find this useful when you need the index and value of each element of the iterable.

3.1 Zip

zip returns an iterator of tuples, combining multiple iterables that are given as arguments. zip can take mulitple arbitrary number of arguments.

Since the return value of zip is an iterator, you need to convert it to a list to see the values, or use it in a for loop.

# use case for zip letters = ['a', 'b', 'c'] numbers = [1, 2, 3] # how do we iterate through two iterables at once? # answer: zip print(list(zip(letters, numbers)))

letters = ['a', 'b', 'c'] numbers = [1, 2, 3]

for element in zip(letters, numbers): print(element[0], element[1])

for letter, number in zip(letters, numbers): print(letter, number)

# create a zipped element zipped = list(zip(letters, numbers)) print(zipped) zipped[1]

letters = [1, 2, 3] numbers = ['a', 'b', 'c'] booleans = [True, False, True] print(list(zip(letters, numbers, booleans))) letter, number, boolean = list(zip(letters, numbers, booleans))[1] # tuple unpacking boolean

# create a zipped element zipped = list(zip(letters, numbers)) print(zipped) numbers, letters = list(zip(zipped[0], zipped[1], zipped[2]))

letters

# create a zipped element zipped = list(zip(letters, numbers)) print(zipped) # list is a zip # we now pass the list, with each element as an argument letters_unzipped, numbers_unzipped = zip(*zipped) print(letters_unzipped, numbers_unzipped)

set1 = {1,2} set2 = {'a', 'b'} list(zip(set1, set2))

3.2 Enumerate

Use enumerate if you want to iterate through an iterator along with the index. That is, at each iteration you want to get not just the element of the iterable but also the index of that element.

# lets say we have a list letters = ['a', 'b', 'c', 'd'] # METHOD 1: to get the index and value of the element at each iteration # by using a dummy variable index = 0 ## DEMO: for loop here for letter in letters: print(index, letter) index += 1

# lets say we have a list letters = ['a', 'b', 'c', 'd'] # METHOD 2: to get the index and value of the element at each iteration # by using zip and range for i, letter in zip(range(len(letters)), letters): print(i, letter)

# now lets say we have a list letters = ['a', 'b', 'c', 'd'] # METHOD 3: to get the index and value of the element at each iteration # by using enumerate for (i, letter) in enumerate(letters): print(i, letter)

# Example 1: use zip to label coordinates (physics) # Given the x, y, and z coordinates of points and the corresponding labels, # use zip to print and label the coordinates as so: # label: x, y, z x_coord = [23, 53, 2, -12, 95, 103, 14, -5] y_coord = [677, 233, 405, 433, 905, 376, 432, 445] z_coord = [4, 16, -6, -42, 3, -6, 23, -1] labels = ["F", "J", "A", "Q", "Y", "B", "W", "X"] # for example, the first coordinate should be printed as # F: 23, 677, 4 points = [] for x, y, z, label in zip(x_coord, y_coord, z_coord, labels): points.append("{}: {}, {}, {}".format(label, x, y, z)) for point in points: print(point)

list(enumerate(zip(x_coord, y_coord)))

# Example 2.1: use zip to create a dictionary # Given the names of movie stars and their heights, create a dictionary called cast # the keys of cast are the names of the movie stars # the values of cast are the heights names = ["Andy", "Bobby", "Cindy", "Deborah"] heights = [184, 177, 168, 172] cast = dict(zip(names, heights)) print(cast)

cast.items()

# Example 2.2: unzip the cast into names and heights names_unzipped, heights_unzipped = zip(*cast.items()) print(names_unzipped) print(heights_unzipped)

# Example 2.3: transform a tuple from a 4x3 matrix to a 3x4 matrix data = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11)) data_transpose = tuple(zip(*data)) print(data_transpose)

%run -i students.py

Exercise 0

Given these two lists

cast = ["Andy", "Bobby", "Cindy", "Deborah"]
heights = [184, 177, 168, 172]

Create a new list, using zip or enumerate, such that the elements in the new list are strings containing name of the cast and his/her height separated by colon as follows.

['Andy: 184', 'Bobby: 177', 'Cindy: 168', 'Deborah: 172']

# Exercise 2.4: modify the cast list so that each element contains the name and height of the movie star # For example, the first element of cast should change from "Andy" to "Andy: 184" cast = ["Andy", "Bobby", "Cindy", "Deborah"] heights = [184, 177, 168, 172] # Solution 1: using enumerate to directly change the original list

for name, height in zip(names, heights): print(name + ': ' + str(height))

# Exercise 2.5: create a cast list so that each element contains the name and height of the movie star # For example, the first element of cast should change from "Andy" to "Andy: 184" names = ["Andy", "Bobby", "Cindy", "Deborah"] heights = [184, 177, 168, 172] cast = [] # Solution 2: append to a new list by iterating with zip for names, height in zip(names, heights): cast.append(name + ": " + str(height)) print(cast)

Exercise 1

Task: Sum the first five odd numbers.

Given a list, find the arithmetic sum of the first five odd numbers in the list. As you go through each number in the list, you have to check if it's even or odd.

# Exercise 1: sum the first five odd numbers # You can use either a while loop or a for loop # Here is the list of numbers num_list = [422, 136, 524, 85, 96, 719, 85, 92, 10, 17, 312, 542, 87, 23, 86, 191, 116, 35, 173, 45, 149, 59, 84, 69, 113, 166]

num = num_list[0] odd5 = [] # check if it's odd if num % 2 != 0: odd5.append(num) print(odd5)

# Solution 1: using while loop # suggested variables (feel free to use or not use them) count_odd = 0 # to count till 5 sum_odd = 0 # where the sum is stored i = 0 # to iterate through the list # TODO: your while loop here

# Solution 2: using for loop sum_odd = [] # TODO: your for loop here

Exercise 2

Use a for loop to convert a list of strings into unordered (bulleted) list in HTML. For example, the list

items = ['Hello World', 'World Hello']

should be converted into a single string that prints

<ul>
<li>Hello World</li>
<li>I am the best</li>
</ul>

# Exercise 2: HTML List Generator items = ['Hello World', 'World Hello'] html_str = "<ul>\n<li>Hello World</li>\n<li>I am the best</li>\n</ul>" print(html_str)

item = items[0] html_str = "<ul>\n" html_str += "<li>" + item + "</li>\n" print(html_str)

# Try your solution here!

Exercise 3

Task: use a while/for loop to compute the factorial of a number

The factorial of a number is the product of all whole numbers between itself and one. For example, 4! = 4 x 3 x 2 x 1 = 24

HINT:

if using a for loop, you can use the range function to create the iterable
if using a while loop, you can decrement the number by 1 as long as it's greater than 1

number = 4 number * (number - 1) * (number - 2) * (number - 3)

# SOLUTION 1: WHILE LOOP # number to find the factorial of number = 4 # 24 number = 5 #120 number = 6 #720 # start with our product equal to one product = 1 # track the current number being multiplied current = 1 # TODO: write your while loop here # print the factorial of number print("The factorial of {} is: {}".format(number, product))

# SOLUTION 2: FOR LOOP # number to find the factorial of number = 6 # start with our product equal to one product = 1 # write your for loop here

# Exercise 4: news ticker

# Exercise 5: fruits in a basket