String.prototype.isRepeated

41

AKTUALIZACJA : Zgłoszenie Pyth isaacga jest zwycięzcą!


Wielu z was musiało usłyszeć, że w mieście jest fajniejsza wersja JavaScript (czytaj ES6), która ma metodę, String.prototype.repeatdzięki której można to zrobić

"Hello, World!".repeat(3)

i dostać

"Hello, World!Hello, World!Hello, World!"

jako wynik.

Twoim zadaniem jest napisanie funkcji lub programu w wybranym języku, który wykrywa, czy łańcuch nie został poddany takiej transformacji.

tzn. Łańcuch wejściowy może być reprezentowany jako dokładne npowtórzenie razy mniejszego łańcucha. Wyjście (jako instrukcja return funkcji lub STDOUT) powinno być zgodne z prawdą, jeśli łańcuch może być, lub fałszem, jeśli łańcucha nie można przedstawić jako powtórzenia mniejszego łańcucha.

Niektóre przykładowe dane wejściowe:

"asdfasdfasdf"  // true
"asdfasdfa"     // false
"ĴĴĴĴĴĴĴĴĴ"     // true
"ĴĴĴ123ĴĴĴ123"  // true
"abcdefgh"      // false

Zauważ, że ostatnie wejście jest fałszywe, dlatego npowinno być większe niż1

Kompletne zasady

  • Napisz funkcję / program w dowolnym języku, aby wprowadzić (za pomocą argumentu funkcji / argumentu wiersza poleceń / STDIN) ciąg znaków
  • Zwróć / Drukuj prawdziwą wartość, jeśli dany ciąg powstaje przez dokładne powtórzenie mniejszego ciągu, co najmniej dwa razy.
  • Maksymalny rozmiar ciągu wejściowego to idealnie Nieskończoność
  • Ciąg może mieć wszystkie możliwe znaki ASCII
  • To jest więc wygrywa najmniejszy kod w postaci.
Optymalizator
źródło
Co powinien „” - pusty ciąg - zwrócić? (Zawiera nieskończoną liczbę kopii pustego ciągu.)
billpg
@billpg wartość falsy
Optimizer
Czy łączysz głosowanie? Myślę, że powszechną praktyką jest wcześniejsze poddanie się (no cóż, pierwsza, która przeszła w golfa do wyniku). Ale nie jestem pewien, czy zapisano to jako domyślny remis gdziekolwiek, więc ostatecznie to zależy od ciebie.
Martin Ender
Czas między ich opublikowaniem wynosi tylko 30 minut. Nie uznam tego za wystarczające do wygrania :). Ponieważ ten czas się teraz nie zmieni, ale głosy mogą, poszedłem z głosami
Optimizer
To pytanie powinno zostać przemianowane na Xnor :) On jest mężczyzną!
Silviu Burcea,

Odpowiedzi:

16

Pyth , 9

/:+zz1_1z

Lub

}z:+zz1_1

Są to zarówno bliskie tłumaczenia odpowiedzi python @ xnor, z tym wyjątkiem, że pobierają dane wejściowe ze STDIN i je drukują. Pierwszy jest równoważny z:

z = input()
print((z+z)[1:-1].count(z))

0 dla False, 1 dla True.

Druga linia odpowiada:

z = input()
print(z in (z+z)[1:-1])

Fałsz za fałsz, prawda za prawda.

Oficjalny kompilator Pytha miał błąd związany z drugim, który właśnie załatałem, więc pierwszy to moje oficjalne zgłoszenie.

isaacg
źródło
Właśnie szukałem sposobu, aby poinformować cię o tym błędzie (wartość logiczna nie jest drukowana). Nie myślałem o pierwszym, a używanie xbyło zbyt długie ...
Dennis
Tak, błąd został już naprawiony. Ponadto, jeśli chcesz zgłosić błędy, dobrym sposobem może być otwarcie problemu na stronie github, tutaj: github.com/isaacg1/pyth/issues
isaacg
Och, oto jest. Nie znam się na GitHubie i nigdy nie zauważyłem panelu nawigacyjnego po prawej ...
Dennis
81

Python (24)

lambda s:s in(s+s)[1:-1]

Sprawdza, czy łańcuch jest podciągiem dwukrotnie połączonym, eliminując pierwszy i ostatni znak, aby uniknąć trywialnych dopasowań. Jeśli tak jest, musi to być niebanalna cykliczna permutacja samego siebie, a zatem suma powtarzających się segmentów.

