Homework 2

Due by 11:59pm on Thursday, 9/15/2016

Instructions

Download hw02.zip. Inside the archive, you will find a file called hw02.py, along with a copy of the OK autograder. Upload the zip file to Jupyter to complete the assignment. See Lab 0 for instructions on using Jupyter to complete assignments.

Submission: When you are done, submit the assignment by uploading the .py file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.

Readings: This homework relies on following references:

• Section 1.4
• Section 1.5
• Section 2.3

Error Messages

By now, you've probably seen a couple of error messages. They might look intimidating, but error messages are very helpful for debugging code. The following are some common types of errors:

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 unfamiliar error messages to see if others have made similar mistakes to help you debug.

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 last line of an error message tells us the type of the error. In the example above, we have a TypeError.
• The error message tells us what we did wrong — we gave square 2 arguments when it can only take in 1 argument. In general, the last line is the most helpful.
• The second to last line of the error message tells us on which line the error occurred. This helps us track down he error. In the example above, TypeError occurred at line 1.

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

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 1: WWPP: Loops

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python ok -q loops -u --local

When using loops, make sure your while loop conditions eventually become false-y, or the loops will never stop! Typing Ctrl-C or refreshing the page will stop infinite loops in the interpreter.

Here's some food for thought: is it possible for a program to detect if there is an infinite loop in any program? Put another way, can you create a program that determines if another program will halt? Read about the Halting problem if you're interested in learning more!

For Loops

In addition to while loops, Python offers an alternate way to iterate using for loops. 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 computating 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

Practice With Lists and Loops

Question 2: Sum of Squares

Complete the function to compute the sum of squares.

def sum_of_squares(n):
    """
    return the sum of squares from 1 to n
    >>> sum_of_squares(3)
    14
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q sum_of_squares --local

Question 3: Factor This!

Implement a function factors which takes in a number n and prints out (in descending order) 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 ***"

Use OK to test your code:

python ok -q factors --local

Question 4: Putting it all Together

Write a function max_list that takes in a list and returns its largest element.

def max_list(s):
    """Return the largest value in a sequence.  None if empty.

    >>> max_list([1,3,-1])
    3
    """
    # Hint: Is there a built-in function you can use for this?
    "*** YOUR CODE HERE ***"

Now write a function remove_element that takes in a list, s, and a value, exclude. It should return a new list that contains all the elements in s that are not equal to exclude.

def remove_element(s, exclude):
    """Remove all entries in sequence s equal to exclude.

    >>> remove_element([1, 3, -1], 1)
    [3, -1]
    """
    "*** YOUR CODE HERE ***"

Using the last two functions, write a new function remove_max that takes in a list and returns the same list with its maximal elements removed.

def remove_max(s):
    """Return a a list containing non-maximal elements of a sequence.

    >>> remove_max([1, 3, -1, 3])
    [1, -1]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q max_list --local
python ok -q remove_element --local
python ok -q remove_max --local

Question 5: Buggy Reverse

Correct the mistake(s) in the reverse function. First open up the function in python tutor and add a test case to see how it fails. You can do this by creating a list and then calling the function on the list. Fix the function by editing within the tutor.

def reverse(s):
    """Return a list that is the reverse of sequence s.

    >>> reverse([1,2,3])
    [3, 2, 1]
    """
    rs = []
    for element in s:
        rs = s + rs
    return rs

Use OK to test your code:

python ok -q reverse --local

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-centeric 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 seccesion. 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]

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

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.

More Practice

Question 6: Pythagorean Triple

Define pythagorean_triple, which takes a three numbers, a, b, and c and returns True if and only if these numbers form a Pythagorean Triplet, ie., the sum of the squares of the first two is equal to the square of the last.

