Parowalne ciągi znaków

28

Ciąg jest pairable jeżeli można podzielić na subtrings, z których każdy jest ciągiem kolejno powtarzane dwa razy. Na przykład aabaaababbbabamożna go sparować jako:

aaba aaba
b b
ba ba

Biorąc pod uwagę niepuste ciągi a„i b”, wypisz wartość Prawda, jeśli jest parowalna, i wartość Falsey, jeśli nie jest.

Parowanie:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Nie można sparować:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Zachęcam do wymyślania rozwiązań nieopartych na wyrażeniach regularnych, nawet jeśli w Twoim języku jest już krótsza odpowiedź na wyrażenia regularne. Możesz oznaczyć je jako „bez wyrażenia regularnego”. Przez wyrażenie regularne mam na myśli wbudowany podsystem dopasowania wzorca ciągu.

Tabela liderów:

Pokaż fragment kodu

code-golf string subsequence xnor
źródło
Czy możemy użyć czegoś innego niż ab?
Erik the Outgolfer,
Jeśli bbababbb można sparować, dlaczego baab i aaaaabbaaaaa nie są?
rnso
@rnso Z mojego zrozumienia, bbababbb można rozlać jako 3 pary: bb, abab i bb, które łączą się w tej kolejności, tworząc oryginalny ciąg, podczas gdy pozostałe dwie nie.
Sunny Pun
Przez pytanie „każdy z nich (podłańcuch) jest ciągiem powtórzonym dwukrotnie WYBIERZ SIĘ” i który nie jest zadowolony z bbababbb. W przeciwnym razie baab można również podzielić na baab, a aaaaabbaaaaa na aaaaa bb aaaaa.
rnso
@rnso Nie jestem pewien, co masz na myśli. Mówiąc kolejno, mam na myśli, że te dwa powtórzenia są obok siebie. W „baa b” dwa b są oddzielone przez a, więc to nie działa.
xnor

Odpowiedzi:

11

Python 2, 68 63 bajtów

f=lambda s,n=1:s==2*s[:n]or''<s[n:]>-f(s,n+1)<f(s[n:])*f(s[:n])

Zwraca wartość prawda lub fałsz . Przetestuj na Ideone .

Dennis
źródło
4
To naprawdę czysta rekurencja, przy użyciu indeksu zarówno dla środka podwójnego, jak i środka do podziału. To zabawne, że prawdziwość jest sprawdzana jako mniejsza niż coś. Widzę pewne ulepszenia ...
xnor
8

Siatkówka , 11 bajtów

^((.+)\2)+$

Wypróbuj wszystkie przypadki testowe. Pierwsze dwa bajty sprawiają, że jest to wieloliniowy.

Całkiem dosłowna interpretacja reguł, oczywiście używa wyrażenia regularnego, tak jak wszystkie programy Retina.

FryAmTheEggman
źródło
2
Cholera, czekałem 3 tygodnie na opublikowanie tego ...
ETHprodukcje
2
Martin też czekał .
xnor
5
Ups! Pokonałem go tylko o 10 sekund ... Cóż, jestem pewien, że jeśli napiszę odpowiedź Heksagonii, on mi wybaczy!
FryAmTheEggman
5
@FryAmTheEggman Nie mogę się doczekać. :)
Martin Ender
2
Z Perlem jest dokładnie tak samo:perl -pE '$_=/^((.+)\2)+$/'
Dada
8

Galaretka , 10 bajtów

ẆŒPẋ€€2F€ċ

Niezupełnie wydajne ... Wypróbuj online!

Jak to działa

ẆŒPẋ€€2F€ċ  Main link. Argument: s (string)

Ẇ           Window, generate the array of all substrings of s.
 ŒP         Powerset; generate all subarrays of substrings of s.
   ẋ€€2     Repeat each substring in each subarray twice.
            For example, ["ab", "a", "b"] becomes ["abab", "aa", "bb"].
       F€   Flatten the subarrays by concatenating their strings.
         ċ  Count how many times s appears in the generated strings.
