Art students intentionally reproduce great works of art to develop their own skills and techniques. The purpose isn’t to become an imitator, but to deepen an understanding of important work and styles that came before you.

Reverse engineering algorithms and abstractions in computer science is of the same spirit! In this exercise you will implement algorithms to practice thinking algorithmically. You will gain familiarity with the names and behaviors of commonly useful functions.

Since the work you do is reproducing tried and true abstractions of the past, in the future you can and should use your language’s preferred functions and idioms instead. In this exercise we will show you how to achieve the same functionality using idiomatic Python in the future. Your function implementations may only make use of the built-in len function, and a List object’s methods append and pop.

Specifically off-limits in this exercise are the following. Making use of any of the following will result in no credit for the function you use them in:

• Cannot use the range function, must iterate using while, a counter variable, and subscription notation
• Cannot use other built-in function besides len - specifically not max, min, slice
• Cannot use slice notation in conjunction with the subscription operator
• Cannot use the List class’s + or == operators nor built-in methods beyond append

count

Given a List of int values, and an int to search for, count should return the number of times the number you are searching for appears in the List. Here is an example use case of your function once completed:

>>> count([1, 0, 1], 1)
2
>>> count([1, 1, 0], 0)
1
>>> count([110, 110, 110], 1)
0

Your implementation should not involve the creation of another List.

Setup and Implementation

1. Create the Python program file
   1. In the comp110/exercises directory create a directory named ex06_list
   2. In the comp110/exercises/ex06_list directory create a file named utils.py
2. Add in a docstring describing your file in a complete sentence, as well as an __author__ variable containing your PID as a str.
3. At the top of your file, type from typing import List. This will allow you to make use of the List type in Python.
4. Next, define a skeleton function with the following signature:
   1. Name: count
   2. Arguments: A list of integers as well as a number to search for.
   3. Returns: The counteded number of occurences of the number you are searching for.
5. Implement the count function as described above.

Testing

1. Create the Python test file in the comp110/exercises/ex06_list directory, create a file named utils_test.py
   • Notice this file is named with the suffix _test.py indicating to the PyTest framework this file should be searched for test functions.
2. Add in a standard, descriptive docstring as well as an __author__ variable containing your PID as a str.
3. Import your count function: from comp110.exercises.ex06_list.utils import count
4. Add a test function, such as:

def test_count_one() -> None:
    """Test counting a single instance of the needle in the haystack."""
    assert count([1, 1, 0, 1, 20, 100], 0) == 1

5. Use the Testing pane to search for tests and try running your test. Once it is failing, see if you can get this test to pass.
6. Add additional tests! Remember to change their function names and rediscover tests as you add them. Test functions must have unique names and their names must begin with test_. Can you think of other examples that are particularly interesting? You probably want to test what happens when the search value isn’t found at all and when it is found more than once. Your goal with testing is to prove the correctness of your implementation.

Idiomatic Python Equivalent of count

Your count function is a reproduction of a Python’s List’s built-in count method. Since it’s a method, rather than a function, notice the list it is counting comes before the dot and the search value is the sole argument to the method call.

>>> [1, 1, 0].count(1)
2
>>> [1, 1, 0].count(0)
1

all

In this exercise you will write a function named all. Given a List of ints and an int, all should return a bool indicating whether or not all the ints in the list are the same as the given int. Example usage:

>>> all([1, 2, 3], 1)
False
>>> all([1, 1, 1], 2)
False
>>> all([1, 1, 1], 1)
True

Continue by defining a skeleton function with the following signature:

1. Name: all
2. Arguments: A list of integers and an int.
3. Returns: A bool, True if all numbers match the indicated number, False otherwise or if the list is empty. This algorithm should work for a list of any length. Hint: remember you can return from inside of a loop to short-circuit its behavior and return immediately.

Testing

You will be responsible for writing tests for this function on your own. Just be sure to remember to add the all function to your import list at the top of your utils_test.py file.

Note that the assert keyword expects a boolean expression following it. You do not need to compare the return value of all with True or False. Consider these example assertions:

1. assert all([1, 1, 1], 1)
2. assert not all([1, 2, 3], 1)

Idiomatic Python Equivalent of all

There is not a directly equivalent built-in function or method for all in Python, but there are some idiomatic ways to achieve this. They involve the use of some concepts we have not arrived at yet (namely either sets or slice subscripts) so we will leave this as a future exercise.

max

Finally, you will write a function named max.

The max function is given a List of ints, max should return the largest in the List.

If the List is empty, max should result in a ValueError. We’ll show you how! Examples:

>>> max([1, 3, 2])
3
>>> max([100, 99, 98])
100
>>> max([])
ValueError: max() arg is an empty List

Define a skeleton function with the following signature:

1. Name: max
2. Argument: A list of integers.
3. Returns: An int, the largest number in the List. If the List is empty, raises a ValueError.

The body of your skeleton function can begin as such, which demonstrates how to raise an error:

def max(input: List[int]) -> int:
    raise ValueError("max() arg is an empty List")

We will discuss errors and error handling in more detail in lecture soon. To give you a working test for the case where the input list is empty, here is one you can use in your utils_test.py file. First, add the following imports to the top of your test file (notice, max was added to the list of functions imported from the utils module – don’t forget to do this!):

import pytest
from comp110.exercises.ex06_list.utils import count, all, max

Then, define this test function:

def test_max_of_empty() -> None:
    """Calling the `max` function with an empty List should raise a Value Error."""
    with pytest.raises(ValueError):
        empty_list: List[int] = []
        max(empty_list)

Rediscover tests to find this test and then it should pass based on the skeleton implementation. How exactly this test works is beyond our current place in the course but the idea is this is a pytest idiom for ensuring that this test passes if a ValueError results in the with block and fails otherwise.

Add additional tests to find the max value of the list. Note, you cannot use the built-in max function Python provides in your implementation.

Idiomatic Python Equivalent of max

Your max function is a reproduction of a Python’s built-in max function: https://docs.python.org/3/library/functions.html#max. Python’s version works on collections of many types more broadly, while yours is specifically typed to work with a list of integers.

Hand-in

Go ahead and delete any submission zips lingering around in your workspace from the previous exercise.

When you are ready to submit for grading, close out any open Python Debug Console terminals using the Trash Can and then open up a clean, new terminal.

python -m tools.submission comp110/exercises/ex06_list

This should produce a submission timestamped with the current date/time for uploading on Gradescope.