Evil Hangman

Designing programs using Java collections.¹

ed Workspace

Table of contents

1. HangmanMain
2. HangmanManager
   1. Method summary
   2. Development strategy
3. Grading
4. Reflection
5. Submission

In a game of hangman, the computer program picks an answer word that the user is supposed to guess. The user then guesses individual letters until the answer is fully revealed. A correct guess is one that reveals new letters in the word, while a wrong guess does not reveal new letters.

In a game of evil hangman, the program delays picking a word until there is only one possible word in its dictionary in an attempt to maximize the number of wrong guesses. As a result, the program is always considering a set of words that could be the answer. In order to fool the user into thinking it is playing fairly, the program only considers words with the same letter pattern.

HangmanMain

HangmanMain reads a dictionary text file as input and passes its contents as a list of strings to a new instance of HangmanManager. In this assignment, we will implement a class HangmanManager that manages the state of an evil game of hangman.

For example, suppose that we run HangmanMain with the words in dictionary2.txt.

1. ally
2. beta
3. cool
4. deal
5. else
6. flew
7. good
8. hope
9. ibex

In our game, instead of choosing a word at the beginning, the program narrows down its set of possible word answers as the user makes guesses.

Welcome to the cse143 hangman game.

What length word do you want to use? 4
How many wrong answers allowed? 7

When the user guesses ‘e’, the program must reveal where the letter ‘e’ appears. Since it hasn’t chosen a word yet, its options fall into five families:

The guess forces the program to choose a family of words, but not a particular word in that family. The program always chooses the family with the largest number of words in order to leave the most options available later. For the example described above, the program would pick - - - -. This reduces the possible answers it can consider to [ally, cool, good].

guesses : 7
guessed : []
current : - - - -
Your guess? e
Sorry, there are no e's

Since the program didn’t reveal any letters, it counts this as a wrong guess and decreases the number of guesses left to 6. Next, the user guesses the letter ‘o’. The program has two word families to consider:

It picks the largest family and reveals the letter ‘o’ in two places. This was a correct guess so the user still has 6 guesses left. The program now has only two possible answers to choose from: [cool, good].

guesses : 6
guessed : [e]
current : - - - -
Your guess? o
Yes, there are 2 o's

Next, the user guesses the letter ‘d’. There are two possible families [cool] and [good], both of which are the same size (one word each). If there is a tie for largest family, the program should choose the family whose pattern comes alphabetically first. In this example, the program removes “good” from its consideration because the pattern - o o - alphabetically precedes the pattern - o o d. This leaves only one possible answer left for the program to pick as its word: [cool].

guesses : 6
guessed : [e, o]
current : - o o -
Your guess? d
Sorry, there are no d's

The game continues with the guesses ‘c’ and ‘l’.

guesses : 5
guessed : [d, e, o]
current : - o o -
Your guess? c
Yes, there is one c

guesses : 5
guessed : [c, d, e, o]
current : c o o -
Your guess? l
Yes, there is one l

answer = cool
You beat me

If the user guesses a letter that doesn’t appear anywhere in the current set of words (e.g. ‘t’), the family you previously chose is still going to match. In this case, guessing ‘t’ only deducts from the number of guesses remaining without changing the set of possible answers.

HangmanManager

Use TreeSet and TreeMap as the implementations for all sets and maps needed for HangmanManager. The elements or keys in a TreeSet or TreeMap are stored in sorted order, so iterating over a TreeSet<String> with a for-each loop will yield strings in dictionary order.

Method summary

public HangmanManager(Collection<String> dictionary, int length, int max)

Initializes the state of a new game of evil hangman using the given dictionary of words, a desired word length, and a maximum number of wrong guesses. The set of words should initially contain all words from the dictionary of the given length, eliminating any duplicates. Throw an IllegalArgumentException if the given length is less than 1 or if max is less than 0. Assume the dictionary contains only non-empty strings composed entirely of lowercase letters.

public Set<String> words()

Returns the current set of possible answers.

public int guessesLeft()

Returns the number of remaining wrong guesses available to the player.

public Set<Character> guesses()

Returns the current set of letters that have already been guessed by the player.

public String pattern()

Returns the current pattern with spaces between each letter. Letters that have not yet been guessed should be displayed as a dash. There should be no leading or trailing spaces. This method should store the pattern rather then recomputing it each time the method is called. Throw an IllegalStateException if the set of words is empty.

public int record(char guess)

Record that the player made a guess and return the number of occurrences of the guessed letter in the new pattern. This method should update the set of possible answers and the number of remaining guesses as necessary. Throw an IllegalStateException if the number of guesses left is less than 1 or if the set of words is empty. If the previous exception was not thrown, it should throw an IllegalArgumentException if the character being guessed was guessed previously. Assume that guess is a lowercase letter.

Development strategy

The most complicated method is record, so write it last. Develop the program incrementally and create a test client to verify behavior.

A good subtask to complete and test in isolation is building the map that associates word family patterns to words in that family. Keep in mind that the patterns come from the words themselves. On any given turn, there is a current set of words that all have the same pattern. When the user guesses a new letter, go through each of the words that are in the current set and compute the new pattern for that particular word given the new guess. Different words go in different sets because they have different patterns.

Then, once all of the words have been processed into different sets, the set of possible answers is the one containing the most words.

HangmanMain has two constants that you will want to change. The first represents the name of the dictionary file. By default, it reads from dictionary.txt which contains over 127,000 words from the official English Scrabble dictionary. When getting started, change it to dictionary2.txt which contains the 9 words used in the example on the first page. SHOW_COUNT is set to false by default. Set it to true to see the words the computer is still considering as you play.

Grading

HangmanManager should exactly reproduce the format and behavior from the Output Comparison Tool and the example game described above. While all of the standard methods from the String class are fair game, be careful not to introduce inefficiency. For example, the toCharArray method introduces an unnecessary array. Regular expressions should not be used for this problem. Use only the features discussed so far in class.

Use TreeSet and TreeMap with correct generic types for this assignment. For the words and guesses method, return a reference to an internal field of HangmanManager. While this potentially allows clients to modify the internal data structures, assume that the client in this case will not attempt to make changes.

Method errors

• Non-exception code should not be in an else branch.
• Not decomposing complex methods into logical subtasks that each have their own method. Create private “helper” methods to capture repeated code. A good rule of thumb for this assignment is that no method should have more than 20 lines of code in its body.

Data structure errors

• Excessive inefficiency when using collections. For example, using a for-each loop to find a value of a map when a call to get would return the value.
• Using a collection when it’s not necessary.

Miscellaneous errors

• Incorrect use of types. For example, using double instead of int, int instead of boolean, or String instead of char for a value known to be exactly one character.
• Recomputing a value when it could have been computed once and stored in a variable.

Reflection

Create a new file reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):

1. What did you learn this week?
2. What did you enjoy in the course this week?
3. What did you find challenging or frustrating this week?
4. What did you find particularly helpful for your learning this week?

Submission

Submit HangmanManager.java and reflection.txt to Grade-It!