xnor
źródło
8
Trywialne tłumaczenie na Golfscript daje 10 znaków:..+);(;\?)
Justin
3
Nie do końca rozumiem, jak to działa. Czy możesz podać ręcznie wyjaśniony przykład obsługi tego ciągu?
Nzall,
8
@NateKerkhofs weź abcabc. s+szamienia to w abcabcabcabc. z [1:-1]kotletów z dwoma końcami z wytworzeniem bcabcabcabcab. a następnie s in ...próbuje znaleźć abcabcto podciąg. Tego podłańcucha nie można znaleźć w żadnej z pierwotnych połówek, ponieważ oba zostały skrócone, więc musi obejmować obie połówki. W szczególności musi mieć swój własny koniec przed rozpoczęciem, co oznacza, że ​​musi składać się z identycznych (powtarzanych) podciągów.
Martin Ender
6
Siekasz go po podwojeniu. abstaje ababsię ba, więc zwraca fałsz, a aastaje aaaasię aa, co zwraca prawdę.
histocrat
1
@SargeBorsch Działa tak samo: qweqweqwein weqweqweqweqweqwis True.
xnor
30

Regex (smak ECMAScript), 11 bajtów

Brzmi jak praca dla wyrażeń regularnych!

^([^]+)\1+$

Sprawdź to tutaj.

Wybrałem ECMAScript, ponieważ jest to jedyny smak (wiem), w którym [^]pasuje dowolny znak. We wszystkich innych albo potrzebuję flagi, aby zmienić zachowanie .lub użycie, [\s\S]która jest o trzy znaki dłuższa.

W zależności od tego, jak liczymy flagę, może to oczywiście być bajt krótszy. Np. Jeśli liczymy wzorzec + flagi (np. Ignorując ograniczniki), odpowiednikiem PCRE / Perla byłoby

/^(.+)\1+$/s

Co oznacza 10 bajtów, ignorując ograniczniki.

Sprawdź to tutaj.

Dopasowuje tylko ciągi, które składają się z co najmniej dwóch powtórzeń niektórych podciągów.

Oto pełna 26-bajtowa funkcja ES6, ale uważam, że przesyłanie wyrażeń regularnych jest ogólnie poprawne:

f=s->/^([^]+)\1+$/.test(s)
Martin Ender
źródło
^(.+)\1+$działa dla mnie, czyli 9 bajtów. To ci nie działa?
Optymalizator
@Optimizer Wypróbuj ciąg z podziałem linii.
Martin Ender
Próbowałem asd\nasd\nasd\n. Działa
Optymalizator
@Optimizer refiddle.com/refiddles/5417fb2475622d4df7e70a00 wydaje się nie działać dla mnie (i nie powinno)
Martin Ender
Tak, to nie działa. Może ucieka przed ręcznym \ pisaniem\n
Optymalizator
12

CJam, 9

q__+)@+#)

Podobne do pomysłu Xnora.

q      " Read input. ";
__+    " Duplicate twice and concatenate them together. ";
)      " Remove the last character of the longer string. ";
@+     " Insert that character at the beginning of the shorter string. ";
#)     " Find the shorter string in the longer string, and increase by one. ";
jimmy23013
źródło
+1 zobowiązało się głosować przed moją własną odpowiedzią CJam
Digital Trauma
Dlaczego potrzeba finału )? Myślę, że uzasadnione jest, aby -1 oznaczało FAŁSZ, a> = 0 oznaczało PRAWDA
Cyfrowa trauma
@DigitalTrauma Myślę, że 0 jest fałszem w CJam ... dla operatorów takich jak gi ?.
jimmy23013
@DigitalTrauma: To, czy jest to ostatecznie potrzebne, zależy od OP, ale ściśle mówiąc, tylko zero jest uważane za fałszywe w CJam.
Dennis
@ user23013 @Dennis Ale co z #operatorem wyszukiwania? Z pewnością wynik tego jest również „prawdomówny” z perspektywy sukcesu kontra porażki?
Digital Trauma
7

APL, 11

2<+/x⍷,⍨x←⍞

Objaśnienie
pobiera ciąg znaków z
x←przypisań ekranowych do zmiennej x
,⍨łączącej ciąg, który sam
x⍷szuka xw ciągu wynikowym. Zwraca tablicę składającą się z 1 w początkowej pozycji meczu i 0 w innym miejscu.
+/sumuje
2<sprawdzenie tablicy, czy suma jest większa niż 2 (ponieważ będą 2 trywialne dopasowania)

TwiNight
źródło
7

CJam, 10 bajtów

Złapałem błąd CJam. Moja pierwsza odpowiedź, więc prawdopodobnie można jeszcze zagrać w golfa:

q__+(;);\#

Wyjścia -1 dla FAŁSZ i liczba> = 0 dla PRAWDA

Cyfrowa trauma
źródło
5
Witaj w klubie!
Dennis
5

GolfScript, 10 bajtów

..+(;);\?)

Kolejna implementacja sprytnego pomysłu xnor.

