List Utility FunctionsArt 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 computational thinking. 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 a limited learning experience for the function you use them in:
len - specifically not max, min, sliceList class’s + or == operators nor built-in methods beyond append
Lists.countGiven 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)
0Your implementation should not involve the creation of another List.
exercises directory create a directory named ex05exercises/ex05 directory create a file named utils.py__author__ variable assigned to your name and e-mail address..from typing import List. This will allow you to make use of the List type in Python.countcount function as described above.exercises/ex05 directory, create a file named utils_test.py
_test.py indicating to the PyTest framework this file should be searched for test functions.__author__ variable containing your PID as a str.count function: from exercises.ex05.utils import countdef test_count_one() -> None:
"""Test counting a single instance of the needle in the haystack."""
assert count([1, 1, 0, 1, 20, 100], 0) == 1test_. 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.countYour 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)
1allIn 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)
TrueContinue by defining a skeleton function with the following signature:
allbool, 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.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:
assert all([1, 1, 1], 1)assert not all([1, 2, 3], 1)allThere 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.
maxNext, 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 ListDefine a skeleton function with the following signature:
maxint, 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:
if len(input) == 0:
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!):
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)You can safely ignore the type-checking error this test will give you. The grader will not take off for it.
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.
maxYour 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.
The following exercises are extensions of those in the previous set. These utility functions continue to emphasize practice algorithmic thinking. In this exercise you will also continue testing the functions you write by writing tests which demonstrate their correctness in a variety of cases.
is_equalGiven two Lists of int values, return True if every element at every index is equal in both Lists.
>>> is_equal([1, 0, 1], [1, 0, 1])
True
>>> is_equal([1, 1, 0], [1, 0, 1]))
FalseYour implementation should not assume the lengths of each List are equal.
This concept is called deep equality. Two separate List objects on the heap may be distinct objects, such that if you changed one the other would remain the same. However, two distinct objects can be deeply equal to one another if what they are made of is equal to each other in essence.
Define a function with the following signature: 1. Name: is_equal 2. Parameters: Two lists of integers. 3. Returns: True if lists are equal, False otherwise.
Implement the is_equal function as described above.
is_equal function.is_equalYour is_equal function is a reproduction of a Python’s List’s built-in == operator when used on two List objects. Compound types, such as List and even custom ones such as those we will write soon, can define their own algorithms for operators such as == through what is called operator overloading.
>>> [1, 1, 0] == [1, 1, 0]
True
>>> [1, 1, 0] == [1, 0, 1]
FalseconcatIn this exercise you will write a function named concat. Given two Lists of ints, concat should generate a new List which contains all of the elements of the first list followed by all of the elements of the second list.
Define your function with the following signature.
concatList containing all elements of the first list, followed by all elements of the second list.concat should NOT mutate (modify) either of the arguments passed to it.
Add tests to the ex05/utils_test.py file which demonstrate the correctness of your concat function. Be sure to consider edge cases which include empty lists on either side.
is_equalPython’s List objects use operator overloading to appropriate the + operator for concatenation, just like with str values:
>>> [1, 1, 0] + [1, 1, 0]
[1, 1, 0, 1, 1, 0]Note that a new List, with the elements copied from each of the operands, results from the evaluation of concatenating two lists, just like your function implements.
subIn this exercise you will write a function named sub. Given a List of ints, a start index, and an end index (not inclusive), sub should generate a List which is a subset of the given list, between the specified start index and the end index - 1. This function should not mutate its input list.
Example usage:
>>> a_list = [10, 20, 30, 40]
>>> sub(a_list, 1, 3)
[20, 30]Next, define a skeleton function with the following signature in ex05/utils.py:
subIf the start index is negative, start from the beginning of the list. If the end index is greater than the length of the list, end with the end of the list.
If the length of the list is 0, start > len of the list or end <= 0, return the empty list.
Add tests to assert the correctness of your implementation.
subPython has a special subscription notation called slice notation related to the built-in slice function. Typically, in Python, you would achieve the results of sub with the following, an example of slice indexing:
>>> a_list = [10, 20, 30, 40]
>>> a_list[1:3]
[20, 30]spliceIn this exercise you will write a function named splice. Given a List of ints, an index, and another List of ints, splice should generate a new List. The new List should contain the Elements of the first list, with the Elements of the second list spliced in at (inserted at) the specified index. For example:
>>> splice([1, 1, 1, 1], 2, [0, 0, 0, 0])
[1, 1, 0, 0, 0, 0, 1, 1]Define a skeleton function with the following signature:
spliceint list, an int index, and another int list, where the index will be used to know where to insert the second list into the first list.List containing elements of the second list “spliced” into those of the first.Neither input list should be mutated in the above.
If the index is negative, insert the second list before the first list.
If the index is greater than the length of the first list, append the second list directly following the fist list.
Hint: You can implement splice in terms of two functions you previously implemented in this exercse rather than from scratch. You are encouraged to make use of the functions implemented earlier. Imagine how you can break down the splice process in terms of other functions written, rather than not making use of any.
There are a number of edge cases you will want to carefully test for the splice function. Think about tests for empty lists and different locations of the index in the first list.
splicePython developers would likely combine the use of the overloaded + operator and the slice subscription notation to pull off splice in a simple, single line of code. See if you can figure out how, based on the examples of these concepts in earlier idioms above, after you’ve implemented your version of splice.