Harvey Mudd College
Computer Science 42
Assignment 7, Due Monday, Oct 25, by 11:59pm

Python fun!

This week introduces you to the Python programming language through a number of fun problems.  Some of you have worked with Python before, some have not, but either way we hope that you will find these problems enjoyable. 

Problem 1: The Mandelbrot Set [30 points; individual or pair]: Submitted in a file named hw7pr1.py

Because the writeup for this problem is quite long, it's on its own page.  Click here to access it...

Problem 2: Markov Text Generation [30 points; individual]: Submitted in a file named hw7pr2.py

Submit this program as hw7pr2.py on the submission server.

Your goal in this section is to write a program that is capable of "learning" English from examples of text and then generating new "meaningful" English random text all by itself! You will accomplish this goal by writing a Markov text generation algorithm.

Here's the basic idea: English is a language with a lot of structure. Words have a tendency (indeed, an obligation) to appear only in certain sequences. Grammatical rules specify legal combinations of different parts of speech. E.g., the phrase "The cat climbs the stairs" obeys a legal word sequence. "Stairs the the climbs cat", does not. Additionally, semantics (the meaning of a word or sentence) further limits possible word combinations. "The stairs climb the cat" is a perfectly legal sentence, but it doesn't make any sense and you are very unlikely to encounter this word ordering in practice.

Even without knowing the formal rules of English, or the meaning of English words, we can get an idea of what word combinations are legal simply by looking at well-formed English text and noting the combinations of words that tend to occur in practice. Then, based on our observations, we could generate new sentences by randomly selecting words according to commonly occurring sequences of these words. For example, consider the following text:

"I love roses and carnations. I hope I get roses for my birthday."

If we start by selecting the word "I", we notice that "I" may be followed by "love", "hope" and "get" with equal probability in this text. We randomly select one of these words to add to our sentence, e.g. "I get". We can repeat this process with the word "get", necessarily selecting the word "roses" as the next word. Continuing this process could yield the phrase "I get roses and carnations". Note that this is a valid English sentence, but not one that we have seen before. Other novel sentences we might have generated include "I love roses for my birthday," and "I get roses for my birthday".

More formally, the process we use to generate these sentences is called a kth-order Markov process. A kth-order Markov process is a process where the next word depends only on the previous k words. A very special case is a first-order Markov process (when k = 1) in which the next word occurs only on the previous word.

Here's what your program must do:

• Using the "main" trick (described below this list of requirements, and in class), your program will start automatically.
• Your program will begin by asking the user how many training files they will provide. (A training file is just a file containing some sample text.)
• The program then queries the user for the names of those training files, which will be read in by the program.
• Next, the user is asked to specify the value of k, the order of the Markov process.
• The program builds a dictionary of sequences of length k that appear in the text. For each sequence of length k, it associates the list of all words that can follow that sequence. For example, assume that we had just one training file with the text I like spam and I like chocolate.  I like spam a lot! If we were using k=2 then the sequences of k=2 consecutive words would be I like, like spam, spam and, and I, etc. The sequence I like would be a key in the dictionary and would be associated with the words that follow it namely: spam, chocolate, and spam. Notice that spam appears twice there. That's good! That indicates that spam is twice as likely as chocolate to appear after the pattern I like.
• The program now asks the user how many sentences they would like to have generated. The program now generates that number of random sentences and asks the user if they would like to generate sentences again.
• Each time random sentences are generated, they are generated as follows. We start with a sequence of k words which are simply the first k words in one of the training files (one of the training files is selected at random for this purpose using the random module discussed below). Then this _k_-word sequence is used to select a random next word using the Markov dictionary of valid next words. The next word should be selected at random but weighted by its probability of occuring as a next word (e.g. in the example above, spam would be twice as likely as chocolate to appear after I like).
• If your program ever encounters a _k_-word sequence that never had a word after it, it should simply start the generating process over again. (Careful, this can result in infinite loops if your training files are too small. You may wish to have a limit on how many "try agains" your program attempts.)
• For this problem, leave the punctuation at the ends of the words. Thus, the sentence "I like spam." ending in a period would look like it comprises the words I, like, and spam. where the last word is spam with a period at the end. There might be another word spam as well, but these would be treated differently!
• Each time you see a punctuation symbol (period, exclamation point, or question mark) generated, that ends one sentence.
• To use randomness in your program, you can simply import random at the top of your file. This module provides many functions. For example, if L is a list then random.choice(L) will return a randomly selected element of that list. For more documentation on random, see this page.

