Cel:

Biorąc pod uwagę tablicę ciągów, utwórz skrócone wersje każdego ciągu.

Specyfikacja:

W przypadku tego wyzwania skrót to pierwsze N ​​znaków ciągu. Dla napisu abc: a, ab, i abcsą ważne skróty, a bc, a acnie są.

Biorąc pod uwagę tablicę ciągów, chcemy znaleźć najkrótszy zestaw skrótów, taki, który biorąc pod uwagę dane wejściowe i dowolny skrót, można określić, do którego elementu danych wejściowych odnosi się skrót.

Przykład:

Wkład: ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]

Przeszukujemy struny, zaczynając od pierwszego.

• Poniedziałek jest tylko ciągiem znaków z M, więc najkrótszym możliwym skrótem jest M.

• Wtorek zaczyna się T, ale i czwartek. Oznacza to, że próbujemy łańcucha TU. Ponieważ żadne inne ciągi nie zaczynają się od tego, używamy TU.

• Środa jest W, czwartek jest Thi piątek jest F.

Więcej przykładów:

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.

Uwagi:

• Wprowadzasz i wyprowadzasz w dowolny rozsądny sposób.

• Możesz założyć, że wejście zawsze będzie prawidłową tablicą ciągów.

• Możesz założyć, że zawsze będzie rozwiązanie, w przeciwieństwie do ostatniego przypadku testowego.

• Ciągi będą się składać wyłącznie z drukowalnego ASCII (lub drukowalnych znaków w twoim kodowaniu)

• To jest kod golfowy, więc wygrywa najmniej bajtów!

Siatkówka , 29 bajtów

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

Dane wejściowe i wyjściowe są listami ciągów oddzielonymi od linii.

Wypróbuj online! (Zestaw testowy z separacją przecinków dla wygody).

Wyjaśnienie

To po prostu dopasowuje wszystkie prefiksy za pomocą jednego wyrażenia regularnego i drukuje je ( !). mi ssą zwykłymi modyfikatorami wyrażeń regularnych służącymi do tworzenia ^początkowych linii .dopasowania i dopasowywania kanałów.

^(.+?)      # 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.

Python 2 , 87 86 bajtów

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]

Wypróbuj online!

JavaScript (ES6), 81 78 74 70 bajtów

Pobiera dane wejściowe jako tablicę ciągów.

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

Sformatowane i skomentowane

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

Przypadki testowe

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

Galaretka , 14 bajtów

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

Wypróbuj online!

Jak to działa

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

Haskell , 48 bajtów

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

Wypróbuj online!

• fjest główną funkcją, biorąc listę Strings i zwracając a String. Jego definicja to skrót monadyczny f a=map (a#) a.
• a#xpatrzy na ciąg xi listę ai próbuje znaleźć najkrótszy prefiks, xktóry jest unikalny w a. Jeśli ama jeden element, po prostu użyj pustego ciągu. Jeśli anie jest to jeszcze jeden element, odetnij pierwszy znak x, odfiltruj i posiekaj elementy azaczynające się od tego samego znaku, a następnie powtórz.

Mathematica, 64 bajty

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

Galaretka , 14 12 bajtów

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

Wypróbuj online!

Jak to działa

ḣ€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.

C ++ 11 (MinGW), 198 bajtów

#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)<<" ";}}

Zadzwoń z:

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

Dodanie voididentyfikatora przed funkcją powinno sprawić, że będzie się kompilować również w innych kompilatorach, tym samym dodając 5 bajtów do długości.

JavaScript ES6, 70 znaków

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

PHP, 131 120 119 118 bajtów

Dzięki @ Jörg za 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)););

pobiera dane wejściowe z argumentów wiersza poleceń; wypisuje wyniki po jednej linii.
Uruchom -nrlub wypróbuj online .

• może się nie powieść, jeśli dane wejściowe zawierają cokolwiek zaczynające się od -.
  +15 bajtów do poprawki: zastąpić drugą $argvz array_slice($argv,1).
• wyświetla ostrzeżenia w PHP 7.1; wymienić a&z ""<(+1 Byte) do naprawienia.
• -12 bajtów jeśli wejściowy zawiera żadnych znaków specjalnych regex:
  Wstaw &($t.=$c)przed &&i wymienić ". preg_quote($t.=$c)."z $t.

awaria

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

wersja bez wyrażenia regularnego, 131 130 bajtów

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

Wymienić pierwszy i ostatni a&z ""<(+2 bajtów) do poprawki dla PHP 7.1.

awaria

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

całkowicie nieciekawa uwaga:
strstr($u,$t)==$ui 0===strpos($u,$t)mają tę samą długość i ten sam wynik.

PHP, 127 bajtów

nie działa z nieprawidłowymi tablicami

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

<?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);

Wersja online

151 bajtów obsługuje znaki specjalne

<?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 bajtów

<?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);

Clojure, 118 bajtów

#(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))))

