## 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.

Pages: 1 2

### 4 Responses to “Cheating Hangman”

1. 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])

2. […] 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 […]

3. “… 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?

4. My example above is wrong: instead [ ‘abd’, ‘acd’, ‘abe’, ‘ace’, ‘dde’, ‘ded’, ‘edd’, ‘ede’, ‘eed’ ] works as intended.