In honor of recent news of Google developing a keyboard for iPhone...

Your input (for simplicity, all input is case sensitive):

  1. Location of standard dictionary file. File format is 1 valid word per line; in alphabetical order. Example file:

  2. Location of personal dictionary file (initially, may be empty or non-existant). Format is 1 word per line, comma separated by count of times that word was used. Example file:

  3. A stream of words on standard input (for simplicity, newline separated), in the following format on each line: "Typed_word,intended_word".

You need to emulate a predictive keyboard, as follows. For every line in the stream of words:

  1. Process the typed word character by character
  2. After 3rd character, generate the 5 most-used words that start with the currently-seen substring

    "5" is a hard-coded constant, but my example below uses "2" for simplicity. "most-used" are picked as first words when words are sorted in the order of counting; alphabetic order within same counts.

    The rules for most-used words are: the word from the standard dictionary is assumed to have the used count of 20 (that's a hard-coded constant, but my example below uses "2" for simplicity). The word from personal dictionary has a used count of whatever number the dictionary file has.

  3. If one of 5 words matches intended word, print the success: "MATCH:$substring,$intended_word" and stop

  4. If typed word is finished and matches intended_word, print it: "FULLWORD:$typed_word,$intended_word" and stop
  5. If typed word is finished, but none of teh matches or the word match intended_word, print ERROR message including both typed and intended word: "MISMATCH:$typed_word,$intended_word"
  6. Add the intended word to the personal dictionary if missing from it; or increment its usage count in personal dictionary if already present

Answers should be genuine working code - no gotchas/loopholes, no edge cases like super-small input.


(I'm going to change the constants to 2 guesses (instead of 5) and main dictionary words weigh as 2 user-usages instead of 20)

Standard Dictionary:


User dictionary





FULLWORD:abanana,abanana #after this, add "abanana,1" to custom dictionary
   # NOTE: your code should have matched "abandon,abandoned" till seeing "abana"
   # change custom dict count for abanana to 2
MATCH:aban,abanana #By now, aban matches "abanana,abandon"
MISMATCH:cat,cad # Add cad to custom dictionary

NOTE: someone asked to be able to live with no files. I'm fine with that, the simplest spec seems to be to pass all 3 inputs on STDIN, separated by empty line between the inputs.

  • 1
    \$\begingroup\$ Yep, that helps a lot, thanks. Re: IO - Instead of specifying where this stuff should live / be sent to you can rely on our community defaults to take care of stuff we consider fair. So you could say something like "a list of words containing only upper and lower case ascii letters" and "a dictionary of words containing only upper and lower case ascii letters and a numerical weight". \$\endgroup\$ Commented Mar 24, 2016 at 19:38
  • \$\begingroup\$ Just something to clarify: words in the standard dictionary will never be added to the custom dictionary? And the two initial dictionaries are guaranteed to be mutually exclusive? \$\endgroup\$ Commented Mar 25, 2016 at 1:54
  • \$\begingroup\$ @FryAmTheEggman - yes. And if it simplifies the code, sure let's make them mutually exclusive, since the natural start state is empty custom dictionary and program logic only adds missing words to custom. \$\endgroup\$
    – DVK
    Commented Mar 25, 2016 at 2:31
  • 1
    \$\begingroup\$ Can we take the standard dictionary from stdin or function argument? Would make solutions easier to test as there's no files involved. \$\endgroup\$ Commented Mar 25, 2016 at 2:36
  • 1
    \$\begingroup\$ Maybe an empty line between dictionary and input? \$\endgroup\$ Commented Mar 25, 2016 at 4:06

1 Answer 1


Python 3.9, 350 bytes

import sys
p,x=[[l.split(',')for l in d.split("\n")]for d in[p,x]]
s={k:20 for k in s.split("\n")}
p={k:int(v)for k,v in p}
for t,i in x:b=s|p;b={k:b[k]for k in b if k[:4]==t[:4]};b=sorted(b,key=b.get);p[i]=p.get(i,0)+1;print((f"MATCH:{t[:4]},"if i in b[:5]else f"FULLWORD:{t},"if t==i else f"MISMATCH:{t},")+i)

Try it online! (Uses {**a,**b} instead of a|b to merge dictionaries)

The I/O formats are restrictive, but this still makes for a simple and fun challenge.

import sys
#s is the standard dictionary, p is the personal dictionary, and x is the input
#They are separated by a blank line
#Turn both p and x into lists (separated by \n) of 2-element lists (separated by commas)
p,x=[[l.split(',')for l in d.split("\n")]for d in[p,x]]
#Split s on \n to get list of words, then map to 20, the default no. of occurrences
s={k:20 for k in s.split("\n")}
#Turn p into a dictionary, and make the values ints
p={k:int(v)for k,v in p}
#Iterate over each typed word t and intended word i in the input
for t,i in x:
  #Merge the personal and standard dictionaries and store in b
  #Filter the words who start with the first 4 characters of t (typed word)
  b={k:b[k]for k in b if k[:4]==t[:4]}
  #b now contains words from the dictionary, sorted by number of occurrences
  #Increment number of occurrences of i in personal dictionary, or set to 1 if it doesn't exist yet
  #Print the corresponding message
  print((f"MATCH:{t[:4]},"if i in b[:5]else f"FULLWORD:{t},"if t==i else f"MISMATCH:{t},")+i)

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.