In this assignment, you will build a mischievous program that bends the rules of Hangman to trounce its human opponent time and time again. In doing so, you'll cement your skills with abstract data types and iterators, and will hone your general programming savvy. Plus, you'll end up with a piece of software which will be highly entertaining.
In case you aren't familiar with the game Hangman, the rules are as follows:
1. One player chooses a secret word, then writes out a number of dashes equal to the word length.
2. The other player begins guessing letters. Whenever she guesses a letter contained in the hidden word, the first player reveals each instance of that letter in the word. Otherwise, the guess is wrong.
3. The game ends either when all the letters in the word have been revealed or when the guesser has run out of guesses.
Fundamental to the game is the fact the first player accurately represents the word she has chosen. That way, when the other players guess letters, she can reveal whether that letter is in the word. But what happens if the player doesn't do this? This gives the player who chooses the hidden word an enormous advantage. For example, suppose that you're the player trying to guess the word, and at some point, you end up revealing letters until you arrive at this point with only one guess remaining:
D O - B L E
There are only two words in the English language that match this pattern: "doable" and double. If the player who chose the hidden word is playing fairly, then you have a fifty-fifty chance of winning this game if you guess 'A' or 'U' as the missing letter. However, if your opponent is cheating and hasn't actually committed to either word, then there is no possible way you can win this game. No matter what letter you guess, your opponent can claim that she had picked the other word, and you will lose the game. That is, if you guess that the word is doable, the opponent can pretend that the committed word was double the whole time, and vice-versa.
2.1 Example of Evil Strategy
Suppose that you are playing Hangman and it's your turn to choose a word, which we'll assume is of length four. Rather than committing to a secret word, you instead compile a list of every four-letter word in the English language. For simplicity, let's assume that English only has a few four-letter words, all of which are reprinted here:
ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX
Now, suppose that your opponent guesses the letter 'E.' You now need to tell your opponent which letters in the word you've "picked" are E's. You haven't picked a word so you have multiple options about where you reveal the E's. Here's the above word list, with E's highlighted in each word:
ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX
If you'll notice, every word in your word list falls into one of five "word families":
---- contains the word ALLY, COOL, and GOOD
-E-- contains BETA and DEAL
--E- contains FLEW and IBEX
E--E contains ELSE
---E contains HOPE
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 word list down to
ALLY COOL GOOD
and since you didn't reveal any letters, you would tell your opponent that his guess was wrong. Now the list of words you have to choose from has been reduced to these three words. If your opponent guesses the letter O, then you would break your word list down into two families:
-OO- contains COOL and GOOD
---- contains ALLY
Since the -OO- family is larger (two words) we go ahead and choose it, revealing two O's in the word and reducing the list down to
COOL GOOD
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 ---- in which T appears nowhere and which contains both COOL and GOOD. Since there is only one word family here, it's already the largest family, and by picking it you would maintain the word list you already had.
There are two possible outcomes of this game.
1. Your opponent might be smart enough to pare the word list down to one word and then guess what that word is. In this case, you should congratulate the player.
2. By far the most common case, your opponent will be completely stumped and will run out of guesses. When this happens, you can pick any word you'd like from your list and say it's the word that you had chosen all along.
The beauty of this setup is that your opponent will have no way of knowing that you were dodging guesses the whole time - it looks like you simply picked an unusual word and stuck with it the whole way.
Your assignment is to write a computer program which plays a game of Hangman using this "Evil Hangman" algorithm. In particular, your program should do the following:
1. Read the file dictionary.txt, which contains the full contents of the Official Scrabble Player's Dictionary, Second Edition. This word list has over 120,000 words, which should be more than enough for our purposes.
2. Prompt the user for a word length, re-prompting as necessary until there's at least one word that's exactly that long. That is, if the user wants to play with words of length -42 or 137, since no English words are that long, you should re-prompt the user.
3. Prompt the user for a number of guesses, which must be an integer greater than zero. Don't worry about unusually large numbers of guesses - after all, having more than 26 guesses is clearly not going to help your opponent!
4. Prompt the user for asking if a running total of the number of words remaining in the word list should be displayed. This completely ruins the illusion of a fair game that you'll be cultivating, but it's quite useful for testing.
5. Play a game of Hangman using the Evil Hangman algorithm, as described below:
6. Ask if the user wants to play again and loop accordingly.
There are many different ways to go about organizing the data. The most convenient and the one that first comes to mind is some sort of lookup table. While we are playing the game, we need to be able to associate each word with a particular family. To accomplish this, we will use hash table that uses the word family as a key and some sort of list or dictionary to store the words associated with that key.
At the very beginning of the game, the user will be asked to give a word length for the mystery word. This will immediately limit the size of the word list.
4.1 Unordered Map
The STL library implementation of a hash table is called an unordered map. It has a key and a value associated with the key. Below is an example of how to use this data type:
int main()
{
// Initialize an unordered_map through initializer_list
std::unordered_map< std::string, int> wordMap(
{
{ "1st", 1 },
{ "2nd", 2 },
{ "3rd", 3 } });
// Iterate over an unordered_map using range based for loop
for (std::pair< std::string, int> element : wordMap) {
std::cout < < element.first < < " :: " < < element.second < < std::endl;
}
std::cout < < "*******************" < < std::endl;
// Get an iterator pointing to beginning of map
std::unordered_map< std::string, int>::iterator it = wordMap.begin();
// Iterate over the map using iterator
while (it != wordMap.end()) {
std::cout < < it->first < < " :: " < < it->second < < std::endl;
it++;
}
return 0;
}
4.2 FamilySet
The FamilySet object is in charge of managing the families using an unordered_map. In this data structure, the unordered_map will use a string as a key and some sort of list or collection as the info. This object will also help filter out words as the user makes guesses. Read the starter files as they contain additional details.
class FamilySet
{
public:
FamilySet();
FamilySet(string file);
// Initializes from a word file
FamilySet(string file, int len);
// Initializes from a word file where the word
// must be of length len.
~FamilySet();
void filterFamilies(string letter, string guessPattern);
// Filters each word from the master list based on the
// letter and guessPattern.
// Example: letter: "a",
// word: "ally" (a word from the master list)
// pattern: "***y"
// In this case, the family is a**y. Once this
// is determined, then "ally" can be added to
// this family dictionary.
void setFamily(string family);
// This updates the master list. The new master list
// should contain the words within the dictionary for family.
// dictionaries should be cleared after updating the master list.
string getRandomWord(); // Gets a random word from the master list
int numWords(); // Returns total number of words in master list
int numFamilies(); // Returns total number of families
int familySize(string family); // Returns the number of words in a family
// Iterator
void resetFamilyIter();
bool hasNext();
string getNextFamily();
private:
vector< string> masterList; // This stores all words currently "valid"
unordered_map< string, vector< string>> dictionaries;
// Stores a dictionary for each family. Each word from
// the masterList is contained within one of these
// these vector dictionaries.
int iterCount; // Used for iterator
};
Here are some random hints that can potentially help.
5.1 Figuring out if a letter is in a word
The find method of a string returns the first position a letter occurs. If the letter does not occur then it will return string::npos (this is actually a special integer).
if (word.find("*") == string::npos) {
}
Get a random number between 0 and some other number
int randInd = rand()%100; // Returns an integer between 0 and 99.
5.3 Gaps in dictionary file
Watch out for gaps in the dictionary. When the user specifies a word length, you will need to check that there are indeed words of that length in the dictionary. You might initially assume that if the requested word length is less than the length of the longest word in the dictionary, there must be some word of that length. Unfortunately, the dictionary contains a few gaps. The longest word in the dictionary has length 29, but there are no words of length 27 or 26. Be sure to take this into account when checking if a word length is valid.