9
\$\begingroup\$

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:

    apple
    banana
    citrus
    domino
    durian
    orange
    tuna
    zabc
    
  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:

    Stackoverflow,15
    StackExchange,11
    Meta,13
    TFGITW,2
    VTC,10
    
  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.

SAMPLE RUN

(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:

abacus
abacii
abandon
abandoned
abandonment

User dictionary

EMPTY

INPUT

abanana,abanana
abanana,abanana
abanana,abanana
abandonmint,abandonment
cat,cad

OUTPUT

FULLWORD:abanana,abanana #after this, add "abanana,1" to custom dictionary
MATCH:abana,abanana 
   # 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"
MATCH:abandonm,abandonment
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.

\$\endgroup\$
6
  • 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\$ Mar 24 '16 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\$ Mar 25 '16 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
    Mar 25 '16 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\$ Mar 25 '16 at 2:36
  • 1
    \$\begingroup\$ Maybe an empty line between dictionary and input? \$\endgroup\$ Mar 25 '16 at 4:06
1
\$\begingroup\$

Python 3.9, 350 bytes

import sys
[s,p,x]=sys.stdin.read().split("\n\n")
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
[s,p,x]=sys.stdin.read().split("\n\n")
#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
  b=s|p
  #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
  b=sorted(b,key=b.get)
  #Increment number of occurrences of i in personal dictionary, or set to 1 if it doesn't exist yet
  p[i]=p.get(i,0)+1
  #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)
\$\endgroup\$

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.