Lab #2: Functions

Introduction

In the previous lab, you were exposed to functions. You called functions that were provided, but you did not write any functions yourself. In this lab, you will write your own functions.

By the end of this lab, you should be able to:

  1. write simple functions and

  2. call them from the interpreter and from other functions.

The concepts required for this lab are discussed in the Introduction to Functions chapter of the textbook.

Getting started

Open up a terminal and navigate (cd) to your cmsc12100-aut-20-username directory, where username is your CNetID. Run git pull upstream master to collect the lab materials and git pull to sync with your personal repository.

Geometry

In this section you will be asked to write several functions from scratch. You will need to decide what each function requires as input and what it produces as an output.

A point in the real plane can be described by an x coordinate and a y coordinate, written mathematically as the point (x, y). A line segment can be described by two points (x1, y1) and (x2, y2). The length of a line segment can be found by computing the following mathematical formula:

\[\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\]

In this section you will create functions to compute the distance between two points and a function to compute the perimeter of a triangle. You will see how one function can be used by another.

Start by opening the file geometry.py in Visual Studio Code (VS Code). You’ll also need an ipython3 window. You can open ipython3 in a separate Linux terminal window or using the terminal mechanism in VS Code.

  1. What types can we use to describe a point in Python? What effect does the choice of type have on the number of variables we need to represent a point?

  2. Consider a function dist that takes in arguments that describe two points and returns one value that is the distance between those two points. Write the function header for the function dist. If you’re not sure how to write the header then ask for help. It is important to get this code right before you move on.

  3. After you have written the function header, write the body of the function. Be sure to return the correct value. You will need to use the function math.sqrt, which takes a float as an argument and returns its square root as a float.

  4. Verify that your code works by using dist in the interpreter with a simple example. For example, compute the distance between the points (0, 1) and (1, 0). You should get a number very close to 1.414.

  5. Repeat steps 2, 3, 4 with a new function named perimeter that takes in enough information to describe three points that define a triangle and returns the perimeter of that triangle. Do not call math.sqrt within the body of the perimeter function. You can try your function on the triangle with vertices (0, 0), (0, 1), and (1, 0). You should get a value close to 2 + math.sqrt(2) (3.414214).

Useful List Functions

Open the file list_exercises.py in an VS Code.

  1. Write a function are_any_true that takes a list of booleans as arguments and returns True if at least one of the entries in the list is True, and False otherwise. Test your code in the interpreter. Recall that you can initialize lists directly to generate test cases. For example:

    test_list = [True, True, False, True, True]

  2. Write a function add_lists that takes two lists of the same length as arguments and adds corresponding values together [a[0] + b[0], a[1] + b[1], ...]. The function should return a new list with the result of the addition. (Your code may assume that the lists are of the same length.)

    Again, test your code in the interpreter. Try out different types for the elements. What happens if the elements are integers? What happens when they are strings? What happens if the lists are of mixed types (e.g., [5, "a", 3.4])? What happens if both lists are the empty list?

  3. Write a function add_one that takes a list and adds 1 to each element in the list. This function should update the input list, not create a new one. What value is printed by the following code?

a = [1, 2, 3, 4, 5]
add_one(a)
print(a)

Abstraction practice

One of the tasks in the Loops and Lists lab was to take a list containing values in the range from 0 to M inclusive, and create a new list, let’s call it frequencies, in which the ith element contains a count of the number of times the value i occurred in the input list. That is, frequencies[i] would be a count of the number of times that the value i occurred in the original list. For example, given:

lst0 = [0, 1, 1, 3, 2, 4, 6, 1, 7, 8]

the expected result is:

[1, 3, 1, 1, 1, 0, 1, 1, 1]

The value 0 occurs once in lst0, the value 1 occurs three times in lst0, the value 5 does not occur in lst0, etc.

Here is a function that performs this task:

def compute_frequencies(lst):
   """
   Count how often each value between 0 and M (the maximum
   value in the list) occurs in the input list.

   Inputs:
     lst: list of integers between 0 and some upper bound M
       (inclusive), where M is expected to be relative small (say,
       less than 1000).

   Returns: list where the ith element is the number of times
     i occurs in lst.
   """

   # allocate space to hold the frequencies
   frequencies = [0] * (max(lst) + 1)

   for val in lst:
       frequencies[val] = frequencies[val] + 1

   return frequencies

To compute the result, we first allocate a list of zeros that is large enough to have an entry for every value between 0 and the maximum value in the list. (We use max(lst) + 1 as the size of the frequencies, rather than max(lst) to give us an entry for the largest value in the list.) And then, we walk through the values in the original list updating the appropriates entries in frequencies as we go. And finally, we return the computed list of frequencies.

Now we are going to look at a function, find_most_frequent_values that takes a list and returns a list with the value or values that occur most often in the input list. We chose to have our function return a list to handle the case of ties.

