Source

phone2word / phone2word.py

#!/usr/bin/env python

# This is a very direct translation of phone2word.hs

import sys
from collections import defaultdict

letters = [ ('0', "")
          , ('1', "")
          , ('2', "ABC")
          , ('3', "DEF")
          , ('4', "GHI")
          , ('5', "JKL")
          , ('6', "MNO")
          , ('7', "PQRS")
          , ('8', "TUV")
          , ('9', "WXYZ")
          ]

numbersMap = dict((l,c) for (c,word) in letters for l in word)

def getNumber(char):
    if char.isdigit():
        return char
    else:
        return numbersMap.get(char.upper())

def buildWordTree(words):
    retval = defaultdict(list)
    for w in words:
        digits = convWord(w)
        if digits is not None:
            addWordToList(w, retval[digits])
    return retval

def convWord(word):
    retval = []
    for c in word:
        d = getNumber(c)
        if d is None:
            return None
        retval.append(d)
    return ''.join(retval)

def addWordToList(word, words):
    if word.upper() not in map(lambda s: s.upper(), words):
        words.append(word)

noWords = () # we only need one of these
def findWords(digits, store):
    return store.get(digits, noWords)

def showCombo(combo):
    return '-'.join(combo)

def hasWord(chars):
    return any(not c.isdigit() for c in chars)

def findCombos(digits, store):
    wordMap = makeWordMap(digits, store)
    allMap = addDigitWords(digits, wordMap)
    return findRoutes(allMap, len(digits))

def makeWordMap(digits, store):
    tl = len(digits)
    retval = []
    for pos in xrange(0, tl):
        for l in xrange(1, tl - pos + 1):
            words = findWords(digits[pos:pos+l], store)
            if words:
                retval.append(((pos,l),words))
    return retval

def addDigitWords(digits, wordMap):
    tl = len(digits)
    wordPos = set(p for (p,ws) in wordMap)
    endPositions = [0] + findEndPositions(wordPos)
    newWords = set()
    for pos in endPositions:
        rightWords = wordsToRightOf(pos, wordPos) + [(tl,1)]
        rightWords.sort()
        n_pos, n_len = rightWords[0]
        for w_pos, w_len in rightWords:
            if w_pos < n_pos + n_len:
                gapWidth = w_pos - pos
                if gapWidth > 0:
                    digitWord = digits[pos:pos+gapWidth]
                    newWords.add(((pos, gapWidth), (digitWord,)))
    return wordMap + list(newWords)

def wordsToRightOf(pos, wordPos):
    return [ (p,l) for (p,l) in wordPos if p >= pos ]

def findEndPositions(wordPos):
    return list(set(pos + l for (pos, l) in wordPos))

def findRoutes(wordMap, totalLength):
    combos = findRoutesR(wordMap, 0, totalLength)
    if len(combos) == 1 and len(combos[0]) == 1 and not (hasWord(combos[0][0])):
        return []
    return combos

def findRoutesR(wordMap, start, end):
    retval = []
    for ((p,l),words) in wordMap:
        if p == start:
            for word in words:
                if p + l == end:
                    retval.append([word])
                else:
                    for combo in findRoutesR(wordMap, start + l, end):
                        if (hasWord(word) or hasWord(combo[0])):
                            retval.append([word]+combo)
    return retval

def getWords(fileName):
    with open(fileName) as fp:
        return fp.read().split('\n')

def countWords(t):
    return sum(map(len, t.values()))

def main():
    dictFile = sys.argv[1]
    words = getWords(dictFile)
    wordTree = buildWordTree(words)
    print "Words: %d" % countWords(wordTree)
    while True:
        digits = raw_input("Enter phone number: ")
        digits = filter(lambda d: d.isdigit(), digits)
        combos = findCombos(digits, wordTree)
        if len(combos) == 0:
            print " [None]"
        else:
            for c in combos:
                print showCombo(c)

if __name__ == '__main__':
    main()
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.