#!/usr/bin/env python
# coding: utf-8

# # An Introduction to Programming in Python
# 
# 
# ## 1. Introduction
# 
# In AddisCoder, we are learning to write code. **Code** is instructions for the computer: you write code to tell the computer what to do. Just like people talk in many languages, there are many languages you can use to talk to the computer. The language we will learn here at AddisCoder is called "Python". **Python** is a popular **programming language** used around the world by many people. You can write Python code to create almost anything you want, including online shopping websites, video games, medical data analysis tools, and more!
# 
# 
# 
# ## 2. Jupyter Notebook 
# 
# We will be using **Jupyter Notebook** throughout this course. Jupyter Notebook is a computer program that lets you write some Python code (write some instructions for the computer), **run** it (order the computer to follow your instructions), and then see the **output** (the result of your instructions).
# 
# Jupyter notebooks are organized into **cells**, which are boxes. Here is a cell with code that computes the amount in a bank account that has $4\%$ interest compounded monthly, if you put in 10,000 birr and wait 5 years or 10 years (don't worry if the code makes no sense to you right now):

# In[1]:


def compound_interest(P, r, n, t):
    return P * (1 + r/n) ** (n*t)

principal = 10000  # birr
print("Amount in account after 5 years:",
      compound_interest(principal, r=0.04, n=12, t=5))
print("Amount in account after 10 years:",
      compound_interest(principal, r=0.04, n=12, t=10))


# The grey box is where you can write the code that you want the computer to execute. Then you can **run** the cell (by pressing `CTRL+ENTER` or `SHIFT+ENTER`) to order to computer to follow the instructions in your code. After the computer executes your code, it will show any outputs (anything you _print_ ) in the space under the cell.

# ## 3. Basic Math
# 
# A computer is like a big and powerful calculator that can do many complicated calculations very fast. Let's learn how to tell the computer to do some math in Python!

# In[2]:


2 + 4


# In[3]:


9 - 1


# In[4]:


10 - 100


# Easy right? You can write simple math problems and tell the computer to solve them. When you run each cell, the computer will show the output right below it.
# 
# Now let's try multiplication and division. But the keyboard doesn't have the muliplication ($\times$) or division ($\div$) symbols! We need to use `*` (called asterisk) for multiplication and `/` (called slash) for division instead:

# In[5]:


5 * 7


# In[6]:


81 / 9


# In[7]:


5 / 2


# Sometimes it's also useful to compute a quotient without any decimal places. For example, what if we want to compute:
# 
# $$56 \div 9 = 6 \text{ R } 2$$
# 
# The quotient without any decimal places is $6$, and the remainder is $2$. We can do this in Python using `//` and `%`:

# In[8]:


56 // 9


# In[9]:


56 % 9


# The `//` operator is called the "floor division" operator, because we compute the quotient then compute its floor. (The floor of a number is the largest integer smaller than that number.)
# 
# The `%` operator is called the "modulo" operator. It divides the first number by the second, and gives the remainder. As you will see in examples later on, this operator is especially useful for checking if one number if divisible by another.
# 
# One more operator that might be useful is `**`, which is for exponentiation. For example, to compute
# 
# $$ 5^3 $$
# 
# we can write:

# In[10]:


5 ** 3


# ### 3.1 Order of operations
# 
# You can also give Python some more complicated math problems. For example, let's say you put 3000 birr into a bank account account, which has an annual interest rate of $4\%$. After 5 years, the bank account should have:
# 
# $$ 3000 ( 1 + (0.04 \times 5) ) = 3600 \text{ birr} $$
# 
# To tell the computer to compute it for you, you can write this code:

# In[11]:


3000 * (1 + 0.04 * 5)


# Notice that you can use **parentheses** `()` to tell the computer to calculate what's inside them first, just like in math. Python will also follow normal order of operations in math. For example, if we remove the parentheses in this code:

# In[12]:


3000 * 1 + 0.04 * 5


# The order of operations in Python is:
# 
# 1. Parentheses `()`
# 2. Exponent `**`
# 3. Multiplication `*` and Division `/` `//` `%`, left to right
# 4. Addition `+` and Subtraction `-`, left to right
# 
# Note that multiplication and division have _equal_ precedence. They are simply executed from left to right. For example, this code:

# In[13]:


4 % 10 * 6 / 2 * 9 // 4


# has the same result as this code:

# In[14]:


(((((4 % 10) * 6) / 2) * 9) // 4)


# Addition and subtraction also have equal precedence.

# ## 4. Printing
# 
# In the real world, a printer is a machine that can put words and pictures on paper. In computer programming, "printing" just means showing something on the screen. To print a number on the screen, we can write something like this:

# In[15]:


print(13)


# You can see that we wrote the word `print`, and then wrote some **parentheses** (the round brackets around these words), and then put what we wanted to print _between_ the parentheses.
# 
# ### 4.1 A Note about Printing in Jupyter
# 
# You might notice that sometimes you see a value displayed on the screen even though you didn't `print` it:

# In[16]:


169


# This is because Jupyter Notebook automatically prints the value of the last line of the cell for you. If you have multiple lines of code in one cell, it will only print the value of the last one, unless you `print` it:

# In[17]:


1
2
3
4


# In[18]:


print(1)
2
3
4


# ## 5. Variables

# To write more complicated programs, sometimes you need to tell the computer to remember some things. In programming, a **variable** is a container that can hold any value. Variables in Python are very similar to variables in math, but not exactly the same. For example, in math we can have:
# 
# $$ x = 10 $$
# $$ y = 7 x + 4 $$
# 
# What would $y$ be?
# 
# $$ y = 7 (10) + 4 = 74 $$
# 
# We can try the same thing in code:

# In[19]:


x = 10
y = 7 * x + 4
print(y)


# It works perfectly. But how do you explain this code?

# In[20]:


x = 10
x = x + 1
print(x)


# This makes no sense in mathematics! This equation 
# 
# $$ x = x + 1 $$
# 
# is not valid -- it is be impossible to solve for $x$. But the code worked, because variables work differently in code than in math in a few major ways:
# 
# 1. **Variables in code can change value.** Variables in math cannot change value in the same set of equations.
# 2. **The equals sign `=` in code does NOT mean equals.** It means "**assign** the value on the right side to the variable on the left side".
# 3. **Code is excecuted one line at a time.** It matters which line is above another.
# 
# For example, this code:
# 
# ```python
# x = 10
# x = x + 1
# ```
# 
# means "put the value 10 inside the variable `x`, and then add `1` to the current value of `x` (which gives `11`), and put that new value inside the variable `x`." Notice that when you assign a new value to a variable, the old value is forgotten.
# 
# Here are some more examples:

# In[21]:


x = 5
print("x at first contains the value: ", x)
x = 10
print("x now contains a new value: ", x)


# Variables can change the values that they hold as shown above. Variables can also interact with other variables.

# In[22]:


y = 15
z = 20
print("y plus z is equal to: ", y + z)
print("y times z is equal to: ", y * z)
print("y divided by z is equal to: ", y/z)


# But notice that not all interactions are allowed in Python. In the code below, we try to add variables `a` and `b`, but we get an error. The error is due to a **type** mismatch in our addition: we try to add a container `a` holding an *integer* value with a container `b` holding a *string* (text) value. So it seems that variables that serve as containers for values must follow specific rules when interacting with other variables of different types.

# In[23]:


a = 15
b = "16"
print(a + b)


# ### 5.1 Variable names
# 
# Variables can have almost any name, not just `x` or `y`. A variable name can be any combination of letters (`A-Z`, uppercase or lowercase), digits (`0-9`), or underscores (`_`), as long as the name does NOT start with a digit.

# In[24]:


very_long_variable_name_123 = 12
print(very_long_variable_name_123)


# In[25]:


007agent = "james bond"


# ## 6. Comments
# 
# Sometimes we want to include some notes in our code for ourselves, or for other people to read. We can writes notes by using the pound sign `#`:

# In[26]:


pi = 3.141559  # I don't know all the digits of pi :(
# I have a circle that is 3 centimeters wide.
diameter = 3
# Compute the area and also the circumference.
r = diameter / 2  # radius
area = pi * r * r
circumference = pi * diameter 
# Display the results on the screen.
print("Area is:", area)
print("Circumference is:", circumference)


# Everything one the line that is on the _right_ of the pound sign `#` is _ignored_ by the computer. These notes are called **comments**. Comments are just for other humans to read, and are usually written to help explain what the code is doing, and why you wrote the code that way.

# ## 7. Strings
# 
# In Python, we can work with more than just numbers. We can also write code that manipulates text. To create a text value, we use quotation marks `"`. For example, we can print `Selam!` by writing this:

# In[27]:


print("Selam!")


# We can also use single quotation marks `'`:

# In[28]:


print('Selam!')


# Both ways of writing strings are exactly the same -- you should just pick the way you like the most.
# 
# What would happen if we don't use quotation marks?

# In[29]:


print(Selam)


# When we don't use quotation marks here, the computer tries to look for a _variable_ named `Selam`. But since we didn't create such a variable, the code fails and gives us an error message.
# 
# Sometimes it is useful to print multiple values on the same line. You can do that by separating the different values with commas.

# In[30]:


age = 25
print('Hello, I am', age, 'years old.')


# If you just use `print` multiple times, each value will be on its own line instead:

# In[31]:


age = 25
print('Hello, I am')
print(age)
print('years old.')


# ## 8. Types

# So far, we have learned that as programmers, we write code, and each line of code we write corresponds to a an instruction for the computer. Instructions to the computer must be specific and must follow the rules of our language (which is Python in our case). **Types** are the different categories of values that the computer understands. Each **type** has its own characteristics and interacts with other **types** according to specific rules. For example, we saw earlier that we could not add an integer variable with a string variable.
# 
# Here are the basic types in Python that you should know about:
# 
# - **int**: an integer.
# - **float**: a decimal number.
# - **string**: a sequence of text characters, including letters, numbers, spaces, and more.
# - **list**: a sequence of items, which can be any value (we will learn more about these later)
# - **boolean**: either `True` or `False`
# - **dict**: a mapping from keys to values (we will learn more about these later)
#   
# Variables contain a value, so imagine a variable as a cup that contains something. However, we use different types of cups for different beverages; coffee cups are different from water cups, which are different from tea cups. Imagine types as giving a cup, or a variable, the unique type. By assigning an integer value to a variable, we give our cup a more specific purpose.
#   
# Let's look at examples of how different types interact with each other in Python.

# In[32]:


print(type(15))


# In[33]:


print(type(15.5))


# In[34]:


print(type(True))


# In[35]:


print(type("fifteen"))


# In[36]:


print(type(None))


# In[37]:


print(type([15, 15.5, True, "fifteen", None]))


# In[38]:


print(type({"egg": 15, "onion": 15.5, "chicken": "fifteen", "water": True}))


# In[39]:


print(15 + 15.5)


# In[40]:


print(15 + "15")


# ### 8.1 Casting between types
# 
# If you write parentheses after the name of a type, you can sometimes ask the computer to convert one type into another.

# In[41]:


print(15 + int("15"))


# In[42]:


print(str(15) + "fifteen")


# ## 9 Lists and Indexing

# A **list** in Python is just a list of values. You can create a list by using square brackets `[]` and separating the values with commas `,`:

# In[43]:


my_list = [1,3,5,7,9]


# You can print a whole list, or you can get a single value out of a list by using the square brackets again `[]`, and placing the position of the value that you want to get between brackets:

# In[44]:


print(my_list)
print(my_list[2])


# Wait, but we asked for the value at position `2`, why did it print `5`? Clearly, `5` is in the third position.
# 
# This is because the position numbers, which we call **indexes** or **indices**, for items in lists start with `0`, instead of `1`. So to print all of the items in `my_list` one by one, we have to write:

# In[45]:


my_list = [1,3,5,7,9]
print(my_list[0])
print(my_list[1])
print(my_list[2])
print(my_list[3])
print(my_list[4])


# Also notice that if we try to get an element with an index that is out of the range of possible indices for a list, we get an error.

# In[46]:


print(my_list[5])


# Python also allows us to use negative indices, which count from the back of the list.

# In[47]:


print(my_list[-1])
print(my_list[-2])
print(my_list[-3])
print(my_list[-4])
print(my_list[-5])


# It is worth noting that lists can contain values of _any_ type, even within one list:

# In[48]:


print([15, 15.5, True, "fifteen", None])


# ### 9.1 String indexing
# 
# All the rules above apply to strings as well. Strings are just like lists, but each item is a letter or character.

# In[49]:


my_string = "hello"


# In[50]:


print(my_string[0])
print(my_string[1])
print(my_string[2])
print(my_string[3])
print(my_string[4])


# In[51]:


print(my_string[-1])
print(my_string[-2])
print(my_string[-3])
print(my_string[-4])
print(my_string[-5])


# ### 9.2 Slicing
# 
# We can also access more than one elements of a list or a string using Python's **slicing** rules.
# ```
# var[start:stop:step] # start through not past stop, by step
# ```

# Remeber the three "s" when using slicing.  
#   
# `start`: the index at which you want to start accessing, includes the item at start index  
#   
# `stop`: the index at which you want to stop accessing, does NOT include the item at stop index  
#   
# `step`: the steps to take for each element in the range defined by start and stop  
#   
# If one does not specify start, then Python will by default start accessing from the beginning of the list or the string. Similarly, if one does not specify stop, then Python wil by default stop accesing before the end of the list or the string.  

# In[52]:


print(my_string[:])
print(my_string[1:])
print(my_string[:-2])
print(my_string[1:-1:2])


# ## 10. Booleans
# 
# A **boolean** value represents whether something is true or not. There are only two possible boolean values in Python: `True` or `False`. **Notice that both `True` and `False` are capitalized!** The computer will not understand if you just write `true` or `false`.
# 
# The type of a boolean value is called `bool`.

# In[53]:


type(True)


# In[54]:


type(False)


# ### 10.1 Boolean expressions
# 
# A boolean expression is a snippet of code that evaluates to either `True` or `False`.
# For example, the operator `==` tests if two values are equal. It results in a boolean value:

# In[55]:


10 == 10


# In[56]:


a = [1, 3]
a == [3]


# Here are some more boolean operators you can use:
# 
#  - `<` "less than"
#  - `>` "greater than"
#  - `<=` "less than or equal to"
#  - `>=` "greater than or equal to"
#  - `!=` "not equals"
#  - `==` "equals"

# In[57]:


x = 2
y = 4
z = 4
print(x > y)
print(x < y)
print(y == z)
print(y >= z)
print(y <= z)
print(y != z)


# There are three **logical operators**, `and`, `or` and `not` which help us build more complex boolean expression. 
# For example, `x > 0 and x < 10` produces `True` only when x is greater than 0 and x is less than 10.

# In[58]:


10 > 5 and 5 < 9


# In[59]:


10 < 4 or 10 < 5


# In[60]:


not True


# In[61]:


not 10 < 4


# ## 11. Dictionaries
# 
# A dictionary or `dict` in Python is an object that can store a mapping from "keys" to "values".
# 
# We can define a dictionary like this:
# 

# In[62]:


countryCapitals = {
    'Ethiopia': 'Addis Abada',
    'Canada': 'Ottawa',
    'Iran': 'Teheran',
    'Turkey': 'Ankara'
}


# This dictionary maps the names of each country (the key) to the name of its capital (the value). Once the dictionary is defined, we can get a value corresponding to a given key using square bracket notation:

# In[63]:


countryCapitals['Ethiopia']


# We can also replace entries or add new ones:

# In[64]:


countryCapitals['Ethiopia'] = 'Addis Ababa'
countryCapitals['Ethiopia']


# In[65]:


countryCapitals['Taiwan'] = 'Taipei'
countryCapitals['Taiwan']


# There are also a few useful methods (functions defined on objects) that give you the full list of keys, or the full list of values, or the number of entries.

# In[66]:


countryCapitals.keys()


# In[67]:


countryCapitals.values()


# In[68]:


len(countryCapitals)


# You can also check if a key exists in the dictionary using the `in` operator.

# In[69]:


'Iran' in countryCapitals


# In[70]:


'Iraq' in countryCapitals


# ## 12. Conditional Statements

# **Conditional statements** allow us as programmers to create a set of rules for our program to follow! Using conditional statements in our code is one of the most powerful tools that we can use to make our instructions to our computer EXACT; that is, IF an exact condition is met in the middle of our program, we can tell our computer to THEN execute a set of specific instructions. Let's take a look at this sentence.  
#   
# - **IF** a value is less than 10, **THEN** display the words "less than 10" on the screen. **OTHERWISE**, display the words "greater or equal to 10".  
#   
# Notice how in this sentence, we only display the words "less than 10" if the condition that a value is less than 10 is true! In Python, we can program this specific line of instruction as well as other instructions with conditions with `if`, `elif`, and `else` keywords. The general structure of conditional statements looks as follows.

# ```
# if <some condition_1 is true>:
#     <do something only when condition_1 is true>
# elif <some condition_2 is true>:
#     <do something only when condition_1 is false and condition_2 is true>
# else:
#     <do something when both condition_1 and condition_2 are false>
# ```

# Following the structure above, our earlier conditional statement would look as following in Python.

# In[71]:


x = 15
if (x < 10):
    print("less than 10")
else:
    print("greater or equal to 10")


# ## 13. Loops
# 
# Sometimes we need to write code to do the same thing many times. For example, if we have a list of numbers, and we want to print all of them, we could write this:
# 
# 

# In[72]:


l = [6, 1, 2, 7, 3]
print(l[0])
print(l[1])
print(l[2])
print(l[3])
print(l[4])


# But this is very painful. What if we ask you print a list of 1,000 numbers?
# 
# Instead, you can use **loops** to make this code easier to write. Loops allow you to write code that gets repeated many times. There are two kinds of loops: **while** loops and **for** loops.

# ### 13.1 `while` loops 
# 
# A `while` loop looks like this:
# 
# ```python
# while <condition>:
#     <statement 1>
#     <statement 2>
#     ...
# ```
# 
# (Anything inside the angle brackets `<>` means that you can choose your own.)
# 
# The magic word `while` will tell the computer to repeat the following indented statements as long as the condition is `True`. In other words, the computer will do this:
# 
# 1. Execute the code in the condition.
# 2. If the condition evaluates to `False`, then _skip_ all the indented code after the `while` word.
# 3. If the condition evaluates to `True`, then run all the indented code after the `while` word once. (Running through the code inside the loop once is called one **iteration**.)
# 4. After running all the statements, go back to **1**.
# 
# 
# **!!DANGER!!** You can break your computer with `while` loops! For example, what would happen if we ran this code?
# 
# ```python
# num = 0
# while True:
#     print(num)
#     num += 1
# ```
# 
# First we would see the computer print 0, 1, 2, 3, ... but then, it won't stop! Because the condition is _always_ `True`, The computer will keeping printing numbers forever until your computer breaks. This is called an **infinite** loop. If this ever happens to you, make sure to click on the **stop button** to tell the computer to stop. The stop button looks like a black square ($\blacksquare$) , and you can find it at the top of the notebook.
# 
# So how do we make sure that the loop stops? We need to make sure that eventually, the condition will be `False`, so that the loop can stop. For example, we can change the above code to look like this:
# 
# 

# In[73]:


num = 0
while num < 5:  # New condition
    print(num)
    num += 1
print("done!")


# Now the computer only prints 5 numbers until the loop finishes. But the condition was `num < 5`, why doesn't the computer also print `5`?
# 
# Remember that the computer checks the condition _before_ each iteration of the loop. So after printing the number `4`, the computer will add `1` to `num`, making it `5`. Then the computer will check the condition, and it sees that `5` is not less than `5`. So it stops the loop, and goes on to the code after the loop.

# #### Examples of `while` loops
# 
# Let's look at some useful examples of `while` loops. If we want to print all the numbers in a list one-by-one, we have to write this:

# In[74]:


lst = [6, 1, 2, 7, 3]
i = 0
while i < len(lst):
    print(lst[i])
    i += 1


# This is a very important pattern for you to remember. 
# 
# - **Initialize**: Since we want to print each number once, we need to create a variable `i` to keep track of the index in the list for us. We want to start at the beginning of the list, and the first index of a list is `0`, so we first assign `i = 0`.
# - **Increment**: At the end of each iteration, we add `i += 1` so that on the next iteration, we will be printing the next item in the list.
# - **Stop**: We want to stop when we've finished printing all the numbers in the list. So we write the condition `i < len(lst)`, which tells the computer to check that `i` is still a proper index in the list before trying to print `lst[i]` again.
# 
# What if we wanted to print the numbers of the list backwards? Then we can write this:

# In[75]:


lst = [6, 1, 2, 7, 3]
i = len(lst) - 1
while i >= 0:
    print(lst[i])
    i -= 1


# ### 13.2 `for` loops
# 
# Writing a `while` loop to go through a list can be a lot of work. You need to remember to _initizalize_ an index variable, then _increment_ it, and also to write a proper _stopping condition_. Is there an easier way?
# 
# A `for` loop can help you easily repeat some code once for each item in a list. Here is what a for loop looks like:
# 
# ```python
# for <name> in <list>:
#     <statement 1>
#     <statement 2>
#     ...
# ```
# 
# The magic word `for` will tell the computer to take each item in `l` and _assign_ it to the variable `x` and then run the indented code that comes after it. In other words, when the computer sees the magic word `for`, it will follow this procedure:
# 
# 1. Take the first item in the _list_ and assign it to a variable with the given _name_.
# 2. Run the indented code after the `for` line.
# 3. Take the next item in the _list_ and assign it to the variables with the given _name_.
# 4. Go back to step 2.
# 
# 
# To you help you remember this, when you see a line of code like this:
# 
# 
# ```python
# for x in l:
# ```
# 
# you can translate it into English like this:
# 
# ```
# for every item in l, put it in x, then do this:
# ```
# 
# #### Examples of `for` loops
# 
# Here is how you would print all the numbers in a list:

# In[76]:


l = [6, 1, 2, 7, 3]
for x in l:
    print(x)


# Notice that with a `for` loop, you do not need to initialize a counter variable nor increment it to loop through a list. The computer does all the work for you. 
# 
# Here is how you would sum all the squares ($x^2$) of the numbers in a list:

# In[77]:


nums = [3, 5, 6, 3, 1]
sum_of_squares = 0
for n in nums:
    n_squared = n * n
    sum_of_squares += n_squared
print(sum_of_squares)


# You can also put loops inside of loops. This code computes and prints the factorial ($x! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot x$) of each number in a list.

# In[78]:


lst = [6, 1, 3, 6, 7]
for x in lst:
    fact = 1
    y = 1
    while y <= x:
        fact *= y
        y += 1
    print(fact)


# ### 13.3 The `range` function
# 
# Let's look the code for printing all the numbers from 0 to 4 again.

# In[79]:


num = 0
while num < 5:
    print(num)
    num += 1


# Wouldn't it be nice if we could also use a `for` loop to make this code simpler?
# 
# There is a useful builtin function called `range` that can be used to create a sequence of numbers. We can rewrite the code above like this:

# In[80]:


for num in range(5):
    print(num)


# It does the exact same thing as the code from before, but it looks a lot simpler! But how does it work? Let's see what `range` returns:

# In[81]:


print(range(5))


# OK, that is not very useful. Maybe we can try making it into a list:

# In[82]:


print(list(range(5)))


# Aha! So `range(5)` simply creates the sequence of integers from 0 to 4. But what happened to the number `5`? Here is the full definition of `range`:
# 
# - `range(end)`:  Returns the sequence of integers in the range $[0, \texttt{end})$.
#   - In other words, returns the integers from `0` up to and including `end - 1`.  
#   
# So `range(5)` returns the sequence of integers from 0 up to 5, but not including 5. There are a couple other ways of using `range`:
# 
# - `range(start, end)`:  Returns the sequence of integers in the range $[\texttt{start}, \texttt{end})$.
#   - In other words, returns the integers from `start` up to and including `end - 1`.
# - `range(start, end, step)`:  Returns every `step`th integer in the range $[\texttt{start}, \texttt{end})$.
#   - In other words, returns the integers starting from `start` and adding `step` to it until it reaches `end - 1`.
#   
# This last one is a bit confusing, so let's see some examples:

# In[83]:


print(list(range(4, 15)))


# In[84]:


print(list(range(4, 15, 2)))


# In[85]:


print(list(range(4, 15, 3)))


# You can even use negative step to creates a sequence of integers in reverse order:

# In[86]:


print(list(range(14, 3, -1)))


# In[87]:


print(list(range(14, 3, -2)))


# #### Using `range` in `for` loops
# 
# So to print all the even numbers from 4 to 15 noninclusive, we can write:
# 

# In[88]:


for num in range(4, 15, 2):
    print(num)


# Notice that we don't have to use `list` to turn the `range` into a list. This is because the keyword `for` is able to use both lists and ranges. The computer can understand the `range`, so you don't need to make it into a `list`.
# 
# Let's use a range with negative step to create a rocket countdown:

# In[89]:


for t in range(10, -1, -1):
    print("T-minus", t, "...")
print("Blast off!!!")


# Now let's say that we have two lists that have the same length, and we want to compute the element-wise product of lists. How can we loop through two lists at the same time? We have `range` to the rescue!

# In[90]:


L1 = [1, 3, 8, 5, 3]
L2 = [5, 4, 3, 2, 1]

prod = []
for i in range(len(L1)):
    print("Multiplying", L1[i], "and", L2[i])
    prod += [L1[i] * L2[i]]
    
print(prod)


# Do you see the key trick here? We use the `range` to generate the sequence of list **indices** that we want to loop through. Then when the computer assigns each index to `i`, we can use it to get the corresponding item from both lists, and multiply them together.

# ### 13.4 Converting `for` loops to `while` loops
# 
# You've probably noticed that `while` loops are a lot simpler to understand than `for` loops. The keyword `for` tells the computer to do a lot more than the keyword `while`. In fact, you can convert **any** `for` loop into a `while` loop that does the same thing. Here are some examples:

# In[91]:


lst = [5, 3, 7, 9, 1]
# This code prints the square of each of the numbers in the list.
for x in lst:
    print(x * x)
    
# This code does the same thing but with a while loop.
i = 0
while i < len(lst):
    x = lst[i]
    print(x * x)
    i += 1


# In[92]:


# This code prints every 7th number between 10 and 30:
for num in range(10, 30, 7):
    print(num)

# This code does the same thing but with a while loop.
num = 10
while num < 30:
    print(num)
    num += 7


# ### 13.5 Advanced Loops: Using `break` and `continue`
# 
# 
# #### Break statement
# 
# 
# Sometimes it's necessary to stop a loop from executing till the end. 
# 
# For example, if we are searching a list `L = [1, 4, 7, 9, 11, 15]` for the number `7`, once we find the number `7` in the list, we no longer want to walk through the list. `break` helps us exit a loop once we no longer want to walk through the loop all the way through.
# 
# ```python
# for val in L:
#     if val == 7:
#         break;
# ```
# 
# #### Continue statement
# 
# The continue statement within loops is used to "skip the cycle". When the continue statement is executed in the loop, the code inside the loop following the continue statement will be skipped and next iteration of the loop will begin.
# 
# ```python
# for val in L:
#     ...
#     if val>0:
#         continue;
#     ...
#     # continue jumps here
#     # end of loop
# 
# ```

# ## 14. Functions

# You want to know how much money you have, so you count all your Birr: every coin and bill in your wallet. You have 4 one birr coins, 1 bill of 5 birr, 2 bills of 10, 1 bill of 50, and 2 bills of 100. You pull out your calculator and type in:
# 
# 
# 

# In[93]:


1 + 1 + 1 + 1 + 5 + 10 + 10 + 50 + 100 + 100


# But you actually want to do this counting every day. Is there an easier way for you to count all your money without typing every number into your calculator every time? We could use multiplication:

# In[94]:


1*4 + 5*1 + 10*2 + 50*1 + 100*2


# But it is still very annoying to type all of this every time. 
# 
# What if you had a special calculator machine that already knows how to count your birr, and works for any amount?
# What if this machine just asks you how many ones, fives, tens, fifties, and hundreds you have, and then it just tells you how much birr you have in total? That would save you a lot of time!
# 
# Writing a **function** in code is just like building a special calculator machine for a specific task. Let's create such a machine for the birr counting task:
# 

# In[95]:


# Here we *create* our machine.
def count_money(ones, fives, tens, fifties, hundreds):
    return 1*ones + 5*fives + 10*tens + 50*fifties + 100*hundreds


# But we don't see any output yet, because we've only created the machine, but we haven't used it yet. This is how we use the machine:

# In[96]:


# Here we *use* our machine.
count_money(4, 1, 2, 1, 2)


# Awesome! And we can use this machine as many times as we want:

# In[97]:


# Now I have 8 coins, 4 bills of 5 birr, 15 bills of 10 birr, 0 bills of 50 birr, and 9 bills of 100 birr
count_money(8, 4, 15, 0, 9)


# In[98]:


# Someone robbed me and now I have no coins and no bills.
count_money(0, 0, 0, 0, 0)


# Now let's learn more details about how to write and use functions.
# 
# ### 14.1 Anatomy of a Function Definition
# 
# In programming, when we create a new function (special calculator machine), we say that we are **defining** a function. When we are using our function, we say that we are **calling** the function.
# 
# Remember that our birr-counting function needed to ask us how many of each bill we had? Those numbers that we gave the function were the inputs for the machine. In programming, we like to call the inputs the **arguments** to the function.
# 
# Also remember that the function needed to tell us the result of the computation? In programming we say that the function **returns** the final result.
# 
# 
# Here is what a function **definition** looks like:
# 
# ```python
# def <function_name>(<argument1>, <argument2>, ...):
#     <statement 1>
#     <statement 2>
#     ...
# ```
# 
# The important details about function definitions are:
# 
# - A function definition starts with a **header** line:
# - The header line always starts with `def`, which is just short for "define".
# - It is followed by the function name, which can be almost anything, just like variable names.
# - Then we list the arguments (inputs) of the function between a pair of parentheses.
# - The arguments of the function are separated by commas.
# - Each argument can have almost any name, just like variable names.
# - All the instructions (statements) for what the function should do must be _indented_. We call these indented lines the **body** of the function. The first line that is not indented after the function header is considered _outside_ of the function.
# 
# Let's practice by writing a function for computing a restaurant bill. Let's say you own a restaurant, and sometimes a group of customers asks you to split the bill evenly between them. How can we compute the bill for each person? First let's think about what are the inputs: 1) we have a list of prices for the items that they ordered, 2) we need to know how many people are in the group, 3) we also need to make sure that we take tax rate into account. So we write this function, which we will name `split_bill`:

# In[99]:


def split_bill(prices, num_people, tax_rate):
    subtotal = 0
    for price in prices:
        subtotal += price
    total = subtotal * (1 + tax_rate)
    return total / num_people


# Note that **the magic word `return` marks the final result of the function**. We will explain `return` more in the next section.
# 
# It is also worth noting that a `return` statement does not have to be the last line in a function. It can be anywhere in the function. You will see more examples of this later in the course.
# 
# 
# ### 14.2 Anatomy of a Function Call
# 
# So now we have **defined** this `split_bill` function, but how do we use it? We need to make a **function call**.
# 
# Let's say that a group of 3 friends ordered a beyaynetu for 105 birr, a tibs firfir for 30 birr, and three Coca-Colas for 15 birr each. The tax rate in Addis Ababa is 5%. Then we should call the function like this:

# In[100]:


split_bill([105, 30, 15, 15, 15], 3, 0.05)


# So each person should pay exactly 63 birr.
# 
# What do you notice about this function call?
# 
# - First, you need to write the name of the function that you want to use. Then write all the inputs that we want to give the function, between a pair of parentheses and separated by commas.
# - It is also important to notice that we provide the arguments in exactly the same order as the list of expected arguments in the function definition. `num_people` was the second argument in the function definition, so we have to give our number of people (3) as the second argument in the function call.
# 
# Also, do function calls look familiar to you at all? (Hint: remember `print()`? Or `type()`?)
# 
# That's right! It turns out that we've been calling functions this whole time: `print`, `type`, `len`, `range`, and even `str` and `int` are all functions. We call these "**built-in functions**": this means that they are functions that are already **defined** inside the computer, so that you can use them any time. You do not need to define them yourself.
# 
# Let's look at another example. Let's say that the group of 3 friends want to each pay 5 birr tip. So we can write this code to show how much each person is paying:

# In[101]:


bill = [105, 30, 15, 15, 15]
print("Each person is paying", split_bill(bill, 3, 0.05) + 5, "birr.")


# How does this code work? What does it mean to call a function _inside_ the `print` call?
# 
# Let's learn the steps of a function call. **When a computer sees a function call, it does this:**
# 
# 1. Jump to the code of the function definition.
# 2. Assign the arguments that you gave the function one by one to the variables with the names you gave in the argument list in the function definition.
# 3. Run the code of the function line by line.
# 4. If the computer reaches a `return` instruction, jump back to the calling location immediately, and do not finish running the function.
# 5. Replace the function call with the return value.
# 
# This is a lot to remember, and it probably doesn't make any sense yet. So let's try it on the example from above. The first line:
# ```python
# bill = [105, 30, 15, 15, 15]
# ```
# just assigns the list of numbers to a variable called `bill`. Then the next line is a call to `print`:
# ```python
# print("Each person is paying", split_bill(bill, 3, 0.05) + 5, "birr.")
# ```
# The computer needs to know exactly what it is printing. But the second argument to `print` is not computed yet:
# ```python
# split_bill(bill, 3, 0.05) + 5
# ```
# So the computer has to call `split_bill`. So first (1) it jumps to the first line of the function definition:
# ```python
# def split_bill(prices, num_people, tax_rate):
# ```
# Now it has to (2) assign all the arguments. The function takes arguments `(prices, num_people, tax_rate)`, and we called the function with `(bill, 3, 0.05)`. So the computer will do this behind the scenes:
# ```python
# prices = bill
# num_people = 3
# tax_rate = 0.05
# ```
# Now the computer is ready to (3) run the **body** of the function line by line:
# ```python
# subtotal = 0
# for price in prices:
#     subtotal += price
# total = subtotal * (1 + tax_rate)
# ```
# At the end of this code, the variable `total` now contains the total amount of the bill, `189`. Then the computer sees a `return` statement:
# ```python
# return total / num_people
# ```
# So now the computer computes `total / num_people` $\rightarrow$ `63` as the final result of the function, then (4) _returns_ to where you first called the function:
# ```python
# split_bill(bill, 3, 0.05) + 5
# ```
# Now the computer (5) _replaces_ the function call with the final result of the function (which we call the **return value**):
# ```python
# 63 + 5
# ```
# Now the computer is able to make the call to the `print` function:
# ```python
# print("Each person is paying", 63 + 5, "birr.")
# ```
# ```python
# print("Each person is paying", 68, "birr.")
# ```

# ### 14.3 Advanced Note: Relationship between code functions and math functions
# 
# You might have heard of the word "function" before in math class, and wondering how it's different from functions in code. They are similar, but not exactly the same. Let's look at some examples to see how they are same and how they are different.
# 
# Let's define a function $f(x)$ like this:
# 
# $$f(x) = 2x + 3$$
# 
# We can use this function in other math expressions like this:
# 
# $$ 4 f(3)^2 = 4 (2 \cdot 3 + 3)^2 = 4 (9)^2 = 4 \cdot 81 = 324 $$
# 
# Notice how this is very similar to the steps of a function call that we described before? When we write $f(3)$, we rewrite the expression $2x + 3$ with the argument $3$ substituted in for $x$. (In code, the computer would assign `x = 3`.) Then we compute the result of the function $f(3) = 2 \cdot 3 + 3 = 9$, and then we replace the original function call with the result: $4f(3)^2 = 4(9)^2$.
# 
# Let's tell the computer to do the same thing in code:

# In[102]:


def f(x):
    return 2 * x + 3

print(4 * f(3) ** 2)


# We get the same result!
# 
# So far, functions in math seem pretty similar to functions in code. There are some differences in the way you write it (for example, we need to write `def` and also write `return` to mark the result), but otherwise the way they are expanded is similar. But what happens if we change our code function a little bit:

# In[103]:


def f(x):
    print("Hello I got number", x)
    return 2 * x + 3

print(4 * f(3) ** 2)


# We added a `print` call inside the function.
# 
# Our first question to you: _Is there any way to do something similar in a math function?_
# 
# No! There is no such thing as "printing something on the screen" in math.
# 
# Our next question: _Does the added `print` call change the result of the function call at all?_
# 
# No! The `print` call does not change the result of the function call. When the computer sees this:
# ```python
# print(4 * f(3) ** 2)
# ```
# it will still expand it to:
# ```python
# print(4 * 9 ** 2)
# ```
# because the function has `return 2 * x + 3`, which does not get affected by the `print`. The only thing that changes is that the computer will also display `Hello I got number 3` on the screen. We call these effects the **side effects** of a function. One of the main differences between functions in math and functions in code is that only functions in code can have side effects.

# ## 15. Indentation
# 
# ```python
# name = "One sip Steve"
# if len(name) > 0:
#     message = 'Hi! ' + name 
#     print message
# ```
# 
# In the above example, we told the computer that the two statements or block of code should be run only if length of name is greater than 0.
# 
# However, how does the computer get to know what all lines of code are to be executed?
# 
# Some programming languages wrap code using curly braces `{}`:
# 
# ```go
# if len(name) > 0 {
#     message = 'Hi! ' + name
#     print message
# }
# ```
# 
# Python relies on **indentation** to know which lines of code is contained under the previous `if` statement, `for` loop, `while` loop, or function `def`inition. Indentation means **space on the left side of the code**.
# 
# All contiguous (touching) lines that have the same amount of space on the left side _or more_ are considered one **block** of code. Let's look at this example:
# 
# ```python
# lst = [6, 1, 3, 6, 7]
# for x in lst:
#     fact = 1
#     y = 1
#     while y <= x:
#         fact *= y
#         y += 1
#     print(fact)
# print("done!")
# ```
# 
# The two lines after the `while` statement are considered one block of code, because they both have the same number of spaces on the left side, and they are touching. Thus they are the only lines _inside_ the `while` loop:
# ```python
#         fact *= y
#         y += 1
# ```
# 
# This is also a block of code, because all these lines have the same number of spaces on the left **or more**. So these are the lines that are considered _inside_ the `for` loop:
# ```python
#     fact = 1
#     y = 1
#     while y <= x:
#         fact *= y
#         y += 1
#     print(fact)
# ```

# ## 16. Recursion

# Recursion is a problem solving method that makes use of solutions to smaller/easier variations of the original problems to answer the original problem.
#   
# In recursion, a function **calls** itself. Recursion is used when a problem can be easily divided into easier problems. 
# 
# A recursive function has **2 components**:
# 
# 1. **Base case:** Simplest possible input and prevents **infinite recursion**.
# 2. **Recursion step:** Call the same function itself with a **smaller/easier** input to the function and act on the output of the smaller function call.

# Given a problem to find the factorial of a given number, compare the **iterative** method to problem solving (involving use of a `for`/`while` loop) with the **recursive** method to problem solving.

# In[104]:


# Iterative
def factorial_iter(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

print(factorial_iter(6))


# In[105]:


# Recursive
def factorial_recur(n):
    if n == 0: # BASE CASE
        return 1
    return n * factorial_recur(n-1) # RECURSION STEP

print(factorial_recur(6))


# There are, however, trade-offs to using recursive method to solving problems over iterative method. Many recursive solutions to a problem end up with few lines of code and some consider them more elegant. However, recursive method, without proper optimization, can run into situations in which the number of recursive function calls with smaller inputs might require too much power from your computer! When approaching a particular problem, consider the trade-offs of different methods before committing to one method.

# ## Glossary
# 
# - **argument**: an input to a function
# - **assign**: to give (a variable) a new value
# - **builtin function**: a function is already defined by Python; a function that Python already knows about
# - **call** a function: to use a function
# - **cast**: to change a value from one type to another
# - **contiguous**: on top of each other; touching
# - **define** a function: to create a function
# - **element**: an item in a list
# - **expression**: a piece of code that the computer executes and turns into a value
# - **error**: a problem in the code; the computer will sometimes give us an error if there is something wrong with our code
# - **execute**: (when the computer) follows the instructions in your code
# - **indent**: to add space to the left of a line of code
# - **indentation**: the space to the left of a line of code
# - **indented**: having space on the left side
# - **index**: the position of an element in a list
# - **indices**: plural of index
# - **iteration**: one cycle of a loop
# - **keyword**: a special word that has special meaning in the programming language; it means something special to the computer
# - **operator**: a symbol that performs an operation on the items next to it. For example, `+`, `*`, or `not`.
# - **parentheses**: round braces like this: `()`
# - **print**: to show something on the screen
# - **program**: a collection of instructions (code) that performs a specific task when executed by a computer
# - **statement**: a full line of code
# - **square brackets**: these are square brackets: `[]` 
# - **string**: a sequence of text characters
# - **syntax**: the "grammar" of a programming language like Python: syntax is the set of rules about where words should go in the code, how they should be spelled, where punctuation should go, etc.
# 
#