JUMBLER

word_jumble.py

#!/usr/bin/python
"""Let's solve a jumble!
"""
MY_WORD_FILE = "/usr/share/dict/words"
class Trie(object):
  def __init__(self):
    self.root = {}
    
  def add(self, word):
    """Add a word to the Trie."""
    node = self.root
    for c in word:
      node = node.setdefault(c,{})
    node[None] = True # Terminate word.
      
  def check(self, word):
    """Is a word in the Trie?"""
    node = self.root
    for c in word:
      try:
        node = node[c]
      except KeyError:
        return False
    return None in node # Is there a word terminator? If not, then fail.

  def get_promising(self, c, node=None):
    """Given a letter and a Trie node, return set of all promising letters (+None)."""
    node = node if node else self.root
    try:
      return node[c]
    except:
      return None

def jumbler(word):
  """Return list of all possible words from these letters."""
  word_d = {}
  for c in word: word_d[c] = word_d.get(c,0)+1
  return _jumbler(word_d)
  
def _jumbler(word_d, prefix=None, node=None):
  """Helper function, uses recursion to find word paths."""
  # Start with each unique letter.
  # return all words that can be made from that letter given the remaining letters
  if not word_d: return []
  if prefix is None: prefix = []
  r = []
  letters = word_d.keys()
  for c in letters:
    # Remove this letter from recursive solutions.
    prefix.append(c)
    word_d[c] -= 1
    if word_d[c] == 0: del word_d[c]
    # Get all promising next steps
    new_node = T.get_promising(c,node)
    if new_node:
      if None in new_node:
        r.append("".join(prefix)) # We found a word!
      r += _jumbler(word_d, prefix=prefix, node=new_node)
    # Replace this letter for future iterations.
    word_d[c] = word_d.get(c,0)+1
    prefix.pop()
  return r
  
if __name__ == "__main__":
  # Compile our Trie from a dictionary.
  print "Compiling Dictionary [%s]..." % MY_WORD_FILE
  T = Trie()
  for line in open(MY_WORD_FILE):
    T.add(line.strip())
  print "OK, you may jumble now: jumbler(your_word)..."