Finding Anagrams with Python

(2010)

Here's a little python program that finds anagrams. I knocked it together real quick one night while my cousin was playing an online anagram game by using code from a Boggle solver I had written previously.

Not much to it. It just reads in a dictionary and runs a little recursive function to check every possible combination of letters. The app is a little bit clever - it hashes all the word prefixes to prevent searching for impossible letter combinations. For example, take the word "apple", the program adds the following keys:

a
ap
app
appl
apple

So if you've got "app", but the only letters remaining are "pqr", you know that "apple" is not a possibility and can save a lot of time by skipping those branches of the search.

Anyway, fun stuff. Here's the code. This is quite a few years old and should be cleaned up, hmm:

import os, sys

# map of letters => counts
letters = {}
for l in sys.argv[1:]:
 if l in letters:
     letters[l] += 1
 else:
     letters[l] = 1

# build a map of every prefix of a real word
# that is, even though "appl" is not a real word
# we keep it anyway because it is the prefix of 
# "apple"
dict = {}
words = open('dict.txt','r').readlines()
for word in words:
    for i in range(len(word)-1):
        if i == len(word)-2 and len(word) > 3:
            dict[word[0:i+1]] = 't'
        else:
            if not dict.has_key(word[0:i+1]):
                dict[word[0:i+1]] = 'n'


# global var holding the solution
soln = {}

def solve(word, letters):
 for l in letters:
     if letters[l] > 0:
         letters[l] -= 1
         if (word+l) in dict:
             if dict[word+l] == 't':
                 soln[word+l] = word+l
             solve(word+l,letters)
         letters[l] += 1

# sort by length
def lensort(x,y):
    return cmp(len(x),len(y))

# find all anagrams
solve("",letters)

# sort and print solution
soln2 = soln.keys()
soln2.sort(lensort)
for w in soln2:
    print w

And here's the output, trying it with my name:

python wracer.py c r a i g e

rag
arc
are
rig
ria
ice
gie
rec
reg
ire
gar
rei
gae
ear
ace
car
age
air
erg
era
ager
crag
cire
rice
race
gear
cage
care
acre
rage
ragi
erica
areic
cigar
grace
ceria
cager
cagier