Matthias Goergens hat eine Regex von 25.604 Zeichen (anstatt der ursprünglichen 63.993 Zeichen), die mit Zahlen übereinstimmt, die durch 7 teilbar sind, aber das beinhaltet eine Menge Flusen: redundante Klammern, Verteilung ( xx|xy|yx|yyanstatt [xy]{2}) und andere Probleme, obwohl ich mir sicher bin, dass a Ein Neustart wäre hilfreich, um Platz zu sparen. Wie klein kann das gemacht werden?
Es sind alle möglichen regulären Ausdrücke zulässig, jedoch kein ausführbarer Code im regulären Ausdruck.
Der reguläre Ausdruck sollte mit allen Zeichenfolgen übereinstimmen, die die Dezimaldarstellung einer durch 7 teilbaren Zahl und keine anderen Zeichen enthalten. Zusätzliches Guthaben für einen regulären Ausdruck, der keine anfänglichen Nullen zulässt.
code-golf
math
regular-expression
Charles
quelle
quelle
Antworten:
10791 Zeichen, führende Nullen erlaubt
10795 Zeichen, führende Nullen verboten
0|((foo)0*)+, wo der obige reguläre Ausdruck ist(0|foo)+.Erläuterung
Durch 7 teilbare Zahlen werden durch den offensichtlichen endlichen Automaten mit 7 Zuständen Q = {0,…, 6}, Anfangs- und Endzustand 0 und Übergängen d: i ↦ (10i + d) mod 7 verglichen. Ich habe diesen endlichen Automaten in umgewandelt Ein regulärer Ausdruck, der eine Rekursion für die Menge der zulässigen Zwischenzustände verwendet:
Wenn i, j ∈ Q und S ⊆ Q gegeben sind, sei f (i, S, j) ein regulärer Ausdruck, der mit allen Automatenpfaden von i nach j übereinstimmt, wobei nur Zwischenzustände innerhalb von S verwendet werden.
f (i, ∅, j) = (j - 10i) mod 7,
f (i, S {k}, j) = f (i, S, j) f (i, S, k) f (k, S, k) * f (k, S, j).
Ich habe mit dynamischer Programmierung k gewählt, um die Länge des resultierenden Ausdrucks zu minimieren.
quelle
0|((foo)0*)+13.75512.69912.731 ZeichenDieser reguläre Ausdruck weist die führende Null nicht zurück.
Dies wird mit dem Regex Coach getestet .
Wie wir dahin kommen
Der obige Regex wurde erstellt, indem zuerst ein DFA konstruiert wurde , der die gewünschte Eingabe akzeptiert (Dezimalstellen durch 7 teilbar), dann in einen regulären Ausdruck konvertiert und die Notation fixiert wurde
Um dies zu verstehen, ist es hilfreich, zunächst einen DFA zu erstellen, der die folgende Sprache akzeptiert:
Dies bedeutet, dass Binärzahlen, die durch 7 teilbar sind, "übereinstimmen".
Das DFA sieht folgendermaßen aus:
Wie es funktioniert
Sie behalten einen aktuellen Wert bei
A, der den Wert der vom DFA gelesenen Bits darstellt. Wann liest du ein0dannA = 2*Aund wann liest du ein1A = 2*A + 1. Bei jedem Schritt, den Sie berechnen, gelangenA mod 7Sie zu dem Zustand, der die Antwort darstellt.Also ein Testlauf:
Wir lesen, in
10101welcher die binäre Darstellung für 21 in Dezimal ist.q0, die derzeitA=01, aus der 'Regel'A = 2*A + 1soA = 1.A mod 7 = 1Also gehen wir zum Staatq10,A = 2*A = 2,A mod 7 = 2so bewegen wir uns aufq21,A = 2*A + 1 = 5,A mod 7 = 5, bewegenq50,A = 2*A = 10,A mod 7 = 3, bewegenq31,A = 2*A + 1 = 21,A mod 7 = 0, bewegenq010101durch 7 teilbar ist!Das Konvertieren des DFA in einen regulären Ausdruck ist eine schwierige Aufgabe, daher habe ich JFLAP beauftragt , dies für mich zu tun.
Für Dezimalzahlen
Der Prozess ist ähnlich:
Ich habe einen DFA erstellt, der die Sprache akzeptiert:
Hier ist das DFA:
Die Logik ist ähnlich, gleiche Anzahl von Zuständen, nur viel mehr Übergänge, um alle zusätzlichen Stellen, die Dezimalzahlen mit sich bringen, zu verarbeiten.
Nun ist die Regel ändern
Abei jedem Schritt ist: Wenn Sie eine Dezimalzahl gelesenn:A = 10*A + n. Dann nochmal kurz vormodA7 und geh zum nächsten Stand.Revisionen
Revision 5
Der obige reguläre Ausdruck lehnt jetzt Zahlen ab, die vor Null stehen - natürlich abgesehen von Null.
Dadurch unterscheidet sich der DFA geringfügig. Wenn Sie die erste Null lesen, verzweigen Sie im Grunde genommen vom Anfangsknoten. Das Lesen einer weiteren Null versetzt Sie in eine Endlosschleife für den verzweigten Zustand. Ich habe das Diagramm nicht korrigiert, um dies zu zeigen.
Revision 7
Habe etwas "Metaregex" gemacht und meinen regulären Ausdruck verkürzt, indem einige der Gewerkschaften durch Zeichenklassen ersetzt wurden.
Revision 10 und 11 (von nhahtdh)
Die Änderung des Autors zur Zurückweisung der führenden Null ist falsch. Dadurch stimmen die regulären Ausdrücke nicht mit gültigen Zahlen überein, z. B. 1110 (dezimal = 14) bei binären regulären Ausdrücken und 70 bei dezimalen regulären Ausdrücken. Durch diese Überarbeitung wird die Änderung rückgängig gemacht, sodass beliebige führende Nullen und leere Zeichenfolgen übereinstimmen können.
Durch diese Überarbeitung wird die Größe des Dezimal-Regex vergrößert, da ein Fehler im Original-Regex behoben wird, der durch das Fehlen einer Kante (9) von Status 5 zu Status 3 im Original-DFA verursacht wird.
quelle
1110, und die Dezimale stimmt nicht überein70. Dies wurde sowohl in Python als auch in Perl getestet. (Python erforderlich jede Umwandlung(zu(?:ersten).NET Regex,
119118105 Bytes111 Zeichen, die anfängliche Nullen nicht zulassen:
113 Zeichen, die anfängliche Nullen nicht zulassen und negative Zahlen unterstützen:
Probieren Sie es hier aus.
Erklärung (der vorherigen Version)
Es werden die Techniken verwendet, die von verschiedenen Antworten in dieser Frage verwendet werden: Cops and Robbers: Reverse Regex Golf . Der .NET-Regex verfügt über eine Funktion namens Balancing Group, mit der arithmetisch gearbeitet werden kann.
(?<a>)drückt eine Gruppea.(?<-a>)Popt das und passt nicht, wenn es noch keineapassende Gruppe gibt .(?>...)Passen Sie an und ziehen Sie sich später nicht zurück. Es wird also immer nur die erste passende Alternative gefunden.((?<-t>)(){3}|){6}Multiplizieren Sie die Anzahl der Gruppe t mit 3. Speichern Sie das Ergebnis in der Anzahl der Gruppe 2.(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d)Ordnen Sie eine Zahl und diese Zahl der Gruppe 2 zu.((?<-2>){7}|){3}Entfernen Sie Gruppe 2 ein Vielfaches von 7 Mal.((?<t-2>)|){6}Entfernen Sie die Gruppe 2 und stimmen Sie mit der gleichen Anzahl von Gruppen t überein.$(?(t)a)Wenn es immer noch eine Gruppe gibt, die mit t übereinstimmt, stimmen Sieanach dem Ende der Zeichenfolge überein , was unmöglich ist.Ich dachte, dass diese 103-Byte-Version auch funktionieren sollte, fand aber keine Umgehung des Fehlers im Compiler.
quelle
468 Zeichen
Rubys Regex-Geschmack erlaubt eine Rekursion (obwohl es sich um eine Art Betrug handelt), so dass es einfach ist, einen DFA zu implementieren, der durch 7 teilbare Zahlen erkennt. Jede benannte Gruppe entspricht einem Status, und jeder Zweig in den Abwechslungen belegt eine Ziffer und springt dann in den entsprechenden Status. Wenn das Ende der Zahl erreicht ist, stimmt der reguläre Ausdruck nur dann überein, wenn sich der Motor in der Gruppe "A" befindet, andernfalls schlägt er fehl.
Es erkennt führende Nullen.
quelle
{a*b*|a and b an equal amount of times})Ich war wirklich beeindruckt von Griffins Antwort und musste herausfinden, wie es funktionierte! Das Ergebnis ist das folgende JavaScript. (Es sind 3,5.000 Zeichen, was in gewisser Weise kürzer ist!) Die
genFunktion verwendet einen Teiler und eine Basis und generiert einen regulären Ausdruck, der mit Zahlen in der angegebenen Basis übereinstimmt, die durch diesen Teiler teilbar sind.Ich habe Griffins NFA für jede Basis verallgemeinert: Die
nfaFunktion nimmt einen Divisor und eine Basis und gibt ein zweidimensionales Array von Übergängen zurück. Der Eingang, der erforderlich ist, um beispielsweise von Zustand 0 zu Zustand 2 zu wechseln, iststates[0][2] == "1".Die
reduceFunktion nimmt dasstatesArray auf und führt es durch diesen Algorithmus , um die NFA in Regex zu übersetzen. Die generierten regulären Ausdrücke sind riesig und scheinen trotz meiner Optimierungsversuche viele redundante Klauseln zu enthalten. Der reguläre Ausdruck für 7 base 10 ist ungefähr ~ 67k Zeichen lang; Firefox löst einen "InternalError" für n> 5 aus und versucht, den regulären Ausdruck zu analysieren. Das Ausführen der regulären Ausdrücke unter Chrome wird für n> 6 langsam.Es gibt auch die
testFunktion, die einen regulären Ausdruck und eine reguläre Basis verwendet und gegen die Zahlen 0 bis 100 läuft, alsotest(gen(5)) == [0, 5, 10, 15, ...].Trotz des suboptimalen Ergebnisses war dies eine fantastische Lernmöglichkeit, und ich hoffe, dass ein Teil dieses Codes in Zukunft nützlich sein wird!
quelle
Perl / PCRE, 370 Zeichen
Verwirft die leere Zeichenfolge sowie Zeichenfolgen mit führenden Nullen (außer "0").
quelle