def pythagorean_triple(a,b,c):
    """
    >>> pythagorean_triple(3,4,5)
    True
    >>> pythagorean_triple(3,4,6)
    False
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q pythagorean_triple --local

Question 7: Temperature Converter

Define temperature_converter, which takes a temperature in Fahrenheit f_temp and returns the same temperature in Celsius.

The equation for converting from Fahrenheit to Celsius is:

1. Temperature in Fahrenheit minus 32
2. Times 5
3. Divided by 9

An outline of the function:

 def temperature_converter(f_temp):
     """
     >>> celsius_temp1 = temperature_converter(32)
     >>> celsius_temp1
     0.0
     """
     "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q temperature_converter --local

Question 8: Largest factor

Write a function that takes an integer n greater than 1 and returns the largest integer smaller than n that evenly divides n*n-1.

Hint: To check if b evenly divides a, you can use the expression a % b == 0, which can be read as, "the remainder of dividing a by b is 0." However, it is possible to solve this problem without any if or while statements.

def largest_factor(n):
    """Return the largest factor of n*n-1 that is smaller than n.

    >>> largest_factor(4) # n*n-1 is 15; factors are 1, 3, 5, 15
    3
    >>> largest_factor(9) # n*n-1 is 80; factors are 1, 2, 4, 5, 8, 10, ...
    8
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q largest_factor --local

Optional questions: Algorithm Practice

Note: There are no tests for these questions. You can test them interactively.

Now that you have learned about call expressions and control structures, you can code an algorithm! An algorithm is a set of steps to accomplish a task. You use algorithms every day — from adding numbers by hand to getting to your next lecture.

Let's play a number guessing game with Python! Pick a number and Python will guess randomly until it guesses correctly.

All the code for this guessing game will be in hw02.py. In your terminal, start an interactive session with Python:

$ python -i hw02.py --local

The guess_random function will prompt you for a number, ask if its guess is correct (many times) and return the number of guesses Python had to make. To tell Python if its guess is correct, just enter y at the [y/n] prompt. If it's wrong, enter n. Python isn't very good at guessing yet, so if it's taking too long, you can type Ctrl-C to make it stop.

>>> guess_random()
Pick an integer between 1 and 10 (inclusive) for me to guess: 7
Is 1 your number? [y/n] n
Is 5 your number? [y/n] n
...

Randomly guessing works, but you can create an even better guessing strategy.

Question 9: Guess Linear

One weakness in the guess_random strategy is that it can repeat (incorrect) guesses. Rather than guessing wildly, let's guess numbers in increasing order.

Note: is_correct is a function that will return True if the guess matches the correct number. Feel free to reference the implementation of guess_random as you implement guess_linear.

def guess_linear():
    """Guess in increasing order and return the number of guesses."""
    prompt_for_number(LOWER, UPPER)
    num_guesses = 1
    guess = LOWER
    "*** YOUR CODE HERE ***"
    return num_guesses

The best way to test this function is by playing with it interactively. See if your algorithm does what you expect!

Question 10: Guess Binary

Challenge question. The guess_linear function can take a long time if your number is large. However, a strategy called binary search can find the correct number faster. The idea is to start in the middle of the range and after each incorrect guess ask if the guess is_too_high or too low. Either way, you can eliminate half the remaining possible guesses.

Hint: Try using the is_too_high function to implement a faster strategy. is_too_high will return True if the guess is greater than the correct number.

>>> result = is_too_high(5)
Is 5 too high? [y/n] y
>>> result
True

Hint: You may want to update other variables besides guess.

def guess_binary():
    """Return the number of attempted guesses. Implement a faster search
    algorithm that asks the user whether a guess is less than or greater than
    the correct number.

    Hint: If you know the guess is greater than the correct number, then your
    algorithm doesn't need to try numbers that are greater than guess.
    """
    prompt_for_number(LOWER, UPPER)
    num_guesses = 1
    lower, upper = LOWER, UPPER
    guess = (lower + upper) // 2
    "*** YOUR CODE HERE ***"
    return num_guesses

If you choose a number between 1 and 10, this approach should need no more than 4 guesses to find your number.

The best way to test this function is by playing it interactively. Try to think of edge cases — numbers that might cause your algorithm to do the wrong thing. If you edit the Python file while running it interactively, you will need to exit() and restart the interpreter in order for those changes to take effect.

So far, your algorithms have only had to find a number between 1 and 10. What if we expanded the possible range of numbers to be between 1 and 100? How many guesses would each algorithm make if you picked 100 to be your number?