"social network" edit distance algorithm for causes.com

thesocialnetwork.py

#-------------------------------------------------------------------------------
# Name:        "social network" edit distance algorithm for causes.com
# Author:      ayumi yu, 2011-10-03
# Licence:     MIT license yeayahhh
#-------------------------------------------------------------------------------
#!/usr/bin/env python

# Imported fresh!
import string, codecs

# Globals!
alphabet = list(string.ascii_lowercase)
dictionary = []
longestWordLen = 0
theSocialNetwork = []  # hehe

# FUNctions!
#    Note: substitutedPos tracks an upstream substitution
def friends( word, substitutedPos=-1 ):
    global alphabet
    global dictionary
    global longestWordLen
    global theSocialNetwork

    # Already got it
    if word in theSocialNetwork:
        return 0

    # Length 0
    if word == '':
        return 0

    # Way long
    elif len(word) > longestWordLen:
        return 0

    # Not a word
    elif word not in dictionary:
        return 0

    # Initialize friends counter with +1
    friendCount = 1
    theSocialNetwork.append(word)
    dictionary.remove(word)

    # Friends! / Addition
    #     e.g. If the word is ABC, try *ABC, A*BC, AB*C, ABC*.
    #     Note the upper limit is len + 1.
    # Iterate over len+1 possible insertion spots
    for i in range( 0, len(word) + 1 ):
        # Iterate over alphabet possible letters to insert
        for j in range( 0, len(alphabet) ):
            testWord = word[:i] + alphabet[j] + word[i:]
            friendCount += friends(testWord)

    # Iterate over len substitutable/deletable letters
    for i in range( 0, len(word) ):
        # Friends! / Substitution
        for j in range( 0, len(alphabet) ):
            # Note that if upstream we had substituted to get here,
            # we can disregard that index.
            if j == substitutedPos:
                next
            else:
                testWord = word[:i] + alphabet[j] + word[(i+1):]
                friendCount += friends(testWord, i)

        # Friends! / Deletion
        testWord = word[:i] + word[(i+1):]
        friendCount += friends(testWord)

    return friendCount


# LOGIC

# Load up a dictionary
defaultDictionary = 'word.list'
theDictionary = raw_input("A dictionary, please. [%s] " % defaultDictionary)
if theDictionary == '':
    theDictionary = defaultDictionary

with codecs.open(theDictionary, "r", encoding = "utf-8-sig") as f:
    for line in f:
        dictionary.append( line.strip() )
longestWordLen = len( max( dictionary ) )
print 'Longest word is length %d.' % longestWordLen
print 'Using "%s", %d words loaded.' % ( theDictionary, len(dictionary) )

# Ask for a word
theWord = raw_input("A word, please. ")
print '"%s"\'s social network has %d members.' % ( theWord, friends(theWord) )