Regex: Spiel eine egalitäre Serie

18

Einführung

Ich sehe hier nicht viele Regex-Herausforderungen, daher möchte ich diese täuschend einfache anbieten, die auf verschiedene Arten mit einer Reihe von Regex-Varianten durchgeführt werden kann. Ich hoffe, es bietet Regex-Enthusiasten ein bisschen Spaß beim Golfen.

Herausforderung

Die Herausforderung besteht darin, zu einer "egalitären" Serie zu passen, die ich sehr locker genannt habe: eine Serie mit der gleichen Anzahl verschiedener Charaktere. Dies lässt sich am besten anhand von Beispielen beschreiben.

Spiel:

aaabbbccc
xyz 
iillppddff
ggggggoooooollllllffffff
abc
banana

Nicht übereinstimmen:

aabc
xxxyyzzz
iilllpppddff
ggggggoooooollllllfff
aaaaaabbbccc
aaabbbc
abbaa
aabbbc

Verallgemeinern wollen wir einen Gegenstand der Form entsprechen ( für jede Liste von Zeichen auf , wo für allec1)n(c2)n(c3)n...(ck)nc1ckci != ci+1i, k > 1, and n > 0.

Klarstellungen:

  • Die Eingabe wird nicht leer sein.

  • Ein Zeichen kann sich später in der Zeichenfolge wiederholen (z. B. "Banane")

  • k > 1Es werden also immer mindestens 2 verschiedene Zeichen in der Zeichenkette sein.

  • Sie können davon ausgehen, dass nur ASCII-Zeichen als Eingabe übergeben werden und kein Zeichen ein Zeilenabschlusszeichen ist.

Regeln

(Vielen Dank an Martin Ender für dieses hervorragend formulierte Regelwerk)

Ihre Antwort sollte aus einem einzelnen regulären Ausdruck ohne zusätzlichen Code bestehen (mit Ausnahme einer optionalen Liste von regulären Ausdrucksmodifikatoren, die erforderlich sind, damit Ihre Lösung funktioniert). Sie dürfen keine Funktionen der Regex-Variante Ihrer Sprache verwenden, mit denen Sie Code in der Hosting-Sprache aufrufen können (z. B. der Perl- eModifikator).

Sie können jedes Regex-Aroma verwenden, das vor dieser Herausforderung existierte, aber geben Sie das Aroma an.

Gehen Sie nicht davon aus, dass der reguläre Ausdruck implizit verankert ist, z. B. wenn Sie Python verwenden, gehen Sie davon aus, dass der reguläre Ausdruck mit re.search und nicht mit re.match verwendet wird. Ihre Regex muss für gültige egalitäre Zeichenfolgen mit der gesamten Zeichenfolge übereinstimmen und für ungültige Zeichenfolgen keine Übereinstimmungen ergeben. Sie können beliebig viele Erfassungsgruppen verwenden.

Sie können davon ausgehen, dass die Eingabe immer eine Zeichenfolge aus zwei oder mehr ASCII-Zeichen ohne Zeilenabschluss ist.

Dies ist Regex-Golf, also gewinnt der kürzeste Regex in Bytes. Wenn in Ihrer Sprache (normalerweise /.../) Begrenzer für reguläre Ausdrücke erforderlich sind, zählen Sie die Begrenzer nicht selbst. Wenn Ihre Lösung Modifikatoren erfordert, fügen Sie ein Byte pro Modifikator hinzu.

Kriterien

Dies ist ein altmodisches Golfspiel. Vergessen Sie also die Effizienz und versuchen Sie einfach, Ihre Regex so klein wie möglich zu halten.

Bitte geben Sie an, welche Regex-Variante Sie verwendet haben, und fügen Sie nach Möglichkeit einen Link hinzu, der eine Online-Demo Ihres Ausdrucks in Aktion zeigt.

Jaytea
quelle
Ist das speziell ein Regex-Golf? Sie sollten das wahrscheinlich klarstellen, zusammen mit den Regeln dafür. Die meisten Herausforderungen auf dieser Site sind Golf mit verschiedenen Programmiersprachen.
Text
@LyricLy Danke für den Rat! Ja, ich möchte, dass es reiner Regex ist, d. H. Ein einzelner regulärer Ausdruck in einem regulären Ausdruck nach Wahl des Übergebers. Gibt es noch andere Regeln, die ich beachten sollte?
Jaytea
Ich verstehe Ihre Definition von "egalitär" nicht, das bananaist egalitär.
msh210
@ msh210 Als ich den Begriff "egalitär" zur Beschreibung der Serie einbrachte, dachte ich nicht, dass ich zulassen würde, dass Zeichen später in der Serie wiederholt werden (z. B. in "banana" oder "aaabbbcccaaa" usw.). . Ich wollte nur einen Begriff, der die Idee repräsentiert, dass jeder Teil der sich wiederholenden Zeichen dieselbe Größe hat. Da "Banane" keine wiederholten Zeichen hat, gilt diese Definition für sie.
Jaytea

