CSC 421: Algorithm Design and Analysis
Spring 2014

HW2: Decrease & Conquer Hangman


Hangman is a children's game in which one person picks a secret word, and the other tries to guess it one letter at a time. For this assignment, you will complete the implementation of a simple, text-based game of Hangman using honest and dishonest strategies. You are given two files to build from: HangmanGame is the driver class for the game, and Hangman is an interface for a class that maintains the state of a game. You are to design and code two different classes that implement this interface:

  1. HonestHangman.java: This class implements the Hangman interface in an honest way. That is, it should select the secret word at random from the supplied dictionary, and allow the player to guess that word. The class will need to maintain a collection of all previous guesses, and be able to return the secret word in redacted form (i.e., in which every non-guessed letter is replaced by a dash).

    For example, suppose the secret word selected by the HonestHangman is "fresher". Initially, before any guesses have been made, this word would be redacted as "-------". However, after guessing 'e', the occurrences of 'e' in the word would be revealed, resulting in "--e--e-". A further guess of 's' would change the redacted form to "--es-e-". A game of Hangman continues until the player guesses all of the letters in the secret word.

  2. DishonestHangman.java: This class implements the Hangman interface in a dishonest way. It works by randomly selecting the secret word from the dictionary, as before. Each time the user makes a guess, however, the DishonestHangman cheats by changing the secret word in a way that is least helpful to the player. It does this by going through the set of plausible words (initially, all the words of the same length) and partitioning them based on their redacted forms. Whichever partition is the largest, it selects a new secret word from that largest partition and the partition then becomes the new set of plausible words. The player has no way of knowing that the game has cheated, since each time a secret word is selected it matches all the clues given to that point.

    For example, consider a dictionary that contains just eight 5-letter words:

        { "apple", "bread", "chair", "dread", "melee", "treat", "trust", "wreck" }
    
    Suppose the DishonestHangman initially selected one of these as the secret word, and the player's first guess was the letter 'e'. Then, the collection of plausible words would be partitioned based on their redacted pattern after guessing 'e':
    	"----e" → { "apple" }
    	"--e--"	→ { "bread", "dread", "treat", "wreck" }
    	"-----"	→ { "chair", "trust" }
    	"-e-ee"	→ { "melee" }
    
    Since the second partition is the largest, the DishonestHangman will select one of the words from this partition as the new secret word and report its redacted form. If the next guess is the letter 't', then the DishonestHangman will partition this collection further:
    	"--e--"	→ { "bread", "dread", "wreck" }
    	"t-e-t"	→ { "treat" }
    
    and thus would select one of the words in the first partition as the new secret word. The process continues until the partition is reduced to a singleton and only one word is plausible.