#!/usr/bin/python
# 
# Installation:
#    gunzip TWL.gz
#    edit TWL_PATH to contain the path to the TWL file
#
# Sample usage:
#
# I have tiles [telewto] and I want the highest scoring options.
#    ./anagram telewto | ./score | sort -n | tail
#
# I have tiles [telewto] and I want the longest word that ends in "ed".
#    ./anagram telewtoed | grep ed$ | lensort
#
# Use the '_' character to indicate a blank tile, e.g.
#    ./anagram telewt_

import string
import sys

TWL_PATH = "/Path/To/TWL"

# Returns true if two words intersect
def intersect(word1, word2):
  for ch in word1:
    if ch in word2:
      return True
  return False

# Returns a dict containing the letters in 'word' by frequency
def get_count(word):
  d = { }
  for ch in word: d[ch] = d.get(ch, 0) + 1
  return d

# Returns true if the letters in needle are a subset of the letters in
# haystack. 'needle' represents the candidate word and 'haystack' the tiles.
def can_play(needle, haystack):
  if len(needle) > len(haystack): return False
  needle_count = get_count(needle)
  haystack_count = get_count(haystack)
  blank_tiles = haystack_count.pop('_', 0)
  for n in needle_count:
    tiles_needed = needle_count.get(n, 0) - haystack_count.get(n, 0)
    if tiles_needed > 0:
      blank_tiles = blank_tiles - tiles_needed
      if blank_tiles < 0:
        return False  # We didn't have enough letters.
  return True

# Normalizes a line read from a file
def normalize(line):
  return line.strip("\n").lower()

# Main ---

# User input
letters = normalize(sys.argv[1])

# Build an array of letters that we can't use.
# (The intersection test is cheaper than the subset test.)
vmask = []
if '_' not in letters:
  vmask = [ ch for ch in string.ascii_lowercase if ch not in letters ]

# Loop through the dictionary, printing out words that match
for line in file(TWL_PATH):
  word = normalize(line)
  if not intersect(vmask, word) and can_play(word, letters):
    print word