Antworten:

11

.NET-Variante, 48 Byte

^(.)\1*((?<=(\5())*(.))(.)(?<-4>\6)*(?!\4|\6))+$

Probieren Sie es online! (mit Retina )

Nun, es stellt sich heraus, dass es immerhin einfacher ist, die Logik nicht zu negieren. Ich mache hier eine separate Antwort, weil die beiden Ansätze völlig unterschiedlich sind.

Erläuterung

^            # Anchor the match to the beginning of the string.
(.)\1*       # Match the first run of identical characters. In principle, 
             # it's possible that this matches only half, a quarter, an 
             # eighth etc of of the first run, but that won't affect the 
             # result of the match (in other words, if the match fails with 
             # matching this as the entire first run, then backtracking into
             # only matching half of it won't cause the rest of the regex to
             # match either).
(            # Match this part one or more times. Each instance matches one
             # run of identical letters.
  (?<=       #   We start with a lookbehind to record the length
             #   of the preceding run. Remember that the lookbehind
             #   should be read from the bottom up (and so should
             #   my comments).
    (\5())*  #     And then we match all of its adjacent copies, pushing an
             #     empty capture onto stack 4 each time. That means at the
             #     end of the lookbehind, we will have n-1 captures stack 4, 
             #     where n is the length of the preceding run. Due to the 
             #     atomic nature of lookbehinds, we don't have to worry 
             #     about backtracking matching less than n-1 copies here.
    (.)      #     We capture the character that makes up the preceding
             #     run in group 5.
  )
  (.)        #   Capture the character that makes up the next run in group 6.
  (?<-4>\6)* #   Match copies of that character while depleting stack 4.
             #   If the runs are the same length that means we need to be
             #   able to get to the end of the run at the same time we
             #   empty stack 4 completely.
  (?!\4|\6)  #   This lookahead ensures that. If stack 4 is not empty yet,
             #   \4 will match, because the captures are all empty, so the
             #   the backreference can't fail. If the stack is empty though,
             #   then the backreference will always fail. Similarly, if we
             #   are not at the end of the run yet, then \6 will match 
             #   another copy of the run. So we ensure that neither \4 nor
             #   \6 are possible at this position to assert that this run
             #   has the same length das the previous one.
)+
$            # Finally, we make sure that we can cover the entire string
             # by going through runs of identical lengths like this.
Martin Ender
quelle
Ich liebe es, dass Sie zwischen den beiden Methoden hin und her geschaukelt haben! Ich dachte auch, der negative Ansatz hätte kürzer sein müssen, bis ich ihn tatsächlich ausprobiert und als sehr viel umständlicher empfunden habe (auch wenn ich der Meinung bin, dass er einfacher sein sollte). Ich habe 48b in PCRE und 49b in Perl mit einem völlig anderen Verfahren, und mit Ihrer dritten Methode in .NET um die gleiche Größe, ich würde sagen , das ist eine ziemlich cool regex Herausforderung: D
jaytea
@jaytea Ich würde die gerne sehen. Wenn sich eine Woche lang niemand etwas einfallen lässt, hoffe ich, dass Sie es selbst veröffentlichen. :) Und ja, stimmte zu, es ist schön, dass die Ansätze in der Byteanzahl so nah sind.
Martin Ender
Ich könnte nur! Auch Perl man hat bis 46b
golfen
Also dachte ich mir, dass Sie diese jetzt vielleicht sehen wollen! Hier 48b in PCRE: ((^.|\2(?=.*\4\3)|\4(?!\3))(?=\2*+((.)\3?)))+\3$Ich war das Experimentieren mit \3*anstatt (?!\3)zu machen , 45b aber , dass nicht auf „aabbbc“ :( Die Perl - Version ist leichter zu verstehen, und es ist bis jetzt 45b: ^((?=(.)\2*(.))(?=(\2(?4)?\3)(?!\3))\2+)+\3+$- der Grund , warum ich es nennen Perl , obwohl es PCRE scheint gültig zu sein, ist, dass PCRE glaubt, (\2(?4)?\3)auf unbestimmte Zeit wiederkehren zu können, während Perl ein wenig schlauer / nachsichtig ist!
Jaytea
@jaytea Ah, das sind wirklich nette Lösungen. Sie sollten sie wirklich in einer separaten Antwort veröffentlichen. :)
Martin Ender
9

