Paarbare Zeichenfolgen

28

Eine Zeichenfolge kann gepaart werden, wenn sie in Unterzeichenfolgen unterteilt werden kann, von denen jede eine Zeichenfolge ist, die zweimal nacheinander wiederholt wird. Zum Beispiel kann aabaaababbbabagepaart werden als:

aaba aaba
b b
ba ba

Bei einer nicht leeren Zeichenfolge aus a's und b' s wird ein Wahrheitswert ausgegeben, falls dies paarweise möglich ist, und ein Falsey-Wert, falls dies nicht der Fall ist.

Pairable:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Nicht paarbar:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Ich ermutige Sie, nicht auf Regex basierende Lösungen zu entwickeln, auch wenn es in Ihrer Sprache bereits eine kürzere Regex-Antwort gibt. Sie können sie als "kein regulärer Ausdruck" markieren. Mit Regex meine ich ein integriertes Subsystem für die Suche nach Zeichenfolgenmustern.


Bestenliste:

xnor
quelle
Können wir etwas anderes als verwenden ab?
Erik der Outgolfer
Wenn bbababbb paarbar ist, warum sind baab und aaaaabbaaaaa nicht?
rnso
@rnso Aus meiner Sicht kann bbababbb als 3 Paare verschüttet werden: bb, abab und bb, die in dieser Reihenfolge zusammengefügt werden, um die ursprüngliche Zeichenfolge zu bilden, während die anderen beiden dies nicht können.
Sunny Pun
Durch die Frage "Welche (Teilzeichenfolge) ist eine Zeichenfolge zweimal hintereinander wiederholt" und das ist mit bbababbb nicht zufrieden. Ansonsten kann baab auch in baab und aaaaabbaaaaa bis aaaaa bb aaaaa aufgeteilt werden.
rnso
@ rnso Nicht sicher, was du da meinst. Mit fortlaufend meine ich, dass die beiden Wiederholungen nebeneinander liegen. In "baa b" werden die beiden b durch a getrennt, so dass das nicht funktioniert.
xnor

Antworten:

11

Python 2, 68 63 Bytes

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

Gibt True oder False zurück . Teste es auf Ideone .

Dennis
quelle
4
Das ist eine wirklich saubere Rekursion, bei der der Index sowohl für die Mitte des Doppels als auch für die Mitte der Partition verwendet wird. Es ist lustig, dass die Wahrhaftigkeit als weniger als etwas überprüft wird. Ich sehe einige Verbesserungen ...
xnor
8

Retina , 11 Bytes

^((.+)\2)+$

Probieren Sie alle Testfälle aus. Die ersten zwei Bytes machen es mehrzeilig.

Ziemlich wörtliche Interpretation der Regeln, verwendet offensichtlich Regex, wie alle Retina-Programme.

FryAmTheEggman
quelle
2
Verdammt, ich hatte 3 Wochen darauf gewartet, dies zu veröffentlichen ...
ETHproductions
2
Martin hatte auch gewartet .
xnor
5
Hoppla! Ich habe ihn auch nur um 10 Sekunden geschlagen ... Nun, ich bin sicher, wenn ich eine Hexagony-Antwort schreibe, wird er mir vergeben!
FryAmTheEggman
5
@FryAmTheEggman Ich freue mich darauf. :)
Martin Ender
2
Bei Perl ist es genauso:perl -pE '$_=/^((.+)\2)+$/'
Dada
8

Gelee , 10 Bytes

ẆŒPẋ€€2F€ċ

Nicht gerade effizient ... Probieren Sie es online!

Wie es funktioniert

ẆŒ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
quelle
Das ... scheint ineffizient. Wie lange können diese Eingaben in einem angemessenen Zeitraum verarbeitet werden?
John Dvorak
1
Es ist extrem ineffizient ( O (2 ^ n ^ 2) , denke ich). Ich müsste vor Ort überprüfen. TIO verfügt nicht über genügend Speicher für Zeichenfolgen der Länge 6 .
Dennis
8
Eine Zeichenfolge mit der Länge 6 dauert auf meinem Computer 3:20 Minuten und erfordert 6 GB Arbeitsspeicher.
Dennis
1
@Dennis Lass uns dann keine Länge 100 eingeben , da alles abstürzen wird. Ja, sogar TIO.
Erik der Outgolfer
@EriktheGolfer Das ist eine gute Idee, da es TIO für andere Zwecke unnötig verlangsamt, aber nicht zum Absturz bringt. Sobald das System keinen Speicher mehr hat, wird der Prozess einfach vom OOM abgebrochen.
Dennis
5

Haskell, 72 bis 69 Bytes (kein regulärer Ausdruck)

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

Ein Brute-Force-Ansatz. Probieren Sie es auf Ideone .

Danke an BlackCap für -3 Bytes.

Erläuterung

