Lab 2: Expressions and Control Structures

Due at 11:59pm on 06/25/2015.

Starter Files

Download lab02.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

• To receive credit for this lab, you must complete Questions 4, 7, and 8 in lab02.py and submit through OK.
• Questions 1, 2, 3, 5, and 6 (What Would Python Print?) are designed to help introduce concepts and test your understanding.
• Questions 9, 10, and 11 are optional extra practice. It is recommended that you complete these problems on your own time.

Using Python

When running a Python file, you can use flags on the command line to inspect your code further. Here are a few that will come in handy. If you want to learn more about other Python flags, take a look at the documentation.

• Using no flags will run the code in the file you provide and return you to the command line.

  python3 lab02.py

• -i: The -i option runs your Python script, then opens an interactive session.

  python3 -i lab02.py

• -m doctest: Runs doctests in a particular file. Doctests are marked by triple quotes (""") and are usually located within functions.

  python3 -m doctest lab02.py

Using OK

In 61A, we use a program called OK for autograding labs, homeworks, and projects. You should have downloaded ok at the start of this lab. You can use ok to run doctests for a specified function. For example,

python3 ok -q factors

By default, only errors will show up. You can use the -v option to show all tests, including successful ones:

python3 ok -v

Finally, when you have finished all the quesitons in lab02.py, you can submit the assignment using the --submit option:

python3 ok --submit

Division

Let's compare the different division-related operators in Python:

>>> 1 / 4
0.25

>>> 25 / 4
6.25

>>> 11 / 3
3.6666666666666665

>>> 5 / 0
ZeroDivisionError

>>> 1 // 4
0

>>> 25 // 4
6

>>> 11 // 3
3

>>> 7 // 0
ZeroDivisionError

>>> 1 % 4
1

>>> 25 % 5
0

>>> 11 % 3
2

>>> 9 % 0
ZeroDivisionError

One useful technique involving the % operator is to check whether a number x is divisible by another number y:

x % y == 0

For example, in order to check if x is an even number:

x % 2 == 0

Boolean Operators

Python supports three boolean operators: and, or, and not:

>>> a = 4
>>> a < 2 and a > 0
False
>>> a < 2 or a > 0
True
>>> not (a > 0)
False

• and will evaluate to True only if both operands evaluate to True. If at least one operand is False, then and evaluates to False
• or will evaluate to True if at least one operand evaluates to True. If all operands are False, then or evaluates to False

What do you think the following expression evaluates to? Try it out in the Python interpreter.

True and not False or not True and False

Using parentheses can be helpful to understand how a program will behave. Python interprets that expression in the following way:

(True and (not False)) or ((not True) and False)

Boolean operators, like arithmetic operators, have an order of operation:

• not has the highest priority
• and
• or has the lowest priority

It turns out and and or don't just work on booleans (True, False). Other Python values can be considered "false-y", including False, 0, None, and "" (the empty string). All other values are considered "truth-y".

Question 1: What Would Python Print?

What would Python print? Try to figure it out before you type it into the interpreter!

>>> 13 and True
______
True
>>> 0 or False
______
False
>>> "" and 0 or False
______
False

Remember and and or do not always return booleans when using truth-y and false-y values.

Short Circuiting

What do you think will happen if we type the following into Python?

1 / 0

Try typing it into Python! You should see a ZeroDivisionError. But what about this expression?

True or 1 / 0

This doesn't cause any errors! In fact, it evaluates to True. That is:

If and and or make it to the last value without stopping, they just return the last value. In Python, and and or are examples of short-circuiting operators (they don't necessarily evaluate every operand).

Question 2: What Would Python Print?

What would Python print? Try to figure it out before you type it into the interpreter!

>>> True and 13
______
13
>>> False or 0
______
0
>>> not 10
______
False
>>> not None
______
True

Question 3: What Would Python Print?

>>> True and 1 / 0 and False
______
ZeroDivisionError
>>> True or 1 / 0 or False
______
True
>>> True and 0
______
0
>>> False or 1
______
1
>>> 1 and 3 and 6 and 10 and 15
______
15
>>> 0 or False or 2 or 1 / 0
______
2

Question 4: Fix the Bug

The following snippet of code doesn't work! Figure out what is wrong and fix the bugs.

def both_positive(x, y):
    """Returns True if both x and y are positive.

    >>> both_positive(-1, 1)
    False
    >>> both_positive(1, 1)
    True
    """
    "*** YOUR CODE HERE ***"
    return x and y > 0
    return x > 0 and y > 0

Use OK to test your code:

python3 ok -q both_positive

If statements

Question 5: What would Python print?

>>> def bar(a, b):
...     if a == 4:
...         return 6
...     elif b >= 4:
...         return 6 + 7 + a
...     else:
...         return 25
...
>>> bar(10, 6)
______
23

First check the if then the elif. If neither of these are True then proceed to else.

>>> def foo(x):
...     if x == 5:
...         return True
...     else:
...         return False
>>> foo(5)
______
True

If no elif is given, proceed straight to else. Functions can have multiple elif in a row.

>>> def abs(x):
...     if x >= 0:
...         return x
...     return -x
...
>>> abs(-5)
______
5
>>> abs(5)
______
5

In these cases, the else can be omitted since the code will either exit the function after the if or proceed to the next unindented line.

>>> def abs(x):
...     if x >= 0:
...         print(x)
...     print(-x)
...
>>> abs(-5)
______
5
>>> abs(5)
______
5
-5

While loops

Question 6: What Would Python Print?

>>> n = 3
>>> while n >= 0:
...     n -= 1
...     print(n)
...
______
2
1
0
-1

The code block will continue to run until n becomes < 0, since 0 is not greater than or equal to 0.

Question 7: What Would Python Print?

>>> # typing Ctrl-C will stop infinite loops
>>> n = 4
>>> while n > 0:
...     n += 1
...     print(n)
...
______
3
2
1
0
-1
-2
# continues forever

Make sure your while loop condition eventually becomes false, or it'll never stop!

Question 8: What Would Python Print?

>>> def exp_decay(n):
...     if n % 2 != 0:
...         return
...     while n > 0:
...         print(n)
...         n = n // 2
...
>>> exp_decay(64)
______
64
32
16
8
4
2
1
>>> exp_decay(5)
______
# No output

The while loop will keep running until the loop condition becomes false.

Question 9: Factor This

Define a function factors(n) which takes in a number, n, and prints out all of the numbers that divide n evenly. For example, the factors of 20 are 20, 10, 5, 4, 2, 1.

def factors(n):
    """Prints out all of the numbers that divide `n` evenly.

    >>> factors(20)
    20
    10
    5
    4
    2
    1
    """
    "*** YOUR CODE HERE ***"
    x = n
    while x > 0:
        if n % x == 0:
            print(x)
        x -= 1

Use OK to test your code:

python3 ok -q factors

Question 10: Fibonacci

The Fibonacci sequence is a famous sequence in mathematics. The first element in the sequence is 0 and the second element is 1. The nth element is defined as F_n = F_n-1 + F_n-2.

Implement the fib function, which takes an integer n and returns the nth Fibonacci number. Use a while loop in your solution.

def fib(n):
    """Returns the nth Fibonacci number.

    >>> fib(0)
    0
    >>> fib(1)
    1
    >>> fib(2)
    1
    >>> fib(3)
    2
    >>> fib(4)
    3
    >>> fib(5)
    5
    >>> fib(6)
    8
    >>> fib(100)
    354224848179261915075
    """
    "*** YOUR CODE HERE ***"
    curr, next = 0, 1
    while n > 0:
        curr, next = next, curr + next
        n -= 1
    return curr

Use OK to test your code:

python3 ok -q fib

Error Messages

By now, you've probably seen a couple of error messages. Even though they might look intimidating, error messages are actually very helpful in debugging code. The following are some common types of errors (found at the bottom of an error message):

Using these descriptions of error messages, you should be able to get a better idea of what went wrong with your code. If you run into error messages, try to identify the problem before asking for help. You can often Google unknown error messages to see what similar mistakes others have made to help you debug your own code.

For example:

>>> square(3, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: square() takes 1 positional argument but 2 were given

Note:

• The error message tells us what we did wrong - we gave square 2 arguments when it only takes in 1 argument. In general, the last line is the most helpful.
• The number in the second to last line (line 1) tells us where the error occured, which will help you track down the error.

Extra Questions

Questions in this section are not required for submission. However, we encourage you to try them out on your own time for extra practice.

Question 11: Factor This

Define a function is_factor that checks whether its first argument is a factor of its second argument. We will assume that 0 is not a factor of any number but any non-zero number is a factor of 0. You should not use if in your solution.

def is_factor(x, y):
    """ Returns True if x is a factor of y, False otherwise.

    >>> is_factor(3, 6)
    True
    >>> is_factor(4, 10)
    False
    >>> is_factor(0, 5)
    False
    >>> is_factor(0, 0)
    False
    """
    "*** YOUR CODE HERE ***"
    return x != 0 and y % x == 0

Use OK to test your code:

python3 ok -q is_factor

Question 12: Disneyland Discounts

Disneyland is having a special where they give discounts for grandparents accompanying their grandchildren. Help Disneyland figure out when the discount should be given. Define a function gets_discount that takes two numbers as input (representing the two ages) and returns True if one of them is a senior citizen (age 65 or above) and the other is a child (age 12 or below). You should not use if in your solution.

def gets_discount(x, y):
    """ Returns True if this is a combination of a senior citizen
    and a child, False otherwise.

    >>> gets_discount(65, 12)
    True
    >>> gets_discount(9, 70)
    True
    >>> gets_discount(40, 45)
    False
    >>> gets_discount(40, 75)
    False
    >>> gets_discount(65, 13)
    False
    >>> gets_discount(7, 9)
    False
    >>> gets_discount(73, 77)
    False
    >>> gets_discount(70, 31)
    False
    >>> gets_discount(10, 25)
    False
    """
    "*** YOUR CODE HERE ***"
    return (x <= 12 and y >= 65) or (x >= 65 and y <= 12)

Use OK to test your code:

python3 ok -q gets_discount

Question 13: Falling factorial

Let's write a function falling, which is a "falling" factorial that takes two arguments, n and k, and returns the product of k consecutive numbers, starting from n and working downwards.

def falling(n, k):
    """Compute the falling factorial of n to depth k.

    >>> falling(6, 3)  # 6 * 5 * 4
    120
    >>> falling(4, 0)
    1
    >>> falling(4, 3)  # 4 * 3 * 2
    24
    >>> falling(4, 1)  # 4
    4
    """
    "*** YOUR CODE HERE ***"
    total, stop = 1, n-k
    while n > stop:
        total, n = total*n, n-1
    return total

Use OK to test your code:

python3 ok -q falling