3
\$\begingroup\$

Pre-Note
Because of popular demand, and to avoid disqualifying certain languages, the dictionary can now be provided as input parameter.

Intro

Given a dictionary of words, you should write an autocomplete program or function.

Autocompletion

"Autocomplete, or word completion, is a feature in which an application predicts the rest of a word a user is typing." (Wikipedia)
Autocompletion is oftenly used to reduce the time needed for typing sentences. After typing a single character, the program will start guessing what the user is trying to say. In this challenge we will simulate the behaviour of autocompleting words.
If the program encounters a word it doesn't know, and no matching autocompletion words can be found, it will assume that the user is trying to type a word the program doesn't know. Good autocompletion software will own and edit a custom dictionary of words, but for the sakes of complexity that's not part of this challenge.

Input

Your program/function will take at least a single parameter of input. This parameter can either be a string or an array of characters, and will consist of lowercase characters [a-z].
Optionally, your program/function will take a second parameter containing a dictionary of words. More info on this in the paragraph Dictionary.

Output

You should print or return an array of autocompleted words. For each character in the input, an autocompletion should be added to the output array.
The autocompletions will be taken from the provided dictionary. If a word doesn't exist in the dictionary, it will alphabetically search for the next word matching your characters. If no matching word is found, the input will be returned (see test cases)

Dictionary

If you choose to read the dictionary from a file, the file structure should be your list of words, seperated by newlines.
If you choose to submit the dictionary of words as a parameter of a function call, it should be structured as an ordered list of strings; ['cat', 'cake', ...].
The input is always fully lowercase and sorted alphabetically.

Test case

a.txt content:

alpha
calf
cave
coax
code
codegimmick
codegolf
cool
gamma

Test cases:

"codegolf"                  // ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"]
"alpaca"                    // ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"]
["t", "h", "i", "s"]        // ["t", "th", "thi", "this"]
("catses", ["cake","cats"]) // ["cake", "cake", "cats", "cats", "catse", "catses"]

This is code-golf, shortest code in bytes wins

\$\endgroup\$
  • 1
    \$\begingroup\$ Why does e.g. alpaca give ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"]? \$\endgroup\$ – Peter Taylor Apr 20 '16 at 10:44
  • 1
    \$\begingroup\$ @PeterTaylor It's [ac("a"), ac("al"), ac("alp"), ..., ac("alpaca")]. \$\endgroup\$ – LegionMammal978 Apr 20 '16 at 12:02
  • \$\begingroup\$ @LegionMammal978 But alpa isn't a word, is it? Shouldn't alpa autocomplete to alpaca or something? \$\endgroup\$ – mbomb007 Apr 20 '16 at 15:34
  • 2
    \$\begingroup\$ @mbomb007 "Alpaca" isn't a word according to the given dictionary. "Alpa" is left as it is because it cannot autocomplete to anything in the dictionary. \$\endgroup\$ – LegionMammal978 Apr 20 '16 at 21:04
  • \$\begingroup\$ Can the dictionary be taken as the first parameter instead? \$\endgroup\$ – Leaky Nun Apr 22 '16 at 15:44
1
\$\begingroup\$

Pyth, 22 13 bytes

mhf!xTd+Qd._z
m         _z  map over prefixes of second input...
 hf    +Qd    find the first element in (dictionary+word) which...
   !xTd       ... starts with k

Sample run:

llama@llama:~$ pyth -c 'mhf!xTd+Qd._z' 
['alpha', 'calf', 'cave', 'coax', 'code', 'codegimmick', 'codegolf', 'cool', 'gamma']
codegolf
['calf', 'coax', 'code', 'code', 'codegimmick', 'codegolf', 'codegolf', 'codegolf']

Thanks to @FryAmTheEggman for 4 bytes!

\$\endgroup\$
  • \$\begingroup\$ I was about to post... Anyway your version is shorter. \$\endgroup\$ – FliiFe Apr 20 '16 at 12:33
  • \$\begingroup\$ @Doorknob I updated the challenge to allow a dictionary to also be given as input parameter. Feel free to update your answer if this will improve the byte count \$\endgroup\$ – Bassdrop Cumberwubwubwub Apr 21 '16 at 9:21
1
\$\begingroup\$

JavaScript (ES6), 56

Input: array of characters, array of words
Output: array

(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

Test

f=(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

dict=['alpha','calf','cave','coax','code','codegimmick','codegolf','cool','gamma']

console.log=x=>O.textContent+=x+'\n'

;[['c','o','d','e','g','o','l','f'],['a','l','p','a','c','a'],['t','h','i','s']]
.forEach(t=>console.log(t+' -> '+f(t,dict)))
<pre id=O></pre>

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6 / Node.js), 94 bytes

s=>s.map(c=>(d.match(`\\b${p+=c}.*`)||p)+"",p="",d=require("fs").readFileSync("a.txt","utf8"))

Anonymous function that takes an array of characters.

Or 52 bytes in JavaScript (ES6) with passing the dictionary as a string:

d=>s=>s.map(c=>(d.match(`\\b${p+=c}.*`)||p)+"",p="")
\$\endgroup\$
  • \$\begingroup\$ I updated the challenge to allow a dictionary to also be given as input parameter. Feel free to update your answer if this will improve the byte count \$\endgroup\$ – Bassdrop Cumberwubwubwub Apr 21 '16 at 9:21
0
\$\begingroup\$

Python 3, 94 bytes

s=""
for c in input():s+=c;print(next((o for o in open("a.txt")if o.startswith(s)),s).strip())
\$\endgroup\$
  • \$\begingroup\$ I updated the challenge to allow a dictionary to also be given as input parameter. Feel free to update your answer if this will improve the byte count \$\endgroup\$ – Bassdrop Cumberwubwubwub Apr 21 '16 at 9:21
0
\$\begingroup\$

Mathematica, 108 89 bytes

Select[Append[#2,c=b~StringTake~a],StringStartsQ@c][[1]]~Table~{a,StringLength[b=""<>#]}&

No, it isn't very pretty.

\$\endgroup\$
  • \$\begingroup\$ I updated the challenge to allow a dictionary to also be given as input parameter. Feel free to update your answer if this will improve the byte count \$\endgroup\$ – Bassdrop Cumberwubwubwub Apr 21 '16 at 9:21
0
\$\begingroup\$

Javascript ES6, 80 77 chars

(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])

Test:

d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])
;[
f("cat", ["cat"])[0] === "cat",
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]

Can reduce 4 chars (73 in total) if return array of single-element arrays:

(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)

Test:

d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)
;[
// f("cat", ["cat"])[0] === "cat", // will be failed
f("cat", ["cat"])[0][0] === "cat", // ok
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]
[false, true, true, true, true]
\$\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.