Działa to na prefiksach o długości do, 1e2ale ta sama liczba bajtów może obsługiwać do 1e9. ipętle długości prefiksów, Sto sekwencja podciągów długości i. Ten ostatni forzastępuje te podciągi, nilktóre występują częściej niż jeden raz. Redukcja zachowuje pierwszą wartość zerową dla każdego łańcucha, szkoda ornie jest funkcją, więc musiałem ją zawinąć.

To faktycznie zwraca listy list takich jak ((\M) (\T \u) (\W) (\T \h) (\F)), ale myślę, że jest to dopuszczalne. Clojure jest dość gadatliwy ze sznurkami i subsrzucałby StringIndexOutOfBoundsExceptioninaczej take.

Pełne przykłady:

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

SQL (smak PostgreSQL 9.4), 219 bajtów

A teraz najdłuższa odpowiedź :) Nie sądzę, żeby to mogło pokonać Java. Spróbuję ogolić jeszcze kilka. Mam nadzieję pozbyć się jednego z zagnieżdżonych zapytań, ale nie podoba mi się moja szansa.
Zakłada się, że istnieje tabela zawierająca ciągi, nad którymi należy pracować. Ponieważ jest to SQL, kolejność zwrotu nie jest taka sama jak kolejność tabel, w tym przypadku jest mało prawdopodobna. Jeśli jest to problem, usunę go.

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
Objaśnienie

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

Wewnętrzne zapytanie wykorzystuje generate_seriesi LATERALłączenie do tworzenia wierszy dla ciągu podzielonego na coraz większe długości, więc „jeden” staje się „o”, „włączony”, „jeden”. Utrzymywana jest również liczba znaków w zwrocie.

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

Następnie dodajemy liczbę rekordów, które mają ten sam wynik. Na przykład „f” z czterech i pięciu ma 2, ale „fo” i „fi” mają po jednym. OVEROświadczenie w SQL może być dość silny. COUNT(*)byłby to zwykły sposób, ale SUM(1)daje ten sam rezultat.

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

Następnie oceniamy wyniki dla każdego wejścia na podstawie najmniejszej liczby powtórzeń i znaków. ROW_NUMBERtu też by działał, ale jest dłuższy.

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

Na koniec wybieramy najniższy numer rangi dla każdego słowa.

Pure Bash , 146 bajtów

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;}

Wypróbuj online!

APL (Dyalog) , 27 bajtów

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

Wypróbuj online!

{ anonimowa funkcja, gdzie ⍵ reprezentuje argument ...

 ∘.( tabela funkcji, w której znajduje się funkcja

  ⊃ pierwszy element

  ⍷ lista boolowska „lewy argument zaczyna się tutaj od prawego argumentu?”

 ) gdzie są właściwe argumenty

 ⍵ argumenty

 ( a lewy argument to

  ↑ stół z rzędami składającymi się z

  ,/ przedrostki

  ¨ każdy z

  ⍵ argumenty

 +/ suma w poprzek (liczy, ile argumentów ma ten prefiks)

 ↓ podziel tabelę na listę wierszy

 ⍳⍨¨ w każdym z nich znajdź lokalizację pierwszego

 1 jeden (tj. pierwszy prefiks, który kieruje tylko jednym argumentem)

 ↑¨⍨ dla każdej lokalizacji pobiera tyle znaków z odpowiedniego elementu

 ⍵ argument

} koniec funkcji anonimowej

PowerShell, 151 139 bajtów

$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

Zainteresowany, jeśli jest na to lepszy sposób. Musiałem użyć znaku foreach(powyżej a |%), aby móc wykonać breakzagnieżdżoną pętlę bez oznaczania go.

Edycja: 2 golfy z AdmBorkBork

APL, 26 bajtów

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

Wyjaśnienie:

• ↓↑⍵: wstaw każdy łańcuch, ⍵aby dopasować długość najdłuższego łańcucha
• ∘.(... )⍨: dla każdej możliwej pary ciągów znajdź wspólny prefiks:
  • ≢: nierówność tablic
  • ∧: i
  • =: równość w kategoriach przedmiotowych
  • ∧\: i skanuj (zachowaj tylko wiodące mecze)
• +/¨: zsumuj każdy wektor w tabeli, podając długość wspólnych prefiksów
• ⌈/: znajdź maksymalną wartość w każdej kolumnie
• 1+: dodaj jeden, podając liczbę znaków potrzebną do zachowania unikalności każdego łańcucha
• ⍵↑¨⍨: weź tyle znaków z każdego ciągu

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│
└─┴─┴─┴─┴─┴─┘

Q, 93 bajty

{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]}

Rozwiązany rekurencyjnie, pobiera ciąg znaków jako dane wejściowe, otrzymuje pierwsze n elementów każdego ciągu przy każdej rekurencji. Jeśli którykolwiek z tych elementów nie jest unikalny, zastępuje je pierwszymi elementami n + 1.