Die Hilfsfunktion erstellt geine Liste von Zeichenfolgen und prüft, ob sie aus Paaren identischer Zeichenfolgen besteht, z ["aa","aa","bba","bba","ab","ab"]. Die (anonyme) Hauptfunktion teilt einen String auf alle möglichen Arten und überprüft, ob mindestens eine Aufteilung zu einer Liste führt, die gakzeptiert.

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
quelle
Sie können or.mapmitany
BlackCap
@BlackCap Natürlich danke! Ich hatte anfangs any g.map(words.concat)und dachte : „Hey, ich kann Golf die anyzu or“ ...
Zgarb
5

Python 2, 60 Bytes

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

Ich hoffe das ist richtig. Es läuft ziemlich langsam und das andsieht nicht optimal aus.

xsot
quelle
1
Ich habe versucht, Zeichenfolgen zu verwenden, aber ich konnte mich meinem indexbasierten Ergebnis nicht annähern. Das ist einer, den anddu da hast.
Dennis
Glückwunsch! Das Wiederholen der Partition war der Trick, den ich im Sinn hatte.
xnor
4

Gelee , 12 Bytes

ŒṖµœs€2ZEµ€S

Zwei Bytes länger als meine andere Antwort , aber dieser Ansatz ist viel effizienter und behandelt alle Testfälle bis auf einen.

Probieren Sie es online!

Wie es funktioniert

ŒṖµœ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
quelle
3

Pyth - Kein Regex - 13 12 Bytes

Überprüft, ob eine der Partitionen aus allen Zeichenfolgen besteht, die einander entsprechen, wenn sie in zwei Teile geteilt werden.

sm.AqMcL2d./

Test Suite .

Maltysen
quelle
3

Brachylog , 14 Bytes (kein regulärer Ausdruck)

lye~l:1j@2zcc?

Probieren Sie es online!

Dies ist für einige Testfälle zu langsam

Erläuterung

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
Tödlich
quelle
3

JavaScript (ES6), kein regulärer Ausdruck, 75 bis 74 Byte

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

Returns 1für paarbar anders 0. Bearbeiten: 1 Byte dank @ edc65 gespeichert.

Neil
quelle
Nett! Gleiche Anzahl mit substrohne Änderung i. Aber mit slice3-
maliger
@ edc65 Wie erhält man die gleiche Zählung ohne Änderung i? Mir ist klar, dass dies s.substr(i,i+i)dasselbe s.slice(i,i+=i)ergibt, aber ich verwende dann den geänderten Wert von ispäter ...
Neil,
es sind s.substr(i,i)2 bytes weniger, dann s.slice(i+i)2 bytes mehr
edc65
@ edc65 Oh, natürlich muss ich mehr Kaffee brauchen ...
Neil
3

Python, 58 Bytes

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

Dies basiert auf der rekursiven Methode von Dennis . Der Boolesche Negationstrick wird auch von dort übernommen.

Die neue Idee besteht darin, Partitionen (p,s)der ursprünglichen Zeichenfolge zu ('',s)wiederholen, indem das erste Zeichen von sals letztes Zeichen von beginnend wiederholt verschoben wird p. Auf diese Weise können die Teile direkt referenziert werden, ohne dass ein Aufschneiden der Zeichenfolgen erforderlich ist. Aber, da die Partition mit beginnt pleer, müssen wir vorsichtig sein , um Endlosschleifen von zu vermeiden f(s)Berufung f(s).

xnor
quelle
2

JavaScript (ES6), 24 Byte

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

Wird wahrscheinlich nicht kürzer.

ETHproductions
quelle
Sollte das nicht sein \2?
Neil
@Neil Aus irgendeinem Grund dachte ich, dass es funktioniert \1, aabkehrt aber zurück true... danke für die Korrektur.
ETHproductions
2

PHP, 40 Bytes

gibt 0 für falsch und 1 für wahr aus

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);
Jörg Hülsermann
quelle
2

Python, 66 64 Bytes

Danke @Zgarb für -1 Byte!

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

Rückgabe Trueoder False.

Probieren Sie es online!

Jede Hilfe beim Golfspielen wäre willkommen.

Oliver Ni
quelle
1

Schläger 230 Bytes

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

Druckt ein '!' für jede Art und Weise, in der die Zeichenfolge paarbar ist. Druckt ein '.' Am Ende.

Ungolfed:

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

Testen:

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

Ausgabe:

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.
rnso
quelle
1

Perl, 16 +2 = 18 Bytes (mit Regex)

Laufen Sie mit den -nlFahnen. -Eist gratis.

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

Rennen wie:

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

Gibt eine Liste der Capture-Gruppen (eine Wahrheit) zurück, wenn sie paarbar sind, und eine Nullzeichenfolge, wenn sie nicht paarbar ist.

Erläuterung

Die -nlFlags führen den Code in einer Schleife ( -n) aus, wobei die Eingabe (mit wegen entferntem Zeilenumbruch -l) $_jedes Mal in die Variable eingefügt und der Code bei jeder Eingabe ausgewertet wird, bis das Programm manuell beendet wird. Mit dem -EFlag können Sie Code in der Befehlszeile auswerten und den sayBefehl aktivieren.

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

