Tomb Raider

#-*- coding: utf-8 -*-
#!/usr/bin/env python
from __future__ import with_statement

button_mapping = {
    'A' : 2, 'B' : 2, 'C' : 2,
    'D' : 3, 'E' : 3, 'F' : 3,
    'G' : 4, 'H' : 4, 'I' : 4,
    'J' : 5, 'K' : 5, 'L' : 5,
    'M' : 6, 'N' : 6, 'O' : 6,
    'P' : 7, 'Q' : 7, 'R' : 7, 'S' : 7,
    'T' : 8, 'U' : 8, 'V' : 8,
    'W' : 9, 'X' : 9, 'Y' : 9, 'Z' : 9,
}


"""
{ word_signature:word }
"""
signatures = {}

def suffeient(word):
    """
    remove empty and un-mapped strings 
    """
    if not word:
        return False
    if len(word) >= 2 and word[-2] == "\'":
        return False
    for c in word:
        if not (c.upper() in button_mapping.keys()):
            return False
    return True

def make_signature(word, sig_dict):
    #def action_maker(seq):
    #    return lambda c: seq.append(c)
    sig_tmp = []
    #f = action_maker(sig_tmp)
    [ sig_tmp.append(str(button_mapping[c])) for c in [c.upper() for c in word] ]
    sig_dict[''.join(sig_tmp)] = word


def make_signatures(words):
    global signatures
    [ make_signature(word, signatures) for word in words if suffeient(word) ]
    
   
def build_word_list(number, words_dict, indent=0):
    """
    Brief introduction of the algorithm:
    
    Find all of the signatures that are contained in the number in the signature dict
    Sort the matched keys in decend order
    For each of the matched element:
        divide the element into 3 parts: header, matched, reminder
        call the build_word_list recursively to find the possible matched word
        for the header and reminder parts, respectively
        examine the result and return
        
    There might be more than one word having the same signature, it depends the
    signature-building algorithm and the signature storage's data structure. In
    this solution the words having the duplicated signatures are omitted to
    reduce the complexity of the implementation; this simplification should not
    (um..., maybe not:-)) affect the correctness of the algorithm.
    """
    
    def compose_result(header, matched, reminder):
        ret = "%s-%s-%s" % (header, matched, reminder)
        if ret[0] == '-':
            return ret[1:]
        elif ret[-1] == '-':
            return ret[0:-1]
        else:
            return ret
    
    #print '%sinput:%s' % (indent * '.', number )
    if not number:
        return True, number
    if number in words_dict.keys():
        #print '%smatches:%s' % ( indent * '.', words_dict[number] )
        return True, number
    else:
        possible_matches = [num for num in words_dict.keys() if num in number]
        possible_matches.sort(lambda a,b:len(a) < len(b) and 1 or -1)
        #print '%spossible_matches: %s' % (indent * '.', [ (word, words_dict[word]) for word in possible_matches ])
        
        for matched in possible_matches:
            header_num, matched_num, reminder_num = number.partition(matched)
            #print "header_num:%s, matched_num:%s, reminder_num:%s" % (header_num, matched_num, reminder_num)
            header_matched, header_word = build_word_list(header_num,
                                                          words_dict, indent + 1)
            reminder_matched, reminder_word = build_word_list(reminder_num,
                                                              words_dict, indent + 1)
            if header_matched and reminder_matched:
                return True, compose_result(header_word, matched, reminder_word)
            elif header_matched and not reminder_matched:
                return False, compose_result(header_word, matched, reminder_num)
            elif not header_matched and reminder_matched:
                return False, compose_result(header_num, matched, reminder_word)
            elif not header_matched and not reminder_matched:
                return False, compose_result(header_num, matched, reminder_num)
            else:
                pass
        return False, number
    
def output(build_result):
    global signatures
    ret = ""
    grouped_result = build_result[1].split('-')
    #print "build result %s, %s:" % build_result
    for group in grouped_result:
        if signatures.has_key(group):
            ret = ret + "-" + signatures[group]
        else:
            ret = ret + "-" + group
    return ret[1:]

def input(number):
    return ''.join(str(number).split('-'))


if __name__ == '__main__':
    with file('words') as f:
        trimed = [ line[0:-1] for line in f ]
        make_signatures(trimed)
        
        word_list = build_word_list('118737829', signatures)
        print word_list and output(word_list) or "None"
        
        word_list = build_word_list('7425877', signatures)
        print word_list and output(word_list) or "None"
        
        word_list = build_word_list('74258777425877', signatures)
        print word_list and output(word_list) or "None"
        
        word_list = build_word_list(input('1-800-7425-877'), signatures)
        print word_list and output(word_list) or "None"