"Python" as an Alternative to Java - http://www.norvig.com/java-lisp.html

words.py

# "Python" as an Alternative to Java.
#
# Given a list of words and a list of phone numbers,
# find all the ways that each phone number can be
# expressed as a list of words.
# http://www.flownet.com/ron/papers/lisp-java/
#
# Here, you can find Peter Norvig's solution in CL:
# http://www.norvig.com/java-lisp.html
#
# It took 4 hours of me. Well, I guess I am not as
# good as Peter Norvig is :)

from collections import defaultdict
import sys

table = {
    'e': '0',
    'jnq': '1',
    'rwx': '2',
    'dsy': '3',
    'ft': '4',
    'am': '5',
    'civ': '6',
    'bku': '7',
    'lop': '8',
    'ghz': '9',
    '"-': '',
}

letters = {l: v for k, v in table.items() for l in k}
letters.update({k.upper(): v for k, v in letters.items()})

dict_file = sys.argv[1]
phone_file = sys.argv[2]

phone_mappings = defaultdict(list)


def word_to_phone(word):
    return ''.join([letters[l] for l in word])


def filter_digits(phone):
    return filter(lambda c: c.isdigit(), phone)


def list_prefixes(phone):
    return [phone[:i] for i in range(1, len(phone) + 1)]


def find_words(phone):
    if not phone:
        return []
    prefixes = filter(phone_mappings.has_key, list_prefixes(phone))
    if not prefixes:
        ret = []
        if len(phone) == 1:
            return [phone]
        for w in find_words(phone[1:]):
            if not w[0].isdigit():
                ret.append(phone[0] + ' ' + w)
        return ret
    ret = []
    for p in prefixes:
        for word in phone_mappings[p]:
            if p == phone:
                ret.append(word)
            else:
                ret.extend([word + ' ' + w
                            for w in find_words(phone[len(p):])])
    return ret

with open(dict_file) as f:
    for word in f.readlines():
        word = word.rstrip()
        phone_mappings[word_to_phone(word)].append(word)

with open(phone_file) as f:
    for phone in f.readlines():
        phone = phone.rstrip()
        for word in find_words(filter_digits(phone)):
            print '%s: %s' % (phone, word)