Wenn eine Übereinstimmung gefunden wird (z. B. wenn die Zeichenfolge gepaart werden kann), gibt der Regex eine Liste der Erfassungsgruppen zurück, die zu einer Wahrheit ausgewertet wird, die dann an übergeben sayund ausgegeben wird. Wenn keine Übereinstimmung gefunden wird, gibt der reguläre Ausdruck die leere Zeichenfolge zurück, die als falsch ausgewertet wird, die dann an übergeben sayund ausgegeben wird.

Probe:

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

GNU Prolog, 49 46 Bytes

Funktioniert wahrscheinlich auch in anderen Varianten, obwohl sie nicht alle Zeichenfolgen auf die gleiche Weise darstellen. Die Darstellung von GNU Prolog ist für dieses Problem nützlich.

Es ist unklar, ob dies als Verwendung von Regex gilt oder nicht. Es werden keine regulären Ausdrücke verwendet, aber die gesamte Semantik der Sprache ähnelt der von regulären Ausdrücken.

Neue Version (verwendet den Rekursionstrick, der in einigen anderen Antworten zu sehen ist):

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

Ältere Version:

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

Dies ist ein aufgerufenes Prädikat (Prolog-Äquivalent einer Funktion) s, kein vollständiges Programm. Benutze es so:

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

Ein interessantes Merkmal der älteren Lösung ist, dass wenn Sie den Interpreter fragen, "gibt es mehr Lösungen?" Bei Verwendung von ;an der true ?Eingabeaufforderung (anstatt zu fragen, ob "Gibt es eine Lösung?", bei Drücken der Eingabetaste an der Eingabeaufforderung, wie oben beschrieben) wird so oft "true" zurückgegeben, wie die Zeichenfolge auf verschiedene Arten ausgedrückt werden kann in der angegebenen Form (zB gibt es mit "true" zweimal zurück s("aaaa")., da dies als (a a)(a a)oder als geparst werden kann)(aa aa) ).

Prolog - Programme sind oft reversibel (so dass generieren eine Liste von Strings mit der angegebenen Eigenschaft). Das ältere ist es nicht (es geht in eine Endlosschleife), aber das liegt an der Golfmethode, die ich verwendet habe, um sicherzustellen, dass C nicht leer ist; Wenn Sie das Programm so umschreiben, dass C explizit als nicht leer angegeben wird, werden Zeichenfolgen der Form "aa", "aabb", "aabbcc" usw. generiert bis, nur eine Angabe, welche Zeichen gleich sind). Das neuere erzeugt Zeichenketten der Form "aa", "abab", "abcabc" und so weiter; Dies ist eine Endlosschleife für sich und trifft daher nie den Punkt, an dem sie hängen bleiben würde, weil eine Zeichenfolge mit der Länge Null nicht erkannt wird.s


quelle
1

Brainfuck, 177 Bytes

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

Formatiert:

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

Erwartet Eingaben ohne abschließende Zeilenumbrüche. Druckt \x00für falsch und\x01 für wahr.

Probieren Sie es online aus.

Dies implementiert die Tiefensuche. Insbesondere: Überprüfen Sie ab dem aktuellen Suffix, ob wiederholte Präfixe mit zunehmender Länge vorhanden sind, und wechseln Sie dann zum nächsten Suffix, wenn eine Übereinstimmung gefunden wird.

Zu Beginn ist die Zeichenfolge umgekehrt und ein Sentinel \x01 am Ende platziert.

Das Band ist in 4-Zellen-Knoten unterteilt. Das Speicherlayout eines Knotens ist:

c h x 0

Dabei chandelt es sich hum ein Flag, das angibt, ob sich das Zeichen in der ersten Hälfte eines wiederholten Präfixes befindet, und xum ein Flag, mit dem das aktuelle Zeichenpaar verfolgt wird, das verglichen wird. Die hFahnen bleiben an Ort und Stelle, während die xFahnen ein sich bewegendes Fenster bilden.

Wenn die Zeichenfolge gepaart werden kann, landet der Zeiger neben dem Sentinel am Ende der Hauptschleife. Andernfalls fällt der Zeiger beim Zurückverfolgen von der linken Seite der Zeichenfolge ab.

Mitch Schwartz
quelle
1

Brachylog , 5 Bytes

~c~jᵐ

Probieren Sie es online!

Beachten Sie, dass dieser Algorithmus sehr lange dauern kann , insbesondere in Falsey-Fällen, da er jede mögliche Partition der Eingabezeichenfolge überprüft.

Erläuterung

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

Versucht für eine Eingabezeichenfolge wie "ababcc", ~cverschiedene Partitionen, bis es zu kommt ["abab", "cc"], an welchem ​​Punkt ~jerfolgreich für beide Elemente der Liste, Ausgaben ["ab", "c"]und das Prädikat erfolgreich ist.

DLosc
quelle
1

R , 31 Bytes

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

Probieren Sie es online!

Basierend auf der Retina-Antwort.

R , 129 Bytes

Und hier ist eine originelle, nicht reguläre Antwort:

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)

Probieren Sie es online!

Nick Kennedy
quelle
0

Lithp , 57 Zeichen

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

Beispielnutzung:

% 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
quelle