ICS 33 Fall 2024
Exercise Set 4
Due date and time: Wednesday, November 6, 11:59pm
Getting started
First of all, be sure that you've read the Reinforcement Exercises page, which explains everything you'll need to know, generally, about how the reinforcement exercises will work this quarter. Make sure you read that page before you continue with this one.
Problem 1 (3 points)
When we recently learned about Iteration, one of the things we learned is how to implement an iterator; while there are many of them built into Python and its standard library, we do sometimes have a problem that's unique enough that we'll need to implement one ourselves, so it's best that we build that ability. To that end, let's build an iterator, so we're sure we understand the mechanics of how they operate.
We say that a substring of a string is a sequence of characters that appear contiguously (and in the same order) in the original string. For example, the string '12345' has substrings such as '12', '234', and '3', but neither '24' nor '543' are substrings of '12345'.
Implement a function all_substrings, which takes a string argument and returns an iterator whose job is to return all of the non-empty substrings of the given string. The order in which the substrings are returned is not important, but they all must be included exactly once. So, for example, if we called all_substrings('123'), the result would be (in some order) '1', '2', '3', '12', '23', and '123'. (In the event that there are duplicate characters in the original string, there may be duplicate substrings in the collection returned by all_substrings, and that's fine; there's no need to detect or work around that specially.)
Because our goal here is to learn the techniques that make iteration work in Python, your iterator must be written as a class whose objects implement the iterator protocol directly.
From a performance perspective, your iterator must require only O(s) memory, where s is the length of the string passed to all_substrings, to produce all of the substrings.
Limitations
The Python standard library is entirely off-limits in this problem. Your solution must not require any module to be imported.
Also off-limits are the yield and yield from statements, as well as generators, more generally. The goal here is to get practice implementing an iterator class by hand, rather than relying on Python to implement the details for us automatically.
What to submit
Submit one Python script named problem1.py, which contains your all_substrings function, your iterator class, and any additional code (if any) necessary to make them work properly. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problem 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)
Recently, we've been exploring Generators in Python, both in terms of how to use them and how to write them. In this problem, let's focus mainly on the second of these, by writing a few generator functions with differing characteristics.
generate_range
Write a generator function named generate_range that accepts up to three positional-only arguments, whose meanings mirror those given to Python's built-in range constructor. Your function should generate a sequence of values that would be the same as the sequence of values that comprise the corresponding Python range.
>>> list(generate_range(5))
[0, 1, 2, 3, 4]
>>> list(generate_range(2, 10))
[2, 3, 4, 5, 6, 7, 8, 9]
>>> list(generate_range(2, 10, 3))
[2, 5, 8]
>>> list(generate_range(11, 1, 2))
[]
>>> list(generate_range(11, 1, -2))
[11, 9, 7, 5, 3]
You can safely assume that all specified arguments are integers, but the third argument (i.e., the range's "step") cannot be zero; if it is, a ValueError must be raised.
Do not use the built-in range function in your solution. The learning goal here is to solve the problem, rather than asking Python to solve it for you.
no_fizz_without_buzz
Write a generator function named no_fizz_without_buzz, which accepts one integer argument and generates a sequence of integers in ascending order that are at least as large as the argument, and that are neither divisible by three nor five unless they're divisible by both three and five. Include every legal Python integer that could be included in this sequence, if the given requirement is met.
We will not be willing to further clarify this requirement; that requirement is definitive, all-inclusive, and that's all there is to it, though you'll have to read and digest every word before you can fully understand what's being asked here, and part of what we're asking you to do is continue developing your abilities to read and understand these kinds of requirements without needing them to be restated. However, here are a few examples of some integers and whether they'd be included the sequence, assuming the argument was 8.
cartesian_product
Write a generator function named cartesian_product, which accepts zero or more arguments that are iterable and returns their Cartesian product. So, what's a Cartesian product? It's a sequence of tuples meeting the following requirements.
There is no requirement about the order in which the tuples are generated, as long as each is generated exactly once.
Here are a few examples of how your function is expected to work when it's finished.
>>> list(cartesian_product())
[]
>>> list(sorted(cartesian_product([1, 2, 3], [4, 5, 6])))
[(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]
>>> list(sorted(cartesian_product([1, 1], [2, 2])))
[(1, 2), (1, 2), (1, 2), (1, 2)] # Duplicates are not handled specially
>>> list(sorted(cartesian_product('BC', 'CD', 'DF')))
[('B', 'C', 'D'), ('B', 'C', 'F'), ('B', 'D', 'D'), ('B', 'D', 'F'),
('C', 'C', 'D'), ('C', 'C', 'F'), ('C', 'D', 'D'), ('C', 'D', 'F')]
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 three generator functions 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 3 (2 points)
It was no accident that we discussed Generators immediately after we explored Iteration, as you can think of generator functions and iterator classes as two different ways to serve the same need: iterating a sequence of values one at a time, while doing only enough work to obtain each value as it's needed, so that no work is done to determine values you never asked for. The two techniques are very similar, with one being essentially a superset of the other (i.e., one technique solves everything the other one does, though not the other way around). Given that, one might reasonably be led to wonder why we need both techniques.
First, which of the two techniques (generator functions or iterator classes) is a superset of the other? There's no need to justify this part of your answer; just be sure you've made clear to us which one it is. (The best way to answer this part is to write either the phrase generator functions are a superset or iterator classes are a superset.)
Now let's suppose that there's a programming language called SubPython, which is exactly the same as Python except that only the superset technique is available. Suppose, too, that you're implementing a language processor whose job is to translate Python code into SubPython code — which is to say that it needs to leave everything as-is except that it needs to convert the subset technique into the superset technique (e.g., either generator functions into iterator classes, or iterator classes into generator functions).
Your main goal in this problem is to propose a strategy for doing that, by showing one representative example of your chosen subset technique and how it would be translated into your chosen superset technique. It's up to you to decide on a code example that would best capture what would be necessary, with your goal being to keep it as simple as possible, but no simpler.
To be clear, we're not asking you to implement a translator here; we're asking you to consider what output you would expect from a hypothetical translator given certain inputs.
What to submit
Submit one PDF named problem3.pdf, which contains your answer to this question.
Problem 4 (2 points)
When we considered techniques for Using Generators in Python, we noticed that Python's standard library contains tools for manipulating both generators and iterators, such as the functions in its itertools module. One of the tools we saw was a function named itertools.islice, which provides the ability to do something that data strucutres like lists provide syntactically instead.
>>> numbers = [1, 3, 5, 7, 9, 11]
>>> numbers[2:5]
[5, 7, 9] # Lists can be sliced with slice notation
>>> import itertools
>>> list(itertools.islice(numbers, 2, 5))
[5, 7, 9] # itertools.islice can slice iterables, including lists
Interestingly, though, these two features are not equivalent to each other. Notably, for example, lists support both the slice notation [x:y] and also itertools.islice, but iterators don't; you can use itertools.islice on an iterator, but not the slice notation.
Python's designers could have allowed slice notation on iterators, though. Let's assume that it wasn't a simple oversight, and that there was a reason why they made this decision. In no more than a couple of sentences, propose a reasonable justification for this decision. Why can't we use slice notation on iterators?
What to submit
Submit one PDF named problem4.pdf, which contains your answer to this question.
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.