Ihre Aufgabe ist es, reguläre Ausdrücke zu kompilieren ... indem Sie für jedes Zeichen in einem regulären Ausdruck eine Ersetzung angeben.

Regexes

Die Regexes unterstützen diese

REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

Warum nur 1 oder 0? Es dient der Vereinfachung. Der Regex hat also nur die folgenden Zeichen:

*()|10

Es wird wie folgt interpretiert:

1. * ist Kleene-Stern (Wiederholung der linken Gruppe oder 0-mal oder öfter).
2. | ist eine Abwechslung (Übereinstimmung, wenn entweder der reguläre Ausdruck nach links oder der reguläre Ausdruck nach rechts übereinstimmt).
3. () gruppiert.
4. 1 stimmt mit Zeichen 1 überein.
5. 0 Entspricht dem Zeichen 0.

Wie kompiliere ich?

Sie geben sechs Codefragmente an: eines, um jedes reguläre Zeichen zu ersetzen. Zum Beispiel, wenn Ihre Antwort lautet:

*: FSAGFSDVADFS
|: GSDGSAG
(: GSDG
): GDSIH
1: RGIHAIGH
0:GIHEBN

Dann ersetzen Sie jeden regulären Ausdruck durch das entsprechende Code-Snippet.

(0|11)*

wird verwandelt in:

GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

Was soll das resultierende Programm tun?

Ihr Programm wird:

1. Nimm die Eingabe.
2. Gibt einen Wahrheitswert aus, wenn der reguläre Ausdruck mit der gesamten Eingabe übereinstimmt.
3. Anderenfalls wird ein falscher Wert ausgegeben.

Eingaben außerhalb 01sind undefiniertes Verhalten. Die Eingabe kann leer sein.

Zusätzliche Regeln

1. Für ein bestimmtes Regex-Zeichen muss das resultierende Snippet immer dasselbe sein.
2. Danach wird kein Präfix- oder Suffixzeichen hinzugefügt.
3. Der reguläre Ausdruck ist garantiert nicht leer.

Wertung

Das am wenigsten kombinierte Snippet ist der Gewinner. Die Punktzahl für den Beispielfall würde also folgendermaßen berechnet:

FSAGFSDVADFS+ GSDGSAG+ GSDG+ GDSIH+ RGIHAIGH+GIHEBN

12 + 7 + 4 + 5 + 8 + 6 = 42

Schnecken , 48 Bytes

0 -> )0(\0!(l.)(~

1 -> )0(\1!(l.)(~

( -> )0({{(

) -> )0}}(~

| -> )0}|{(

* -> )0),(~

Wenn wir nach Teilübereinstimmungen suchen müssten, anstatt nur die vollständigen Eingaben abzugleichen, wäre dies sehr einfach. 0würde werden \0, 1würde werden \1, *würde werden ,, und die anderen würden sich selbst zuordnen. Stattdessen gibt es eine Menge Spielereien, die verhindern, dass Spiele an einem anderen Ort als dem Anfang beginnen oder an einem anderen Ort als dem Ende enden. !(l.)ist eine Zusicherung, die fehlschlägt, wenn der Beginn der Übereinstimmung nicht am Anfang der Eingabe liegt. ~Stimmt mit einer Zelle außerhalb der Eingabe überein, sodass sie zu allen Zeichen hinzugefügt wird, die am Ende des regulären Ausdrucks stehen dürfen. Wenn ein anderes Regex-Zeichen folgt, wird es durch einen numerischen Quantifizierer aufgehoben0was erfordert, dass es 0-mal übereinstimmt und im Wesentlichen auskommentiert. Damit *( ,) korrekt funktioniert, obwohl der Dummy-Out-of-Bound-Test im Weg ist, werden die Regeln für die Klammerzuordnung der Sprache häufig verwendet. Aus der Dokumentation:

Übereinstimmende Paare von Klammern ()oder geschweiften Klammern {}verhalten sich erwartungsgemäß (wie Klammern in Regex), es ist jedoch auch möglich, die Hälfte eines Paares wegzulassen und es nach den folgenden Regeln abzuleiten. )oder }gruppiert alles nach links, bis die nächste nicht geschlossene Gruppenöffnungsanweisung desselben Typs ( (bzw. desselben Typs {) oder der Beginn des Musters, falls keine vorhanden ist. Es schließt alle nicht geschlossenen Öffnungsanweisungen des entgegengesetzten Typs in der Mitte dieses Bereichs. Ein ansonsten nicht passendes Muster (oder {wird am Ende des Musters geschlossen.

Klar wie Schlamm, oder?

CJam, 151 Bytes

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

Die Zeilen entsprechen den Zeichen 01(|)*(in dieser Reihenfolge). Probieren Sie es online!

Dies verwendet keine eingebauten regulären Ausdrücke oder andere Arten der Mustererkennung. Tatsächlich hat CJam keine dieser Funktionen. Stattdessen beginnt es mit dem regulären Ausdruck, den es darstellt, und erstellt alle möglichen Zeichenfolgen, mit denen es übereinstimmen könnte , um schließlich zu überprüfen, ob die Benutzereingabe eine davon ist.

Testläufe

Im Folgenden wird ein Programm verwendet, das einen regulären Ausdruck aus STDIN liest, jedes seiner Zeichen durch das richtige Snippet ersetzt und schließlich den generierten Code auswertet, um festzustellen, ob er mit der im Befehlszeilenargument angegebenen Eingabe übereinstimmt.

$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

Dies ist leider nicht besonders schnell. Es wird ziemlich schnell ersticken, wenn mehr als 9 Zeichen in der Eingabe oder mehr als ein einzelner Kleene-Stern in der Regex enthalten sind.

Auf Kosten von 5 zusätzlichen Bytes - für insgesamt 156 Bytes - können kürzere Zeichenfolgen generiert werden, um die potenziellen Eingaben mit diesen abzugleichen und sie zu deduplizieren. Dies ändert nichts an der Funktionsweise des Codes. es macht es nur effizienter.

$ cat regex-fast.cjam 
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1