Evil Hangman

Normally in hangman, a word is selected that the player tries to guess one letter at a time. If the letter is in the word, all occurrences of the letter are revealed to the player. If the letter is not in the word, the player receives a penalty point. The game proceeds until the player either guesses the entire word or the penalty points reach a morbid threshold. That game is a little easy, if you have an effective strategy. You are going to create a version of hangman that cheats. It doesn't pick the word at the beginning, but rather in response to player guesses.

Setup

Create a directory assignment10 under assignments in your cs170 directory. All code for the assignment should be stored in this directory.

cd ~/cs170/assignments
mkdir assignment10 
cd assignment10

Details

You are going to create a command line version of hangman. Instead of picking a word at the beginning, like a typical game of hangman, a whole list of words are chosen. As the player makes guesses, you are going to whittle the list of words down, until either the player exhausts all of their guesses or they narrow down the list of possible words to just a single word.

Your program will read in a file of words, where the file name is specified to your program through an input statement. The user should then be allowed to pick how long of a word they would like to guess. Your program should read through the entire file of words, and add all of the words of the appropriate length to a linked list. This is now a list of all of the words your program could chose from, and still have a valid hangman game.

You are going to allow the user to make guesses at letters that could appear in the word specified. Remember that for a hangman game the user is going to have a limited number of guesses they can make. When the user makes a guess, your program should display whether their guessed letter appeared in their "word," as well as a list of all guesses made by the user. When the user makes a guess, you program is going to find the largest set of words that makes that guess still valid. It is going to do this by computing word families.

A word family is a set of words that have a specific letter in the same locations. For example, consider the following word list:

boot boon pole bone hoot

There are two different word families for the letter O. One family is _ O O _, which are words that contain O as the second and third letters (boot, boon, and hoot). The other family is _ O _ _, words that contain o as the second letter (pole and bone). For words of length 4, there are a maximum of \(2^{4+1}\) possible word families:

____, ___o, __o_, __oo, _o__, _o_o, _oo_, _ooo, o___, o__o, o_o_,
o_oo, oo__, oo_o, ooo_, oooo

In order to make the game as hard as possible, you want to keep the length of the linked list of words as large as possible. Every time the player guesses a letter, the program should compute the number of words in each word family, and pick the family with the largest size. You need to remove any word that does not belong to this largest family from the list. The word family also defines the feedback to the user: If the user guessed 'o' for the above word list, the program would determine that the _ O O _ family was the largest, which means you inform the user that their word has two o's in the middle locations of their word.

Pseudo Code

Word Family

One of the challenges you are going to face is to figure out how to determine what word family a given word belongs to. As such, you will want to define a function compute_word_family(word, letter_guess), which returns a representation of the word family word belongs to as far a guess is concerned.

For Monday, March. 23^th, I want you to turn in (on paper!) pseudo code for the word family function, with 3 test cases that demonstrate that you understand how the code should operate. You will have to come up with your own encoding scheme for this portion as well, so you might want to think about how you will use this function in your program as well.

After Monday, I will not answer any questions about how to determine what word family a word belongs to. Figure this part out this weekend! That means I will not answer these questions on Thursday night!!!!!!!!

Submission

You are required to submit a tar file to http://inquire.roanoke.edu/. On inquire, there is a link for Assignment 10. You can create a tar file by issuing the following commands:

cd ~/cs170/assignments
tar czvf assignment10.tgz assignment10/

"Hacker" Prompt

1. Graphics: Once again, I have assigned a project that doesn't require a graphical component. However, If you are strongly desiring one, you can easily create one. Look at the documentation for the ttk.Entry widget, to see how to handle getting user input through the tk interface. At the very least, you should be able to replicate the above program in tkinter. However, adding a graphical portion that also draws the hangman would be desirable as well.

2. A.I.: It might seem a little unfair right now that the user is at such a disadvantage. However, with some reasoning skills you can easily determine that there is still an optimal strategy for the user, which would result in them winning at least some amount of time. Write an additional program, which reads in the same words text file. This program also needs to read in the list of guesses the user has made, as well as the currently revealed letters of the word. This program should return the letter the user should guess, for optimal play. In this case, the optimal play would be the letter that results in the largest set of words being removed from the potential pool of words.