Simple Hangman AI

hangman.py

BLANK = "_"
WORDS = "/usr/share/dict/words"

def letter_indexes(word):
    indexes = {}
    for i, L in enumerate(word):
        indexes.setdefault(L, []).append(i)
    return indexes

class Hangman(object):
    
    def __init__(self, puzzle, solution):
        self.puzzle = list(puzzle)
        self.solution = solution
        self.solved = BLANK not in self.puzzle
        self.guesses = []

        self._letter_positions = letter_indexes(self.solution)

        # do not do this in production code
        assert BLANK not in self.solution
        assert len(self.solution) == len(self.puzzle)
    
    @property
    def puzzle_string(self):
        return "".join(self.puzzle)

    def try_guess(self, letter):
        if self.solved:
            raise ValueError("Cannot try a guess on a puzzle that has already been solved")
        
        if letter in self.guesses:
            raise ValueError("Duplicate guess")

        self.guesses.append(letter)

        # need to ensure that letter hasn't already been guessed
        if letter in self._letter_positions and letter not in self.puzzle:
            for index in self._letter_positions[letter]:
                self.puzzle[index] = letter

            self.solved = BLANK not in self.puzzle
            return True
        
        return False

class HangmanAI(object):

    def __init__(self, game):
        self.game = game
        self.words_cache = []

    def guess(self):
        potential_guesses = self.potential_guesses()
        return potential_guesses.pop(0)

    def remove_invalid_guess(self, guess):
        self.words_cache = [w for w in self.words_cache if guess not in w]

    def potential_guesses(self):
        sample = self.reduced_words()
        if not sample:
            raise ValueError("No words left to guess!")

        total_frequencies = self.total_frequencies(sample)
        for letter in set(self.game.puzzle):
            if letter != BLANK:
                del total_frequencies[letter]

        # At this point, total_frequencies should just contain the frequencies
        # of letters that could potentially fill the blank spaces in the puzzle
        sorted_frequencies = sorted(total_frequencies.iteritems(), key=lambda x: x[1], reverse=True)
        return [L for L, n in sorted_frequencies]

    def total_frequencies(self, words):
        freq = {}
        for word in words:
            for letter in word:
                freq[letter] = freq.setdefault(letter, 0) + 1
        return freq

    def reduced_words(self):
        words = self.words_cache or self.words_of_length(len(self.game.puzzle))

        letter_positions = letter_indexes(self.game.puzzle)
        del letter_positions[BLANK]
        self.words_cache = [w for w in words if self.matches_positions(w, letter_positions)]

        return self.words_cache

    def matches_positions(self, word, positions):
        """Returns True if a word has its letters in the given positions and if those letters do not exist elsewhere"""
        word = list(word)
        for letter, indexes in positions.iteritems():
            for index in indexes:
                if word[index] != letter:
                    return False
                word[index] = None # mark letter found

            if letter in word:
                return False # extra letter

        return True

    def words_of_length(self, length):
        return (w for w in self.words() if len(w) == length)

    def words(self):
        with open(WORDS) as f:
            for word in f:
                yield word.strip()

if __name__ == "__main__":
    import sys
    if len(sys.argv) == 3:
        word = sys.argv[1]
        solution = sys.argv[2]
    else:
        word = "_______m"
        solution = "bookworm"

    game = Hangman(word, solution)
    ai = HangmanAI(game)

    print "Solving:", word
    print
    while not game.solved:
        guess = ai.guess()
        success = game.try_guess(guess)
        if not success:
            ai.remove_invalid_guess(guess)
        print "Guess:", guess, "Result:", game.puzzle_string

    print
    print "Got word after", len(game.guesses), "guesses."

i dont run code :(