import sys

# -----------------------------------------------------------
# getWords - Reads 'fileName' and returns an array of the
#            lines found in that file.  Exits the program
#            if the file cannot be opened.
# -----------------------------------------------------------

def getWords(fileName):

   try:

      f = open(fileName, "r")

   except IOError:

      print("Could not open file: [" + fileName + "]")
      sys.exit()

   content = f.readlines()
   f.close()

   list = []

   for word in content:
      list.append(word.strip().lower())

   return(list)

# -----------------------------------------------------------
# isValidWord - Does 'word' appear in our word list?
# -----------------------------------------------------------

def isValidWord(word, words):
   return(word.lower() in words)

# -----------------------------------------------------------
# extraLetterMatch - Can we turn 'longer' into 'shorter'
#                    by removing a letter?
# -----------------------------------------------------------

def extraLetterMatch(shorter, longer):

   n = len(longer)

   if len(shorter) + 1 != n:
      return(False)

   for i in range(0, n):

      s = longer[0:i] + longer[i + 1:]

      if s == shorter:
         return(True)

   return(False)

# -----------------------------------------------------------
# singleLetterDifferenceMatch - Are 'first' and 'second' the
#                               same except for one letter?
# -----------------------------------------------------------

def singleLetterDifferenceMatch(first, second):

   n = len(first)

   if n != len(second):
      return(False)

   count = 0

   for i in range(0, n):
      if first[i] != second[i]:
         count += 1

   return(count == 1)     

# ----------------------------------
# getAlternatives
# ----------------------------------

def getAlternatives(word, words):

   # ------------------------------------------
   # We look for these typos/misspellings:
   #
   # a) missing letter
   # b) transposed letters
   # c) extra letter
   # d) single changed letter
   # e) missing space
   # ------------------------------------------

   alternatives = []

   # -------------------------------------------------
   # For each entry in 'words', can we create 'word'
   # by removing a single letter from the entry?
   # -------------------------------------------------

   for entry in words:
      if extraLetterMatch(word, entry):
         alternatives.append(entry)

   # ---------------------------------------------
   # Now, transpose each pair of letters in
   # 'word' and see if a valid word results
   # ---------------------------------------------

   for i in range(1, len(word)):

      other = word[0:i - 1] + word[i] + word[i - 1] + word[i + 1:]

      if isValidWord(other, words):
         alternatives.append(other)

   # ---------------------------------------------
   # For each entry in words, can we create this
   # entry by removing a letter from 'word'?
   # ---------------------------------------------

   for entry in words:
      if extraLetterMatch(entry, word):
         alternatives.append(entry)

   # ---------------------------------------------
   # For each word in words, can we create this
   # word by altering one letter from 'word'?
   # ---------------------------------------------

   for entry in words:
      if singleLetterDifferenceMatch(entry, word):
         alternatives.append(entry)

   # ---------------------------------------------
   # Can we create two valid words by splitting
   # 'word' into two parts?
   # ---------------------------------------------

   for i in range(1, len(word)):

      left  = word[0:i]
      right = word[i:]

      if isValidWord(left, words) and isValidWord(right, words):
         alternatives.append(left + " " + right);

   return(alternatives);

# ----------------------------------
# processWord
# ----------------------------------

def processWord(word, words):

   if isValidWord(word, words):
      print(word + " appears to be spelled correctly")

   else:

      print("Could not find: '" + word + "' in the dictionary,")

      alternatives = getAlternatives(word, words)

      if len(alternatives) == 0:

         print("and no similar words were found")

      else:

         print("but here are some similar words:")

         i = 1

         for s in alternatives:
            print("   %d) %s" % (i, s))
            i += 1

   print()

# ----------------------------------
# Script Begins Here
# ----------------------------------

wordsFileName = "words.txt"
words         = getWords(wordsFileName)

list = [ "testing", "dgo", "ct", "berd", "frabbit", "energyturtle", "ttestingg" ]

for item in list:
   processWord(item, words)