26
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Related: 1, 2, 3 \$\endgroup\$ – Sp3000 Mar 18 '17 at 14:23
  • 5
    \$\begingroup\$ Possible duplicate of Golf Down the PPCG Usernames \$\endgroup\$ – Okx Mar 18 '17 at 14:37
  • 2
    \$\begingroup\$ I don't think it's a duplicate of any of those (although they're all fairly similar). Actually, I think this is probably the best challenge among the four; the others all have variants which make them needlessly complicated. \$\endgroup\$ – user62131 Mar 18 '17 at 14:39
  • 2
    \$\begingroup\$ Is case important? In particular, your weekday example uses a capital U for Tuesday, but a lowercase h for Thursday. \$\endgroup\$ – Brian J Mar 20 '17 at 14:34
  • 1
    \$\begingroup\$ @Mego Don't edit my post unless a moderator will mark it as not a duplicate \$\endgroup\$ – Julian Lachniet Mar 23 '17 at 10:37

18 Answers 18

10
\$\begingroup\$

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.
\$\endgroup\$
10
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ lambda a:[[b[:i]for i in range(len(b))if sum(s[:i]==b[:i]for s in a)<2][0]for b in a] for 85 bytes \$\endgroup\$ – Curtis Bechtel Sep 18 '18 at 5:36
  • \$\begingroup\$ replacing len(b) with 4**8 saves 2 more bytes, assuming that strings will be no longer than 65536 characters \$\endgroup\$ – Curtis Bechtel Sep 18 '18 at 5:52
8
\$\begingroup\$

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"])))

\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 64 bytes

#&@@@StringCases[#,Shortest@x__/;Tr@Boole@StringStartsQ[#,x]<2]&
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Just wondering, why do you have 2 answers here? I like them both but I'm just wondering why you have two Jelly answers here. :) \$\endgroup\$ – HyperNeutrino Mar 19 '17 at 0:48
  • \$\begingroup\$ If I have two similarly competitive approaches but sufficiently different approaches, I usually post them in separate answers. \$\endgroup\$ – Dennis Mar 19 '17 at 0:51
  • \$\begingroup\$ Good point. Yeah, I was just wondering. :) That's a good idea; I usually don't have more than one approach :P \$\endgroup\$ – HyperNeutrino Mar 19 '17 at 1:02
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It should be void f..., it does't work otherwise... + 5 bytes, unfortunately. Functions, as far as I know, need type specifiers in C++ \$\endgroup\$ – Mr. Xcoder Mar 18 '17 at 15:54
  • \$\begingroup\$ Besides for that, outstanding approach! Golfing in C/C++ can be painful \$\endgroup\$ – Mr. Xcoder Mar 18 '17 at 16:02
  • \$\begingroup\$ @Mr.Xcoder It does compile on the MinGW compiler I'm using, though. So it's either a compiler extension or undefined behaviour. \$\endgroup\$ – Steadybox Mar 18 '17 at 16:06
  • \$\begingroup\$ I think it's about the compiler extension, on GCC it doesn't work... \$\endgroup\$ – Mr. Xcoder Mar 18 '17 at 16:07
  • 1
    \$\begingroup\$ So long as there's an environment in which the code works, it's valid \$\endgroup\$ – undergroundmonorail Mar 19 '17 at 0:48
2
\$\begingroup\$

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")

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

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.

\$\endgroup\$
  • \$\begingroup\$ Use a real newline character (0x0A) instead of \n, it will save one byte ;). \$\endgroup\$ – Blackhole Mar 20 '17 at 3:20
  • \$\begingroup\$ @Blackhole Thanks; I forgot about that this time. \$\endgroup\$ – Titus Mar 20 '17 at 11:55
1
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ This will fail if the input contains regex special characters. I´d have 113 bytes instead of 131 if not. \$\endgroup\$ – Titus Mar 18 '17 at 16:24
  • \$\begingroup\$ @Titus In this case I could add a preg_quote Make only 10 Bytes more \$\endgroup\$ – Jörg Hülsermann Mar 18 '17 at 16:33
  • \$\begingroup\$ It will also fail if input contains 0. But you can save one byte with $i=+$s="". \$\endgroup\$ – Titus Mar 18 '17 at 18:29
  • \$\begingroup\$ and you can remove the count()-count() stuff: input is guaranteed to be valid (-21 bytes). I think I could fix and golf this down to 120 bytes. $_GET was a good idea! \$\endgroup\$ – Titus Mar 18 '17 at 18:56
  • \$\begingroup\$ @Titus I have not realized that only valid arrays are allowed. Yes it would fail if the string contain a zero but this had born an idea \$\endgroup\$ – Jörg Hülsermann Mar 18 '17 at 22:36
0
\$\begingroup\$

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"))
\$\endgroup\$
0
\$\begingroup\$

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.

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

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!

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

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

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I've not gone through the code directly, but surely you could use -notin instead of -not$x.contains($a) and !($w... instead of -not($w... to save some bytes, yes? \$\endgroup\$ – AdmBorkBork Mar 21 '17 at 13:01
0
\$\begingroup\$

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│
└─┴─┴─┴─┴─┴─┘
\$\endgroup\$
0
\$\begingroup\$

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.

\$\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.