breathalyzer.py

import sys

# Get word list here: https://www.facebook.com/jobs_puzzles/twl06.txt
VALID_WORD_LIST_FILE = "twl06.txt"

def main():
    try:
        input_phrase = sys.argv[1]
    except Exception, e:
        print "Get yourself fixed."
        exit()

    # Initializing word list
    word_list = get_valid_words_list(VALID_WORD_LIST_FILE)

    for word in input_phrase.split():
        errors = check_errors_for(word, word_list)
        print errors

def get_valid_words_list(file_name):
    try:
        f = open(file_name, "r")
    except Exception, e:
        raise Exception, "Check word list file path"

    word_list = []
    for word in f:
        word_list.append(word.rstrip())

    return word_list

def check_errors_for(phrase, word_list):
    """Return the numbers of changes which need to be applied to a
    `phrase` in order be valid from a given a word_list

    Arguments:
    - `phrase`: string
    - `word_list`: list
    """
    errors = 0

    phrase = phrase.upper()

    # For each word
    if phrase in word_list:
        return 0
    else:
        errors = 10000
                   # Uhhh... the power of filter() and lambdas
        for bla in filter(lambda item: item.startswith(phrase[0]), word_list):
            num = levenshtein(phrase, bla)
            if num < errors:
                errors = num
    return errors

def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return levenshtein(s2, s1)
    if not s1:
        return len(s2)
 
    previous_row = xrange(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
 
    return previous_row[-1]

if __name__ == '__main__':
    main()