# Lab 3 Solutions

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.

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.

## Lists

In Data 8, you have recently started working with `Tables`

. Tables are an extremely useful and powerful data type. In CS88 we will work with other data types. Python provides
several important built-in data types that we can build from. So far, you have met numberical data types (ints, floats, and booleans) and one sequence type (strings). Lists, tuples, and dictionaries are other sequence data types in Python. Here, we will take a closer look at lists. **A list can contain a sequence of values of any type.**

You can create a list just by placing the values, separated by commas, within square brackets. Here are some examples. As you will see in one of the examples, lists can contain other lists.

```
>>> [1,2,3]
[1, 2, 3]
>>> ["frog", 3, 3.1415]
['frog', 3, 3.1415]
>>> [True, [1, 2], 42]
[True, [1, 2], 42]
```

Open up your python interpreter and create some lists of your own.

You learned last week that what really makes a data type useful is the operations that you can
perform on it. What can you do with lists?

```
>>> x = [1,2,3] # assign them to variables
>>> len(x) # get their length, i.e., the number of elements in them
3
>>> x + [4,5] # + is concatenation
[1, 2, 3, 4, 5]
>>> [1,2] * 3 # * is replication
[1, 2, 1, 2, 1, 2]
>>> len([1,2] * 3)
6
>>> [1,2] * [3,4] # what's this?
TypeError: can't multiply sequence by non-int of type 'list'
```

The `in`

operator is very useful when working with lists. It operates on the entire list and produces a boolean that answers the question, "Is this item in the list?".

```
>>> 2 in [1,2,3]
True
>>> "frog" in [1,2,3]
False
>>> [1,2] in [1,2,3]
False
>>> [1,2] in [[1,2],3]
True
```

### Question 1: Second Max

Write a function that finds the second highest number in a list of positive integers. You can assume that the list always has at least two integers.

```
def second_max(lst):
"""
Return the second highest number in a list of positive integers.
>>> second_max([3, 2, 1, 0])
2
>>> second_max([2, 3, 3, 4, 5, 6, 7, 2, 3])
6
>>> second_max([1, 5, 5, 5, 1])
5
>>> second_max([5, 6, 6, 7, 1])
6
>>> second_max([5, 6, 7, 7, 1])
7
"""
"*** YOUR CODE HERE ***"
highest = 0
second_highest = 0
for num in lst:
if num >= highest:
second_highest = highest
highest = num
elif num < highest and num > second_highest:
second_highest = num
return second_highest
```

Use OK to test your code:

`python3 ok -q second_max`

## 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 world 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 2: Perfect squares

Implement the function `squares`

, which takes in a list of positive
integers, and returns a new list which contains only elements of the original
list that are perfect squares. Use a list comprehension.

```
from math import sqrt
def is_square(n):
return float(sqrt(n)) == int(sqrt(n))
def squares(seq):
"""Returns a new list containing elements of the original list that are
perfect squares.
>>> seq = [49, 8, 2, 1, 102]
>>> squares(seq)
[49, 1]
>>> seq = [500, 30]
>>> squares(seq)
[]
"""
"*** YOUR CODE HERE ***"
return [n for n in seq if is_square(n)]
```

Use OK to test your code:

`python3 ok -q squares`

### Question 3: Perfect Pairs

Implement the function `pairs`

, which takes in an integer n,
and returns a new list of lists which contains pairs of numbers from 1 to n.
Use a list comprehension.

```
def pairs(n):
"""Returns a new list containing two element lists from values 1 to n
>>> pairs(1)
[[1, 1]]
>>> x = pairs(2)
>>> x
[[1, 1], [2, 2]]
>>> pairs(5)
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]
>>> pairs(-1)
[]
"""
"*** YOUR CODE HERE ***"
return [[i, i] for i in range(n + 1)]
```

Use OK to test your code:

`python3 ok -q pairs`

## 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 4: 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(lst, 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 [n for n in lst if n > limit]
```

Use OK to test your code:

`python3 ok -q where_above`

## 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 5: 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. You CANNOT use any in-built functions.

```
def minmax(s):
"""Return the minimum and maximum elements of a non-empty list. Hint: start
with defining two variables at the beginning. Do not use the built in
max or min functions
>>> minmax([1, 2, -3])
[-3, 2]
>>> x = minmax([2])
>>> x
[2, 2]
>>> minmax([4, 5, 4, 5, 1, 9, 0, 7])
[0, 9]
>>> minmax([100, -10, 1, 0, 10, -100])
[-100, 100]
"""
"*** YOUR CODE HERE ***"
mn, mx = s[0], s[0]
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`

## 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 6: 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 ***"
exponent = 0
while x > (2 ** (exponent + 1)):
exponent += 1
return 2 ** exponent
```

Use OK to test your code:

`python3 ok -q closest_power_2`

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.