Specification 5 - Evil Hangman - Using Data Structures solution

Programming Assignment 5: (Note, there is no assignment named "Assignment 4" this semester.) Individual Assignment. You must complete this assignment on your own. You may not acquire from any source (e.g. another student or a web site) a partial or complete solution to a problem or project that has been assigned. You may not show another student your solution to an assignment. You may not have another person (current student, former student, tutor, friend, anyone) “walk you through” how to solve an assignment. You may get help from the instructional staff. You may discuss general ideas and approaches with other students but you may not develop code together. Review the class policy on collaboration from the syllabus.
Placed online: Wednesday, February 18
20 points, ~2% of final grade.
Due: no later than 11 pm, Thursday, March 5 (the week after the midterm)
General Assignment Requirements
The purpose of this assignment is to implement a program that uses data structures including lists and maps to play an almost unbeatable version of Hangman.
Many thanks to Keith Schwarz of Stanford University for introducing me to this programming project and to Stuart Reges of The University of Washington for his explanation of how the program cheats.
Files:
File
Responsibility
Dictionaries
smallDictionary.txt A dictionary with just 9 words, good for testing.
dictionary.txt A large dictionary with tens of thousands of words.
Provided by me
Java Documentation
Java API for Map Interface, TreeMap, and HashMap
Java API for ArrayList
Java API for StringBuilder
Java API for Comparator
Provided by Oracle
Sample output
Sample outputs of the Evil Hangman Program
sample log 1 (using the small dictionary with debugging and hardest difficulty)
sample log 2 (using the small dictionary with debugging and easiest difficulty)
sample log 3 (using the small dictionary without debugging, various difficulties)
sample log 4 (using the large dictionary with debugging and hardest difficulty)
sample log 5 (using the large dictionary with debugging and easiest difficulty)
sample log 6 (using the large dictionary without debugging and hardest difficulty)
sample log 7 (using the large dictionary without debugging and medium difficulty)
sample log 8 (using the large dictionary without debugging and easiest difficulty)
Provided by me. Your programs output must match the sample runs with debugging off exactly. You can copy and paste into quick diff to compare.
The only allowable difference is when a player loses. The word printed is random and so your output may not match in some cases.
Implementation
HangmanMain.java - The driver program for the game.
Provided by me.
Implementation
HangmanDifficulty.java - An Enumerated Type with the three difficulty levels. Used in HangmanMain and HangmanManager.
Provided by me. Do not alter.
Implementation
and Submission
HangmanManager.java - A class that keeps track of the state of the Hangman game.
I provide the shell, you complete the class.
Testing
In the past students visual inspected their results and compared them to the sample output logs. Students often missed or didn't test for errors and then failed 50 or more of our automated tests. Now you have access to the kinds of tests we run and a version of our testing program. (The actual tests we use will be different of course.)
Once you are sure your program is correct, you can and should generate your own tests and share them with other students.
EvilHangmanAutoTester.java - Uses your HangmanManager and the tests encoded in evilTests.txt to automatically test. As new test files get generated you can alter the name of the input file.
evilTest.eht - Data file for EvilHangmanAutoTester.java. The file was generated by printing out objects that implement the Serializable interface (such as TreeMap or HashMapf) that allow an object to be printed out and read in with a single line of code. (And is generally more efficient that printing out a String version of the object.)
GenerateTests.java - Use this to generate your own tests to share with other students. Replace the test methods or add new ones and change the name of the output file.
Provided by me. You are not required to turn in any tests.
Problem Description: Hangman in CS312 was easy. Time to ramp up the difficulty with our Hangman program. This is Evil Hangman. In this version of the game the computer cheats, but in a very clever way.
If you are not familiar with the game read the Wikipedia entry. You can also find many versions of the game online such as this one.
Our version of the game will not have any graphics or drawings of the gallows..
Evil Hangman is, well, evil, because the computer puts off picking a word for as long as possible. The computer starts off with a dictionary (list) of words. As the user guesses letters the computer narrows the list of words that are active, meaning words that could still be chosen. The words (really just Strings) in the active list all have the same pattern as the "word" displayed to the user.
In other words the program does not pick a word until it has to. It keeps a list of possible words based on user guesses.
A pattern consist of the letters that have been guessed correctly and the letters that have not been guessed yet. For example, if the current pattern is "-e-e-" then the words "beget", "beret", "bevel", "defer", "deter" and so forth would be in the list of active words. Those words "match" the pattern. The "-" characters are wildcard characters and represent any character that has not been guessed yet.
When the user guesses a letter the computer splits the current list of words into different families (really just various lists of words) based on the letter the user just guessed and the resulting pattern of that letter in words from the current list. The computer then picks a list of word from the various lists that have been created. If the computer is being evil, it picks the hardest list of words as the new active list. In general the longest list of words is considered the hardest, but there are tiebreakers explained below. The program also allows the difficulty to vary so the picked list may not always be the list with the largest number of words.
I am providing a driver program that handles the input and output. You are writing a class, HangmanManager that keeps track of the state of the game and narrows the list of words as the user makes guesses. Your HangmanManager class must have the following methods:
Method Name
Description
public HangmanManager(List<String words,
boolean debug)
A constructor that creates the HangmanManager. words will be a nonempty list of Strings. You can assume the Strings will contain only lower case letters a through z. The List is unmodifiable, so you will have to store the active words in another list. (an ArrayList of Strings)
The constructor only copies the dictionary. It doesn't do a lot of other prep work. Most of that is done in prepForRound.
public void prepForRound(int wordLen, int numGuesses, HangmanDifficulty diff)
This method must be called before each game, including the first one.
It is an important method. The HangmanMain program allows the user to play the game. Instead of creating a new HangmanManager object each time a person plays a game, call this method to prepare (or reset) the HangmanManager object with the new word length, number of wrong guesses allowed, and the difficulty. It is important to realize this method must also reset the list of active words to the original dictionary, the pattern, and the number of wrong guesses.
public TreeMap<String, Integer makeGuess(char guess)
This is the method does the heavy lifting. The precondition is !alreadyGuessed(guess). If the character has already been guessed throw an IllegalStateException .
Using this guess, the HangmnaManager decides what set of words to use going forward. The method returns a map of the patterns it generated and how many words matched each pattern. (Note, the HangmanManager does not keep track of this map as an instance variable.) After this method the active list of words may be changed. It is important to realize there is a lot to do in this method including updating the active pattern, the letters that have been guessed so far, and the number of wrong guesses if the pattern does not change.
public boolean alreadyGuessed(char guess)
This method returns true if the user has already guessed the given character, false otherwise.
public int getGuessesLeft()
This method returns the number of wrong guesses the user has left.
public String getGuessesMade()
This method returns the letters the user has guessed so far in sorted order. (Hint: use an ArrayList<Character to store the guesses made so far and return the result of toString on that ArrayList. Use the Collections.sort method to sort the ArrayList of guesses each time one is added.)
public String getPattern()
This method returns the current pattern to be displayed for the hangman game taking into account guesses that have been made. Letters that have not yet been guessed should be displayed as a dashes. There shall only be lower case letters and dashes in the returned String.
public String getSecretWord() {
This method gets the secret word the computer finally settles on. If the active list of words has more than one element, then pick a word at random from the active list. If the list has been narrowed to one word and the user has guessed it, return that word. This method throws an IllegalStateException if the list of active words is size 0. (This should never occur if you implement the program correctly.)
public int numWords(int length)
This method returns the number of words in the original dictionary of the given length. It is used at the beginning of each game to ensure the user picks a valid word length.
public int numWordsCurrent()
This method returns the number of words in the active list of words. (not the original dictionary.) It is used for debugging purposes to show how many words are left in the active list.
Add the instance variables you need to HangmanManager class. Add helper methods as necessary to keep methods small and easy to understand. My version of the makeGuess method uses five private helper methods in addition to the public methods listed above. For reference my solution has 10 (That is a lot and I am trying to figure out a way to reduce it.) instance variables and is 315 lines long. That 315 lines includes a lot of blank lines, debugging code, instance variable declarations, method headers, import statements, comments, and lines with a single closing brace. The actual number of lines of code is on the order of 170.

Explanation of How the Computer Cheats: As noted earlier, this version of hangman cheats. It doesn’t actually pick a word until it needs to. Suppose that the user has asked for a 5-letter word. Instead of picking a specific 5-letter word, it picks all 5-letter words from the original dictionary. But then the user makes various guesses, and the program can’t completely lie. It has to somehow fool the user into thinking that it isn’t cheating. In other words, it has to cover its tracks. Your HangmanManager object shall do this in a very specific way every time the makeGuess method is called. Let’s look at a small example.
Suppose that the dictionary contains just the following 9 words:
[ally, beta, cool, deal, else, flew, good, hope, ibex]
Now, suppose that the user guesses the letter ‘e’. You now need to indicate which letters in the word you've “picked” are e's. Of course, you haven't picked a word, and so you have multiple options about where you reveal the e's. Every word in the set falls into one of five “word families:”
· “- - - -”: which is the pattern for [ally, cool, good]
· “- e - -”: which is the pattern for [beta, deal]
· “- - e -”: which is the pattern for [flew, ibex]
· “e - - e”: which is the pattern for [else]
· “- - - e”: which is the pattern for [hope]
Since the letters you reveal have to correspond to some word in your word list, you can choose to reveal any one of the above five families. There are many ways to pick which family to reveal – perhaps you want to steer your opponent toward a smaller family with more obscure words, or toward a larger family in the hopes of keeping your options open. In this assignment, in the interests of simplicity, we'll adopt the latter approach and always choose the largest of the remaining word families. In this case, it means that you should pick the family “- - - -”. This reduces your set of words to:
[ally, cool, good]
Since you didn't reveal any letters, count this as a wrong guess.
Let's see a few more examples of this strategy. Given this three-word set, if the user guesses the letter 'o;, then you would break your word list down into two families:
· “- o o -”: containing [cool, good]
· “- - - -”: containing [ally]
The first of these families is larger than the second, and so you choose it, revealing two 'o's in the word and reducing your set of words to
[cool, good]
In this case the user has correctly guessed a letter because there are two occurrences of 'o' in the new pattern.
But what happens if your opponent guesses a letter that doesn't appear anywhere in your word list? For example, what happens if your opponent now guesses 't'? This isn't a problem. If you try splitting these words apart into word families, you'll find that there's only one family – the family “- o o -” in which t appears nowhere and which contains both “cool” and “good”. Since there is only one word family here, it's trivially the largest family, and by picking it you have maintain the word list you already had and you would count this as an incorrect answer.
Here is a useful diagram that shows the winnowing process based on user guesses.
To implement this strategy, use a map. The keys will be the different patterns for each word family. (You are free to use String, StringBuilder, arrays, or other classes to determine what patterns exist based on the active word list, the previous pattern, and the user's guess.) Those keys should map to a list of words that have that pattern.
For each call to makeGuess, you will find all of the word families based on the current list of active words (not the original dictionary, except for the first guess) and pick the one that is the hardest.
The hardest word list / family is defined as the one with the largest number of words with certain tiebreakers. (This family becomes the new list of words for the next round of the game.) If there is a tie for the family with the most words (two of the word families are of equal size), pick the family that reveals the fewest total characters. If there is still a tie, pick the family that has the pattern that is "smallest" based on the ASCIIbetical (lexigraphical order based on ASCII codes) ordering of the patterns. This is not as hard as it sounds. A TreeMap with keys of type Strings, stores the the keys in ASCIIbetical order without any extra effort on your part. This, in turn, is based on the compareTo method in the String class. Look here for more info on ASCIIbetical order, lexigraphical order, and Alphabetical vs. ASCIIbetical order. (The last link is to a very interesting blog post about Alphabetical vs. ASCIIbetical order and how most built in String sorts are ASCIIbetical, but when displaying info to real users, like a list of files, true alphabetical is preferred.)
Summary of hardest word list / family:
Family with the maximum elements
If there are two or more families with the maximum number of elements break the tie by picking the one that reveals the fewest characters
If there are two or more families with the maximum number of elements and reveal the same number of characters break the tie by picking the pattern that is "smallest" based based on the lexigraphical ordering of Strings.

Toy example of lexigraphical ordering.

String pat1 = "---a";
String pat2 = "a---";
System.out.println(pat1.compareTo(pat2)); // prints out a negative integer. "---a" is lexigraphically smaller (or before) "a---"
System.out.println(pat2.compareTo(pat1)); // prints out a positive integer. "a---" is lexigraphically larger (or after) "---a"
Your program shall be reasonably efficient way in terms of time and space.
Difficulty: Worry about this last. In order to moderate the evilness of the program the user is allowed to enter a difficulty level, an Enum from HangmanDifficulty. The strategy described above assumes the difficulty is HangmanDifficulty.HARD, the hardest.
Initially ignore the user's choice for difficulty and implement the algorithm above. When you have that working then alter the makeGuess method to take into account the difficulty.
If the difficulty is HangmanDifficulty.HARD then the program picks the word list as descried above. HangmanDifficulty.HARD always picks the hardest word list / family.
If the difficulty is HangmanDifficulty.MEDIUM the program picks the hardest word list / family 3 times in a row, then the second hardest word list, then the hardest word list / family 3 times in a row, then the second hardest word list / family. This pattern repeats until the game is over. The game should be a little less difficult if the program doesn't always pick the hardest word list / family. If their is only one word list / family and it is time to pick the second hardest , just pick the single word list / family. Then go back to picking the hardest. In other words the behavior for picking word lists at this difficulty level is:
Medium behavior for picking new list of words in makeGuess method:
Guess 1, PICK HARDEST WORD LIST
Guess 2, PICK HARDEST WORD LIST
Guess 3, PICK HARDEST WORD LIST
Guess 4, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
Guess 5, PICK HARDEST WORD LIST
Guess 6, PICK HARDEST WORD LIST
Guess 7, PICK HARDEST WORD LIST
Guess 8, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
and so forth ...
If the difficulty is HangmanDifficulty.EASY the program alternates between picking the hardest word list and the second hardest word list if it exists:
Easy behavior for picking new list of words in makeGuess method:
Guess 1, PICK HARDEST WORD LIST
Guess 2, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
Guess 3, PICK HARDEST WORD LIST
Guess 4, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
Guess 5, PICK HARDEST WORD LIST
Guess 6, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
Guess 7, PICK HARDEST WORD LIST
Guess 8, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
and so forth ...
If it is time to pick the second hardest word list, but there is only one word list, then that single word list is the pick. The second hardest does not "roll over" to the next round in this case.
Hint: To find the hardest word list / family and to make the difficulty portion easier make create a Comparator or a nested class that implements Comparable and use Collections.sort. The official Java tutorial section on Comparable and Comparators and another tutorial.

Submission: Fill in the header for HangmanManager.java. Replace <NAME with your name. Note, you are stating, on your honor, that you did the assignment on your own.
Create a zip file name a5.zip [case sensitive! Do not name the file A5.zip!] with your HangmanManager.java file. (Yes, a zip with one file.) The zip file must not contain any directory structure, just the required file.

See this page for instructions on how to create a zip via Eclipse.
Turn in a5.zip via your Canvas account to programming assignment 5.
Ensure you file is named HangmanManager.java. Failure to do so will result in points off.
Ensure HangmanManager.java is part of the default package. Do not add a package statement to the file.
Ensure your zip has no internal directory structure. When the file is unzipped no directories (folders) are created. (Note, the built in unzip feature of some versions of Windows and Apple OS X "help" by adding a directory when you unzip with the same name as the file. The unzip we use on the CS Linux system does not do this. Neither do unzip programs such as 7zip.)
Ensure you submit the assignment under Programming Assignment 5 in Canvas.
If you resubmit your file you must first delete the previous versions, otherwise Canvas renames the file. See this page for instructions.

Checklist. Did you remember to:
review and follow the general assignment requirements?
work on the assignment by yourself?
fill in the header in your HangmanManager.java?
ensure your program does not suffer a compile error or runtime error?
test your program and ensure it passes the provided tests?
turn in your file named HangmanManager.java in a zip named a5.zip with no internal directory structure?
turn in your zip named a5.zip to Programming Assignment 5 via Canvas no later than 11 pm on Thursday, March 5?

Back to the CS 314 homepage.