15-110 Fall 2010 Homework 6

Due Friday, October 15, at 10pm (no late submissions accepted!)

Note: to do this homework, you should download Homework6.zip, then unzip it, edit the files, rezip, and submit that zipped file to Autolab.

Read these instructions first!

· Do not change any file names!  Each problem that includes a changed file name will be docked a 50% penalty.

· Include your name, AndrewID, and section clearly on the top of each file in your assignment.

· Place all your solutions in a single file ZIP file (extension.zip). Once again, start with Homework6.zip. No other file formats will be accepted. You need to start by downloading a ZIP file that contains a template (a file ending in .py) for each problem in this homework.

· Show your work. Correct answers without supporting calculations will not receive full credit.

· How to submit:

1. Start at the course web site (http://www.cs.cmu.edu/~110)
2. Select the Autolab link
3. Select the Hw6 link
4. Select the Submit link
5. Click on the "Choose File" button
6. Find your Hw6 file that you are submitting
7. Click on the "Upload" button
8. If it worked, you will see this text: Submission Accepted.

Your submission is not completed until you see that text!!!

Once again: Late submissions will be rejected.

Log

We want to gauge how much time you are spending in each homework and how you are using your resources. This week we are going to record your answers using an online survey. An email with the details will be sent to you.

Problem 1:  mostFrequentWord (30 points)

Write a function, mostFrequentWord(text), that takes a string containing perhaps a large amount of text and returns the most frequent word in that text (in uppercase).  You must use this approach:  first, convert the text to uppercase using text.upper().  Then, using a well-named helper function that you must also write, convert the uppercase text string into a list of individual words in the text.  You should assume that words only contain letters, so you should ignore all non-letters, and all words are separated by at least one space (or newline).  So you would convert "This is fun!" into "THIS IS FUN!" and then into ["THIS", "IS", "FUN"].  Next, sort this list using list.sort().  Then, iterate over the sorted list, counting how many times each word occurs in succession, and returning the word that occurs the most often, with ties going to the first word alphabetically.  Note:  You may not use the string.split() method in your solution.
Hint:  Apostrophes are not letters, so they are ignored.  So mostFrequentWord("It's on its last legs") first converts the input to the list ["ITS", "ON", "ITS", "LAST", "LEGS"] (the apostrophe in the first word is gone!), and then returns "ITS", as that word occurs twice in the input.

Problem 2:  mastermindScore (30 points)

This problem involves the game Mastermind.  First, read the top part (through Gamplay and Rules) of the Wikipedia page on Mastermind so we can agree on the rules.  The basic idea is that one player (the computer in our example) randomly chooses a code, which is a row of 4 pegs, each chosen from among 6 colors (with duplicate colors allowed).  The code is hidden from the other player (the human in our example).  The second player tries to guess the code.  A guess is also a row of 4 pegs, each also from among the same 6 colors.  After each guess, the first player reveals some information about the guess -- specifically, how many pegs in the guess matched exactly (same color, same position), and how many matched partially (same color, but a different position).  Each peg in the code can match at most one peg in the guess.  Based on this information, the second player guesses repeatedly until finally cracking the code (or running out of turns).  Note that in our version, we will use the integers from 1 to 6 to represent the 6 different "colors".  Also, we will represent the 4-peg code and each 4-peg guess as a list of length 4, containing 4 integers from 1 to 6 (each representing a "color").

With this description in mind, write the function mastermindScore(code, guess), which takes two lists of length 4, a code and a guess as just described, and returns a new list of length 2 containing the score for the given guess.  The first value in the score is the number of exact matches (matching both color and position).  The second value is the number of partial matches (matching color but not position).  A given value in the code can only match one value in the guess.  Read the Wikipedia page carefully to understand this process.  For example:
  mastermindScore([3,4,5,6], [3,3,4,6]) returns [2,1]
The first and last guesses (3 and 6) are exact matches, hence the 2 in the result.  The 4 is a partial match (right color, wrong location), hence the 1 in the result.  Note that the second 3 in the guess does not count as a partial match, because there is only one 3 in the code and it was already matched against the first 3.  Your function may ignore the case where either the code or the guess is illegal (that is, it may assume both are lists of length 4 containing only values from 1 to 6).

Problem 3:  isLegalSudoku (30 points)

This problem involves the game Sudoku.  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 9 3-by-3 subregions as "blocks".  The following figure shows each of the 9 blocks highlighted in a different color:

For our purposes, we will number the blocks from 0 to 8, with block 0 in the top-left (in light blue in the figure), moving across and then down (so 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 8, the left column as column 0, and the right column as column 8.

A Sudoku is in a legal state if all 81 cells are either blank or contain a single digit from 1 to 9 (inclusive), and if each digit from 1 to 9 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 a 9x9 2d list of integers, where 0 indicates that a given cell is blank.  For example, here is how we would represent the 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, 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.  You may assume the board is a 9x9 list, and also that every element in the list is an integer (but you may not assume that all the integers are in the proper range of 0 to 9 -- if a board contains an out-of-range integer, then it is not a legal Sudoku board).

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:

3A)  [10pts]   areLegalValues(values)
This function takes a 1d list of values, which you can assume is of length 9 and contains only integers (but you may not assume the integers are in any particular range).  These values may be taken from any given row, column, or block in a Sudoko board.  The function returns True if the values are legal:  that is, if every value is a single digit (between 0 and 9, inclusive), and if each digit from 1 to 9 occurs at most once in the given list.  Note that this function does not take a Sudoku board, but only a list of values that presumably have been extracted from some Sudoku board.

3B)  [5pts]   isLegalRow(board, row)
This function takes a Sudoku board and a row.  You may assume the board is a 9x9 2d list of integers and that the row is an integer (but you may not assume the integers are in any particular range).  The function returns True if the given row in the given board is legal (where row 0 is the top row and row 8 is the bottom row), and False otherwise.  To do this, your function must create a 1d list of length 9 holding the values from the given row, and then provide these values to the areLegalValues function you previously wrote.

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