Here are some sample uses:

In [1]: import min_max

In [2]: lst0 = [0, 1, 1, 3, 2, 4, 6, 1, 7, 8]

In [3]: min_max.compute_frequencies(lst0)
Out[3]: [1, 3, 1, 1, 1, 0, 1, 1, 1]

In [4]: min_max.find_most_frequent_values(lst0)
Out[4]: [1]

In [5]: lst1 = [0, 1, 1, 3, 2, 4, 6, 1, 7, 8, 6, 6]

In [6]: min_max.compute_frequencies(lst1)
Out[6]: [1, 3, 1, 1, 1, 0, 3, 1, 1]

In [7]: min_max.find_most_frequent_values(lst1)
Out[7]: [1, 6]

In the first call, the value 1 occurs most often in lst0 and so, the result is [1]. In the second example, there is a a tie, both 1 and 6 occur three times in lst1 and so the result is [1, 6].

We will start by using compute_frequencies to determine how frequently each value occurs. Then we will determine the largest frequency and use that to find the values that occur most often. Recall that each index in the list of frequencies corresponds to a value in the range 0 to M (inclusive).

def find_most_frequent_values(lst):
    """
    Find the value or values (in the case of ties) that occur most
    frequently in the list.

    Inputs:
      lst: list of integers between 0 and some upper bound M
        (inclusive), where M is expected to be relative small
        (say, less than 1000).

    Returns: list of the int(s) that occur most frequently.
    """

    # Determine how frequently most frequent
    # value(s) occurs.
    frequencies = compute_frequencies(lst)
    max_freq = max(frequencies)

    # Find all the values that occur max_freq times
    rv = []
    for i, freq in enumerate(frequencies):
        if freq == max_freq:
            rv.append(i)

    return rv

Your first task in this part is to write a function that computes the value or values that occur least frequently. You can start by making a copy of the function find_most_frequent_values. Rename the copy find_least_frequent_values and replace the code that computes the largest frequency with code that computes the smallest non-zero frequency.

Careful: if there is a zero in the list of frequencies, calling the min() function on that list will return zero. Before finding the smallest frequency, you need to make sure you’ve filtered out the zeroes in the list of frequencies.

That said, after your modifications, the code for find_least_frequent_values should be nearly identical to the code for find_most_frequent_values.

Here are some sample uses of this function:

In [12]: lst0
Out[12]: [0, 1, 1, 3, 2, 4, 6, 1, 7, 8]

In [13]: min_max.find_least_frequent_values(lst0)
Out[13]: [0, 2, 3, 4, 6, 7, 8]

In [14]: lst1
Out[14]: [0, 1, 1, 3, 2, 4, 6, 1, 7, 8, 6, 6]

In [15]: min_max.find_least_frequent_values(lst1)
Out[15]: [0, 2, 3, 4, 7, 8]

In [16]: lst2
Out[16]: [2, 2, 2, 1, 1, 2, 2, 2]

In [17]: min_max.find_least_frequent_values(lst2)
Out[17]: [1]

Notice that many values in lst0 and lst1 occur exactly once.

Much of the code in find_most_frequent_values and find_least_frequent_values is the same and, in particular, both functions have code that finds the indices of the elements in the list that match a particular value. In the case of find_most_frequent_values, we use this code:

# Find all the values that occur max_freq times.
rv = []
for i, freq in enumerate(frequencies):
    if freq == max_freq:
        rv.append(i)

to find the indices of the elements in frequencies that match max_freq. You should have very similar code in find_least_frequent_values.

Your next task is to abstract this code into a function that can find the indices of the elements in a list that match some specified value. For example, we might want to find all the spots in the list that hold the value 2 (i.e., find all the numbers with a frequency of 2).

The work required to create this new function is as follows:

  • create a function header,

  • write a doc string,

  • copy the block of code above,

  • update the code to use the parameters instead of frequencies and max_freq,

  • update the loop variables to have names that match the more general context, and

  • add a statement to return the result.

Once you have written your function, try it out in ipython3 with some sample values.

Once you are sure it works, replace the relevant lines in find_most_frequent_values and find_least_frequent_values with calls to the your new function. Note that your implementations of these functions will still call compute_frequencies and will still compute the maximum (minimum) frequency. The for-loop and associated code, however, will be replaced with a call to your new function.

This process of abstracting a block of code into a function is something you will do over and over again as you write code for this class and in the future.

When Finished

When finished with the lab please check in your work. Assuming you are inside the lab directory, run the following commands from the Linux command-line:

git add geometry.py
git add list_exercises.py
git add min_max.py
git commit -m "Finished with lab2"
git push

No, we’re not grading your work. We just want to make sure your repository is in a clean state and that your work is saved to your repository (and to our Git server)