5
\$\begingroup\$

In this challenge, you have to implement a basic spell checker and autocorrector. Your program will use the first input as a source for a dictionary of words, and will use that to autocorrect the second input, finding a close match to some incorrectly spelt words, outputting the result

Specifications

  • You will receive two inputs, one is a sentence/paragraph you use as a source for your spell checker, and the other includes wrong words (they can be correct too) which you have to correct using the first input.
  • Possible mistakes: Missing one letter (e.g. helo), one extra letter (e.g. heello), substitution of one character (e.g. hilp instead of help), transposition of two adjacent characters (e.g. hlep instead of help).
  • In other words, the mistake and the original word have to have a Damerau–Levenshtein distance of one.
  • You can separate the inputs in any reasonable format. For example, instead of using a newline, you can use a pipe sign to separate them. (|) However, watch out so you don't use something like letters because they are used in the 1st input.
  • It's possible for a word to have neither an identical word nor a word with 1 distance from the first input. You will have to leave them unchanged.
  • You don't need to do anything with punctuation. That is, I won't test words that are followed by a punctuation. (E.g. From the first example, I won't ask the correction of 'blod')
  • Challenge is case insensitive, both the input and output. Meaning that if 'The' is used in the 1st input and the 2nd input is 'teh' you can change it to 'The', 'teh', 'teH', and similar cases.
  • If a word is in the first input, but also has a distance of 1 with one of the other words, do not correct it.
  • If there are two words with the same distance, you can output either of them. (E.g. 'en' can change into 'on' and 'in' if the words are both in the first input.) You can also output both of them, but you'll have to use a slash between them. (E.g. 'en' can be corrected into 'in/on')
  • You can assume words are just sequences of letters separated by spaces.
  • You can use STDIN or the closest alternative in your language.
  • Standard loophole rules apply.
  • This is , so the shortest code wins.

Examples

Input:

A criminal strain ran in his blood, which, instead of being modified, was increased and rendered infinitely more dangerous by his extraordinary mental powers. 

increasd mnetal

Output:

increased mental

Input:

The fact is that upon his entrance I had instantly recognized the extreme personal danger in which I lay.

I recognizid dnger en

Output:

I recognized danger in    
\$\endgroup\$
  • 2
    \$\begingroup\$ In the second example, recognize does not occur in the source text (recognized does). Is that intentional? Also, which punctuation characters can the input contain? \$\endgroup\$ – Zgarb Jun 5 '15 at 8:09
  • 1
    \$\begingroup\$ Not a duplicate, but what a weird coincidence \$\endgroup\$ – trichoplax Jun 5 '15 at 10:48
  • 1
    \$\begingroup\$ @Zgarb Sorry, it wasn't intentional. I meant recognized, thanks. Punctuation will appear, however as said in the specifications, you don't need to do anything with punctuation, for example I won't ask "blood" from the first input because it's followed by a punctuation mark. \$\endgroup\$ – JNV Jun 5 '15 at 11:07
  • \$\begingroup\$ @trichoplax Yep, I was really shocked when I saw that. I posted 12 mins earlier than that. (Though they aren't duplicates of each other, they cover different things.) \$\endgroup\$ – JNV Jun 5 '15 at 11:08
3
\$\begingroup\$

CJam, 90 87 bytes

qelN%Sf%~f{1$:W,,_:_2ewWf{\~e\}\Wf{' t_S-}W,),Wf{1$m<S\+m>}++Sf/26,'af+\ff*:+\&\a+0=}S*

Try it online in the CJam interpreter.

\$\endgroup\$
  • \$\begingroup\$ I think this has a problem with words ending with an identical word. (E.g. 'Bathe' will change into 'The') \$\endgroup\$ – JNV Jun 7 '15 at 15:01
  • \$\begingroup\$ @JNV: I hope I can fix that. I've rolled it back to a previous version for now. \$\endgroup\$ – Dennis Jun 7 '15 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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