Homework 6

Due Tuesday 20-Feb, at 9:00pm

To start

  1. Create a folder named hw6
  2. Create a file named hw6.py (We are not providing a starter file this week.)
  3. Edit hw6.py and build the functions as described below.
  4. When you have completed and fully tested hw5, submit hw6.py to Gradescope. You may submit up to 15 times, but only your last submission counts.

Some important notes

  1. This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
  2. Do not hardcode the test cases in your solutions.
  3. Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

Limitations

Do not use sets, dictionaries, try/except, classes, or recursion this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.

A Note About Style Grading

Like in the previous assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading already started, so please use good style from now on!

A Note About Testing

There is no skeleton file provided this week, meaning that we also are not providing testcases. You should write testcases for each function. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)

Problems

  1. nondestructiveRemoveRepeats(L) [20 pts]
    Important Note: to receive any credit for this problem, you may not simply create a copy of L and then call the destructiveRemoveRepeats function below. Instead, you must create the resulting list from scratch here. Also, note that the autograder has no way to check this, so our CA's will check this manually after the hw deadline.
    Write the function nondestructiveRemoveRepeats(L), which takes a list L and nondestructively returns a new list in which any repeating elements in L are removed. For example:
    assert(nondestructiveRemoveRepeats([1, 3, 5, 3, 3, 2, 1, 7, 5]) == [1, 3, 5, 2, 7])
    Also:
    L = [1, 3, 5, 3, 3, 2, 1, 7, 5] assert(nondestructiveRemoveRepeats(L) == [1, 3, 5, 2, 7]) assert(L == [1, 3, 5, 3, 3, 2, 1, 7, 5]) # nondestructive!
    Note that the values in the resulting list occur in the order they appear in the original list, but each occurs only once in the result. Also, since this is a nondestructive function, it returns the resulting list.

  2. destructiveRemoveRepeats(L) [20 pts]
    Important Note: this is the analog of the previous important note. Here, to receive any credit for this problem, you may not simply call nondestructiveRemoveRepeats(L) and then somehow remove all the elements in L and then append the elements from that call. Instead, you must destructively modify the list as you go. Also, again, note that the autograder has no way to check this, so our TA's will check this manually after the hw deadline.
    Write the function destructiveRemoveRepeats(L), which implements the same function destructively. Thus, this function should directly modify the provided list to not have any repeating elements. Since this is a destructive function, it should not return any value at all (so, implicitly, it should return None). For example:
    L = [1, 3, 5, 3, 3, 2, 1, 7, 5] assert(destructiveRemoveRepeats(L) == None) assert(L == [1, 3, 5, 2, 7]) # destructive!

  3. multiplyPolynomials(L) [25 pts]

    We can represent a polynomial as a list of its coefficients. For example, we will represent the polynomial 2x3 + 3x2 + 4 with the list [2, 3, 0, 4].

    With this in mind, write the function multiplyPolynomials(p1, p2), which takes two lists representing polynomials as described above, and returns the list representing the polynomial that is the product of p1 and p2.

    For example, multiplyPolynomials([2, 3, 0, 4], [1, 5]) represents the problem (2x3 + 3x2 + 4)(x + 5). This equals 2x4 + 13x3 + 15x2 + 4x + 20. So the function would return [2, 13, 15, 4, 20].

    How did we find that answer? To multiply two polynomials p1 and p2, you do this:

    1. Multiply each term in p1 by each term in p2, then
    2. Collect like terms -- that is, terms which share the same exponent for x.

  4. firstNAcceptedValues(n, L) [35 pts]

    This exercise consists of a list of rules that specify which positive numbers can be included in the result. For example:

    ['x must be a multiple of 3']

    The first 6 integers that follow this rule are: [3, 6, 9, 12, 15, 18].

    We can add a second rule to the list:

    ['x must be a multiple of 3', 'x must not be a multiple of 9']

    The first 6 integers that follow these rules are: [3, 6, 12, 15, 21, 24].

    We can add two more rules:

    ['x must be a multiple of 3', 'x must not be a multiple of 9', 'x%2 must be a multiple of 2', 'x%10 must not be equal to 4']

    The first 6 integers that follow these rules are: [6, 12, 30, 42, 48, 60].

    The rules will always have 3 parts (always in this order), each with 2 options:

    1. 'x' or 'x%N', where N is a positive integer.
    2. 'must be' or 'must not be'.
    3. 'a multiple of M' or 'equal to M', where M is a non-negative integer.

    We will only test your code on valid rules.

    With this in mind, first write the helper function isAcceptedValue(x, rules), which takes a positive integer x and a list of rules, and returns True if x follows all the rules and False otherwise.

    Next, write the function firstNAcceptedValues(n, rules), which takes a positive integer n and a non-empty list of rules, and returns a list containing the first n positive integers that follow all the given rules.

    Hints:

    • Because the format is so restricted, you can check for a few specific strings to determine which kind of command each line is.
      • To tell if we are using x or x%n, just check if '%' is anywhere in the rule.
      • To check if the condition is 'must be' or 'must not be', just check if 'not' is anywhere in the rule.
      • To check if the condition is 'a multiple of' or 'equal to', just check if 'equal' is anywhere in the rule.
    • Some methods like .split() return lists, which you now know how to index into.