Lab 3 Solutions | CS 88 Fall 2018

Solutions: You can find the file with solutions for all questions here.

Last lab, we went over how to use python tutor to help us visualize the execution of python code. Let's do another example to review the concept of scopes for variables and nesting for functions.

Scopes and Nested Functions

Let’s see what nested function calls look like in the python interpreter.

PythonTutor

Paste this code into the interpreter or follow this link Ex1

def bonus(score):
  previousScore = score
  multiplier = 1
  if score > 25:
    multiplier = 2
  score *= multiplier
  return score
print(bonus(score))
print(previousScore)

Now step through the code. Why does it error out? The error message reads

NameError: name 'previousScore' is not defined

But didn't we define previousScore in the body of the bonus function? We did, but that previousScore is only defined in the scope of the function. So it is not accessible outside in the global scope.

Let's try another function Ex2

def totalScore(score):
  multiplier = 2
  def bonus(score):
    if score > 25:
      score *= multiplier
    else:
      score /= multiplier
    return score
  return score, bonus(score)
score = 12
totalScore(score)
print(score)

There's a lot to unpack here. We purposefully gave the variables the same names so you can see how python lookups values for variables. The general principle is that python looks for the value in the current scope first. If it can't find the variable there, it checks it's parent scope, and the parent's parent, all the way up to the global scope. If the variable still isn't found there, an error is raised. Walk through the lookup for multiplier on line 7 in your head as a sanity check.

List Comprehensions

Now that we can create lists, assign variables, write expressions, and define functions, we can compose these concepts to do lots of interesting things. Python's list comprehensions open a beautiful of data-centric programming.
The comprehension is in brackets, just like a list, but rather than a static sequence of literals, it is a dynamically computed list.

>>> somelist = [1, 2, 9, -1, 0]
>>> [x+1 for x in somelist]
[2, 3, 10, 0, 1]
>>> [x*x for x in somelist]
[1, 4, 81, 1, 0]

