Cheating Hangman
December 27, 2011
We have a tradition here at Programming Praxis of celebrating milestones by having a party, and parties require games. Today, for our three-hundredth exercise we will write a cheating version of the hangman from a previous exercise.
The idea is simple. Instead of choosing a single answer at the beginning of the game, choose a length, and make a list of all possible answers. Each time the player guesses a letter, delete as few words from the possible-answer list as possible consistent with the guesses the player has made; most of the time another body part will be added to the gibbet.
Your task is to write a referee for the game of cheating hangman. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
I decided to make a quick prototype in python this time, just to illustrate the new algorithm. The user interface is very rudimentary with the gibbet replaced by a numerical indicator. Following the hint in the exercise I have also implemented the same method of choosing the largest set of possible answers. I just wonder if the size of the set is the best measure; maybe something like remaining letter diversity would be better.
import re import random from collections import defaultdict LEVELS=6 pat_small = re.compile(r"[a-z]+$") f = open("wordlists/english.0") words = f.readlines() f.close() words = [ w.rstrip() for w in words if pat_small.match(w) ] print("Using dictionary with %d lowercase words" % len(words)) len2words = defaultdict(list) for w in words: len2words[len(w)].append(w) while True: length = random.choice(list(len2words.keys())) possible_answer = len2words[length] letters = [ chr(c) for c in range(ord('a'), ord('z') + 1) ] mask = [ '_' ] * length level = 0 while level < LEVELS: print(" ".join(mask)) if '_' not in mask: print("Congratulations") break ch = input("Level %d/%d. Letter: " % (level, LEVELS)) if ch not in letters: print("Not a letter or letter already used") continue d = defaultdict(int) dl = defaultdict(list) for w in possible_answer: t = tuple([ int(w_ch == ch) for w_ch in w]) d[t] += 1 dl[t].append(w) best = max(zip(d.values(), d.keys())) best_mask = best[1] possible_answer = dl[best_mask] if 1 not in best_mask: print("No %s in the word" % ch) level += 1 continue for i, m in enumerate(mask): if best_mask[i]: mask[i] = ch if level == LEVELS: print("Word was: %s" % possible_answer[0])[…] have created a Python solution to the cheating hangman problem and posted it there in the comments. I have a follow-up question though. Let us assume both […]
“… the groups are sorted by descending length, and car picks the longest, which gives the cheating referee the most possibilities for cheating at the next letter.”
I disagree with this statement. If the remaining words are [ abd, acd, abe, ace, bbb, ccc, ddd, eee, fff ] and the player picks letter “a”, the referee actually has more possiblilities to cheat with the shorter [ abd, acd, abe, ace ] list, as I described elsewhere.
I was trying to compute which side has the winning strategy for a given word length. For the English alphabet the search space is too large to process effectively, however. Perhaps someone has a better idea than the straightforward consideration of every letter and every word type in each step?
My example above is wrong: instead [ ‘abd’, ‘acd’, ‘abe’, ‘ace’, ‘dde’, ‘ded’, ‘edd’, ‘ede’, ‘eed’ ] works as intended.