Dennis
źródło
To ... wydaje się nieefektywne. Jak długo dane wejściowe mogą sobie poradzić w rozsądnych ramach czasowych?
John Dvorak,
1
To bardzo mało wydajne (jak sądzę, O (2 ^ n ^ 2) ). Musiałbym sprawdzić lokalnie. Brakuje pamięci TIO dla ciągów o długości 6 .
Dennis
8
Ciąg o długości 6 zajmuje 3:20 minut na moim komputerze i wymaga 6 GB pamięci.
Dennis
1
@Dennis Nie róbmy wtedy danych wejściowych o długości 100 , ponieważ wszystko się zawiesi. Tak, nawet TIO.
Erik the Outgolfer,
@EriktheGolfer To dobry pomysł, ponieważ niepotrzebnie spowolni TIO do innych zastosowań, ale go nie zawiesi. Gdy tylko systemowi zabraknie pamięci, proces po prostu zostaje zabity przez OOM.
Dennis
5

Haskell, 72 69 bajtów (bez wyrażenia regularnego)

g(a:b:c)|a==b=g c
g x=x==[]
any(g.words.concat).mapM(\c->[[c],c:" "])

Podejście brutalnej siły. Wypróbuj na Ideone .

Dzięki BlackCap za -3 bajty.

Wyjaśnienie

Funkcja pomocnika gpobiera listę ciągów znaków i sprawdza, czy składa się z par identycznych ciągów znaków, takich jak ["aa","aa","bba","bba","ab","ab"]. (Anonimowa) funkcja główna dzieli ciąg na wszystkie możliwe sposoby i sprawdza, czy co najmniej jedno dzielenie daje listę, która gakceptuje.

g(a:b:c)                                  g on list with elements a, b and tail c,
        |a==b                              in the case that a==b,
             =g c                          recurses to the tail c.
g x=                                      g on any other list x
    x==[]                                  checks that x is empty.
                                           This includes the case where a is not equal
                                           to b, resulting in False.
any(g.words.concat).mapM(\c->[[c],c:" "]) The main function:
                    mapM(\c->[[c],c:" "])  Replace each letter c with either "c" or "c "
                                           in all possible ways, return list of results.
any(              ).                       Check that at least one result satisfies this:
            concat                          Concatenate the 1- or 2-letter strings,
      words.                                split again at each space,
    g.                                      apply g.
Zgarb
źródło
Można wymienić or.mapzany
Gajówka
@BlackCap Oczywiście, dziękuję! Początkowo miałem any g.map(words.concat)i pomyślałem „hej, mogę anyor
pograć w
5

Python 2, 60 bajtów

f=lambda s,t='':''<s>f(s[1:],t+s[0])|f(t and s)*f(t)>-(s==t)

Mam nadzieję, że to prawda. Działa dość wolno i andnie wygląda optymalnie.

xsot
źródło
1
Próbowałem użyć ciągów, ale nie mogłem zbliżyć się do mojego wyniku opartego na indeksie. To jeden sprytny andmasz tam.
Dennis,
Gratulacje! Recursing na partycji to sztuczka, o której myślałem.
xnor
4

Galaretka , 12 bajtów

ŒṖµœs€2ZEµ€S

Dwa bajty dłuższe niż moja inna odpowiedź , ale to podejście jest znacznie bardziej wydajne i obsługuje wszystkie przypadki testowe oprócz jednego.

Wypróbuj online!

Jak to działa

ŒṖµœs€2ZEµ€S  Main link. Argument: s (string)

ŒṖ            Generate all partitions of s.
  µ      µ€   Map the monadic chain between the µ's over the partitions.
   œs€2         Split each string in the partition into two chunks of equal length.
       Z        Zip/transpose, collecting the first halves in one array and the
                second halves in another.
        E       Test the arrays of halves for equality.
           S  Return the sum of the results, counting the number of different
              ways s can be paired.
Dennis
źródło
3

Pyth - Bez Regex - 13 12 bajtów

Sprawdza, czy którakolwiek z partycji składa się ze wszystkich ciągów, które są sobie równe po podzieleniu na dwie części.

sm.AqMcL2d./

Pakiet testowy .

Maltysen
źródło
3

Brachylog , 14 bajtów (bez wyrażenia regularnego)

lye~l:1j@2zcc?

Wypróbuj online!

Jest to zbyt wolne w przypadku niektórych przypadków testowych

Wyjaśnienie

