ICS 33 Fall 2024, Exercise Set 5

Problem 1 (3 points)

We began our exploration of the Python Data Model recently, so it would be wise for us to begin applying our understanding of it, even if we may yet have more to learn. There are two things worth understanding about it.

What tools are available to us? In other words, what can we do to change the behavior of objects of our classes?
What tools do we actually need to use in a given circumstance? When are the defaults appropriate, so we can avoid writing (and testing) our own bespoke code?

To put those ideas into practice, write a class MultipleSequence, which represents a finite sequence of the multiples of a numeric value, meeting the following requirements.

When constructing a MultipleSequence, two arguments can be passed (only) positionally.
- The first is the length of the sequence. This must be a non-negative integer.
- The second, which is optional, is the sequence's multiplier. This can be anything numeric. When not specified, the multiplier is the integer 1.
- We can think of a MultipleSequence(5, 3) as representing the sequence 0, 3, 6, 9, 12, with 0 being the 0^th value in the sequence, 3 being the 1^st, and so on.
- Constructing a MultipleSequence must take O(1) time.
A MultipleSequence must be sized; its length is the number of values in the sequence. It must be possible to determine this in O(1) time.
A MultipleSequence must be truthy when it contains at least one value, and falsy when it contains no values. It must be possible to determine this in O(1) time.
A MultipleSequence must be indexed, meaning that we can ask for its individual values using an integer index.
- The result when given the non-negative index i is the i^th multiple in the sequence.
- Negative indexing is also required, with the same meaning that it has for Python data structures; e.g., the index -1 would be the last value in the sequence.
- It must be possible to index a MultipleSequence, using a non-negative or negative index, in O(1) time.
- Asking for a non-existent element (i.e., an index beyond the sequence's boundaries) must cause an IndexError to be raised.
It must be possible to use the in operator to check whether a value is contained within a MultipleSequence, and this must be possible in O(1) time.
A MultipleSequence must be iterable, which is to say that it's possible to iterate one (e.g., use it to drive a for loop, pass it to the list constructor, and so on). Completely iterating a sequence with n values must be possible in O(n) time and require O(1) memory.
The representation of a MultipleSequence in the Python shell must identically match the shortest Python syntax that can possibly be used to construct one that's equivalent to it. It must be possible to determine this representation in O(1) time.
A MultipleSequence must use O(1) memory (i.e., no more than a constant amount, regardless of the multiplier or how the sequence is used subsequently).

We're requiring you to write the minimum set of dunder methods that address all of the requirements above. We will not be willing or able to answer questions like "Are you requiring a __whatever__ method in my class?", because that's part of what the question is asking you to determine: What do you need, at minimum, to solve this?

Limitations

The Python standard library is entirely off-limits in this problem. Your functions must not require any module to be imported.

What to submit

Submit one Python script named problem1.py, which contains your MultipleSequence class and nothing else. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problems we're solving here.

There is no credit being offered for writing automated tests — though you certainly might want to, since that's a great way to ensure that your code works as you expect — and we'd prefer you not submit them even if you do.

Problem 2 (3 points)

This problem will ask you to implement a Python class named Collection, beginning with the following code.


class Collection:
    def __init__(self, values):
        self._values = values

You can assume that values is iterable, but otherwise will not be able to make any safe assumptions about what it is; it can be anything iterable. Given that, add code to the Collection class that meets the following requirements.

A Collection is equivalent to another Collection only when the sequence of values in both collections are equivalent (i.e., equivalent values in the same order).
A Collection is never equivalent to an object that is not a Collection.
Determining whether a Collection of n elements is equivalent to a Collection of m elements can be done in O(min(n, m)) time (i.e., proportional to the number of elements in the shorter collection). When we can determine the answer asymptotically faster than that, we should.
Determining whether two Collections are equivalent can be done with O(1) additional memory.
Collections have a natural ordering that is determined lexicographically. In other words, we can determine how two Collections are ordered with respect to one another (e.g., that one is less than another), and it's the lexicographical comparison of the elements in the two collections that determines the result.
Collections have no natural ordering with objects of any other type (e.g., we can't compare whether a Collection is less than a string, or whether a list is greater than a Collection).
When comparing two Collections for the purposes of ordering them, we can do so in O(min(n, m)) time (i.e., proportional to the number of elements in the shorter collection). When we can determine the answer asymptotically faster than that, we should.
Comparing two Collections for the purposes of ordering them can be done with O(1) additional memory.
When the comparison of values in two Collections fails (i.e., raises an exception), the comparison of the Collections fails correspondingly.

We're requiring you to write the minimum set of methods that address all of the requirements above. We will not be willing or able to answer questions like "Are you requiring a __whatever__ method in my class?", because that's part of what the question is asking you to determine: What do you need, at minimum, to solve this? Similarly, we will not be willing or able to answer questions like "Is it possible to solve this part of the problem faster than O(min(n, m)) time?" That, too, is for you to determine.

Limitations

The Python standard library is entirely off-limits in this problem. Your functions must not require any module to be imported.

What to submit

Submit one Python script named problem2.py, which contains your class and nothing else. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problems we're solving here.

Problem 3 (2 points)

Recently, we've discussed how The Python Data Model allows us to overload the meanings of operators when used on objects of our classes, followed by an exploration of Inheritance. As we learn features of a programming language, though, we don't want to stop at learning each feature in isolation; we need also to consider the ways in which they interact with each other. To do that, let's write two classes that overload operators and are related via inheritance; resolving whatever friction we encounter will help us to understand how to use these features in combination with each other.

Step 1: Write a base class

Write a Python class that meets the following requirements.

An object of the class can only be constructed by giving its constructor exactly two positional arguments.
Those arguments are stored in attributes within the object, and together comprise the entirety of the object's "meaning".
A separate method allows each of those original arguments to be obtained from the object.
An object of this class can only be equivalent to other objects of this class, only if the values in those two attributes are equivalent to those in the other object.

Furthermore, we're requiring you to write the minimum number of methods necessary to meet these requirements. (You'll need to decide which ones are truly required; that's part of what this question is asking you to consider.)

Where no particular name is necessary to meet the requirements above, you can use any name you'd like; for example, you can give your class any name you'd like (though you should tie it to some kind of real-world concept, rather than using a nonsense name like Xyz).

Step 2: Write a derived class

Write another Python class that singly inherits from the class you wrote in Step 1, meeting the following requirements.

Constructing an object of the derived class requires all of the arguments required to construct an object of the base class, plus at least one additional positional argument. (In other words, an object of the derived class stores a superset of the information stored in an object of the base class.)
Like the base class, those arguments are stored in attributes within the object, and together comprise the entirety of the object's "meaning".
Like the base class, a separate method allows each of those original arguments to be obtained from the object.
Two objects of the derived class are equivalent if and only if the values in those attributes are equivalent.
A base class object is never equivalent to a derived class object, nor vice versa.

As before, you'll need to decide what real-world concept your class models, though it should naturally be related to the concept you chose in Step 1. (In other words, there should be a reason why single inheritance is appropriate.) Otherwise, anything goes.

But there's one additional twist: Your goal is to reuse as much of the base class functionality as you can. In other words, if there's a way for code in the base class to do any part of any job without knowing that the derived class exists, it should; only the parts of a job that are relevant only to the derived class should be done in the derived class.

No further clarifications

We will not be answering questions about what code does or does not need to be in your base class or your derived class, nor anything else about what you'll need to write in this question. Part of what we're asking to do is interpret these requirements as written, derive an experiment from them, and learn something from that experiment. That learning will only happen if you do that, even if it takes a little bit of time.

The requirements above are comprehensive, though you may need to read them a couple of times and think about them a bit before plunging into writing your solution. Beyond what's written in this problem, we'll have nothing further to say about what this problem is asking, nor whether an answer is "correct" or "headed in the right direction" or "what we're looking for", while this assignment is active.

Limitations

The Python standard library is entirely off-limits in this problem. Your functions must not require any module to be imported.

What to submit

Submit one Python script named problem3.py, which contains the two classes described here and nothing else. Neither docstrings, nor comments, nor type annotations are required.

Problem 4 (1 point)

Early in your Python journey, you likely learned about the del statement. While its precise meaning can differ subtly, depending on both where and how it's used, the basic premise is always the same: Remove the ability for some object to be accessed in a way that it could previously be accessed. It may surprise you — as it did me, the first time I saw it — that it is perfectly legal to write a del statement directly in the body of a class statement (i.e., within a class statement, but not within a method or other surrounding statement within the class). But rather than being surprised by it, we should investigate its meaning, and there's no better way to start that investigation than to experiment with it.

Perform two short experiments in the Python shell that convince you of two aspects of the behavior of the del statement, documenting your results as your submission for this problem. (The goal here isn't to read the documentation and look up that behavior just to "be right"; the goal is to determine what you would need to try if you wanted to figure it out through experimentation. Not every language feature is best learned this way, but learning how to learn this way is an important skill to build, if you've never tried it before; that's the learning goal here.) Follow each experiment with a sentence or two that summarizes what you've learned from it.

What can we accomplish with a del statement in a class definition where no base class is specified?
How, if at all, does a del statement's abilities change in a class definition that specifies exactly one base class other than object?

For each experiment, assume that the Python shell begins fresh, and show the evaluation of each expression and its result, similar to how I've been doing in the Notes and Examples. Feel free to add a short sentence of commentary after each expression that you think needs it. For example, if you wanted to perform an experiment to demonstrate that global variables in a module cannot be used until a value is assigned to them, you might submit this experiment (along with a brief summary afterward, which I've not written).


>>> boo
    Traceback (most recent call last):
      ...
    NameError: name 'boo' is not defined. Did you mean 'bool'?
                # Variables don't exist until assigned a value.
>>> boo = 13
>>> boo
    13          # Variables hold the value assigned to them.

What to submit

Submit one PDF named problem4.pdf, which contains your two experiments.

Problem 5 (1 point)

As you've perhaps seen previosuly, the set and dict types built into Python both offer the ability to perform a union operation, which is denoted by the operator |.


>>> a = {1, 2, 3}
>>> b = a | {4, 5, 6}
>>> b
    {1, 2, 3, 4, 5, 6}     # The union of {1, 2, 3} and {4, 5, 6}

In our conversation about The Python Data Model, we didn't discuss every possible operator whose meaning can be overloaded; the operator used as a union operator for set and dict is one that we skipped, but it's straightforward enough to explain here, since it mirrors the conventions we saw for arithemtic operators. The one bit of confusion is that Python refers to it, in this broader context, as an "or" operator.

The dunder method def __or__(self, other) provides an implementation for the | operator.
The dunder method def __ror__(self, other) provides an implementation for the reflected | operator.
The dunder method def __ior__(self, other) provides an implementation for the augmented | operator.

Now, suppose that you were implementing the set and dict types from scratch in Python, with the goal that they behave identically (i.e., any expression involving an object of your types would produce an identical result to the one produced by the types built into Python, and would do it at the same asymptotic level of performance). It's certainly true that they would need their own implementations of the __or__ method, but what about the other variants?

Would your set and dict types implement the __ror__ method? Briefly explain why or why not.
Would your set and dict types implement the __ior__ method? Briefly explain why or why not.

What to submit

Submit one PDF named problem5.pdf, which contains your answer to these two questions.

Deliverables

In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submitted in the incorrect area.

Submit each file as-is, without putting it into a Zip file or arranging it in any other way. If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for (e.g., a text file when we asked for a PDF, even if its filename ends in .pdf), we will not be offering you any credit on the submission. There are no exceptions to this rule.

Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally.

Can I submit after the deadline?

Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 2% of your grade, with the lowest score dropped — see the Reinforcement Exercises page for details — so it's not a disaster if you miss one of them along the way.

You're responsible for making a submission in order to receive credit, which means you'll want to be sure that you've remembered to submit your work and verify in Canvas that it's been received. A later claim of having forgotten to submit your work or having misremembered the due date will not be grounds for a resubmission under any circumstances.

What do I do if Canvas adjusts my filename?

Canvas will sometimes modify your filenames when you submit them (e.g., by adding a numbering scheme like -1 or a long sequence of hexadecimal digits to its name). In general, this is fine; as long as the file you submitted has the correct name prior to submission, we'll be able to obtain it with that same name, even if Canvas adjusts it.