Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a list of the most common names, in alphabetical order (actually, in whatever order sorted() uses). So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the list ["Aaron", "Jane"]. If the list is empty, return None. Also, treat names case sensitively, so "Jane" and "JANE" are different names.
Write the function areaOfPolygon that takes a list of (x,y) points that are guaranteed to be in either clockwise or counter-clockwise order around a polygon, and returns the area of that polygon, as described here. For example (taken from that text), areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]) returns 45.5 (at least the result is almostEqual to 45.5).
Write the function linearRegression that takes a list of (x,y) points and finds the line of best fit through those points. Specifically, your function should return a triple of floats (a,b,r) such that y = ax+b is the line of best fit through the given points and r is the correlation coefficient as explained here (and yes, you must follow this exact approach). For example (taken from the text), linearRegression([(1,3), (2,5), (4,8)]) should return a triple of 3 values approximately equal to (1.6429, 1.5, 0.9972), indicating that the line of best fit is y = 1.6429x + 1.5, with a correlation coefficient of 0.9972 (so it’s a really good fit, too). Note that the result is approximately equal to these values. We'll use a large-ish epsilon as noted above. Also note: the notes we refer you to do not discuss the meaning of the sign of r, so just return the absolute value |r|. And: you may ignore the case of a vertical line in your linearRegression code (and you may also ignore that in your linearRegression_requires function).
This problem involves the game Sudoku, though we will generalize it to the N2xN2 case, where N is a positive integer (and not just the 32x32 case which is most commonly played). First, read the top part (up to History) of the Wikipedia page on Sudoku so we can agree on the rules. As 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 9 blocks in a 32x32 puzzle highlighted in a different color:
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 (in light blue in the figure), moving across and then down (so, in the figure, block 1 is yellow, block 2 is maroon, block 3 is red, block 4 is pink, block 5 is gray, block 6 is tan, block 7 is green, and block 8 is sky blue). 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 or contain a single digit from 1 to N2 (inclusive), and if each digit 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 the function isLegalSudoku(board), which takes a Sudoku board (a 2d list of integers), and returns True if it is a legal (if perhaps not fully solved) board, and False otherwise. Your contract should require that the board is an N2xN2 list for some positive integer N, and also that every element in the list is an integer between 0 and N2, inclusive. You can ensure little more than that the answer is a boolean.
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! So you should solve the problem by writing the following functions in the order given:
areLegalValues(values) [5 pts]
This function takes a 1d list of values, which you should require to be of length N2 for some positive integer N and should contain only integers in the range 0 to N2 (inclusive). These values may be extracted from any given row, column, or block in a Sudoko 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). Note that this function does not take a 2d Sudoku board, but only a 1d list of values that presumably have been extracted from some Sudoku board.
isLegalRow(board, row) [5 pts]
This function takes a Sudoku board and a row number. You should require that the board is an N2xN2 2d list of integers, all in the range 0 to N2 (inclusive), and that the row number is an integer in the range 0 to (N2-1) (inclusive). 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.)
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.
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.
isLegalSudoku(board)
[5 pts]
Finally, 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? Seriously, this exercise is a very clear demonstration of the principle of top-down design and function decomposition.
Finally, 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? Seriously, this exercise is a very clear demonstration of the principle of top-down design and function decomposition.
You must write contracts using @contract (so include the gray code at the top of your hw4.py file) with requires and ensures functions for every required function (but not any extra helper functions you might write). We will autograde your precondition (requires) and postcondition (ensures) functions separately.
Q: So for mostCommonName, we’d define these functions:
def mostCommonName_requires(nameList)
and
def mostCommonName_ensures(result, nameList)?
A: Yes, that’s right.
Q: How clever do we have to be in our requires and ensures functions?
A: This week, not very. Mainly, you have to require and ensure the types of the parameters and the results, but nothing so much about the specific values. For example, the requires for the areaOfPolygon does not have to check for clockwise or counterclockwise. But it does have to verify that the parameter is indeed a list, and every element is a pair of numbers (integers, longs, or floats). As for the ensures of the areaOfPolygon, you do not have to ensure the answer is correct (how would you do that, besides writing an entirely separate areaOfPolygon function, which is of course absurd!). But you do have to ensure that the answer is a number, and then a non-negative number. That’s good enough.
Q: Do we have to use loop invariants?
A: No, that would be optional this week.
Q: for requires and ensure functions, do we need to write test functions for those functions?
A: No. You may, but it’s not required.
Q: Do we have to write contracts for all 5 required functions in the Sudoku problem?
A: Yes. They'll most likely share some logic, though, so you may want to write some helper functions for them.
Q: Do we have to write contracts for any other helper functions we might write?
A: No.
Q: In areaOfPolygon, wouldn't our requires test have to check that at least 3 points are in the list, and that the points are not vertical?
A: Yes, but seeing as we are easing our way into contracts, we'll not autograde for those cases. We'll focus for now just on the right types of parameters. So you have to confirm it's a list, and then each element in the list is a pair of numbers. That's it.
Q: Similarly, in mostCommonName, does our requires check have to check for empty strings for names?
A: Again, it should, but this week the autograder will just test if you are verifying that it is indeed a list and that every element in the list is a string.
The goal here is to get you thinking carefully about the preconditions and postconditions of a function, and to write contract code that enforces those conditions at runtime, and then in an autogradeable way. But it’s not to be onerous and to squeeze the fun out of programming. Let’s hope we find that sweet spot!
Write the function solveSudoku, which takes a 2d list representing a sudoku board and returns a new 2d list that is the solution to that puzzle. Note: you may not use backtracking (basically, the guess-and-check approach) or recursion or stacks in your solution. Most of you presumably do not know what that means, so that’s fine! Just use techniques we have already covered in this course. In particular, try to solve it the way you would without a program. And you can get partial credit here. We’ll first test it with really simple boards (say, with just one number missing), and get increasingly complex (for increasing credit) from there. Have fun!