Dennis
źródło
Hahaha, ja tylko napisałem to minutę temu: codegolf.stackexchange.com/questions/37851/... . Myślałem o opublikowaniu go jako odpowiedzi, ale myślałem, że trywialne tłumaczenia są nieciekawe.
Justin
Tym razem nawet szukałem nowych odpowiedzi, ale nie nowych komentarzy ... )Mimo to w twoim kodzie brakuje ; gdy nie pasuje, zostanie wydrukowane -1. Jeśli masz zamiar wysłać to jako odpowiedź, chętnie usunę moje.
Dennis
Dodałem )tuż przed opublikowaniem odpowiedzi (edytowałem komentarz)
Justin
1
Ulepszona wersja (w CJam) q__+)@+#). Nie działa w GolfScript.
jimmy23013
1
@ user23013: Nie ponownie. Właśnie zamierzałem to opublikować! Jest już zbyt wielu CJammerów ...: P
Dennis
3

Python - 59 57

lambda s:any([s*n==s[:n]*len(s)for n in range(2,len(s))])
Falko
źródło
3

Pure Bash, 30 bajtów

Prosty port sprytnej odpowiedzi @ xnor :

[[ ${1:1}${1:0: -1} =~ "$1" ]]

Kod zakończenia to 0 dla PRAWDA i 1 dla FAŁSZ:

$ for s in 'Hello, World!Hello, World!Hello, World!' 'asdfasdfasdf' 'asdfasdfa' 'ĴĴĴĴĴĴĴĴĴ' 'ĴĴĴ123ĴĴĴ123' 'abcdefgh'; do echo "./isrepeated.sh "\"$s\"" returns $(./isrepeated.sh "$s"; echo $?)"; done
./isrepeated.sh "Hello, World!Hello, World!Hello, World!" returns 0
./isrepeated.sh "asdfasdfasdf" returns 0
./isrepeated.sh "asdfasdfa" returns 1
./isrepeated.sh "ĴĴĴĴĴĴĴĴĴ" returns 0
./isrepeated.sh "ĴĴĴ123ĴĴĴ123" returns 0
./isrepeated.sh "abcdefgh" returns 1
$ 

Uwaga: =~w wyrażeniu bash[[ ... ]] znajduje się operator wyrażenia regularnego . Jednak „można zacytować dowolną część wzorca, aby wymusić dopasowanie go jako łańcucha” . Tak więc, jak to często bywa w przypadku bash, poprawne cytowanie jest bardzo ważne - tutaj chcemy po prostu sprawdzić przesłanie ciągu, a nie dopasowanie wyrażenia regularnego.

Cyfrowa trauma
źródło
3

TI-BASIC - 32

Myślałem, że spróbuję tokenizowanego języka. Uruchom z ciągiem w Ans, zwraca 0, jeśli false, a długość powtarzanego ciągu, jeśli true.

inString(sub(Ans+Ans,1,2length(Ans)-1),sub(Ans,length(Ans),1)+Ans

Niesamowite, jak to jest jedna linijka.

Josiah Winslow
źródło
Ale ... ale ... zamierzałem użyć TI-BASIC: P +1
Timtech
@Timtech Cóż, zwróć uwagę na każdego, kto próbuje manipulować ciągiem w TI-BASIC: Nie próbuj manipulować ciągiem w TI-BASIC. : P Trudno było to zrobić i zoptymalizować.
Josiah Winslow,
Dobry pomysł. Manipulacja łańcuchem jest jedną z najtrudniejszych rzeczy do zrobienia. Jednak opublikowałem kilka takich odpowiedzi, więc myślę, że teraz masz konkurenta;)
Timtech
Przynieś to! : P
Josiah Winslow,
3

ECMAScript 6 (189)

(function(){var S=String.prototype,r=S.repeat;S.isRepeated=function(){return!1};S.repeat=function(c){var s=new String(r.call(this,c));if(c>1)s.isRepeated=function(){return!0};return s}}());

 

< console.log("abc".isRepeated(),"abc".repeat(10).isRepeated());
> false true

Czy to jedyne prawidłowe rozwiązanie? Na przykład słowo (ciąg) nananiekoniecznie jest tworzone z"na".repeat(2)

Mardoxx
źródło
"nana"nie jest, ale pytaniem nie jest sprawdzenie, czy .repeatzostał użyty, czy nie. Raczej, czy ciąg jest powtórzony, czy nie
Optimizer
Wiem, po prostu starałem się być bystry: P
Mardoxx
2

ECMAScript 6 (34 36 )

Kolejna odpowiedź ES6, ale bez używania repeati korzystania sztuczkę XNOR za :

f=i=>(i+i).slice(1,-1).contains(i)

