Implement tab completion

Question

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 code-golf, so make your answers as short as possible!

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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||$`

Answer 8

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]

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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!

Answer 13

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;

Answer 14

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

Answer 15

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.

Answer 16

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

Answer 17

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!

Answer 18

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"

Answer 19

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