In general, the expression just inside the [ is evaluated for each element in the list, using the variable between the for and the in to name each element in succession. The result is the transformed list.

>>> def square(x):
...     return x*x
...
>>> def squares(s):
...     return [square(x) for x in s]
...
>>> squares([0,1,2,4])
[0, 1, 4, 16]

>>>x, y = 2, 3
>>> x+y
5
>>> [x+y for x,y in [(1,2), (2,3), (3,4)]]
[3, 5, 7]

This is a powerful design pattern, called map, that you will use in often in analyzing data. It maps, or transforms, one data structure into another under some expression, often by applying a function to each of the elements.

Do you remember the Table.apply( ) function from Data 8? The Table.apply function is another great example of the map design pattern as it applies a "transformation" or a function to a row or column.

Sometimes you need a sequence to get started, and Python provides handy tools for that. One of them is range.

>>> [x*x for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

You can review range in Section 2.3 of Composing Programs.

Question 1: Shopping - Tax

Let's write a function that transforms a shopping cart, which we will represent as a list of 3 element tuples, by adding a specified percent tax to the price of each item. We will then compute the cost of all our items including tax.

Shopping carts are represented like this:

[(item1, cost1, quantity1), (item2, cost2, quantity2), ..., (itemN, costN, quantityN)]

Implement tax(shopping_cart, percent) and sum(shopping_cart) so you can figure out how much you have to pay for all of your items.

def tax(shopping_cart, percent):
    """
    Adds a `percent` tax to each item's price in a shopping cart.

    >>> fruitCart = [("apple", 0.5, 3), ("banana", 0.25, 4)]
    >>> tax(fruitCart, 10)
    [('apple', 0.55, 3), ('banana', 0.275, 4)]

    >>> calCart = [("oski", 1000, 1), ("go", 1, 2), ("bears", 3.5, 2)]
    >>> tax(calCart, 100)
    [('oski', 2000.0, 1), ('go', 2.0, 2), ('bears', 7.0, 2)]
    """
    "*** YOUR CODE HERE ***"
    return ______
    taxMultiplier = 1 + (percent / 100)
    return [(name, price * taxMultiplier, quantity) for (name, price, quantity) in shopping_cart]

Use OK to test your code:

python3 ok -q tax --local

Question 2: Shopping - Cart Sum

def cartSum(shopping_cart):
    """
    Sums a shopping cart

    >>> fruitCart = [("apple", 0.5, 3), ("banana", 0.25, 4)]
    >>> taxedFruit = tax(fruitCart, 10)
    >>> cartSum(taxedFruit)
    2.75
    >>> calCart = [("oski", 1000, 1), ("go", 1, 2), ("bears", 3.5, 2)]
    >>> taxedCal = tax(calCart, 100)
    >>> cartSum(taxedCal)
    2018.0
    """
    "*** YOUR CODE HERE ***"
    return ______
    return sum([price*quantity for (name, price, quantity) in shopping_cart])

Use OK to test your code:

python3 ok -q cartSum --local

Conditionals

You can review the syntax and behavior of if statements in Section 1.5.4 of Composing Programs.

The conditional statement is a statement, not an expression; it does not return a value. The if-expression (or predicate) is evaluated first, before any other part of the statement, to determine whether to evaluate an arm. If the if-expression evaluates to a True value then the statement(s) following the : is evaluate. Otherwise, the else arm is evaluated, if present. Multiple predicates can be chained together with elif. They are evaluated sequentially. Often conditionals are often used along with return statements in functions. For example, in some census data you see in c8 you might want to decode the gender code.

def decode_gender(code):
    if (code == 0):
        return 'all'
    elif (code == 1):
        return 'male'
    elif (code == 2):
        return 'female'
    else:
        return 'unknown'

Conditionals are often used with assignment statements to simplify later expressions.

if ((year % 4) == 0) and (((year % 100) != 0) or ((year % 400) == 0)):
    year_len = 366
else:
    year_len = 365
<do something with year_len>

Or with print statements to control output

if (scene == 'architect skit'):
    print("spam, spam, spam")
else
    print("nobody expects the Spanish inquisition")

Omitting the else

Consider the following function:

def abs(x):
    if x >= 0:
        return x
    else:
        return -x

It is correct to rewrite abs in the following way:

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

This is a direct consequence of how return works — when Python sees a return statement, it will immediately terminate the function, and the rest of the function will not be evaluated. In the above example, if x >= 0, Python will never reach the final line. Try to convince yourself that this is indeed the case before moving on.

Keep in mind that omitting the else only works if the function is terminated! For example, the following function will always print "less than zero", because the function is not terminated in the body of the if suite:

>>> def foo(x):
...     if x > 0:
...         print("greater than zero")
...     print("less than zero")
...
>>> foo(-3)
less than zero
>>> foo(4)
greater than zero
less than zero

In general, omitting the else will make your code more concise — however, if you find that it makes your code harder to read, by all means use an else statement.

Question 3: Where Above

Lets use list comprehensions to implement some of the filters we could apply in Data 8's table.where() function. In particular, fill in the where_above function that returns a list that filters out any elements less than or equal to limit. Try to do this in only one line.

def where_above(list, limit):
    """
    where_above behaves like table.where(column, are.above(limit)).
    The analogy is completed if you think of a column of a table as a list and return the filtered column instead of the entire table.

    >>> where_above([1, 2, 3], 2)
    [3]
    >>> where_above(range(13), 10)
    [11, 12]
    >>> where_above(range(123), 120)
    [121, 122]

    """
    "*** YOUR CODE HERE ***"
    return ______
    return [n for n in list if n > limit]

Use OK to test your code:

python3 ok -q where_above --local

Iteration: For loops

You might remember for loops from simulations in Data 8. A for loop can be constructed by using the for statement. Typically, the for statement is used to iterate through a sequence, such as a list, and perform some computing on each iteration. Here is an example:

def sum(s):
   """
   Return the sum of the elements in the sequence, s.
   >>> sum([1, 2, 3])
   6
   """
   total = 0           
   for number in s:         # for each element in the sequence
      total = total + number  # accumulate it into the partial sum
   return total         # the final partial sum is the total sum

The line total = total + number is called an accumulation statement. This statement is so common that it has a special shorthand notation.

total += number

Question 4: Minmax

In c8 you often need to understand the spread of data. Write a simple function to find the minimum and maximum elements in a sequence using a for loop.

def minmax(s):
    """Return the minimum and maximum elements of a sequence.

    >>> minmax([1, 2, -3])
    (-3, 2)
    >>> minmax([2])
    (2, 2)
    >>> minmax([])
    (None, None)
    """
    "*** YOUR CODE HERE ***"
    return ______
    mn, mx = None, None
    for x in s:
        if mn is None or x < mn:
            mn = x
        if mx is None or x > mx:
            mx = x
    return mn, mx

Use OK to test your code:

python3 ok -q minmax --local

Iteration: While loops

Python also has a more basic iteration construct that is closely related to conditionals, the while loop. It does not make any assumption of iterating through a sequence. It iterates until a predicate is satisfied.

You can review the syntax of while loops in Section 1.5.5 of Composing Programs.

Typically, some state will be established before the while loop. The predicate will compute a boolean expression involving that state. And the body of the loop will advance the state, thereby iterating until the predicate is satisfied.

Question 5: Closest Power of 2

Let's test out our knowledge by making a function that finds the largest power of 2 that is less than a given number. Fill in the function closest_power_2 below to return the closest power of 2 using a while loop.

def closest_power_2(x):
    """ Returns the closest power of 2 that is less than x
    >>> closest_power_2(6)
    4
    >>> closest_power_2(32)
    16
    >>> closest_power_2(87)
    64
    >>> closest_power_2(4095)
    2048
    >>> closest_power_2(524290)
    524288
    """
    "*** YOUR CODE HERE ***"
    return ______
    exponent = 0
    while x > (2 ** (exponent + 1)):
        exponent += 1
    return 2 ** exponent

Use OK to test your code:

python3 ok -q closest_power_2 --local

Here's some food for thought: What mathematical operation is closely related to finding the closest power of 2? It's the logarithm! (at least with a base of 2) By keeping track of which power of 2 you are on, you can compute rounded down version of log base 2 of numbers using your closest_power_2 function. If this stuff is cool to you, you should check out CS61C, particularly the sections on binary representations of data, and bitwise operators.