Sign up ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question

This question has an open bounty worth +50 reputation from ghosts_in_the_code ending in 5 days.

This question has not received enough attention.

an ingteresring undereretanding ohf what a minoe typpe is... what exactly does "scrambled" include, apparently it's not just swapping letters? – ceased to turn counterclockwis Jul 4 '12 at 6:57
e.x. water -> waert (ert is scrambled ter) or wtrae (trae is scrambled ater) – beary605 Jul 4 '12 at 7:02
But what's pinbala or pinbnal then? The second l is missing completely in both cases. – ceased to turn counterclockwis Jul 4 '12 at 7:35
And pingball adds a new letter - it's fundamentally the same error as pinbalgl. – Peter Taylor Jul 4 '12 at 8:07
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. – Leif Willerts yesterday

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

share|improve this answer
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. – primo Dec 17 '12 at 19:06
@primo. I see your point. I missed entirely the constraint about adjacent keys. Clearly, that would require considerably more coding. – David Carraher Dec 17 '12 at 19:12
Even so, I would still consider this an acceptable solution, given the lack of participation. You already have my +1 – primo Dec 17 '12 at 19:33
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. – David Carraher Dec 17 '12 at 19:46

Python 2, 634 581 568 bytes

import random
for j in range(len(s)-1):d[s[j]]=d.get(s[j],"")+s[j+1]
print v
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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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