3D)  [5pts]   isLegalBlock(board, block)
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 9 holding the values from the given block, and then provide these values to the areLegalValues function you previously wrote.

3E)  [5pts]   isLegalSudoku(board)

Finally, this function takes a Sudoku board (which you may assume is a 9x9 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.

Problem 4: Mystery code (10 points)

This week's mystery code problems are somewhat different than in past assignments.  In the zip folder, you will find the file mysteryCode1.py.  This contains a complete Mastermind game with a (not too elegant, but functional) console-based user interface.  Actually, the game is almost complete -- it is lacking the mastermindScore function that you wrote in Part 2 of this assignment.  So, to do this problem, first complete Part 2 and then replace the mastermindScore function in the mysteryCode1.py file with a copy of the one you wrote in Part 2 (along with any necessary helper functions).  Next, run the code and play the game to get some ideas of what the code is doing.  Next, study the code, trying to understand the general design of the program.  Finally, find the functions named mystery1A, mystery1B, and mystery1C.  These are the mystery functions which you must describe.  Place each of your answers in a comment immediately above each mystery function.  As usual, do not say what these functions do line-by-line (no credit for that), but rather describe what they do at a high level, in a few words of plain English.  Note that the mystery functions are real functions that serve an important role in the given implementation.  Your task here is to identify and describe that role.

You will also find the file mysteryCode2.py.  This contains a near-complete implementation of Sudoku, missing only the isLegalSudoku function (and its helper functions) that you wrote in Part 3 above.  So add that function (and its helper functions) to the mysteryCode2.py file, then run the program and study it, and finally find the functions named mystery2A and mystery2B, and describe these functions in comments just above them.

In total, there are 5 mystery functions, worth 2 points each.

Bonus/Optional:

Problem 5: Bonus/Optional:  Generate and Solve Simple Sudokus (5 points)

We will define a "simple" Sudoku as one that can be solved by repeatedly applying this one rule:  find a row, column, or block that is missing exactly one value, and fill in that value (which,of course, you can easily determine in this case).

5A)  [3pts] solveSimpleSudoku(board)

With this definition in mind, write the function solveSimpleSudoku(board).  This function takes a Sudoku board which is guaranteed to be a simple Sudoku as just defined.  It does not modify the board, but returns a series of moves required to solve the board.  The moves are returned in a list in the order they must be applied.  Each move itself is also a list, where the first element is the row, the second element is the column, and the third element is the value (from 1 to 9) to place at the given row,col location on the board.  So [3, 5, 2] represents the move of playing the value 2 in row 3, column 5.

5B)  [2pts] generateSimpleSudoku(difficulty)

Write a the function generateSimpleSudoku that takes a difficulty level (a float from 0.0 for low to 1.0 for high), and returns a randomly-generated Simple Sudoku (as a 9x9 2d list of integers) of the given difficulty level.  Your result must be a Simple Sudoku.  As for the difficulty level, you are free to interpret that as you wish, except that as the value goes up, the games you generate must in general require more steps to solve.  Of course, these are all "simple", so they won't get "harder" in some sense, but they will at least require more steps.  Hint:  It may help to start from a solved Sudoku and work backwards.  In that case, you can receive full credit if you hardcode those solved Sudokus from which you generate your Simple Sudokus.