ly                  The list [0, …, length(Input)]
  e~l               A list whose length is an element of the previous list
     :1j            Append itself to this list
        @2zc        Split in half, zip and concatenate so that the list contains pairs of
                      consecutive identical elements
            c?      The concatenation of that list must result in the Input
Fatalizować
źródło
3

JavaScript (ES6), bez wyrażenia regularnego, 75 74 bajtów

f=s=>!s|[...s].some((_,i)=>i&&s[e='slice'](0,i)==s[e](i,i+=i)&&f(s[e](i)))

W 1przeciwnym razie zwraca do parowania 0. Edycja: Zapisano 1 bajt dzięki @ edc65.

Neil
źródło
Miły! Ta sama liczba przy użyciu substrbez modyfikacji i. Ale slicepowtarzając 3 razy możesz zaoszczędzić 1 bajt aliasing go
edc65
@ edc65 Jak uzyskać taką samą liczbę bez modyfikacji i? Zdaję sobie sprawę, że s.substr(i,i+i)zwraca to samo, s.slice(i,i+=i)ale potem używam zmodyfikowanej wartości ipóźniej ...
Neil,
to s.substr(i,i)2 bajty mniej, a następnie s.slice(i+i)2 bajty więcej
edc65
@ edc65 Och, oczywiście, że potrzebuję więcej kawy ...
Neil,
3

Python, 58 bajtów

f=lambda s,p='':s>''and(f(p)>-(s==p)<f(s))|f(s[1:],p+s[0])

Jest to oparte na rekurencyjnej metodzie Dennisa . Stąd bierze się również logiczna sztuczka negacji.

Nowym pomysłem jest powtarzanie się w partycjach (p,s)oryginalnego łańcucha, zaczynając od ('',s)i wielokrotnie przesuwając pierwszą postać, saby była ostatnią postacią p. Umożliwia to bezpośrednie odwoływanie się do części bez przecinania sznurka. Ponieważ jednak partycja zaczyna się od ppustego, musimy uważać, aby uniknąć nieskończonych pętli f(s)wywoływania f(s).

xnor
źródło
2

JavaScript (ES6), 24 bajty

x=>/^((.+)\2)+$/.test(x)

Prawdopodobnie nie jest krótszy niż ten.

ETHprodukcje
źródło
Nie powinno tak być \2?
Neil,
@Neil Z jakiegoś powodu myślałem, że to działa \1, ale aabwraca true... dzięki za poprawkę.
ETHprodukcje
2

PHP, 40 bajtów

wypisuje 0 dla false i 1 dla true

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);
Jörg Hülsermann
źródło
2

Python, 66 64 bajtów

Dzięki @Zgarb za -1 bajt!

f=lambda x,s=1:x>x[:s]and(x==2*x[:s])|f(x[:s])&f(x[s:])|f(x,s+1)

Zwraca Truelub False.

Wypróbuj online!

Każda pomoc w golfa będzie mile widziana.

Oliver Ni
źródło
1

Rakieta 230 bajtów

(let((sl string-length)(ss substring))(if(odd?(sl s))(printf ".~n")(begin(let p((s s))(if(equal? s "")(printf "!")
(for((i(range 1(add1(/(sl s)2)))))(when(equal?(ss s 0 i)(ss s i(* 2 i)))(p(ss s(* 2 i)(sl s)))))))(printf ".~n"))))

Drukuje „!” dla każdego sposobu, w jaki ciąg jest parowany. Drukuje „.” na końcu.

Nie golfowany:

(define (f s)
  (let ((sl string-length)                              ; create short names of built-in fns
        (ss substring))
    (if (odd? (sl s))  (printf ".~n")                   ; odd length strings cannot be pairable; end here.
        (begin
          (let loop ((s s))                             ; start testing here
            (if (equal? s "") (printf "!")              ; if no remaining string, it must be pairable
                (for ((i (range 1 (add1 (/(sl s)2)))))  ; ch lengths varying from 1 to half of string length
                  (when (equal? (ss s 0 i)              ; ch if substrings are same
                                (ss s i (* 2 i)))
                    (loop (ss s (* 2 i) (sl s) ))))))   ; if yes, loop to check remaining string.
          (printf ".~n")))))                            ; End of testing.

Testowanie: 

