Coding-Quiz {18}
Reguläre Ausdrücke - Reverse Engineered
Regeln
Es ist erlaubt und erwünscht, dass ihr euch direkt in diesem Thema über die Aufgabe austauscht.
Also stellt bei Unklarheiten in der Aufgabenstellung oder Problemen bei der Umsetzung Fragen,
versorgt uns mit nützlichen oder weiterführenden Links, diskutiert mögliche Lösungsansätze.
Macht bei Beiträgen, die allzu viel verraten, aber bitte trotzdem Gebrauch vom [ spoiler ]-Tag.
Sinn der Sache ist nicht, fertige Codes/Libraries zu genau der Aufgabe von irgendwo zu Kopieren.
Die verwendete
Programmiersprache steht frei zur Auswahl,
mehrere Lösungen in verschiedenen Sprachen sind erlaubt.
Die Abgabe erfolgt wie immer im Abgabeforum.
Threadname bitte in Form: [Quiz #18] Name (Sprache)
Die Einreichungen sind dort vorerst nicht für andere Teilnehmer sichtbar;
Danach kann natürlich alles gelesen und auch diskutiert werden.
Es ist nur die höchste gemachte Schwierigkeitsstufe abzugeben,
da sie automtisch die Niedrigeren erfüllt. Sofern diese nicht gelöst werden konnte,
sind die Codes für die niedrigeren Stufen natürlich auch willkommen!
Abgabefrist ist Sonntag, der 29. September 2013 um 23:59 Uhr.
Die Aufgabe
Reguläre Ausdrücke sind von jeher ein mächtiges Werkzeug,
welche dem Programmierer an die Hand gelegt wird.
Normalerweise prüft solch ein RegExp, ob ein Text zu ihm passt,
doch nun spielen wir das Spiel rückwärts: findet einen Text, der zum RegExp passt!
Allgemeines
"Zeilenbegrenzer" bei den Regexp werde implizit angenommen.
Die Regexp a.c passt also auf abc, nicht aber auf mnoabcqrst
(was zB. .*a.c.* wäre)
Von den Regexp sollen mindestens unterstützt werden:
Als Alphabet soll mindestens der ASCII-Code (die ersten 128 Zeichen) zur Verfügung stehen.
Nicht nur abc, 01 oder Ähnliches.
Hinweis: Wer mit Unicode arbeiten will sollte beachten,
dass beim man sich beim Direktzugriff auf Buchstaben eines Strings
ggf. selbst mit verschiedenen Bytelängen pro Zeichen herumärgern kann,
weil zB. Java-char´s nur 2 Byte haben (während es zB. in UTF8 und UTF16 Längeres gibt).
Hier ein paar Regexes, damit ihr eure Parser testen könnt (sofern ihr einen nutzt):
Stufe 1
Euer Programm soll für einen regulären Ausdruck R
jeweils mindestens n passende Texte finden
(oder weniger, falls nicht mehr möglich sind)
R und n sind vom Benutzer einzugeben.
Als Beispiele könnt ihr folgende nutzen:
a) n = 10
b) n = 1
Der Einfachkeit halber kann man annehmen, dass die Texte
eine vorgegebene Maximallänge nicht überschreiten.
Bruteforce-Lösungen sind ausdrücklich erlaubt.
Die Verwendung fertiger Sachen zum Prüfen, ob ein String ein Regexp matcht, ist erlaubt.
Art der Eingabe/Ausgabe bleibt euch überlassen (Konsole, Gui, Dateien...)
Stufe 2
Nun erweitert euer Programm so, dass mehrere reguläre Ausdrücke
gleichzeitig berücksichtigt werden.
Das Programm soll nun mindestens n Strings ausgeben,
die jeweils auf alle regulären Ausdrücke passen.
Stufe 3
Diesmal ist es wieder nur ein Regexp, der gelten muss,
aber: Bruteforce-Durchprobieren aller Wörter ist nicht mehr erlaubt.
Damit fällt auch die Annahme zur maximalen Länge weg.
Damit die Aufgabe nicht ganz so schwer wird beschränken wir die Syntax der regulären Ausdrücke:
Es muss nichts unterstützt werden, was irgendwie mit variablen Anzahlen zu tun hat,
also keine * + ? {} mehr.
Die Implementierung ist/sollte zwangsläufig mit Stufe 1 kompatibel sein
(wenn man die vereinfachte Syntax beachtet).
Stufe 4
Noch ein Schritt schwerer: Mehrfache Regexp (die wieder alle zusammen gelten müssen).
nach wie vor kein Bruteforce und vereinfachte Syntax.
Die Implementierung ist/sollte zwangsläufig mit Stufe 1+2+3 kompatibel sein
(wenn man die vereinfachte Syntax beachtet).
Stufe 5
Die Spitze des Ganzen:
Mehrfache Regexp, kein Bruteforce, aber:
Volle Regexp, ohne Vereinfachung.
Wer diese letzte Stufe schafft deckt mit diesem Programm auch alle anderen Stufen ab.
Und jetzt ran an die Tasten und viel Spaß beim Programmieren!
Reguläre Ausdrücke - Reverse Engineered
Regeln
Es ist erlaubt und erwünscht, dass ihr euch direkt in diesem Thema über die Aufgabe austauscht.
Also stellt bei Unklarheiten in der Aufgabenstellung oder Problemen bei der Umsetzung Fragen,
versorgt uns mit nützlichen oder weiterführenden Links, diskutiert mögliche Lösungsansätze.
Macht bei Beiträgen, die allzu viel verraten, aber bitte trotzdem Gebrauch vom [ spoiler ]-Tag.
Sinn der Sache ist nicht, fertige Codes/Libraries zu genau der Aufgabe von irgendwo zu Kopieren.
Die verwendete
Programmiersprache steht frei zur Auswahl,mehrere Lösungen in verschiedenen Sprachen sind erlaubt.
Die Abgabe erfolgt wie immer im Abgabeforum.
Threadname bitte in Form: [Quiz #18] Name (Sprache)
Die Einreichungen sind dort vorerst nicht für andere Teilnehmer sichtbar;
Danach kann natürlich alles gelesen und auch diskutiert werden.
Es ist nur die höchste gemachte Schwierigkeitsstufe abzugeben,
da sie automtisch die Niedrigeren erfüllt. Sofern diese nicht gelöst werden konnte,
sind die Codes für die niedrigeren Stufen natürlich auch willkommen!
Abgabefrist ist Sonntag, der 29. September 2013 um 23:59 Uhr.
Die Aufgabe
Reguläre Ausdrücke sind von jeher ein mächtiges Werkzeug,
welche dem Programmierer an die Hand gelegt wird.
Normalerweise prüft solch ein RegExp, ob ein Text zu ihm passt,
doch nun spielen wir das Spiel rückwärts: findet einen Text, der zum RegExp passt!
Allgemeines
"Zeilenbegrenzer" bei den Regexp werde implizit angenommen.
Die Regexp a.c passt also auf abc, nicht aber auf mnoabcqrst
(was zB. .*a.c.* wäre)
Von den Regexp sollen mindestens unterstützt werden:
- Fixe String und der Punkt . für ein beliebiges Zeichen
- * (Etwas beliebig oft wie .*), ? (0 oder 1 mal),
+ (Mindestens einmal), {min,max} (Genaue Grenzen der erlaubten Anzahl) - ( | ) Logisches Oder und Klammerung zum Abgrenzen und Schachteln
- \ Escapen der Steuerzeichen. Escapesequenzen wie \n Zeilenwechsel sind nicht erforderlich
- [] [^] Beschränken des erlaubten Zeichens, und die Nicht-variante
Die zulässigen Zeichenbeschränkungen [] :- Aufzählungen wie abcdef
- Gruppen wie a-z A-Z 0-9
- \s Whitespace
- \d Zahlen (entspricht [0-9], sofern man Unicode außen vor lässt)
Als Alphabet soll mindestens der ASCII-Code (die ersten 128 Zeichen) zur Verfügung stehen.
Nicht nur abc, 01 oder Ähnliches.
Hinweis: Wer mit Unicode arbeiten will sollte beachten,
dass beim man sich beim Direktzugriff auf Buchstaben eines Strings
ggf. selbst mit verschiedenen Bytelängen pro Zeichen herumärgern kann,
weil zB. Java-char´s nur 2 Byte haben (während es zB. in UTF8 und UTF16 Längeres gibt).
Hier ein paar Regexes, damit ihr eure Parser testen könnt (sofern ihr einen nutzt):
Code:
[0-9]*
[asd]+.?a?([^asd]){2,3}
\s+[^\s]*\\s{2,3}
[0-9][a-z]*.+\s{89,100}.*[uas\s]Stufe 1
Euer Programm soll für einen regulären Ausdruck R
jeweils mindestens n passende Texte finden
(oder weniger, falls nicht mehr möglich sind)
R und n sind vom Benutzer einzugeben.
Als Beispiele könnt ihr folgende nutzen:
a) n = 10
Code:
[a-zA-Z][^reg](exp|sind).[toll]?b) n = 1
Code:
[^comfreek]*Der Einfachkeit halber kann man annehmen, dass die Texte
eine vorgegebene Maximallänge nicht überschreiten.
Bruteforce-Lösungen sind ausdrücklich erlaubt.
Die Verwendung fertiger Sachen zum Prüfen, ob ein String ein Regexp matcht, ist erlaubt.
Art der Eingabe/Ausgabe bleibt euch überlassen (Konsole, Gui, Dateien...)
Stufe 2
Nun erweitert euer Programm so, dass mehrere reguläre Ausdrücke
gleichzeitig berücksichtigt werden.
Das Programm soll nun mindestens n Strings ausgeben,
die jeweils auf alle regulären Ausdrücke passen.
Stufe 3
Diesmal ist es wieder nur ein Regexp, der gelten muss,
aber: Bruteforce-Durchprobieren aller Wörter ist nicht mehr erlaubt.
Damit fällt auch die Annahme zur maximalen Länge weg.
Damit die Aufgabe nicht ganz so schwer wird beschränken wir die Syntax der regulären Ausdrücke:
Es muss nichts unterstützt werden, was irgendwie mit variablen Anzahlen zu tun hat,
also keine * + ? {} mehr.
Die Implementierung ist/sollte zwangsläufig mit Stufe 1 kompatibel sein
(wenn man die vereinfachte Syntax beachtet).
Stufe 4
Noch ein Schritt schwerer: Mehrfache Regexp (die wieder alle zusammen gelten müssen).
nach wie vor kein Bruteforce und vereinfachte Syntax.
Die Implementierung ist/sollte zwangsläufig mit Stufe 1+2+3 kompatibel sein
(wenn man die vereinfachte Syntax beachtet).
Stufe 5
Die Spitze des Ganzen:
Mehrfache Regexp, kein Bruteforce, aber:
Volle Regexp, ohne Vereinfachung.
Wer diese letzte Stufe schafft deckt mit diesem Programm auch alle anderen Stufen ab.
Und jetzt ran an die Tasten und viel Spaß beim Programmieren!
Zuletzt bearbeitet von einem Moderator:
