Commits

Luke Plant  committed 8803167

Added Python version.

  • Participants
  • Parent commits 055bf77
  • Branches simple-wordtree

Comments (0)

Files changed (1)

File 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()