EE 312 - Project 9 - Evil Hangman

This assignment originated from a submission to the 2011 Nifty Assignments session at the annual CIGCSE meeting. This nifty assignment was originally developed by Keith Schwarz at Stanford University. As part of this assignment, you will code, as Professor Schwarz describes it, an awesome variant of Hangman, where the computer dodges the user's guesses.

Thank you to EE 312 TA Colin Maxfield for his assistance with this project, and to Mike Scott in UTCS for allowing me to utilize his project materials.

In this project, you will get practice with:

Due: Wednesday, November 29, 2017 at 11 pm

You may not acquire from any source (e.g., another student or an internet site) a partial or complete solution to a problem or project that has been assigned. You may NOT show other students your solution to an assignment. You may not have another person "walk you through" how to solve an assignment, or walk another student through the solution. You may get help from the instructional staff. You may discuss general ideas and approaches. Review the class policy on collaboration from the syllabus. I will run plagiarism detection software on project submissions. If you cheat, you will receive an F in the course and I will submit a report to the office of the dean of students. If you provide your solution to another student, you are as guilty of cheating as the other student.

Make sure that you follow the EE 312 style guide. You will lose points if you do not. You must include the honor statement below in your .cpp files. You will lose points if you do not. 

Include the following at the top of your file: 

// EvilHangmanGame.cpp (or RunEvilHangman.cpp) -- EE 312 Project 9

/* Student information for project:
 *
 * Replace <NAME> with your name.  <--- REMOVE THIS LINE FROM YOUR HEADER
 *
 * On my honor, <NAME>, this programming project is my own work
 * and I have not provided this code to any other student.
 *
 * Name:
 * email address:
 * UTEID:
 * Section 5 digit ID:
 * Number of slip days used on this assignment.
 */

You must also include a description of the project in a comment at the top of your file. Include comments that describe each function, as well as comments that describe code chunks inside your functions, following the class style guide. You may write helper functions in EvilHangmanGame.cpp that the member functions call - include prototypes for those functions at the top of the file. Likewise, include prototypes of the functions you include in RunEvilHangman.cpp at the top of that file. 

Do NOT add additional #includes or globals to the files. Your EvilHangmanGame.cpp file must NOT include a main function. Do NOT modify the EvilHangmanGame.h file. You may not add additional member functions. As part of our testing, we will use our own version of RunEvilHangman.cpp and EvilHangmanGame.h with your EvilHangmanGame.cpp. We will also grade the game set-up (prompting the user for guesses, displaying the number of guesses remaining, the letters guessed, the current pattern, etc.) that you write in RunEvilHangman.cpp. 

Provided files: EvilHangmanGame.cpp, RunEvilHangman.cpp, EvilHangmanGame.h
We've also provided two sample dictionaries: dictionary.txt, smallDictionary.txt. We may not use these dictionaries when we are grading. 

Create a zip file a9.zip with no internal structure that contains your EvilHangmanGame.cpp and RunEvilHangman.cpp files. Upload your zip file on Canvas. Your files must all have the specified names, including the zip file. 

Modularity and style are part of the project grade.
Program Description: Evil Hangman is a program that cheats at Hangman. Instead of initially choosing a word from the dictionary that the player tries to guess, the program has a set of words that it updates as the user makes guesses.

If you are not familiar with the original Hangman game, read about it on Wikipedia. You will also find versions of the game online. Our version will not use graphics or draw the gallows.

In Evil Hangman, the computer postpones picking a word as long as possible. The computer starts with a dictionary of words. As the user guesses letters, the computer narrows the list of words that are active, i.e., words that could still be chosen. The words in the active list all have the same pattern as the "word" displayed to the user. The program does not pick a word until it has to. It keeps a list of possible words based on user guesses. 
A pattern consists of the letters that the user has guessed correctly, combined with dashes to represent letters that haven't been guessed yet. E.g., if the current pattern is "-e-e-" then the words "beret", "defer" and "bevel" could be in the list of active words, since they all match the pattern. 

Whenever the user guesses a letter, the computer splits the current list of words that it is maintaining into different families (lists) based on the letter that the user just guessed and the resulting pattern of that letter in words from the current list. The computer then picks one list from those, with the goal of choosing the hardest list of words as the new active list. Generally speaking, the longest list of words is considered the hardest, but sometimes tiebreakers are required as described below.
How the Computer Cheats. Suppose the user has asked for a 4-letter word. Instead of picking a specific 4-letter word, it picks all 4-letter words from the original dictionary. The user then guesses various letters. The computer must disguise the fact that it's cheating.

