Source

pythonwise / word_reduction.py

#!/usr/bin/env python
# A little solution to http://ddj.com/cpp/202806370?pgno=3
# Works fast enough as well (running on http://www.gutenberg.org/etext/3201)
# $ time ./word_reduction.py dictionaries/SINGLE.TXT
# restraint's
# restraints
# restrains
# retrains
# retains
# retain
# retin
# rein
# rin
# in
# n
# 
# real    0m4.088s
# user    0m4.023s
# sys     0m0.065s

DICTIONRAY = set()

def load_dictionary(filename):
  DICTIONRAY.add("a")
  DICTIONRAY.add("i")
  for line in open(filename):
      DICTIONRAY.add(line.strip())

def _reduction(word):
  if word not in DICTIONRAY:
      return []
  if len(word) == 1:
      return [word]

  for i in range(len(word)):
      subword = "%s%s" % (word[:i], word[i+1:])
      if subword not in DICTIONRAY:
          continue
      path = reduction(subword)
      if path:
          return [word] + path
  return []

CACHE = {}
def reduction(word):
  if word not in CACHE:
      CACHE[word] = _reduction(word)

  return CACHE[word]

def main(argv=None):
  if argv is None:
      import sys
      argv = sys.argv

  from os.path import isfile
  from optparse import OptionParser

  parser = OptionParser("usage: %prog DICTIONRAY")

  opts, args = parser.parse_args(argv[1:])
  if len(args) != 1:
      parser.error("wrong number of arguments") # Will exit

  dictfile = args[0]
  if not isfile(dictfile):
      raise SystemExit("error: can't find %s" % dictfile)

  load_dictionary(dictfile)
  for word in sorted(DICTIONRAY, key=lambda w: len(w), reverse=1):
      path = reduction(word)
      if path:
          print "\n".join(path)
          break

if __name__ == "__main__":
  main()
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.