Abbreviate an array

Question

Goal:

Given an array of strings, create abbreviated​ versions of each string.

Specification:

For this challenge, an abbreviation is the first N characters of a string. For the string abc: a, ab, and abc are all valid abbreviations, while bc, and ac are not.

Given an array of strings, we want to find the shortest set of abbreviations, such that given the input and any abbreviation, you could determine which item of the input that the abbreviation was referring to.

Example:

Input: ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]

We work our way through the strings starting with the first one.

• Monday is only the item string with an M, so the shortest possible abbreviation is M.

• Tuesday starts withT, but so does Thursday. This means that we try the string TU. Since no other strings start with that, we use TU.

• Wednesday is W, Thursday is Th, and Friday is F.

More Examples:

Input: "one,two,three,four,five,six,seven"
Output: "o,tw,th,fo,fi,si,se"

Input: "red,orange,yellow,green,blue,purple"
Output: "r,o,y,g,b,p"

Input: "a,ab,abc"
Output: Not valid! No abbreviation for `a` that doesn't apply to the other items.

Notes:

• You make input and output in any reasonable way.

• You can assume that input will always be a valid array of strings.

• You can assume that there will always be a solution, unlike in the last test case.

• Strings will only consist of printable ASCII (or the printable characters in your encoding)

• This is code golf, so fewest bytes win!

Answer 1

Retina, 29 bytes

