Wkład
Ciąg alfanumeryczny s
.
Wydajność
Najkrótszy ciąg występujący dokładnie raz jako (ciągły) podciąg w s
. Nakładające się wystąpienia są liczone jako odrębne. Jeśli jest kilku kandydatów o tej samej długości, musisz wydrukować wszystkie z nich w kolejności występowania. W tym wyzwaniu pusty ciąg występuje n + 1
razy w ciągu długości n
.
Przykład
Rozważ ciąg
"asdfasdfd"
Pusty ciąg występuje w nim 10 razy, więc nie jest kandydatem na wyjątkowe wystąpienie. Każda z liter "a"
, "s"
, "d"
, i "f"
pojawia się co najmniej dwa razy, więc nie są oni kandydatami albo. Podciągów "fa"
i "fd"
występuje tylko raz, w tej kolejności, a wszystkie inne podrzędnymi długości 2 występują dwukrotnie. Zatem prawidłowe wyjście to
["fa","fd"]
Zasady
Zarówno funkcje, jak i pełne programy są dozwolone, a standardowe luki nie. Dokładne formatowanie danych wyjściowych jest elastyczne w granicach rozsądku. W szczególności niedozwolone jest wytwarzanie danych wyjściowych dla pustego ciągu znaków, ale nie jest zgłaszanie błędu. Wygrywa najniższa liczba bajtów.
Przypadki testowe
"" -> [""]
"abcaa" -> ["b","c"]
"rererere" -> ["ererer"]
"asdfasdfd" -> ["fa","fd"]
"ffffhhhhfffffhhhhhfffhhh" -> ["hffff","fffff","hhhhh","hfffh"]
"asdfdfasddfdfaddsasadsasadsddsddfdsasdf" -> ["fas","fad","add","fds"]
Tabela liderów
Oto obiecana przeze mnie tabela liderów według języków.
Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
# Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
# Ruby, <s>104</s> <s>101</s> 96 bytes
<script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>site = 'meta.codegolf',postID = 5314,isAnswer = true,QUESTION_ID = 45056;jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)<\\/code><\/pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
Odpowiedzi:
Pyth,
2726 bajtówWypróbuj tutaj.
Zauważ, że z powodu błędu w kompilatorze online pusta wielkość liter działa poprawnie tylko w wersji wiersza poleceń, którą można znaleźć tutaj.
Możesz także wyleczyć błąd, podając nowy wiersz jako dane wejściowe kompilatora online.
Wyjaśnienie:
źródło
z
brak danych wejściowych kończy się niepowodzeniem online, więc jest to z pewnością błąd w tłumaczu.Python 3,
12412311196 bajtówSzuka ciągów znaków takich, że pierwsze wystąpienie od lewej jest takie samo jak pierwsze wystąpienie od prawej. Opcja „
+1
in”range
ma uwzględniać pustą wielkość ciągu.Teraz, jeśli tylko Python miał
.count()
których liczy się nakładających się mecze, to byłoby w porządku trochę krótszy.źródło
Mathematica,
959479 bajtówStringCases
dostaje wszystkie możliwe podciągiTally
iCases
odfiltrowuje te, które pojawiają się więcej niż jeden raz, iMinimalBy
znajduje te, które są najkrótsze.źródło
&
na końcu kodu nie ma dodatkowych ?GolfScript, 44 bajty
Pobiera dane wejściowe jako ciąg na standardowym wyjściu i wypisuje je w składni z podwójną tablicą: np
[["b"] ["c"]]
. Demo onlineSekcja
Jest to ustawione tak, że nie jest wymagany specjalny przypadek dla pustego ciągu (który umieściłem jako przypadek testowy w demo online, do którego link powyżej).
źródło
CJam,
52 4340 bajtówDane wejściowe to ciąg bez cudzysłowów
Objaśnienie :
Przykład:
Wydajność
Wypróbuj online tutaj
źródło
Scala, 120 bajtów
Zacząłem od 140, które przynajmniej już mieszczą się w tweecie.
źródło
(_)
działa jako tożsamość zamiastl=>l
?list.groupBy(_)
jest taki sam jakx => list.groupBy(x)
. Nie mam pojęcia, dlaczego tak to zaimplementowali.JavaScript (ES6), 109
110Edytuj wyszukiwanie zamiast indexOf, ponieważ ciąg wejściowy jest alfanumeryczny. Dzięki @IsmaelMiguel
Funkcja rekurencyjna, szukająca podciągów zaczynających się od długości 1 i rosnących.
Nie golfił i wyjaśnił
Testuj w konsoli FireFox / FireBug
Wydajność
źródło
.search
zamiast,.indexOf
a zaoszczędzisz 2 bajty.s.indexOf(a)+1
). Chociaż jest wtorek, nie będzie działać z tymi znakami, nie musisz się martwić! Cytując OP: „Input: An alphanumeric string s.
”Java, 168
176 233Oto całkiem prosty przykład zagnieżdżonej pętli.
Lub nieco bardziej czytelny:
źródło
+++
się, aby zobaczyć, czy to+ ++
lub++ +
pomoże ... A jeśli chcesz zaoszczędzić kilka bajtów więcej, nie może być sposobem, aby to zrobić poprzez inicjowanieq=1
, zastępującq++
zq=t
, i zastąpieniel++<t&q<1
czegoś podobnegot>l+=q
. Prawdopodobnie wymaga dostosowania jednego lub dwóch innych przesunięć, aby działało.+++
. Próbowałem go ulepszyć (szczególnieq
, co wydaje się nieco marnotrawstwem), ale nie znalazłem jeszcze niczego solidnego.+++
zawsze rozwiązuje++ +
.Haskell,
169162155153151138120115Aby go użyć:
Co daje:
Btw. Nienawidzę ostatniego wiersza mojego kodu (powtórzenieh y
). Czy ktoś chce się go pozbyć?źródło
g y=q(minimum.(map l)$y)$y
(czy nawiasy wokół sąmap l
naprawdę wymagane?), A następnief=g.concat.q 1.group.sort.concatMap inits.tails
?>>=
zamiastconcatMap
, tzn.f x=p$concat$q 1$group$sort$(tails x>>=inits)
Oszczędza 2 bajty. DlaczegoData.Ord
import?q
są niepotrzebne, ponieważ możesz pisaćfilter$(==)k.l
, podobnie jak ostatnia$
i spacje przedy
sp
. Możesz także usunąć średnik po imporcie (Data.Ord
wydaje się to rzeczywiście niepotrzebne).$
po którym następuje spacja. Ogoliłby się kilka bajtów, ale czy jest to zgodne ze specyfikacją języka?J,
61584442403837 bajtówOto wersja podzielona na poszczególne składniki rozwiązania:
x #/. y
oblicza dla każdego odrębnego elementux
częstość występowania wy
. Jeśli użyjemy tego jakoy #/. y
, otrzymamy dla każdego odrębnego elementuy
jego liczbę. Na przykłada #/. a
dlaa =. 1 2 2 3 4 4
plonów1 2 1 2
.1 = y
sprawdza, które elementyy
są równe1
. Na przykład1 = a #/. a
daje1 0 1 0
.u~
jest zwrotna z monadycznej czasownikau
. To jestu~ y
to samo coy u y
. Zatem#/.~ y
jest taki sam jak#/.~ y
. Przy stosowaniu na diadycznej czasowniku~
jest bierny wu
. Oznacza to, żex u~ y
jest taki sam jaky u x
. Są one używane w kilku innych miejscach, o których wyraźnie nie wspominam.~. y
Jest to zgrubienie ody
wektora, kopiami usunięte. Na przykład~. a
daje1 2 3 4
.x # y
( kopiuj ) wybieray
pozycje z indeksów, w którychx
zawiera1
.(1 = y #/. y) # (~. y)
tworzy wektor tych elementów,y
które pojawiają się tylko raz. W milczącej notacji czasownik ten zapisano jako~. #~ 1 = #/.~
; nazwijmy to wyrażenieunqs
do końca wyjaśnienia.x ]\ y
stwarza obrazx
przez1 + y - x
tablicę wszystkich wrostków wektoray
długościx
. Na przykład3 ]\ 'asdfasdfd
daje# y
jest tally ofy
, czyli liczba elementówy
.u\ y
odnosiu
się do każdego prefiksu zy
. Nawiasem mówiąc,#\ y
tworzy wektor liczb całkowitych od1
do#y
.< y
wkładay
do pudełka. Jest to konieczne, ponieważ tablice nie mogą być obdarte i obliczamy tablicę sufiksów o różnych długościach; tablica w pudełku liczy się jako skalar.W ten sposób
(i. # y) <@:unqs@(]\) y
generuje wektor#y
tablic w ramkach o długości k (dla wszystkich 0 ≤ k <#y
) przedrostków y, które występują dokładnie raz. Milcząca forma tego czasownika toi.@# <@unqs@(]\) ]
lubi.@# <@(~. #~ 1 = #/.~)@(]\) ]
jeśli nie używamyunqs
nazwy. Nazwijmy to wyrażenieallsbsq
resztą tego wyjaśnienia. Na przykładallsbsq 'asdfasdfd'
daje:(#@> y) # y
pobiera z wektora tablic pudełkowychy
te, które nie są puste.{. y
bierze pierwszy element wektoray
.> y
usuwa pudełko zy
.> {. (#@> y) # y
uzyskuje się rozpakowaną pierwszą niepustą tablicę z wektora tablic pudełkowychy
. To wyrażenie jest zapisane>@{.@(#~ #@>)
w sposób milczący.Na koniec
[: >@{.@(#~ #@>) allsbsq
składa się z poprzedniej frazy,allsbsq
aby stworzyć rozwiązanie naszego problemu. Oto pełna fraza ze spacjami:źródło
Haskell, 135 bajtów
źródło
PHP,
171152134125http://3v4l.org/RaWTN
źródło
$j=0
. Przed tobąsubstr($s,$j++,$i)
. Bez definiowania$j
możesz to przepisaćsubstr($s,0+$j++,$i)
i zapisać 2 bajty. Dlaczego? Cóż, po raz pierwszy$j
będzienull
. I skutecznie przejdziecienull
dosubstr
, co nie wydaje mi się, że to zadziała dobrze. Używanie0+$j++
spowoduje konwersjęnull
do0
. Jeśli zauważysz, że nie jest to konieczne, kontynuuj bez niego i po prostu usuń$j=0
część.$j
nie jest czyszczone i ponownie inicjowane dla każdej iteracjiwhile()
pętli. Tak więc, mimo że po raz pierwszy jest zerowy (a zatem zostanie przekształcony0
w$j++
wywołanie), w przyszłych iteracjach zewnętrznej pętli pozostawia wartość wcześniejszą. To nie tyle inicjowanie, co resetowanie. Dziękuję za sugestię :-)function f($s){$l=strlen($s);while(!$a&&++$i<$l)for($j=0;$j<$l;)($b=substr($s,$j++,$i))&(strpos($s,$b)==strrpos($s,$b)&&($a[]=$b));return$a;}
Zmiany: Usunąłem WSZYSTKIE||1
, użyłem bitowej&
(AND
) zamiast&&
w jednym miejscu, przeniosłem$j<$l&&[...]
część pozafor
(oszczędzając 2 bajty) i usunąłem niepotrzebne nawiasy.function f($s){$l=strlen($s);while(!$a&&++$i<$l)for($j=0;$j<$l;)strpos($s,$b=substr($s,$j++,$i))==strrpos($s,$b)&&($a[]=$b);return$a;}
zmiany wprowadzone w poprzednim kodzie: przeniesiono$b=substr($s,$j++,$i)
dostrpos($s,$b)
tworzeniastrpos($s,$b=substr($s,$j++,$i))
, usunięto więcej niepotrzebnych nawiasów i usunięto niepotrzebne&
.substr($s,$j++,$i)
zwraca,""
gdy$j
osiągnie długość łańcucha, afalse
następnie, aby przypisanie mogło również służyć jako warunkowe przerwanie pętli.$l
Pozostało tylko jedno użycie , więc można to również skonsolidować.Groovy (regex Java na implementacji Oracle), 124
Testowane na Groovy 2.4 + Oracle JRE 1.7. Wyrażenie regularne powinno działać dla Java 6 do Java 8, ponieważ błąd, który pozwala na działanie powyższego kodu, nie został naprawiony. Nie jestem pewien co do poprzedniej wersji, ponieważ w Javie 5 występuje błąd, który został naprawiony w Javie 6.
Wyrażenie regularne znajduje najkrótszy ciąg, który nie ma zduplikowanego podłańcucha w innym miejscu, w każdej pozycji ciągu wejściowego. Kod na zewnątrz zajmuje się filtrowaniem.
(?=...)
.(.*?)
wyszukuje od najkrótszego podłańcucha(?=(.*))
przechwytuje resztę ciągu, aby zaznaczyć bieżącą pozycję.(?<=^(?!.*\1(?!\2$)).*)
to emulacja z tyłu o zmiennej długości, która wykorzystuje błąd implementacji, który pozwala(?<=.*)
przejść kontrolę długości.(?!.*\1(?!\2$))
po prostu sprawdza, czy nie można znaleźć tego samego podciągu w innym miejscu.(?!\2$)
Odrzuca pierwotnego położenia, gdzie podciąg jest dopasowana.Limit zewnętrznej konstrukcji rozglądającej się nie dotyczy zagnieżdżonej konstrukcji rozglądającej się. Dlatego zagnieżdżone negatywne spojrzenie w przyszłość
(?!.*\1(?!\2$))
sprawdza cały ciąg, a nie tylko do prawej granicy z tyłu.źródło
Rebol, 136 bajtów
Nie golfowany:
Przykład użycia:
NB. Przypuszczam, że sednem kodu jest sposób działania tej
find
części. Mam nadzieję, że pomoże to wyjaśnić ...źródło
Haskell, 119
źródło
q = length
gdzieś położyć i używaćq
,Brachylog , 10 bajtów
Wypróbuj online!
Chociaż w
ᵍ
naturalny sposób nie sortuje według wartości, którą grupuje, zamiast tego porządkuje grupy według pierwszego wystąpienia każdej wartości, pierwsze wystąpienia każdej długości są malejące. Nie jestem w 100% pewien, że filtrowanie unikatowości nie może tego zepsuć, ale nie wpadłem na przypadek testowy, który zawodzi.źródło
05AB1E , 10 bajtów
Nie wyświetla niczego dla pustego ciągu.
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
Wykorzystuje to fakt, że 05AB1E ma tylko
1
tak prawdziwą wartość, a wszystko inne jako falsey. Gwarantujemy, że najkrótsze unikalne podciąg wystąpi dokładnie raz dla wszystkich możliwych ciągów wejściowych. (W przypadku łańcucha wejściowego zawierającego tylko te same znaki (tj.aaaaa
) Łańcuchy wejściowe same jako podłańcuch występują tylko raz, więc wynik jest taki["aaaaa"]
. W przypadku łańcucha wejściowego z powtarzalnym wzorcem (tj."abcabc"
) Nadal istnieją unikatowe podciągi, które tylko występuje raz (["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]
), więc spowoduje to["ca"]
.)źródło
Python 2, 150
źródło
""
, ale nic nie drukujesz.Perl 5
-a
,11487 bajtówWypróbuj online!
Stara metoda: 114 bajtów
źródło