#!/usr/bin/python

# [python] phl| ./addagram.py /net/doc/random-facts/WORD.LST    
# read dictionary
# best addagram:
#     indeterminations
#     intermediations
#     determinations
#     antimodernist
#     terminations
#     nitrosamine
#     antinomies
#     antinoise
#     sonatine
#     enation
#     eonian
#     inane
#     nine
#     inn

import sys
import string

args = sys.argv[1:]

if len(args) not in (1, 2):
  print "usage: %s <dictfile> [<start-word>]" % sys.argv[0]
  sys.exit(1)

dictfile = args.pop(0)
start = args and args.pop(0) or None
startlen = start and len(start) or 3

def sort(l):
  l = l[:]; l.sort(); return l


# read dictionary and build tree
dictionary = {}
dict = open(dictfile, "r")
while 1: #{
  line = dict.readline()
  if not line:
    break

  word = string.lower(string.strip(line))
  wlen = len(word)
  chrs = string.join(sort(list(word)), "")

  if wlen > startlen or wlen == startlen and (word == start or start == None):
    if not dictionary.has_key(wlen):
      dictionary[wlen] = {}

    dictionary[wlen][chrs] = [word, wlen == startlen and [word, None] or None]
#}
print "read dictionary"
dict.close()

def get_subchrs(chrs):
  subchrs = {}
  for i in range(len(chrs)):
    subchrs[chrs[0:i]+chrs[i+1:]] = 1
  return sort(subchrs.keys())

l = startlen
best = None
found = 1
if dictionary.has_key(startlen):
  while found and dictionary.has_key(l+1):
    l = l + 1
    found = 0
    for chrs in dictionary[l].keys():
      entry = dictionary[l][chrs]
      word = entry[0]
      subentry = None
      for subchrs in get_subchrs(chrs):
        subentry = dictionary[l-1].get(subchrs, None)
        if subentry and subentry[1]:
          break
      if subentry and subentry[1]:
        entry[1] = [word, subentry[1]]
        best = entry
        found = 1

if best:
  print "best addagram:"
  while best[1]:
    best = best[1]
    print "   ", best[0]
else:
  print "no addagrams"