.NET-Variante, 54 Byte

^(?!.*(?<=(\2)*(.))(?!\2)(?>(.)(?<-1>\3)*)(?(1)|\3)).+

Probieren Sie es online! (mit Retina )

Ich bin mir ziemlich sicher, dass dies nicht optimal ist, aber es ist das Beste, was ich mir derzeit für Bilanzkreise einfallen lässt. Ich habe eine Alternative mit der gleichen Byteanzahl, die größtenteils gleich ist:

^(?!.*(?<=(\3())*(.))(?!\3)(?>(.)(?<-2>\4)*)(\2|\4)).+

Erläuterung

Die Hauptidee ist, das Problem umzukehren, nicht egalitäre Zeichenfolgen zuzuordnen und das Ganze in einen negativen Lookahead zu setzen, um das Ergebnis zu negieren. Der Vorteil ist, dass wir n nicht über den gesamten String hinweg verfolgen müssen (da Sie aufgrund der Art der Bilanzkreise normalerweise n beim Überprüfen verwenden), um zu überprüfen, ob alle Läufe gleich lang sind. Stattdessen suchen wir nur ein einzelnes Paar benachbarter Läufe, die nicht die gleiche Länge haben. Auf diese Weise muss ich n nur einmal verwenden.

Hier ist eine Aufschlüsselung der Regex.

^(?!.*         # This negative lookahead means that we will match
               # all strings where the pattern inside the lookahead
               # would fail if it were used as a regex on its own.
               # Due to the .* that inner regex can match from any
               # position inside the string. The particular position
               # we're looking for is between two runs (and this
               # will be ensured later).

  (?<=         #   We start with a lookbehind to record the length
               #   of the preceding run. Remember that the lookbehind
               #   should be read from the bottom up (and so should
               #   my comments).
    (\2)*      #     And then we match all of its adjacent copies, capturing
               #     them separately in group 1. That means at the
               #     end of the lookbehind, we will have n-1 captures
               #     on stack 1, where n is the length of the preceding
               #     run. Due to the atomic nature of lookbehinds, we
               #     don't have to worry about backtracking matching
               #     less than n-1 copies here.
    (.)        #     We capture the character that makes up the preceding
               #     run in group 2.
  )
  (?!\2)       #   Make sure the next character isn't the same as the one
               #   we used for the preceding run. This ensures we're at a
               #   boundary between runs.
  (?>          #   Match the next stuff with an atomic group to avoid
               #   backtracking.
    (.)        #     Capture the character that makes up the next run
               #     in group 3.
    (?<-1>\3)* #     Match as many of these characters as possible while
               #     depleting the captures on stack 1.
  )
               #   Due to the atomic group, there are three two possible
               #   situations that cause the previous quantifier to stopp
               #   matching. 
               #   Either the run has ended, or stack 1 has been depleted.
               #   If both of those are true, the runs are the same length,
               #   and we don't actually want a match here. But if the runs
               #   are of different lengths than either the run ended but
               #   the stack isn't empty yet, or the stack was depleted but
               #   the run hasn't ended yet.
  (?(1)|\3)    #   This conditional matches these last two cases. If there's
               #   still a capture on stack 1, we don't match anything,
               #   because we know this run was shorter than the previous
               #   one. But if stack 1, we want to match another copy of 
               #   the character in this run to ensure that this run is 
               #   longer than the previous one.
)
.+             # Finally we just match the entire string to comply with the
               # challenge spec.
Martin Ender
quelle
Ich habe versucht, es zu machen scheitern: banana, aba, bbbaaannnaaannnaaa, bbbaaannnaaannnaaaaaa, The Nineteenth Byte, 11, 110, ^(?!.*(?<=(\2)*(.))(?!\2)(?>(.)(?<-1>\3)*)(?(1)|\3)).+, bababa. Ich habe versagt. :( +1
Erik der Outgolfer
1
In diesem Moment, wenn Sie Ihre Erklärung beendet haben und dann herausfinden, dass Sie 1 Byte sparen können, indem Sie den genau entgegengesetzten Ansatz verwenden ... Ich denke, ich werde gleich eine andere Antwort geben ...: |
Martin Ender
@MartinEnder ... Und dann stellen Sie fest, dass Sie diesen um 2 Bytes Golf spielen können haha: P
Mr. Xcoder
@ Mr.Xcoder Müsste jetzt 7 Bytes groß sein, also hoffe ich, dass ich in Sicherheit bin. ;)
Martin Ender