Suppose that the dictionary contains the following 9 words:
[ally, beta, cool, deal, else, flew, good, hope, ibex]

Suppose that the user guesses 'e'. The game must indicate which letters in the word that it has "picked" are 'e'. The game hasn't really picked a word, and so there are multiple options about where to reveal the e's. Every word in the set falls into one of five word "families:"

Your program will choose the largest family of words. In this example, your program picks the "----" family, which changes the set of possible words to [ally, cool, good]. The program didn't reveal any letters, so this counts as a wrong guess.

Given the 3-word set, assume the user's next guess is 'o'. Then you break the word list into two families:

The first family, [cool, good], is larger than the other, so your program chooses it, revealing the two o's in the "word" to the user and reducing the set of words to [cool, good]. This time, the user guessed correctly, since there are two occurrences of 'o' in the new pattern.

If the user guesses a letter that isn't in the word list, what happens? Suppose the user guesses 't'. When you try to split the current word list into families, there's only one family, "-oo-" in which 't' does not appear, and which still contains "cool" and "good". There's only one word family, so it's obviously the largest, so you keep the existing word list and this counts as an incorrect guess by the user.

You will need to use maps to implement your solution. The keys will be the different patterns for each word family. Each key will map to a list of words with that pattern.

For each call to makeGuess, you will find all the word families based on the current list of active words, and pick the one that is hardest.

The hardest word list/family is the one with the largest number of words with some 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 (i.e., two or more word families have the same size), choose the one to return according to the following:

How the Program Works:
Your program will take the dictionary filename, word length, and number of guesses on the command line. If you compiled your program to evilHangman, run your program with a command of the following form:
./evilHangman [dictionary] [wordLength] [guesses]

The dictionary is the path to a text file which contains whitespace separated words. The words are sequences of letters. Letter comparisons will be case-insensitive, so 'a' matches 'a' or 'A', and 'A' matches 'a' or 'A'.

wordLength is an integer which is 2 or greater. guesses is an integer that is 1 or larger.

To run the game:
1. At the beginning of each turn, display the number of remaining guesses, an alphabetized list of letters guessed so far, and the pattern (i.e., the partially constructed word.)
2. Prompt the user for her next letter guess. If the guess is not an upper or lower-case letter, print "invalid input" on the next line and re-prompt. If the user has already guessed the letter, print "You already guessed that letter, try again" on the next line and re-prompt.
3. Report the new pattern. If the current word list doesn't contain any word with that letter, decrement the number of remaining guesses and print "Sorry, there are no <letter>'s" on a new line, replacing <letter> with the actual letter guess. If all words in the list contain that letter, print, "Yes, there is 1 <letter>" or "Yes there are <num> <letter>'s" where <letter> is the guessed letter and <num> is the number of times <letter> appears in the new word family.

See the sample output below.

Notes:

Your program's output should match what is displayed below for the given inputs.
Sample Run 1:
./EvilHangman smallDictionary.txt 4 5

You have 5 guesses left
Letters guessed:
Word: ----
Enter guess: e
Sorry there are no e's

You have 4 guesses left
Letters guessed: e
Word: ----
Enter guess: o
Yes, there are 2 o's

You have 4 guesses left
Letters guessed: e o
Word: -oo-
Enter guess: c
Sorry there are no c's

You have 3 guesses left
Letters guessed: c e o
Word: -oo-
Enter guess: g
Yes, there is 1 g

You have 3 guesses left
Letters guessed: c e g o
Word: goo-
Enter guess: d
Yes, there is 1 d
You win!
The word was: good

Sample Run 2:
./EvilHangman smallDictionary.txt 4 5

You have 5 guesses left
Letters guessed:
Word: ----
Enter guess: a
Sorry there are no a's

You have 4 guesses left
Letters guessed: a
Word: ----
Enter guess: p
Sorry there are no p's

You have 3 guesses left
Letters guessed: a p
Word: ----
Enter guess: e
Sorry there are no e's

You have 2 guesses left
Letters guessed: a e p
Word: ----
Enter guess: e
You have already guessed that letter, try again

You have 2 guesses left
Letters guessed: a e p
Word: ----
Enter guess: h
Sorry there are no h's

You have 1 guesses left
Letters guessed: a e h p
Word: ----
Enter guess: i
Sorry there are no i's
You lose!
The word was: cool

Checklist: Did you remember to