Mind Games

I recently learned of a travel word game with a few simple rules:

  • Start with any word.
  • Construct a new word, using all but one of the letters of the original word.
  • Repeat until you have a one letter word.

I decided to replicate it using Python and a dictionary file, and here are the results. The program consists of a WordTree class and a small wrapper. Given a word to begin with, the class finds all permutations of the word, less one character. It then spellchecks each one, discarding the gibberish.

Next, it creates a child WordTree class for each of its valid words. Through the magic of recursive processing, it creates a tree of slowly shrinking words.

WordTree has a few features that are just for show. It uses a custom __str__() function that prints a representation of the entire tree, using DOS box characters for prettiness. There are also two levels of notification for progress updates, and the dictionary is customizable.


# Benjamin Nitkin
# Summer 2012
# There's a game where you start with a word, then remove a letter
# and try to make another word, repeating until you're down to one
# letter.
# It seemed like it'd be fun to copy in code.
# I'm also brushing up on Python3 syntax.

import readline, sys

### SETTINGS ###

#Used in the initial output screen.
#PRINT_LEVEL[0]: Print basic status messages
#PRINT_LEVEL[1]: Show more details.
#Note that print() is a slow function, and
#setting PRINT_LEVEL too low will slow the program.
PRINT_LEVEL = [3, 5]

#Used to delimit layers of recursion.
HEAD = '┃ '
PAD  = '┣ '
CLEAR = '                                      \r'

#A dictionary file - a long list of newline-seperated words.
#Cracklib is a linux thing; in Windows, try something else.
DICT = '/usr/share/dict/american-english'

#The dictionary itself, populated from the file
WORDS = []
for word in open(DICT, 'r').readlines():
    #Import and sanitize dictionary.
    WORDS.append(word.rstrip('\r\n     '))

class WordTree:
    def __init__(self, word, head = ''):
        self.word = word
        self.head = head
        self.children = []
        except KeyboardInterrupt:
            print('\n ***Interrupted. There may be a partial tree built.***')
    def __str__(self):
        string = self.head + PAD + self.word + '\n'
        for child in self.children:
            if len(child.word): string += str(child)
        return string
    def process(self):
        notificate = 0
        if len(self.word) > PRINT_LEVEL[0]: notificate = 1
        if len(self.word) > PRINT_LEVEL[1]: notificate = 2
        if notificate == 1: print(self.head, PAD, 'Processing children of ',
self.word, sep='', file=sys.stderr)
        if notificate == 2: print(CLEAR, self.head, PAD, 'Finding permutations of ',
self.word, sep='', end = '\r', file=sys.stderr)
        possibleWords = self.removeLetter()
        if notificate == 2: print(CLEAR, self.head, PAD, 'Spellchecking children of ',
self.word, sep='', end = '\r', file=sys.stderr)
        words = self.spellcheck(possibleWords)
        if notificate == 2: print(CLEAR, self.head, PAD, 'Processing children of ',
self.word, sep='', file=sys.stderr)
        for word in words:
            self.children.append(WordTree(word, head = self.head + HEAD))
    def removeLetter(self):
        possibleWords = []
        for index in range(len(self.word)):
            possibleWords += self.permutations(self.removeIndex(index), results=[])
        return possibleWords
    def removeIndex(self, index, word = None):
        if word == None: word = self.word
        return word[:index]+word[index+1:]
    def permutations(self, letters, head = '', results = []):
        #Find all of the permutations of a set of letters
        for index in range(len(letters)):
            lettersTemp = self.removeIndex(index, letters)
            headTemp = head+letters[index]
            results = self.permutations(lettersTemp, headTemp, results)
        if len(letters) == 0:
        return results
    def spellcheck(self, wordList):
        #Checks a list of words against a dictionary; returns a unique list
        #of correctly spelled words.
        realWords = []
        for word in wordList:
            if (word in WORDS) and (word not in realWords):
        return realWords

def main():
    print('This program solves a simple game with the following rules:\n\
 - Start with a word. \n - Remove one letter to make another word\n\
 - Repeat until you arrive at a one letter word\n\
 This program generates a tree of all possible words, given an input.')
    while 1:
            print('==> ', end='', file = sys.stderr) #Workaround to send prompt to stderr.
            word = input()

        except EOFError or KeyboardInterrupt: