# Implement tab completion

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'       ['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!

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

(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. • You can replace e.startsWith(s) with e.match("^"+s) for a byte off Currying will save another Sep 22, 2016 at 19:33 • @ShaunH I can't use match with arbitrary printable ASCII. – Neil Sep 22, 2016 at 19:36 • Oh right regex and control characters. you can still curry (s,a)=> to s=>a=> Sep 22, 2016 at 19:42 # Jelly, 14 12 bytes ḣJ$€ċÐff\ṪṪȯ


### 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.


# 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
@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:
Implicitly print

• f}zT => /#z Sep 23, 2016 at 16:23

## 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 ...

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  ## 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 • Why l.pop() instead of l[-1]? Sep 23, 2016 at 20:54 • @Cyoce Because l is usually a set at that point, which doesn't allow indexing (being unordered). (Fortunately, both sets and lists support pop().) Sep 24, 2016 at 2:56 # 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  # 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||$  # 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]  ## 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 ?.

# 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.

## 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.

# 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!

• With os.path.commonprefix as Beta Decay found, you can have it do the work for you.
– xnor
Sep 23, 2016 at 6:43
• Wow, that saves a lot of bytes. Are you sure you don't want to post that yourself? Sep 23, 2016 at 6:48
• I wouldn't feel right posting it myself since it's solely Beta Decay's idea combined with your answer.
– xnor
Sep 23, 2016 at 6:50
• 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;_.
– xnor
Sep 23, 2016 at 6:57
• I think that would fail if x is a singleton array. Sep 23, 2016 at 7:05

# PHP, 167160157 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;  # 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

• 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) Sep 24, 2016 at 7:40 • 6) <2 is shorter than ==1. (-1) 7) You could use strstr in the first loop: strstr($v,$s)==$v. (-3) Sep 24, 2016 at 7:40
$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. # 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  # 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!

# 05AB1E, 14 bytes

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


Explanation:

ʒ   }           # Filter the (implicit) input-list
#   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"


# 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