Homework 3

Due Tuesday 31-Jan, at 10:00pm

To start

  1. Create a folder named ‘hw3’
  2. Download hw3.py to that folder
  3. Edit hw3.py and modify the functions as required
  4. When you have completed and fully tested hw3, submit hw3.py to Gradescope. For this hw, 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. After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
  3. There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
  4. Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
  5. Do not hardcode the test cases in your solutions.
  6. The starter hw3.py file includes test functions to help you test on your own before you submit to Gradescope. When you run your file, problems will be tested in order. If you wish to temporarily bypass specific tests (say, because you have not yet completed some functions), you can comment out individual test function calls at the bottom of your file in main(). However, be sure to uncomment and test everything together before you submit! Ask a CA if you need help with this.
  7. 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 convert numbers to strings, use string indexing 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

Starting with this 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 starts this week, so please use good style from now on!

A Note About Testing

You will notice that the skeleton file only includes testcases for some of the functions you are writing. You should write testcases for the others. (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. removeOdds(L) [10 pts]
    Write the function removeOdds(L), which takes a list L and returns a new list in which any odd integer elements in L are removed. For example:
    assert(removeOdds([1, 3, 5, 4, 3, 2, 1, 7, 5]) == [4,2])
    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.

  2. maxProfit(prices) [15 pts]
    Write the function maxProfit(prices) which takes a list prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell it. The function should return the maximum profit you can be achieved from any buy-sell trade. If no profit can be achieved, the function should return 0. For example, maxProfit([7,1,5,3,6,4]) returns 5 because the best possible trade is to buy on day 1 (price = 1) and sell on day 4 (price = 6), thus the maximum profit is 6-1 = 5. Note that buying on day 1 and selling on day 0 is not allowed because you must buy before you sell. maxProfit([4,3,2,1]) should return 0 because the stock prices are declining and any buy-sell trade would generate losses.

  3. nondestructiveRemoveRepeats(L) [15 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.

  4. destructiveRemoveRepeats(L) [15 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!

  5. averageWithPolicy(scores) [20 pts]

    Consider the following excerpt from a course syllabus:
    In order to reward improvement, I will replace one quiz score that is immediately followed by two higher scores. So, if you have a quiz that goes very badly, but your next two quizzes are each better than that bad quiz, I will replace that low quiz with the higher of the two scores immediately following it. If you have multiple "bad" quizzes that meet the criteria, I will replace the one that maximizes your point gain.

    Write the non-destructive function averageWithPolicy(scores) which takes as an argument a list of scores and returns the average of those scores after applying this policy.

    Consider the following examples:

    assert(averageWithPolicy([42, 20, 40, 35, 50, 65]) == 47.0) assert(averageWithPolicy([25, 30, 20, 45, 40, 60, 70, 80, 90, 100]) == 59.0)

    The first example is 47 because the quiz to be replaced is the 35, and it will be replaced by a 65. That means we are finding the average of [42, 20, 40, 65, 50, 65]

    The second example is 59 because the quiz to be replaced is the 40, and it will be replaced by a 70. That means we are finding the average of [25, 30, 20, 45, 70, 60, 70, 80, 90, 100]

    Hint: You don’t actually need to find and replace anything in the list. Instead, you just need to find the largest difference among all candidates that meet the "lower before two higher" criteria. I recommend you create a helper function to do that.


  6. Code-Writing: Sudoku Logic [25 pts]
    This problem involves the game Sudoku, a game which is played on a 32x32 grid, though we will generalize it to the N2xN2 case, where N is a positive integer. First, read the top part (up to History) of the Wikipedia page on Sudoku so we can agree on the rules. For terminology, we will refer to each of the N2 different N-by-N sub-regions as "blocks". The following figure shows each of the 4 blocks in a 22x22 completed puzzle highlighted in a different color:



    While the next example shows the blocks of a 32x32 incomplete puzzle:



    For our purposes, we will number the blocks from 0 to N2-1 (hence, 0 to 8 in the figure), with block 0 in the top-left (red), moving across and then down (so, in the figure, block 1 is orange, block 2 is yellow, block 3 is green, block 4 is blue, block 5 is purple, block 6 is gray, block 7 is brown, and block 8 is tan). We will refer to the top row as row 0, the bottom row as row (N2-1), the left column as column 0, and the right column as column (N2-1).

    A Sudoku is in a legal state if all N4 cells are either blank (0) or contain a single integer from 1 to N2 (inclusive), and if each integer from 1 to N2 occurs at most once in each row, each column, and each block. A Sudoku is solved if it is in a legal state and contains no blanks.

    We will represent a Sudoku board as an N2xN2 2d list of integers, where 0 indicates that a given cell is blank. For example, here is how we would represent the 32x32 Sudoku board in the figure above:

    [
  [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ],
  [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
  [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ],
  [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ],
  [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ],
  [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ],
  [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ],
  [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ],
  [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ]
]

    With this description in mind, your task is to write some functions to indicate if a given Sudoku board is legal. To make this problem more approachable, we are providing a specific design for you to follow. And to make the problem more gradeable, we are requiring that you follow the design! You should solve the problem by writing the following functions in the order given:

    1. areLegalValues(values) [5 pts]
      This function takes a 1d list of values, which you should verify is of length N2 for some positive integer N and contains only integers in the range 0 to N2 (inclusive). These values may be extracted from any given row, column, or block in a Sudoku board (and, in fact, that is exactly what the next few functions will do -- they will each call this helper function). The function returns True if the values are legal: that is, if every value is an integer between 0 and N2, inclusive, and if each integer from 1 to N2 occurs at most once in the given list (0 may be repeated, of course); otherwise, it returns False. Note that this function does not take a 2d Sudoku board, but only a 1d list of values that may or may not have been extracted from some Sudoku board. Also, note that this function must be non-destructive.

    2. isLegalRow(board, row) [5 pts]
      This function takes a Sudoku board and a row number. The function returns True if the given row in the given board is legal (where row 0 is the top row and row (N2-1) is the bottom row), and False otherwise. To do this, your function must create a 1d list of length N2 holding the values from the given row, and then provide these values to the areLegalValues function you previously wrote. (Actually, because areLegalValues is non-destructive, you do not have to copy the row; you may use an alias.)

    3. isLegalCol(board, col) [5 pts]
      This function works just like the isLegalRow function, only for columns, where column 0 is the leftmost column and column (N2-1) is the rightmost column. Similarly to isLegalRow, this function must create a 1d list of length N2 holding the values from the given column, and then provide these values to the areLegalValues function you previously wrote.

    4. isLegalBlock(board, block) [5 pts]
      This function works just like the isLegalRow function, only for blocks, where block 0 is the left-top block, and block numbers proceed across and then down, as described earlier. Similarly to isLegalRow and isLegalCol, this function must create a 1d list of length N2 holding the values from the given block, and then provide these values to the areLegalValues function you previously wrote. Note that getting the values from a block is much harder than getting the values from a row or col. You'll need to do a bit of math to find the starting row and col for each block based on the block's number.

    5. isLegalSudoku(board) [5 pts]
      This function takes a Sudoku board (which you may assume is a N2xN2 2d list of integers), and returns True if the board is legal, as described above. To do this, your function must call isLegalRow over every row, isLegalCol over every column, and isLegalBlock over every block. See how helpful those helper functions are?