!ms`^(.+?)(?!.+^\1)(?<!^\1.+)

Input and output are linefeed-separated lists of strings.

Try it online! (Test suite with comma-separation for convenience.)

Explanation

This simply matches all the prefixes with a single regex and prints them (!). m and s are the usual regex modifiers to make ^ match line beginnings and . match linefeeds.

^(.+?)      # Match the shortest possible prefix of a line and capture
            # it in group 1.
(?!.+^\1)   # Make sure that this prefix does not show up in a line after
            # the current one.
(?<!^\1.+)  # Make sure that this prefix does not show up in a line before
            # the current one.

Answer 2

Python 2, 87 86 bytes

lambda a:[b[:min(i for i in range(len(b))if sum(s[:i]==b[:i]for s in a)<2)]for b in a]

Try it online!

Answer 3

JavaScript (ES6), 81 78 74 70 bytes

Takes input as an array of strings.

a=>a.map(s=>[...s].reduce((y,c)=>a.some(x=>x!=s&!x.indexOf(y))?y+c:y))

Formatted and commented

a =>                          // given an array of strings 'a'
  a.map(s =>                  // for each string 's' in 'a':
    [...s].reduce((y, c) =>   //   starting with 'y' = first character of 's',
                              //   for each subsequent character 'c' of 's':
      a.some(x =>             //     if we find a string 'x' in 'a' such that:
        x != s &              //       - 'x' is different from 's'
        !x.indexOf(y)         //       - and 'y' appears at the beginning of 'x'
      ) ?                     //     then:
        y + c                 //       append 'c' to 'y'
      :                       //     else:
        y                     //       keep 'y' unchanged
    )                         //   end of reduce(): returns the correct prefix
  )                           // end of map()

Test cases

let f =

a=>a.map(s=>[...s].reduce((y,c)=>a.some(x=>x!=s&!x.indexOf(y))?y+c:y))

console.log(JSON.stringify(f(["Monday","Tuesday","Wednesday","Thursday","Friday"])))
console.log(JSON.stringify(f(["one","two","three","four","five","six","seven"])))
console.log(JSON.stringify(f(["red","orange","yellow","green","blue","purple"])))

Answer 4

Jelly, 14 bytes

;\w@þ=1Si1⁸ḣð€

Try it online!

How it works

;\w@þ=1Si1⁸ḣð€  Monadic link. Argument: A (string array)

            ð   Collect all links to the left into a chain (arity unknown) and
                begin a dyadic chain.
             €  Map the previous chain over A. The current chain is dyadic and the
                mapped one inherits its arity. Thus, the right will be A for all
                invocations, while the left argument will iterate over A.
                For each string s in A, the following happens.
;\                Cumulative reduce by concatenation; yield all prefixes of s.
  w@þ             Window index swapped table; for each string t in A and each
                  prefix p of s, find the index of the substring t in p.
                  The first index is 1; 0 means not found.
     =1           Compare the indices with 1, returning 1 iff t begins with p.
       S          Sum the Booleans across columns, counting the number of strings
                  in A that begin with a given prefix.
        i1        Find the first index of 1, the shortest prefix that is unique
                  across all strings in A.
          ⁸       Head; truncate s to the computed length.

Answer 5

Haskell, 48 bytes

[_]#x=""
a#(c:y)=c:[z|d:z<-a,c==d]#y
f=map=<<(#)

Try it online!

• f is the main function, taking a list of Strings and returning a String. Its definition is a monadic shortcut for f a=map (a#) a.
• a#x looks at the string x and the list a and tries to find the shortest prefix of x that is unique in a. If a has a single element, just use the empty string. If a isn't already a single element, chop off the first character of x, filter and chop the elements of a starting with the same character, then recurse.

Answer 6

Mathematica, 64 bytes

#&@@@StringCases[#,Shortest@x__/;Tr@Boole@StringStartsQ[#,x]<2]&

Answer 7

Jelly, 14 12 bytes

ḣ€JṙLḶ$ḟ/€Ḣ€

Try it online!

How it works

ḣ€JṙLḶ$ḟ/€Ḣ€  Main link. Argument: A (string array)

  J           Yield the 1-based indices of A, i.e., [1, ..., len(A)].
ḣ€            Head each; for each string s in A, take the first 1, ..., and len(A) 
              characters. This builds the 2D array of prefixes of all strings in A.
    LḶ$       Length-unlength; yield [0, ..., len(A)-1].
   ṙ          Rotate the 2D array 0, ..., and len(A)-1 units to the left.
       ḟ/€    Reduce filterfalse each; for each rotation, remove all prefixes from
              the first set that also occur in later sets.
          Ḣ€  Head each; for each rotation, keep only the shortest unique prefix.

Answer 8

Javascript ES6, 70 chars

s=>(s+'#'+s).replace(/(\w+?)(\w*)(?=(\W(?!\1(?!\2))\w+)+$)|#.+/g,"$1")

f=s=>(s+'#'+s).replace(/(\w+?)(\w*)(?=(\W(?!\1(?!\2))\w+)+$)|#.+/g,"$1")

console.log(f("one,two,three,four,five,six,seven")==="o,tw,th,fo,fi,si,se")
console.log(f("red,orange,yellow,green,blue,purple")==="r,o,y,g,b,p")
console.log(f("one,two,three,four,five,six,seven".split`,`)==="o,tw,th,fo,fi,si,se")
console.log(f("red,orange,yellow,green,blue,purple".split`,`)==="r,o,y,g,b,p")

Answer 9

C++11 (MinGW), 198 bytes

#import<list>
#import<iostream>
f(std::list<std::string>l){int i,m;for(auto s:l){for(i=0,m=1;++i<s.length();)for(auto t:l)if(t!=s&&t.substr(0,i)==s.substr(0,i))m=i+1;std::cout<<s.substr(0,m)<<" ";}}

Call with:

int main()
{
    f({"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"});
}

Adding void identifier before the function should make it compile on other compilers too, thereby adding 5 bytes to the length.

Answer 10

PHP, 131 120 119 118 bytes

Thanks @Jörg for preg_grep.

for(;a&$s=$argv[++$k];$i=+$t=!print"$t
")for(;a&$s[$i]&&1<count(preg_grep("(^".preg_quote($t.=$s[$i++]).")",$argv)););

takes input from command line arguments; prints results one line each.
Run with -nr or try it online.

• may fail if input contains anything starting with -.
  +15 bytes to fix: replace the second $argv with array_slice($argv,1).
• yields warnings in PHP 7.1; replace a& with ""< (+1 byte) to fix.
• -12 bytes if input contains no regex special chars:
  Insert &($t.=$c) before && and replace ". preg_quote($t.=$c)." with $t.

breakdown

for(;a&$s=$argv[++$k];      # loop $s through arguments
    $i=+$t=!                # 3. reset $i and $t to empty
    print"$t\n")            # 2. print abbreviation
    for(;a&($c=$s[$i++])    # 1. loop $c through characters
        &&1<count(              # 3. if count==1, break loop
            preg_grep("(^"      # 2. find matching arguments
                . preg_quote(
                $t.=$c          # 1. append $c to abbreviation
            ).")",$argv)
        );
    );

non-regex version, 131 130 bytes

for($a=$argv;a&$s=$a[++$k];$i=+$t=!print"$t
")for($n=1;$n&&a&$c=$s[$i++];)for($n=$m=1,$t.=$c;a&$u=$a[$m++];)$n-=0===strpos($u,$t);

Replace the first and the last a& with ""< (+2 bytes) to fix for PHP 7.1.

breakdown

for($a=$argv;a&$s=$a[++$k];     # loop through arguments
    $i=+$t=!print"$t\n")            # 2. print abbreviation, reset $i and $t to empty
    for($n=1;$n&&a&$c=$s[$i++];)    # 1. loop through characters while $n<>0
        for($n=$m=1,                    # reset $n and $m to 1
            $t.=$c;                     # append current character to prefix
            a&$u=$a[$m++];              # loop through arguments:
        )$n-=0===strpos($u,$t);         # -$n = number of matching strings -1

completely uninteresting note:
strstr($u,$t)==$u and 0===strpos($u,$t) have the same length and the same result.

Answer 11

PHP, 127 Bytes

works not with invalid arrays

<?foreach($a=$_GET as$k=>$v)for($i=0,$c=2,$s="";$c>1;$r[$k]=$s)$c=count(preg_grep("_^".($s.=$v[$i++])._,$a));echo join(",",$r);

PHP, 132 Bytes

<?foreach($a=$_GET as$v)for($i=0,$s="";a&$v[$i];)if(count(preg_grep("_^".($s.=$v[$i++])._,$a))==1){$r[]=$s;break;}echo join(",",$r);

Online Version

151 Bytes supports special characters

<?foreach($a=$_GET as$v)for($i=0,$s="";a&$v[$i];)if(count(preg_grep("_^".preg_quote($s=substr($v,0,++$i),_)._,$a))==1){$r[]=$s;break;}echo join(",",$r);

PHP, 140 Bytes

<?foreach($a=$_GET as$k=>$v)for($i=0;a&$v[$i];)if(count(preg_grep("#^".($s=substr($v,0,++$i))."#",$a))==1){$r[]=$s;break;}echo join(",",$r);

Answer 12

Clojure, 118 bytes

#(reduce(partial map(fn[a b](or a b)))(for[i(range 1e2)S[(for[c %](take i c))]](for[s S](if(=((frequencies S)s)1)s))))

This works on prefixes up-to length of 1e2 but the same byte count can support up-to 1e9. i loops lengths of prefixes, S is the sequence of substrings of length i. The last for replaces those substrings with nil which occur more frequently than once. The reduction keeps the first non-nil value for each string, too bad or isn't a function so I had to wrap it.

This actually returns lists of lists of characters like ((\M) (\T \u) (\W) (\T \h) (\F)), but I guess it is acceptable. Clojure is quite verbose with strings, and subs would throw StringIndexOutOfBoundsException unlike take.

Full examples:

(def f #(reduce(partial map(fn[a b](or a b)))(for[i(range 1e2)S[(for[c %](take i c))]](for[s S](if(=((frequencies S)s)1)s)))))

(f ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"])
(f (re-seq #"[^,]+" "one,two,three,four,five,six,seven"))
(f (re-seq #"[^,]+" "red,orange,yellow,green,blue,purple"))

Answer 13

SQL (PostgreSQL 9.4 flavour), 219 bytes

Now for the longest answer:) I don't think this could even beat Java. I will try to shave a few more off this. Hoping to get rid of one of the nested queries, but don't like my chances.
This assumes that there is a table that contains the strings to be worked on. As this is SQL the order of the return is not guaranteed to be the same as the table order and in this case unlikely. If this is a problem I will delete.

SELECT R FROM(SELECT*,RANK()OVER(PARTITION BY A ORDER BY C,N)Z FROM(SELECT*,SUM(1)OVER(PARTITION BY R)C FROM(SELECT*FROM A JOIN LATERAL(select left(A,n)R,N FROM generate_series(1,length(A))S(n))L ON 1=1)X)Y)Z WHERE Z=1

SQL Fiddle
Explanation

  SELECT *
  FROM A 
    JOIN LATERAL(SELECT LEFT(A,n)R,N 
    FROM generate_series(1,length(A))S(n))L ON 1=1

The innermost query uses generate_series and a LATERAL join to create rows for the string split into increasing lengths, so 'one' becomes 'o','on','one'. The number of characters in the return is also kept.

SELECT 
  *,
  SUM(1)OVER(PARTITION BY R)C
FROM ( ... )X

Then we add the number of records which have the same result. For example 'f' from four and five has 2, but 'fo' and 'fi' each have one. The OVER statement in SQL can be quite powerful. COUNT(*) would be the usual way, but SUM(1) gives the same result.

SELECT 
  *,
  RANK()OVER(PARTITION BY A ORDER BY C,N)Z
FROM ( ... )Y

Then we rank the results for each input based on the least repetitions and characters. ROW_NUMBER would work here as well, but is longer.

SELECT R FROM ( ... )Z WHERE Z=1;

Finally we select the lowest rank number for each word.

Answer 14

Pure Bash, 146 bytes

for i in $@;{ K=1;U=${i::1};((M++));L=;while [[ `for v in $@;{ ((L++));(($L!=$M))&&echo ${v::K}||:;}` =~ $U ]];do U=${i::K};((K++));done;echo $U;}

Try it online!

Answer 15

APL (Dyalog), 27 bytes

{⍵↑¨⍨1⍳⍨¨↓+/(↑,\¨⍵)∘.(⊃⍷)⍵}

Try it online!

{ an anonymous function, where ⍵ represents the argument...

 ∘.( a function table where the function is

  ⊃ the first element of

  ⍷ the Boolean list "left argument begins here in the right argument?"

 ) where the right arguments are

 ⍵ the arguemts

 ( and the left argument is

  ↑ a table with rows consisting of

  ,/ prefixes of

  ¨ each of

  ⍵ the arguments

 +/ sum across (counts how many of the arguments befin with this prefix)

 ↓ split table into list of rows

 ⍳⍨¨ in each one, find the location of the first

 1 one (i.e. the first prefix that only heads one argument)

 ↑¨⍨ for each location, takes that many characters from the corresponding element of

 ⍵ the argument

} end of anonymous function

Answer 16

PowerShell, 151 139 bytes

$x,$w=@(),$args[0];$w|%{$k=$_;$a='';foreach($l in [char[]]$k){$a+=$l;if($a-notin$x-and!($w|?{$_-ne$k-and$_-like"$a*"})){$x+=$a;break;}}};$x

Interested if there's a better way to do this. Had to use a foreach (over a |%) to be able to perform a break in the nested loop without labeling it.

Edit: 2 golfs from AdmBorkBork

Answer 17

APL, 26 bytes

{⍵↑¨⍨1+⌈/+/¨∘.(∧\=∧≢)⍨↓↑⍵}

Explanation:

• ↓↑⍵: pad each string in ⍵ to match the length of the longest string
• ∘.(...)⍨: for each possible pair of strings, find the shared prefix:
  • ≢: array inequality
  • ∧: and
  • =: itemwise equality
  • ∧\: and-scan (keep only the leading matches)
• +/¨: sum each vector in the table, giving the length of the shared prefixes
• ⌈/: find the maximum value in each column
• 1+: add one, giving the amounts of characters needed to keep each string unique
• ⍵↑¨⍨: take that many characters from each string

Test:

      {⍵↑¨⍨1+⌈/+/¨∘.(∧\=∧≢)⍨↓↑⍵}'Monday' 'Tuesday' 'Wednesday' 'Thursday' 'Friday'
┌─┬──┬─┬──┬─┐
│M│Tu│W│Th│F│
└─┴──┴─┴──┴─┘
      {⍵↑¨⍨1+⌈/+/¨∘.(∧\=∧≢)⍨↓↑⍵}'one' 'two' 'three' 'four' 'five' 'six' 'seven'
┌─┬──┬──┬──┬──┬──┬──┐
│o│tw│th│fo│fi│si│se│
└─┴──┴──┴──┴──┴──┴──┘
      {⍵↑¨⍨1+⌈/+/¨∘.(∧\=∧≢)⍨↓↑⍵}'red' 'orange' 'yellow' 'green' 'blue' 'purple'
┌─┬─┬─┬─┬─┬─┐
│r│o│y│g│b│p│
└─┴─┴─┴─┴─┴─┘

Answer 18

Q, 93 bytes

{n:1;{$[any e:(,/)1<{(+/)i like x}each i:z#'x;[z+:1;y:?[e;z#'x;i];.z.s[x;y;z]];y]}[x;n#'x;n]}

Solved recursively, takes string as input, gets first n elements of each string with every recursion. If any of those elements aren't unique it replaces them with first n+1 elements.