By Ben Nitkin on
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.
#!/usr/bin/python3
#wordtree.py
# 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.
#Effect:
#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 '))
### END SETTINGS ###
class WordTree:
def __init__(self, word, head = ''):
self.word = word
self.head = head
self.children = []
try:
self.process()
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:
results.append(head)
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):
realWords.append(word)
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\
\n\
This program generates a tree of all possible words, given an input.')
while 1:
try:
print('==> ', end='', file = sys.stderr) #Workaround to send prompt to stderr.
word = input()
print(WordTree(word))
except EOFError or KeyboardInterrupt:
print()
exit()
main()