CSC 421: Algorithm Design and Analysis
Spring 2016

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 abstract class that maintains the state of a game. This abstract class implements some basic methods, but you are to define two different classes that complete its functionality (using vastly different strategies).

  1. HonestHangman.java: This class extends the Hangman abstract class 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.

    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 wins (by guessing all of the letters in the secret word) or loses (by exhausting all of their guesses).

  2. DishonestHangman.java: This class extends the Hangman abstract class in a dishonest way. It works by randomly selecting a word at random and building a collection of all words in the dictionary that are that length. Each time the user makes a guess, however, the DishonestHangman cheats by producing a plausible response that is least helpful to the player. It does this by going through the collection of potential words and partitioning them based on their redacted forms. Whichever partition is the largest, it reports that redacted form as its response. The player has no way of knowing that the game has cheated, since each response is consistent with all of the guesses 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 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 say the guess was correct and update the redacted word to "--e--". 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 the first partition (responding that the guess was incorrect). The process continues until the partition is reduced to a single word, after which the DishonestHangman must respond honestly.