"""
Solve phone number -> word problem.

See http://www.norvig.com/java-lisp.html for a description of the problem.
"""

# Log:
# 4:10 start 4:20 finished reading problem 4:28 done coding 4:34 done debugging 4:39 done documenting
# too slow, optimized.  4:59 done optimizing, 5:16 fixed mis-reading of problem, 5:19 moved some
# comments around

import string

trans_table = string.maketrans('ejnqrwxdsyftamcivbkulopghz', '01112223334455666777888999')

def word_to_phone(s):
  """
  Translate a word in the dictionary to the corresponding string phone number (digits only)
  """
  return s.lower().translate(trans_table, '-"')

def phone_encodings(phone, phone_to_words, prev_is_number=False):
  """
  Yield all word encodings (as a list of individual word strings) of the given phone number.

  Here phone is the string phone number with non-digit chars stripped, phone_to_words
  is a dict where the keys represent partial phone numbers and the values are a list of all
  words in the dictionary which map exactly to the given partial phone number.  Finally,
  prev_is_number is a bool for whether the previous word was a number.
  """
  if len(phone) == 0:
    yield []
    return
  # Try all words to see which match the beginning of our current phone number.
  count = 0
  for sublen in range(1, len(phone)+1):
    num = phone[:sublen]
    for word in phone_to_words.get(num, []):
      count += 1
      # Recurse on the remaining part of the phone number.
      for rest in phone_encodings(phone[len(num):], phone_to_words):
        yield [word] + rest
  # Try digits iff no word matches and the previous word was not a digit.
  if not prev_is_number and count == 0:
    for rest in phone_encodings(phone[1:], phone_to_words, True):
      yield [phone[0]] + rest

def main(dictfile='dict.txt', phonefile='phone.txt'):
  """
  Solve phone encoding problem for given dictionary file (list of words) and phone file.
  """
  d = open(dictfile, 'rU').read().split()
  phones = open(phonefile, 'rU').read().split()

  # Build multimap from phone number parts to corresponding words that map exactly to that
  # number (see phone_encodings() docstring).
  phone_to_words = {}
  for word in d:
    num = word_to_phone(word)
    phone_to_words.setdefault(num, [])
    phone_to_words[num].append(word)
  for phone in phones:
    for encoding in phone_encodings(phone.replace('-', '').replace('/', ''), phone_to_words):
      print phone + ': ' + ' '.join(encoding)

if __name__ == '__main__':
  main()