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:
Note: this example is 32x32 but your code must work for arbitrary sizes (N2xN2 for arbitrary N). 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 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! 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 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 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. 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]
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.
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.
Write the function bestQuiz(a), which takes a rectangular 2d list of numbers that represents a gradebook, where each column represents a quiz, and each row represents a student, and each value represents that student’s score on that quiz (except -1 indicates the student did not take the quiz). For example:
a = [ [ 88, 80, 91 ],
[ 68, 100, -1 ]
]
This list indicates that student0 scored 88 on quiz0, 80 on quiz1, and 91 on quiz2. Also, student1 scored 68 on quiz0, 100 on quiz1, and did not take quiz2. The function returns the quiz with the highest average. In this case, quiz0 average is 78, quiz1 average is 90, and quiz2 average is 91 (since we ignore the -1). Thus, quiz2 is the best, and so the function returns 2 in this case. You are not responsible for malformed input, except you should return None if there are no quizzes. Also, resolve ties in favor of the lower quiz number.
Background: Say we have a 2d list like so:
flightCosts = [
[ "Atlanta", "Boston", "Chicago", "Denver" ],
[ 0 , 125 , 230 , 300 ], # to Atlanta
[ 135 , 0 , 130 , 350 ], # to Boston
[ 200 , 130 , 0 , 210 ], # to Chicago
[ 270 , 330 , 220 , 0 ], # to Denver
]
The first row of this table lists the names of several cities, and the rest of the table lists the costs in US Dollars to fly between these cities. Each row represents a different destination city. For example, the table indicates that it costs $350 to fly from Denver to Boston and $330 to fly the other way from Boston to Denver. Consider this: if we are flying from Denver to Boston, can we do better than that $350 price if we are ok with flying through one connecting city? Well, Denver to Chicago costs $210, and Chicago to Boston costs $130, so by flying through Chicago the total cost is $340. So, yes, we can!
With this in mind, write the function bestConnection(flightCosts) that takes a table such as the one above and returns information about the best possible connection (that is, the one-stop connection that saves the most money over flying non-stop between any two cities). Your function should return the tuple (fromCity, toCity, connectingCity, nonstopCost, costWithConnection). Resolve ties in favor of the first fromCity alphabetically (and case-insensitively), and if still tied, in favor of the first toCity alphabetically. Note that the city names in the first row may not be sorted (even though they are sorted in the example above).
Hint: in response to some questions about this, your function finds the single best connection, the one that saves the most money over the non-stop flight, among every fromCity, every toCity, using every connectingCity.
Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:
d["fred"] = set(["wilma", "betty", "barney", "bam-bam"])
d["wilma"] = set(["fred", "betty", "dino"])
With this in mind, write the function friendsOfFriends(d) that takes such a dictionary mapping people to sets of friends and returns a new dictionary mapping all the same people to sets of their friends of friends. For example, since wilma is a friend of fred, and dino is a friend of wilma, dino is a friend-of-friend of fred. This set should exclude any direct friends, so even though betty is also a friend of wilma, betty does not count as a friend-of-friend of fred (since she is simply a friend of fred). Thus, in this example, if fof = friendsOfFriends(d), then fof["fred"] is a set containing just "dino" and fof["wilma"] is a set containing both "barney" and "bam-bam". Also, do not include anyone either in their own set of friends or their own set of friends-of-friends.
Note: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary. Also, do not worry about friends-of-friends-of-friends.