EX04 - `list` Utility Functions

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 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 no credit for the function you use them in:

• 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 in operator of Python
• Cannot use the list class’s + or == operators nor built-in methods beyond append and pop
  • Note: You can use + and == for individual elements, just not entire lists.

Assignment Outline

• all (Level: Novice) – 30 Points Autograded
• is_equal (Level: Advanced) – 35 Points Autograded
• max (On Your Own) – 15 Points Autograded
• Style, Linting, Typing – 20 Points Autograded

General Notes:

• You are not required to implement a main function for this exercise. However, it may be helpful to have one to make test function calls with lists you construct.
• The grader will evaluate your code by importing your functions and calling them with our own chosen list inputs. You do not need to worry about generating lists for each of your functions to work with. These will be passed in as parameters.
• Writing unit tests (as discussed in Tuesday’s lecture) is another great way to test that your functions are working as expected!

0. Pull the skeleton code

You will find the starter files needed by “pulling” from the course workspace repository. Before beginning, be sure to:

0. Be sure you are in your course workspace. Open the file explorer and you should see your work for the course. If you do not, open your course workspace through File > Open Recent.
1. Open the Source Control View by clicking the 3-node (circles) graph (connected by lines) icon in your sidebar or opening the command palatte and searching for Source Control.
2. Click the Ellipses in the Source Control pane and select “Pull” from the drop-down menu. This will begin the pulling process from the course repository. It should silently succeed.
3. Return to the File Explorer pane and open the exercises directory. You should see it now contains another directory named ex04. If you expand that directory, you should see the starter file for the three functions you’ll be writing.
4. If you do not see the ex04 directory, try once more but selecting "Pull From" and select upstream in step 2.

1. all – 30 Points

This is the first function you will write in utils.py. The other two functions will also be defined in this file.

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.

2. is_equal – 35 Points

Given 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]))
False

Your 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.

3. max ON YOUR OWN – 15 Points

Next, 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:
    if len(input) == 0:
        raise ValueError("max() arg is an empty List")

4. Make a Backup Checkpoint “Commit”

As you make progress on this exercise, making backups is encouraged.

1. Open the Source Control panel (Command Palette: “Show SCM” or click the icon with three circles and lines on the activity panel).
2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
3. Move your mouse’s cursor over the word Changes and notice the + symbol that appears. Click that plus symbol to add all changes to the next backup. You will now see the files listed under “Staged Changes”.
   • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
4. In the Message box, give a brief description of what you’ve changed and are backing up. This will help you find a specific backup (called a “commit”) if needed. In this case a message such as, “Progress on Exercise 3” will suffice.
5. Press the Check icon to make a Commit (a version) of your work.
6. Finally, press the Ellipses icon (…), look for “Pull/Push” submenu, and select “Push to…”, and in the dropdown select your backup repository.

5. Submit to Gradescope for Grading

Login to Gradescope and select the assignment named “EX04 - Lists.”. You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to Visual Studio Code.

If you do not see a Terminal at the bottom of your screen, open the Command Palette and search for “View: Toggle Integrated Terminal”.

Type the following command (all on a single line):

python -m tools.submission exercises/ex04

In the file explorer pane, look to find the zip file named “21.mm.dd-hh.mm-exercises-ex04.zip”. The “mm”, “dd”, and so on, are timestamps with the current month, day, hour, minute. If you right click on this file and select “Reveal in File Explorer” on Windows or “Reveal in Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.

Autograding will take a few moments to complete. If there are issues reported, you are encouraged to try and resolve them and resubmit. If for any reason you aren’t receiving full credit and aren’t sure what to try next, come give us a visit in office hours!