People sometimes make spelling eorrors. A lto. Your challenge is to write a program that can take a string with certain spelling errors, such as the switching of I and E, and correct those mistakes. This has to be able to make changes to any combination of characters in any string, and fix the spelling errors. This is a , the winner will be chosen in three days. If I need to clarify any additional details, please do say, and I will add it to my challenge. Good luck!


  • You may read correctly-spelled words from a file.
  • You will read the string from standard input.
  • You need only correct basic spelling errors.
  • It's ok if your program makes a few errors.
  • 2
    \$\begingroup\$ Is it OK if we read correctly spelled words from a file? And are we reading from stdin? \$\endgroup\$ – golfer9338 Jul 9 '14 at 21:19
  • \$\begingroup\$ @golfer9338 Yes and yes. \$\endgroup\$ – DatEpicCoderGuyWhoPrograms Jul 9 '14 at 21:38
  • 3
    \$\begingroup\$ Yes, there are some things which you need to clarify. What do you mean by "has to be able to make changes to any combination of characters in any string"? Which errors does it need to correct? What about overcorrection? What about other languages? \$\endgroup\$ – Peter Taylor Jul 9 '14 at 22:02
  • \$\begingroup\$ @PeterTaylor It needs to be able to fix basic spelling errors. Such as the swapping of I and E. Like misspelling their. It doesn't matter what language you make it in. In the case of overcorrecting, that's okay if it makes a few mistakes, even advanced autocorrect like the one on my iphone makes mistakes. \$\endgroup\$ – DatEpicCoderGuyWhoPrograms Jul 9 '14 at 22:07
  • 1
    \$\begingroup\$ You need a set of production rules like "If you see this, it should be replaced with this." Making it a popularity contest is not an excuse for completely leaving out the details of the task you have asked us to do. Btw, golfer9338 added a neat idea: read correctly spelled words from a file. His edit was not perfect, but I approved it anyway because I think that his idea could salvage this challenge. \$\endgroup\$ – Rainbolt Jul 11 '14 at 2:01

for a real "good" correction, we need to know the set of words which are "reasonable". In a program editor, this depends on the word before the cursor. This may be either a class or variable name, or the name of the function to be called (some syntax awareness required here). In a general text editor, this would be a list of words from a dictionary.

In the following code, I assume that the list of "good" words is found in "candidates", in Smalltalk this would be one of:

Smalltalk allClasses collect:[:cls | cls name]

for class names, or

Smalltalk allClasses collectAll:[:cls | cls methodDictionary keys] as:Set

for the names of all methods.

Of course, in a real world corrector, this would take into account the current scope to restrict the set of possible candidates.

The code then selects the best candidate by its editing distance, which is the distance between two strings based on the weighted number of insert, delete and replace operations required to change one string onto another. All Smalltalks provide a "spellAgainst:" method in their String class, which is based on levenshtein or a similar algorithm.

"the following is of course very Smalltalk dialect specific,
 as the GUI frameworks are slightly different.
 It assumes there is an editor object, which represents the code edit

candidates := <one of the above>.
wordToFix := editor wordBeforeCursor.

best := candidates detectMax:[:each | each spellAgainst: wordToFix].

editor selectWordBeforeCursor.
editor replaceSelectionBy:best.

PS: one of the coolest features of Smalltalk is that the IDE is part of your program and vice versa (they are the same), so you can actually add the above code fragment to your editor's keyPress method and have it work immediately!

| improve this answer | |


This uses Levenshtein distance, but doesn't account for non-alpha characters and case. Corrects single misspelled words. Enter a string on stdin, output on stdout, and have a newline separated list of words in a file called words.txt in the same directory.


# Open list of correcly-spelled words.
wordFile = open("words.txt")
threshold = 8
listOfWords = input().split()
index = 0

def lev(a, b):
    if min(len(a), len(b)) == 0:
        return max(len(a), len(b))
        return min(lev(a[:-1], b) + 1, lev(a, b[:-1]) + 1, 
            lev(a[:-1], b[:-1]) + int(not a[-1] == b[-1]))

for x in listOfWords:
    replacement = (x, threshold + 1)

    for word in wordFile:
        x = x.lower()
        word = word[:-1].lower()

        if x == word:
            replacement = (x, 0)
            break # Some words may actually be spelled correctly!

        d = lev(x, word)
        if (d < threshold) and (replacement[1] > d):
            replacement = (word, d)

    listOfWords[index] = replacement[0]
    index += 1



All words are corrected now.

| improve this answer | |
  • \$\begingroup\$ Python3, I take it? \$\endgroup\$ – DatEpicCoderGuyWhoPrograms Jul 9 '14 at 23:34
  • 1
    \$\begingroup\$ @DatEpicCoderGuyWhoPrograms Yes. \$\endgroup\$ – golfer9338 Jul 10 '14 at 0:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.