The "main" trick:

In order to get your python program to start automatically, you should include a function called main() that invokes the main loop of your Markov test generator.  Then include the following line, anywhere after the definition of main:

if __name__ == "__main__" : main()

This way, the main function will start automatically when you press F5 from Idle or invoke the program at the python shell.

The text you want to use is up to you. IRS documents like this one (http://www.irs.gov/newsroom/article/0,,id=159925,00.html may be good. Random scenes from Shakespeare might also strike your fancy (http://www-tech.mit.edu/Shakespeare/). Please play with your program and try using some of your own text.  You might try your Writ001 essay!

Problem 3: Mastermind [40 points; individual or pair]: Submitted in a file named hw7pr3.py

In this problem you will be implementing a "generalized" version of the Mastermind game! First, we describe the basic functionality of this program and then, at the bottom of this page, we describe some fun optional super extra bonus parts that you might wish to do for bonus credit.

The program begins "automatically": We just include the line

if __name__ == "__main__" : main()

When the game begins, the program asks the player to enter:

• The number of holes per row (this is 4 in the commercial version of the game, but it can be anything in our generalized version!)
• The number of rows (this is the number of rounds in the game—it is 10 or 12 in the commercial versions of the game, but again it can be anything here!)
• The number of colors (these will actually be consecutive integers beginning at 0—in the commercial version there are 6 colors, but it can be anything here)

Once the player has specified these values, the game commences. The program chooses a random "code"—the secret selection of colors in the holes. Remember that the colors are actually integers ranging from 0 to the number of colors specified by the user, minus one.

At each round of the game, the player is asked to guess the code—that is, to guess the color for each hole. The program then "scores" the player's guess. For each guess that is the correct color in the correct hole, the player gets one "black" point. Among the remaining guesses, each guess that is the correct color but in the wrong hole gets one "white" point. The score is simply the number of black points followed by the number of white points.

After each round of play, the game board is displayed. The displayed game board shows the rows that have been guessed so far along with their scores. Here is some sample input and output. Please follow these input/output conventions to make it easier for the grutors to evaluate your program. You may make minor cosmetic changes to this, but your input/output display should be essentially like this:

Welcome to Mastermind!
----------------------
How many holes per row shall we have? 3
How many rounds shall we have? 42
How many colors shall we have? 4
Enter your guess for round 0...
  Enter guess for hole 0: 0
  Enter guess for hole 1: 1
  Enter guess for hole 2: 2
===START BOARD===
Round 0   [0, 1, 2]   Score: 1 black and 1 white
====END BOARD====
Enter your guess for round 1...
  Enter guess for hole 0: 0
  Enter guess for hole 1: 0
  Enter guess for hole 2: 2
===START BOARD===
Round 0   [0, 1, 2]   Score: 1 black and 1 white
Round 1   [0, 0, 2]   Score: 1 black and 2 white
====END BOARD====
Enter your guess for round 2...
  Enter guess for hole 0: 0
  Enter guess for hole 1: 2
  Enter guess for hole 2: 0
You got it in 3 rounds!
Would you like to play again? n
Bye!

The game ends if the player guesses the score correctly (a win!) or the player has not succeeded at the end of the specified number of rounds. In either case, the player is asked if she/he would like to play again. If so, the process starts from the beginning, with the player being asked for the number of holes, rounds, and colors.

In addition to the functionality described above, your program must check to ensure that the player's input is valid. You may assume that the player will always enter a non-negative integer, but if the number of colors specified was 4 and the user guesses a color of 10, this is invalid and the user should be asked to re-enter the input.

Your program will be evaluated both for correctness and also for quality of design and style. Approximately half of your score on this problem will be based on following the good design principles discussed in lecture and summarized below. Here are a few guidelines to follow for design and style. We'll consider these guidelines in grading your code:

• First, think about the design of your program and lay out the functions that you'll need on paper before you do any actual programming. In particular, try to identify the separate logical parts of your program. For example, you might have a part of your program that prints the contents of the board, another part that evaluates a guess, and so forth. For each part, ask yourself what input it will require and what output it will produce. These parts can then be translated into python functions.
• Make sure that each of your python functions really encapsulates one particular well-defined task. Then, write the functions one by one. For each function, include a docstring that explains the input that the function takes, what the function is "responsible for doing", and what output it produces. If your function is more than 10 or 12 lines of code, ask yourself it makes sense to break it up into separate subfunctions. The answer may be "no"—but think about it.
• Think about your code carefully before you write it. There is usually more than one way to get a computational task done. Software takes a "short" time to write relative to the amount of time that it is used. It's worth programming slowly and making sure that the code that you write is clear, simple, and easy for you (or someone else) to go back and read and/or modify. If your code seems complicated, it probably can be rewritten in a simpler and more elegant way.
• Use comments when there is something in your code that is not self-evident. You don't need to have a comment for every line, but lines or blocks of code that do something that is not immediately obvious to the casual observer merit at least some documentation. You will find that it takes some experience to decide what is "not immediately obvious"; if in doubt, ask a professor or grutor.
• Test each function as you write it. Make sure that the function that you just wrote behaves correctly before moving on to the next function. This will potentially save you enormous amounts of time and anguish when debugging.
• Avoid global variables! debug is a notable exception, and on very rare occasions it makes sense to introduce others. In general though, it's cleaner and safer for functions to pass one another just what they need to do their jobs.
• Use descriptive function and variable names. A function name like printBoard is more descriptive than pb. Similarly, a variable name like colors or numcolors is more descriptive than c or x.

For the sake of debugging, you should have the following line at the top of your code:

debug = True # debug is True if debugging info is to be displayed, and False otherwise

In particular, if debug is True, your program should print out the computer's chosen secret random code (the sequence of colors that you are trying to guess). This will allow you to ensure that the behavior of your program is correct. Later, of course, you can set debug to False to deactivate the printing of this information.

For example, in the game shown above, here's what things might look like in debug mode:

% python mastermind.py
Welcome to Mastermind!
----------------------
How many holes per row shall we have? 3
How many rounds shall we have? 42
How many colors shall we have? 4
DEBUG MODE:  THE CODE IS [0, 2, 0]
Enter your guess for round 0...
  Enter guess for hole 0: 0
  Enter guess for hole 1: 1
  Enter guess for hole 2: 2
DEBUG MODE:  MATCH AT HOLE 0
===START BOARD===
Round 0   [0, 1, 2]   Score: 1 black and 1 white
====END BOARD====


...

• To generate a random number, include the line

  from random import *

  at the top of your file. Then, the function randint(x, y) can be used to generate a random integer in the range from x to y inclusive.
• Remember from class that all python types can be cast as strings. This is useful when printing! For example, if mylist = [1,2,3] then we can print it as part of a string as follows:

  print "My list is : " + str(mylist)

  The same can be done with integers, floating-point numbers, etc.
• To construct a list incrementally, we can use the append method. For example:

  >>> mylist = []
  >>> mylist.append(1)
  >>> mylist.append(2)
  >>> mylist
  [1, 2]
  

• Remember that a function can return several items by placing those items in a list and returning the list!

Submit your code as hw7pr3.py. Please make sure to submit your code with debug = True so that we can see the debugging information (and particularly the secret code) when testing your program.

Totally Optional Super Fun Bonus Parts! If you want more entertainment, here are several fun optional bonus parts for you to consider:

• [Up to 10 bonus points] Use python's turtle graphics package or another drawing tool to visualize the board. Note, to use turtle you will need to include the statement:
  
  from turtle import *
  
  at the top of your file and then create a new turtle object with the following line:
  
  turtle = Turtle()
  
  For this bonus problem, the user should see a graphical display of the board, the guesses, and the scoring rather than a textual representation.  
  
• [Up to 20 bonus points] Allow the player to specify two options: Option 1 is that the computer chooses the code and the player tries to guess it (what you just did above) and option 2 is that the human player chooses the code (and keeps it secret from the computer) and the computer tries to guess the code! For full bonus credit on this, your computer player must be "good". See the Mathworld web page for some references on good strategies. This problem has been studied by mathematicians and computer scientists and there is a rich body of published research on it!