A typing speed test loads up a dictionary of words, and gives you one to type: pinball. You, with your fast but inaccurate fingers, type in pinbnal. Darn it!

Make a program that will print out a random word from a dictionary, then ask for the user to type this word back, and finally return whether or not they got the word right. The catch is: the program must accept minor typos.

Accept a typo if it has only one of the following:

  • one letter is repeated in the input 1 or 2 more times. Only accept the letter if it is directly adjacent to a letter it is next to.
  • one letter in the word is repeated 1 time.
  • 2-4 of the letters in the input are scrambled.

Some acceptable typos of the word pinball are:
pingball pinbala pinbanll
Some unacceptable typos:
pibnannl maxwell pinbalgl

Shortest code wins. Good luck.

  • 5
    \$\begingroup\$ an ingteresring undereretanding ohf what a minoe typpe is... what exactly does "scrambled" include, apparently it's not just swapping letters? \$\endgroup\$ Jul 4, 2012 at 6:57
  • 5
    \$\begingroup\$ But what's pinbala or pinbnal then? The second l is missing completely in both cases. \$\endgroup\$ Jul 4, 2012 at 7:35
  • 4
    \$\begingroup\$ And pingball adds a new letter - it's fundamentally the same error as pinbalgl. \$\endgroup\$ Jul 4, 2012 at 8:07
  • 2
    \$\begingroup\$ I don't see which of your accepted typos includes adding a letter, and why 'pingball' is acceptable while 'pinbalgl' is not. -1 until fixed, sorry. \$\endgroup\$ Nov 25, 2015 at 9:56
  • 1
    \$\begingroup\$ usually asking people to fill-in-the-blank about local files/dictionaries is a bad idea, because my dict/words has some modifications ;) \$\endgroup\$
    – cat
    Nov 25, 2015 at 11:09

2 Answers 2


Mathematica 179

Edit: As Primo correctly notes, the following does not adhere to the constraint of pardoning only those intrusions from QWERTY neighbors. DL distance, of course, has nothing to do with distance on a keyboard. Oh, well. I'll leave up my response, which someone with more patience will easily better.


d = DictionaryLookup[]; i = d[[RandomInteger@{1, Length@d}]];o = InputString["Type: " <> i];
Print["in: ", i, "\nout: ", o, "\n", Switch[i~DamerauLevenshteinDistance~o, 0, "perfect",
1, "ok", _, "wrong"]]


  1. d = DictionaryLookup[] stores a built-in dictionary of 92 k English words in d.
  2. i = d[[RandomInteger@{1, Length@d}]] selects a random word and stores it in i.
  3. o = InputString["Type: " <> i]; opens a dialog window (see figure) with the prompt "Type [i]."
  4. i~DamerauLevenshteinDistance~o computes the Damerau-Levenshtein distance beween the requested word and the word typed by the user. If the DL distance = 0, "perfect"; if the DL distance = 1, "ok"; otherwise, "wrong".


Test Results

For the first 7 tests, the input string, i, was manually set to "pinball". The results were as desired with the exception of "pinbalgl", which was considered acceptable because it returns a DL distance value of 1.

in: pinball
out: pinball

in: pinball
out: pingball

in: pinball
out: pinbala

in: pinball
out: pinbanll

in: pinball
out: pinbannl

in: pinball
out: maxwell

in: pinball
out: pinbalgl

in: tureen
out: turen

in: feeder
out: feedr

in: tarmacs
out: tarmax

  • \$\begingroup\$ I like the interface :D Not sure if it answers the question exactly as stated though. Judging from the examples, (I think) it should accept an inserted character (and here's where the wording gets a bit unclear) if and only if one or both of the two characters it is adjacent to in the string is also adjacent to it on a keyboard (presumably qwerty). A test slightly stronger than the Levenshtein distance. \$\endgroup\$
    – primo
    Dec 17, 2012 at 19:06
  • \$\begingroup\$ @primo. I see your point. I missed entirely the constraint about adjacent keys. Clearly, that would require considerably more coding. \$\endgroup\$
    – DavidC
    Dec 17, 2012 at 19:12
  • \$\begingroup\$ Even so, I would still consider this an acceptable solution, given the lack of participation. You already have my +1 \$\endgroup\$
    – primo
    Dec 17, 2012 at 19:33
  • \$\begingroup\$ Thanks. I thought the question looked lonely and abandoned being unanswered. So I gave it my best shot. To craft a fully suitable response, I'd need more time than I have. \$\endgroup\$
    – DavidC
    Dec 17, 2012 at 19:46

Python 2, 634 581 568 565 bytes

import random
for j in range(len(s)-1):d[s[j]]=d.get(s[j],"")+s[j+1]
q=any([v[:j]+e(v[j:j+4])+v[j+4:]==u[:j]+e(u[j:j+4])+u[j+4:]for j in range(l-3)])
while i<l*g:
 if v[i]!=u[i]:
  if any([0<=i<l and u[i]in d[v[i+c]]for c in-1,0]):n+=1;g-=(b and u[i]!=b);b=u[i];del u[i]
  elif u[i]in v:r+=1;del u[i]
print'good'if q+g*(n+2*r<3)else'bad'

It took a heck of lot of bytes to meet every single little special case and exception that this problem called for, and that's reflected in the size. There's probably some optimizations I'm missing, but I'm just happy that I met all the requirements.

To run it, put your list of lowercase words in a file called d in the same directory and just run.

It should be clear how this works once you know what each variable is:

  • s: a String of adjacent keys used to construct d
  • d: a Dictionary encoding a graph of key adjacencies, according to the keyboard i'm using right now. Lines 1 through 4 set this up.
  • v: the random word, first as a string, then as a list of characters
  • u: the User input, as a list of characters
  • e: the sortEd built-in
  • i: the Index into the correct word
  • n: the number of times an incorrect character that is Next to a correct character appears
  • r: the number of times an incorrect character that is in the word Repeats
  • g: whether the input is currently believed to be Good
  • l: the correct Length of the word
  • q: whether some shuffling of four adjacent letters in the user input would yield the correct word
  • j: a temp used in the creation of q

The important parts are:

  • the for at the top, which maps each letter in s to the next character. At the end, each lowercase letter is mapped to a string containing all letters adjacent on the keyboard (some with several repeats, but it doesn't matter).
  • the line where q is evaluated, which basically just sorts each set of four adjacent characters in both the input and correct word while leaving the rest of the lists alone. If sorting any such part results in both lists being the same, this is an allowed typo according to rule 3
  • the while loop, which iterates over both strings, looking for mismatches. Where one is found, it determines whether its of type 1 or type 2, preferring the former since we're allowed more type 1 errors than type 2 errors. The numbers of errors of type 1 and 2 are counted in n and r respectively. Errors which don't fall into either of these categories set g to 0 which breaks the loop. Notice the g-=(b and u[i]!=b);b=u[i]. This checks that this type 1 error involved the same character (saved in b) as last time (if there was a last time). This is because the first rule allows us to repeat the same character 1 or 2 times, but not two different characters.
  • the final line outputs good if and only if q OR (g AND (n<3 AND r==0) OR (r<2 AND n==0) ). Type 3 errors are mutually exclusive with the other types, but it is possible to have both type 1 and 2 in the same input. The condition is complex to allow one or the other but not both.

NB: this program will NOT accept "pinbala" as a correct spelling of "pinball", as it does not fall into any of the three described typo categories, as pointed out by ceased to turn counterclockwis


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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