Musi być uruchomiony w konsoli przeglądarki obsługującej ES6, takiej jak Firefox.

Ingo Bürk
źródło
2

C 85

l,d;f(s){return l=strlen(s),strstr(d,strcpy(strcpy(d=alloca(l*2+1),s)+l,s)-1)-d-l+1;}

Okazało się, że jest dość długi, ale funkcje zewnętrzne są zawsze takie. Przyszło mi do głowy, że mogę przepisać każdą funkcję łańcuchową, zastępując je pętlą lub funkcją rekurencyjną. Ale z mojego doświadczenia wynika, że ​​okaże się to dłuższe i szczerze mówiąc nie chcę tego wypróbowywać.

Po kilku badaniach zobaczyłem rozwiązania o wysokiej wydajności, ale nie tak sprytne (i krótkie) jak xnor. żeby być oryginalnym ... przepisałem ten sam pomysł w ok.

wyjaśnienie:

int length, 
    duplicate;
int is_repetition(char *input)
{
    // length = "abc" -> 3
    length = strlen(input);
    // alloca because the function name is as long as "malloc" 
    // but you don't have to call free() because it uses the stack
    // to allocate memory
    // duplicate = x x x x x x + x
    duplicate = alloca(length*2 + 1);
    // duplicate = a b c 0 x x + x
    strcpy(duplicate, input);
    // duplicate = a b c a b c + 0
    strcpy(duplicate + length, input);
    if (strstr(duplicate,duplicate + length - 1) != duplicate + length - 1)
        // repetition
        // e.g. abab -> abababab -> aba[babab]
        // -> first occurence of [babab] is not aba[babab]
        // but a[babab]ab -> this is a repetition
        return 1;
    else
        // not repetition
        // e.g. abc -> abcabc -> ab[cabc]
        // -> first occurence of [cabc] is ab[cabc]
        // it matches the last "cabc"
        return 0;
}
bebe
źródło
1

ECMAScript 6 (59 62 67 73 )

Nie jest zwycięzcą, ale wydaje się, że w ES6 powinna być przynajmniej jedna odpowiedź na to pytanie, które faktycznie korzysta z repeatfunkcji:

f=i=>[...i].some((_,j)=>i.slice(0,j).repeat(i.length/j)==i)

Musi być uruchomiony w konsoli przeglądarki obsługującej ES6, takiej jak Firefox.

Robi wiele niepotrzebnych iteracji, ale po co wydłużać czas, aby tego uniknąć, prawda?

  • Edycja nr 1: Zapisano kilka bajtów, przekształcając je w funkcję. Dzięki Optimizer!
  • Edytuj # 2: Dzięki hsl za sztuczkę operatora rozprzestrzeniania, aby zaoszczędzić więcej bajtów!
  • Edycja nr 3: I dzięki Robowi W. za kolejne 3 bajty!
Ingo Bürk
źródło
Możesz po prostu przekonwertować go na funkcję, aby zapisać tam więcej bajtów
Optimizer
@Optimizer To prawda, myślę, że nie musi to być „standardowe”. Twoje życie zależy od twojego imienia :)
Ingo Bürk
Nie testowałem tego, ale powinieneś być w stanie korzystać z operatorem spread dla [...i]zamiasti.split('')
NinjaBearMonkey
1
@ hsl Crazy, to działa. Nie wiedziałem, że operator rozprzestrzeniania działa w ten sposób. Początkowo desperacko próbowałem użyć go do stworzenia tablicy z zakresem 0..N. Dzięki!
Ingo Bürk
1
.slice(0,j)jest jedną postacią krótszą niż .substr(0,j). Ponadto konwersja na liczbę całkowitą wydaje się niepotrzebna, |0można ją usunąć (użycie |0faktycznie zmniejsza przydatność metody, ponieważ zakończy się niepowodzeniem w przypadku powtórzeń przekraczających 2 ^ 31).
Rob W
0

Java 8, 28 bajtów

s->s.matches("(?s)(.+)\\1+")

Wypróbuj online.

Wyjaśnienie:

Sprawdza, czy ciąg wejściowy pasuje do wyrażenia regularnego, gdzie String#matchesniejawnie dodaje się, ^...$aby dopasować cały ciąg.
Objaśnienie samego wyrażenia regularnego:

^(s?)(.+)\1+$
^                Begin of the string
 (s?)            Enable DOTALL-mode, where `.` also matches new-lines
     (           Open capture group 1
      .+          One or more characters
        )        Close capture group 1
         \1+     Plus the match of the capture group 1, one or more times
            $    End of the string

Więc w zasadzie sprawdza, czy podciąg jest powtarzany dwa lub więcej razy (obsługując nowe wiersze).

Kevin Cruijssen
źródło