(println "Following should be pairable")
(f "bbaabbaa")            ; should produce 2 '!' since 2 ways are possible.
(f "aa")
(f "abaaba")
(f "bbababbb")
(f "aabaaababbbaba")
(f "babababa")                    ; should be pairable in 2 ways.
(f "bbbbbbbbbbbb")                ; should be pairable in many ways.
(f "aaababbabbabbbababbaabaabaababaaba")
(f "aaaabaab")
(println "Following should be unpairable")
; (f "a")
(f "ba")
(f "baab")
(f "abaabaaba")
(f "bbbbbbbbbbbbbbb")
(f "baababbabaaaab")
(f "aaaaabbaaaaa")

Wydajność: 

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.
rnso
źródło
1

Perl, 16 +2 = 18 bajtów (z wyrażeniem regularnym)

Uruchom z -nlflagami. -Ejest wolny.

say/^((.+)\2)+$/

Uruchom jako:

perl -nlE 'say/^((.+)\2)+$/'

Zwraca listę grup przechwytywania (prawda), jeśli można je sparować, łańcuch zerowy, jeśli nie można sparować.

Wyjaśnienie

Te -nlflagi będą uruchamiać kod w pętli ( -n), umieszczenie wejściowe (z tylną przełamane usunięte ze względu -l) w zmiennej $_za każdym razem, a następnie oceny kodowe wejście czas wprowadzony do momentu, gdy program jest ręcznie zakończone. -EFlaga pozwala kod w wierszu poleceń oceniać i umożliwia saypolecenie.

say/^((.+)\2)+$/

   /^((.+)\2)+$/  #The regex engine
      (.+)\2      #Find any set of at least one character, followed by itself
     (      )+    #Do this at least one time
   /^         $/  #Make sure that this matches the entire string from start to end
say               #Output the result of the regex

Jeśli zostanie znalezione dopasowanie (np. Jeśli ciąg znaków można sparować), wyrażenie regularne zwraca listę grup przechwytywania, która zwraca wartość true, która jest następnie przekazywana sayi generowana. Jeśli nie zostanie znalezione dopasowanie, wyrażenie regularne zwraca pusty ciąg znaków, który przekształca się w fałsz, który jest następnie przekazywany sayi generowany.

Próba:

$ perl -nlE 'say/^((.+)\2)+$/'
aaababbabbabbbababbaabaabaababaaba
baababaababaaba                      #Truthy
baababbabaaaab
                                     #Falsy
bbababbb
bbb                                  #Truthy
aabaaababbbaba
bababa                               #Truthy
abaabaaba
                                     #Falsy
Gabriel Benamy
źródło
1

GNU Prolog, 49 46 bajtów

Prawdopodobnie działa również w innych wariantach, chociaż nie wszystkie reprezentują ciągi w ten sam sposób; Reprezentacja GNU Prolog jest przydatna w przypadku tego problemu.

Nie jest jasne, czy liczy się to jako użycie wyrażenia regularnego, czy nie. Nie używa żadnej funkcji podobnej do wyrażenia regularnego, ale cała semantyka języka jest podobna do wyrażeń regularnych.

Nowa wersja (wykorzystuje sztuczkę rekurencyjną widoczną w innych odpowiedziach):

s(X):-append(A,B,X),(A=B;A\=X,B\=X,s(A),s(B)).

Starsza wersja:

s(X):-X=[];append(A,B,X),B\=X,append(C,C,A),s(B).

Jest to wywołany predykat (odpowiednik funkcji Prologa) s, a nie pełny program. Użyj tego w ten sposób:

| ?- s("aa").
true ?
yes
| ?- s("aaababbabbabbbababbaabaabaababaaba").
true ?
yes
| ?- s("baababbabaaaab").
no
| ?- s("bbbbbbbbbbbbbbb").
no

Ciekawą cechą starszego rozwiązania jest to, że jeśli zapytasz tłumacza „czy jest więcej rozwiązań?” poprzez korzystanie z ;Pod true ?szybka (zamiast pytać „czy istnieje jakieś rozwiązanie” poprzez naciśnięcie powrót w wierszu, jak ja powyżej), to zwraca „true” kilka razy równa liczbie różnych sposobów ciąg może być wyrażony w podanej formie (np. zwraca dwa razy „prawda” s("aaaa")., ponieważ można to parsować jako (a a)(a a)lub jako (aa aa)).

