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.

About these ads

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 631 other followers

%d bloggers like this: