31
\$\begingroup\$

Tab completion is a useful feature that auto-completes partially written commands. You're going to be implementing it.

For example, if the available commands were ['apply','apple','apple pie','eat'], then a would complete to appl, as all of the commands that start with a also start with appl.

Input/Output

You need to input a string, A, and a set of strings, B.

You need to output the longest common prefix of all B that starts with A.

  • If none of the options starts with A, then return A
  • You can assume that B is nonempty, and that all strings are nonempty
  • You cannot assume that any of the options start with A, nor that the common prefix will be longer than A
  • You can be case sensitive or case insensitive.
  • You only need to handle printable ASCII
  • Built-ins that explicitly do this task are allowed

Test cases:

'a'       ['apply','apple','apple pie','eat'] => 'appl'
'a'       ['apple pie']                       => 'apple pie'
'apple'   ['eat','dine']                      => 'apple'
'program' ['programa','programb']             => 'program'
'*%a('    ['*%a()-T>','*%a()-T<','@Da^n&']    => '*%a()-T'
'a'       ['abs','absolute','answer']         => 'a'
'a'       ['a','abs']                         => 'a'
'one to'  ['one to one','one to many']        => 'one to '

Note the trailing space on the last test case

This is a , so make your answers as short as possible!

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – nimi Sep 22 '16 at 18:31
  • \$\begingroup\$ Could you add an example with non-alphabetic, printable ASCII characters for posterity? \$\endgroup\$ – Conor O'Brien Sep 22 '16 at 19:05
  • \$\begingroup\$ More examples with non-alphabetic characters couldn't hurt. I just deleted my answer because I realized that it broke with inputs containing \​ or '. \$\endgroup\$ – Dennis Sep 23 '16 at 5:08
  • \$\begingroup\$ Not sure how to represent ' in an example. If I use " for the strings, then the strings are different than other examples. \$\endgroup\$ – Nathan Merrill Sep 23 '16 at 5:10
  • \$\begingroup\$ That's exactly the problem my answer had. :P \$\endgroup\$ – Dennis Sep 23 '16 at 5:21

19 Answers 19

10
\$\begingroup\$

JavaScript (ES6), 75 bytes

(s,a)=>/^(.*).*(\n\1.*)*$/.exec(a.filter(e=>e.startsWith(s)).join`
`)[1]||s

Explanation: Filters on all matching prefixes, then joins with newlines and matches against a regex that finds the longest common prefix of all lines. If there are no prefixes then the regex returns an empty string in which case we simply return the original string.

\$\endgroup\$
  • \$\begingroup\$ You can replace e.startsWith(s) with e.match("^"+s) for a byte off Currying will save another \$\endgroup\$ – Shaun H Sep 22 '16 at 19:33
  • \$\begingroup\$ @ShaunH I can't use match with arbitrary printable ASCII. \$\endgroup\$ – Neil Sep 22 '16 at 19:36
  • \$\begingroup\$ Oh right regex and control characters. you can still curry (s,a)=> to s=>a=> \$\endgroup\$ – Shaun H Sep 22 '16 at 19:42
7
\$\begingroup\$

Jelly, 14 12 bytes

ḣJ$€ċÐff\ṪṪȯ

Try it online! or verify all test cases.

How it works

ḣJ$€ċÐff\ṪṪȯ  Main link. Left argument: B. Right argument: A

  $€          Convert the two links to the left into a monadic chain and apply it
              to each string s in B.
 J              Generate the indices of s, i.e., [1, ..., len(s)].
ḣ               Head; for each index i, take the first i characters of s.
              This generates the prefixes of all strings in B.
     Ðf       Filter; keep prefixes for which the link to the left returns 1.
   ċ            Count the number of times A appears in the prefixes of that string.
       f\     Do a cumulative (i.e., keeping all intermediate values) reduce by
              filter, keeping only common prefixes. f/ is a more obvious choice,
              but it errors on an empty array, i.e., when A isn't a prefix of any
              string in B.
         Ṫ    Tail; take the last prefix array (if any) or return 0.
          Ṫ   Tail; take the last common prefix (if any) or return 0.
           ȯ  Logical OR (flat); replace 0 with A, leave strings untouched.
\$\endgroup\$
6
\$\begingroup\$

Pyth, 14 13 bytes

Thanks to @isaacg for -1 byte

.xe@F/#z._MQz

A program that takes the list of strings, and then the string, on STDIN and prints the result.

Verify all test cases

How it works

.xe@F/#z._MQz  Program. Inputs: Q, z
        ._MQ   Map prefixes over Q
     /#z       Filter that by count(z)>0, removing the prefixes corresponding to elements
               in Q that do not start with z
   @F          Fold intersection over that. This yields all the common prefixes
  e            Yield the last element of that, giving the longest common prefix, since the
               prefixes are already sorted by length
.x             But if that throws an exception since no elements of Q start with z:
            z  Yield z instead
               Implicitly print
\$\endgroup\$
  • 1
    \$\begingroup\$ f}zT => /#z \$\endgroup\$ – isaacg Sep 23 '16 at 16:23
5
\$\begingroup\$

PowerShell v3+, 112 bytes

param($a,$b)if($c=@($b-like"$a*")){([char[]]$c[0]|%{($i+="$_")}|?{($c-like"$_*").count-eq$c.count})[-1]}else{$a}

Takes input as a string $a and an array of strings $b. Uses the -like operator to pull out those elements from $b that (case-insensitive) starts with $a, explicitly cast those as an array @(...) (since the result could be one match as a scalar, in which case indexing later fails), and store that array into $c.

That forms the if clause. If there's nothing in $c (i.e., nothing starts with $a, so the array is empty), then output $a with the else. Otherwise ...

We cast the first element of $c as a char-array and loop through each element, string-concatenating with the previous $i and placing the strings on the pipeline via encapsulating parens. Those are filtered through |?{...} (the Where-Object clause) to verify that the .count of $c is -equal to the .count of things in $c that are -like the substring (i.e., the substring matches everything in $c). Since we're building our substrings in order shortest to longest, we need the last [-1] of the resultant strings.

Test Cases

PS C:\Tools\Scripts\golfing> $tests=@('a',@('apply','apple','apple pie','eat')),@('a',@('apple pie')),@('apple',@('eat','dine')),@('program',@('programa','programb')),@('one to',@('one to one','one to many')),@('*%a(',@('*%a()-T>', '*%a()-T<', '@Da^n&'))

PS C:\Tools\Scripts\golfing> $tests|%{""+$_[0]+" ("+($_[1]-join',')+") -> "+(.\implement-tab-completion.ps1 $_[0] $_[1])}
a (apply,apple,apple pie,eat) -> appl
a (apple pie) -> apple pie
apple (eat,dine) -> apple
program (programa,programb) -> program
one to (one to one,one to many) -> one to 
*%a( (*%a()-T>,*%a()-T<,@Da^n&) -> *%a()-T
\$\endgroup\$
4
\$\begingroup\$

Python 2, 122 bytes

s=input();l=[x for x in input()if x[:len(s)]==s]or[s];i=len(l[0])
while len(l)>1:i-=1;l=set(x[:i]for x in l)
print l.pop()

Full program; takes string and list from stdin exactly as given in the examples, except the inputs must be on separate lines.

Verify all test cases

\$\endgroup\$
  • \$\begingroup\$ Why l.pop() instead of l[-1]? \$\endgroup\$ – Cyoce Sep 23 '16 at 20:54
  • \$\begingroup\$ @Cyoce Because l is usually a set at that point, which doesn't allow indexing (being unordered). (Fortunately, both sets and lists support pop().) \$\endgroup\$ – DLosc Sep 24 '16 at 2:56
3
\$\begingroup\$

Perl, 54 bytes

Includes +2 for -Xp (can be combined with -e) and +3 for -i (cannot be combined)

Give dictionary on STDIN and the word after the -i option, e.g.:

perl -ia -Xpe '/^\Q$^I\E.*?(?{$F[$a{$&}++]=$&})^/}{$_=pop@F||$^I'
apply
apple
apple pie
eat
^D

Just the code:

/^\Q$^I\E.*?(?{$F[$a{$&}++]=$&})^/}{$_=pop@F||$^I
\$\endgroup\$
3
\$\begingroup\$

Perl, 61 bytes

Includes +2 for -0p

Run with the first word followed by the dictionary words on STDIN:

tabcompletion.pl
a
apply
apple
apple pie
eat
^D

tabcompletion.pl:

#!/usr/bin/perl -0p
/^(.+)
((?!\1).*
)*(\1.*).*
((?!\1).*
|\3.*
)*$|
/;$_=$3||$`
\$\endgroup\$
2
\$\begingroup\$

Python 2, 112 bytes

lambda n,h:[a.pop()for a in[{s[:-i]for s in h if s.find(n)==0}for i in range(-len(`h`),0)]+[{n}]if len(a)==1][0]
\$\endgroup\$
2
\$\begingroup\$

Haskell, 67 bytes

(a:b)?(c:d)|a==c=a:(b?d)
_?_=""
s%l=foldr1(?)$max[s][x|x<-l,x?s==s]

The auxiliary function ? finds the longest common prefix of two strings by recursively taking the first character as long as it's the same for both strings and the strings are non-empty.

The main function % first keeps only the strings in the list that start with the given one s, checked by the longest common prefix with s being s. To handle there being no valid competitions, it adds s to an empty result via max. Then, it finds the longest common prefix of those by folding the binary function ?.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 75 bytes

import os
lambda s,x:os.path.commonprefix([t for t in x if s<=t<s+'ÿ'])or s

Thanks to @xnor for suggesting the built-in, originally used by @BetaDecay in this answer.

For scoring purposes, ÿ can be replaced with a DEL byte. Test it on Ideone.

\$\endgroup\$
1
\$\begingroup\$

D, 88 bytes

S f(S)(S p,S[]q){try p=q.filter!(a=>a.startsWith(p)).fold!commonPrefix;catch{}return p;}

Usage:

assert(f("a", ["apply","apple","apple pie","eat"]) ==  "appl");

The code simply removes all elements from q that don't start with p, then computes the largest common initial subsequence of the remaining elements.

The templated parameters save us two repetitions of string and one of auto. The exception misuse lets us avoid the temporary variable and conditional that would otherwise be necessary to handle the case where no elements of q start with p.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 107 102 bytes

s,x=input();r='';q=1
for c in zip(*[t for t in x if s<=t<s+'ÿ']):q/=len(set(c));r+=c[0]*q
print r or s

For scoring purposes, ÿ can be replaced with a DEL byte. Test it on Ideone.

Thanks to @xnor for saving 5 bytes!

\$\endgroup\$
  • \$\begingroup\$ With os.path.commonprefix as Beta Decay found, you can have it do the work for you. \$\endgroup\$ – xnor Sep 23 '16 at 6:43
  • \$\begingroup\$ Wow, that saves a lot of bytes. Are you sure you don't want to post that yourself? \$\endgroup\$ – Dennis Sep 23 '16 at 6:48
  • \$\begingroup\$ I wouldn't feel right posting it myself since it's solely Beta Decay's idea combined with your answer. \$\endgroup\$ – xnor Sep 23 '16 at 6:50
  • \$\begingroup\$ For your solution, it looks a bit shorter to iterate for c in ... directly and terminate with error after printing like if len(set(c))>1:print r or s;_. \$\endgroup\$ – xnor Sep 23 '16 at 6:57
  • \$\begingroup\$ I think that would fail if x is a singleton array. \$\endgroup\$ – Dennis Sep 23 '16 at 7:05
1
\$\begingroup\$

PHP, 167 160 157 152 bytes

<?for($r=preg_grep("$^".preg_quote($s=$_GET[s])."$",$a=$_GET[a]);$r[0]>$s&&preg_grep("$^".preg_quote($t=$s.$r[0][strlen($s)])."$",$a)==$r;)$s=$t;echo$s;

I could save 3 more bytes by assigning variables with preg_grep and preg_quote, but eh.

breakdown

for(
    // find items in $a that start with $s
    $r=preg_grep("$^".preg_quote($s=$_GET[s])."$",$a=$_GET[a]);
    // while the first match is longer than $s
    $r[0]>$s
    // and appending the next character of the first match
    &&preg_grep("$^".preg_quote($t=$s.$r[0][strlen($s)])."$",$a)
    // does not change the matches
    ==$r
;)
    // keep appending
    $s=$t;
return$s;
\$\endgroup\$
1
\$\begingroup\$

PHP, 156 Bytes

with much Help from Titus Thank You

<?foreach($_GET[t]as$v)if(strstr($v,$s=$_GET[s])==$v)$r[]=$z=$v;for(;$i++<strlen($z);){$s=substr($z,0,$i);foreach($r as$x)if($x[$i]!=$z[$i])break 2;}echo$s;

PHP, 199 Bytes

32 Bytes saves by Titus with array_unique

<?foreach($_GET[t]as$v)if(strstr($v,$s=$_GET[s])==$v)$r[]=$v;for(;$i++<strlen($r[0]);$a=[]){foreach($r as$x)$a[]=substr($x,0,$i);if(count($r)==count($a)&count(array_unique($a))<2)$s=$a[0];}echo$s;

I know that the Regex Solution by Titus was shorter till Titus help me to improve my way. Maybe the way I found is interesting for you

\$\endgroup\$
  • 1
    \$\begingroup\$ 1) Replace $z with $s to fix the apple, [eat,dine] case. 2) $l= is obsolete; You don´t use that variable. (-2) 3) $i++<$m is shorter than ++$i<=$m. (-1) 4) substr($x,0,$i); is shorter than str_split($x,$i)[0]. (-3) 5) You can put $r[]=$v inside the strlen. (-5) \$\endgroup\$ – Titus Sep 24 '16 at 7:40
  • 1
    \$\begingroup\$ 6) <2 is shorter than ==1. (-1) 7) You could use strstr in the first loop: strstr($v,$s)==$v. (-3) \$\endgroup\$ – Titus Sep 24 '16 at 7:40
  • 1
    \$\begingroup\$ Let me rephrase it: 5) You can combine $r[]=$v;$m=max($m,strlen($v)); to $m=max($m,strlen($r[]=$v)); and drop the curlys. This doesn´t touch the condition. \$\endgroup\$ – Titus Sep 24 '16 at 12:43
  • 1
    \$\begingroup\$ On second thought, you don´t need $m at all. All you need is something that is >= the minimum length of the replacements. The new 5) Replace {$r[]=$v;$m=max($m,strlen($v));} with $r[]=$v;} and <$m with <strlen($r[0]) (-13) \$\endgroup\$ – Titus Sep 24 '16 at 12:50
  • 1
    \$\begingroup\$ Great! And I just found another golf: 9) $r[]=$z=$v; in the first loop and {$s=substr($z,0,$i);foreach($r as$x)if($x[$i]!=$z[$i])break 2;} for the second (-3) \$\endgroup\$ – Titus Sep 24 '16 at 15:40
1
\$\begingroup\$

Retina, 60 bytes

^(.*)(\n(?!\1).*)*(\n(\1.*)).*(\n((?!\1)|\4).*)*$
$4
s`\n.*

The trailing new line is significant. Takes input as the string on a line and then each word on a separate line (but no trailing newline!). Works in a similar way to my JavaScript answer by matching the longest common prefix of all lines that begin with the string on the first line. If it doesn't find one then it simply deletes all the words.

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

Scala, 119 bytes

def f(s:String,a:Seq[Char]*)=a filter(_ startsWith s)reduceOption(_ zip _ takeWhile(t=>t._1==t._2)map(_._1))getOrElse s

Ungolfed:

def tabComplete(input: String, options: Seq[Char]*) = {
  options.
  filter((x: String) => x.startsWith(input)).
  reduceOption((x: Seq[Char], y: Seq[Char]) =>
    x.zip(y).
    takeWhile((t: (Char, Char)) => t._1 == t._2).
    map((t: (Char, Char)) => t._1)
  ).getOrElse(input)
}

Explanation:

def g(s:String,a:Seq[Char]*)= //define a method g with a string and a vararg array of strings as parameter
  a filter(_ startsWith s)    //filter the options to contains only elements starting with the input
  reduceOption(               //if the filtered array is nonempty, reduce it: 
    _ zip _                     //zip two elements together
    takeWhile(t=>t._1==t._2)    //take the tuples while they contain the same char
    map(_._1)                   //take the first element from each tuple
  )getOrElse s                //else return the input
\$\endgroup\$
0
\$\begingroup\$

PowerShell, 101 bytes

Based on Nail's awesome regexp.

if($args-join'
'-cmatch'^(.*)(\n(?!\1).*)*(\n(\1.*)).*(\n((?!\1)|\4).*)*$'){$Matches.4}else{$args[0]}

Try it online!

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

05AB1E, 14 bytes

ʒIÅ?}€ηøʒË}‚˜θ

Try it online or verify all test cases.

Explanation:

ʒ   }           # Filter the (implicit) input-list
 IÅ?            #  Does it start with the (second) input-string
                #   i.e. ["codex","bla","codegolf"] and "c" → ["codex","codegolf"]
     €η         # Then take the prefixes of every remaining string
                #  → [["c","co","cod","code","codex"],
                #     ["c","co","cod","code","codeg","codego","codegol","codegolf"]]
       ø        # Zip/transpose; swapping rows/columns
                #  → [["c","c"],["co","co"],["cod","cod"],["code","code"],["codex","codeg"]]
        ʒ }     # Filter:
         Ë      #  Only keep sublists which only contain the same substrings
                #   → [["c","c"],["co","co"],["cod","cod"],["code","code"]]
           ‚    # Pair it with the (second implicit) input
                #  → ["c",["c","c"],["co","co"],["cod","cod"],["code","code"]]
                # (workaround if nothing in the input-list starts with the input-string)
            ˜   # Flatten this list
                #  → ["c","c","c","co","co","cod","cod","code","code"]
             θ  # And only leave the last item (which is output implicitly as result)
                #  → "code"
\$\endgroup\$
0
\$\begingroup\$

Gaia, 12 bytes

e…¦&⊢…Ė⁇_+ₔ)

Try it online!

Takes input as B, then A.

e		| eval B as list of strings
 …¦		| take prefixes of each string
   &⊢		| reduce by set intersection
     …		| take list prefixes of each.
      Ė⁇	| Keep only those with A as an element
	_	| flatten
	 +ₔ	| add A to the beginning of the list
	   )	| take the last element
\$\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.