Programy prolog często są odwracalne (pozwalający sna generowanie listy ciągów z danej nieruchomości). Starsza nie jest (przechodzi w nieskończoną pętlę), ale to z powodu metody golfowej, której użyłem, aby upewnić się, że C nie jest puste; jeśli przepiszesz program, aby jawnie podać C jako niepuste, wygeneruje ciągi znaków w postaci „aa”, „aabb”, „aabbcc” itd. (Prolog jest Prologem, nie określa tożsamości tworzących je znaków w górę, tylko specyfikacja, które znaki są takie same). Nowsze generuje ciągi znaków w postaci „aa”, „abab”, „abcabc” i tak dalej; jest to nieskończona pętla sama w sobie, a zatem nigdy nie osiągnie punktu, w którym utknie z powodu niewykrycia ciągu o zerowej długości.


źródło
1

Brainfuck, 177 bajtów

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Sformatowany:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Oczekuje wprowadzania bez końcowego znaku nowej linii. Drukuje \x00jako fałszywe i \x01prawdziwe.

Wypróbuj online.

To implementuje wyszukiwanie w pierwszej kolejności. W szczególności: sprawdź powtarzające się prefiksy o większej długości, zaczynając od bieżącego sufiksu, a następnie przejdź do następnego sufiksu, jeśli znaleziono dopasowanie, w przeciwnym razie cofnij się.

Na początku łańcuch jest odwracany, a \x01na końcu umieszczany jest wartownik .

Taśma jest podzielona na 4-komórkowe węzły. Układ pamięci węzła to:

c h x 0

gdzie cjest znakiem, hoznacza flagę określającą, czy znak znajduje się w pierwszej połowie powtarzanego prefiksu, i xflagę służącą do śledzenia bieżącej pary porównywanych znaków. Te hflagi pozostać w miejscu, podczas gdy xflagi tworząc okno poruszający.

Jeśli łańcuch można sparować, wskaźnik wyląduje obok wartownika na końcu głównej pętli; w przeciwnym razie wskaźnik spadnie z lewej strony łańcucha podczas cofania.

Mitch Schwartz
źródło
1

Brachylog , 5 bajtów

~c~jᵐ

Wypróbuj online!

Zauważ, że ten algorytm może zająć bardzo dużo czasu, szczególnie w przypadkach falsey, ponieważ sprawdza każdą możliwą partycję ciągu wejściowego.

Wyjaśnienie

~c     Reversed concatenate: find a list that, when concatenated, results in the input string
       This examines all partitions of the input
  ~jᵐ  Map reversed juxtapose: for each string in that list, is it the result of concatenating
       a string to itself?

W przypadku ciągu wejściowego, takiego jak "ababcc", ~cpróbuje różnych partycji, aż dojdzie do tego ["abab", "cc"], w którym momencie ~joba elementy listy, ᵐwyniki ["ab", "c"]i predykat się powiodą.

DLosc
źródło
1

R , 31 bajtów

grepl("^((.+)\\2)+$",scan(,""))

Wypróbuj online!

Na podstawie odpowiedzi Retina.

R , 129 bajtów

A oto oryginalna odpowiedź, która nie jest wyrażeniem regularnym:

o=(y=utf8ToInt(scan(,"")))<0;for(i in 2*1:(sum(y>0)/2))for(j in 1:(i/2)){w=i:(i-j+1);v=w-j;if(all(y[w]==y[v]))o[c(v,w)]=T};all(o)

Wypróbuj online!

Nick Kennedy
źródło
0

Lithp , 57 znaków

#S::((? (!= (null) (match S "^((.+)\\2)+$")) true false))

Przykładowe użycie:

% pairable_strings.lithp
(
    (def f #S::((? (!= (null) (match S "^((.+)\\2)+$")) true false)))
    (print (f "aa"))
    (print (f "aabaaababbbaba"))
    (print (f "aaababbabbabbbababbaabaabaababaaba"))
    (print (f "ba"))
)

# ./run.js pairable_strings.lithp
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 3, type: 'Atom', name: 'false' }
Andrakis
źródło