Programmierquiz: Kürzesten, nicht passenden String finden, auf dass ein RegExp nicht passt
Geschrieben von skaldrom am 15. Oktober 2011
Hier mal eine lustige Aufgabe, mit der ich vor Kurzem konfrontiert war: Gegeben sei ein Alphabet Σ mit Symbolen und eine Regular Expression, wie etwa (0*|1*)(0*|1*)(0*|1*). Nun ist dar kürzeste String mit Symbolen aus dem Alphabet gesucht, auf dass der gegebene RegExp nicht passt.
…Hier würde etwas Musik gespielt und ein Countdown eingeblendet werden, damit der interessierte Leser eine Lösung erarbeiten kann 
…
Meine Lösung funktioniert, sofern die Symbole im Alphabet einem Symbol in UTF-8 entsprechen und ist trivial: Zuerst werden alle Permutationen gebildet und der RegExp daran getestet. Aus reinem Masochismus habe ich versucht, dies in Python 3.2 zu implementieren. Und nein, itertools packt das nicht!
Ein Testdurchgang könnte folgendermassen aussehen (Das Alphabet besteht aus 0 und 1):
$ python3.2 msfr.py -v '(0*|1*)(0*|1*)(0*|1*)' 0 1
Σ: {0, 1}
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with ε MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 00 MATCH
[...]
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0011 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0100 MATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0101 NOMATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 0110 MATCH
[...]
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1010 NOMATCH
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1011 MATCH
[...]
Testing: '^(0*|1*)(0*|1*)(0*|1*)$' with 1111 MATCH
Found nonmatching strings with length 4: 0101, 1010
Klappt also nicht schlecht. ε ist übrigens der leere String .
Dies ist mein erstes Script in Python überhaupt. Für Anregungen und Verbesserungsvorschläge bin ich mehr als dankbar:
'''
Find a minimal non-matching string for a given regular expression and an alphabet.
Created on Oct 1, 2011
@author: Skaldrom Y. Sarg
'''
import argparse
import re
import sys
def allstrings(alphabet, length):
"""Find the list of all strings of 'alphabet' of length 'length'"""
if length == 0:
return [""]
c = []
for i in range(length): # @UnusedVariable
c = [[x] + y for x in alphabet for y in c or [[]]]
return c
if __name__ == '__main__':
scriptHelp= "msfr: Find a minimal non-matching string for a given regular expression and an alphabet.\n\
\n\
Example: python3 msfr.py '(0*|1*)(0*|1*)(0*|1*)' 0 1"
parser = argparse.ArgumentParser(description=scriptHelp, epilog='Written by Michael Schneider.')
parser.add_argument('-v, --verbose', dest='verbose', action='store_true', default=False, help='output more verbose')
parser.add_argument('-m, --maxlength', dest='maxlength', default=10, help='max number of symbols to test (default: 10)')
parser.add_argument('regexp', type=str, nargs=1, help='the regular expression')
parser.add_argument('alphabet', metavar='S', type=str, nargs='+', help='a symbol of the alphabet')
args = parser.parse_args()
# Start
if(args.verbose):
print('Σ: {' + ", ".join(args.alphabet)+'}')
foundNonMatch = []
for wordlength in range(0, args.maxlength):
for string in allstrings(args.alphabet, wordlength):
testString = "".join(string)
testRegexp = args.regexp[0]
if args.verbose:
print(" Testing: '^" + testRegexp + "$' with " + (testString if len(testString) != 0 else 'ε'), end="")
try:
result = re.match('^' + testRegexp + '$', testString)
except re.error as exc:
if args.verbose:
print("\n")
print("ERROR - Invalid regexp: " + str(exc))
sys.exit(0)
if(result != None):
if args.verbose:
print(" MATCH")
else:
foundNonMatch.append(testString)
if args.verbose:
print(" NOMATCH")
if(foundNonMatch):
break
if not foundNonMatch:
print("No nonmatching strings found until length " + args.maxlength + ".")
else:
foundStingsLength = str(len(foundNonMatch[0]))
foundStrings = ", ".join(foundNonMatch) if len(foundNonMatch[0]) > 0 else 'ε'
print("Found nonmatching string" + ("s" if len(foundNonMatch) else "") + " with length " + foundStingsLength +": " +foundStrings)
Eingeordnet in Theorie und Schnipsel | Keine Kommentare »
Wie man in 
Das Arsenal an Geräten, die ein durchschnittlicher Geek heutzutage mit sich herumschleppt, hat bald den Gegenwert eines kleinen Autos. Wenn früher ein Rucksack geklaut wurde (oder, hmm, ehrlich gesagt, zerstreut wie immer “irgendwo liegen gelassen” wurde), dann war der Rucksack selbst oftmals das teuerste Ding des ganzen Verlustes. Heutzutage – mit Laptop, Pad, Phone, … – geht ein ganzer Serverraum verloren. Meine Wenigkeit ist so was von Monotasking, dass ich oftmals mit atmen, laufen, verdauen und transpirieren schon an die Grenze komme (darum spreche ich so wenig, weil dann mein Herz aussetzen würde!), wie soll ich dann noch an die 1001 Geräte denken, die ich irgendwie zusammen wischen und mitnehmen sollte? Da ich körperlich auch nicht unbedingt einem Standard-Hulk entspreche, muss ich wohl gegen Diebstahl andere Massnahmen ergreifen.
Während ich im 
Ich mag Code. Nicht jeden natürlich, “Douchebag” Code nervt, Code der aussieht wie ein schreiender Quasimodo oder Code der von einem Dr. Frankenstein in Ausbildung erstellt wurde sind bemitleidenswert und sehr viel Code stinkt. Code, der gefällt (wie beispielsweise der von 
Eigentlich hätte ich ja ganz Anderes zu tun, aber per Zufall bin ich über den 
Während Andere von ihren Liebsten eine Kravatte geschenkt bekommen, habe ich heute eine Playstation 3 vom Kristkind erhalten *freu*. Ein unglaubliches Teil, das mich schon voll in den Bann gezogen hat. Das Gamen damit ist psychisch: Man schwankt zwischen “Wow, ist das realistisch”, einem epileptischen Anfall und einem Amoklauf. Auf jeden Fall habe ich alle meine Pendenzen ein paar Tage nach hinten verschoben.
Ich hab da so ein Projekt, dass ich schon mehr als ein Jahr vor mir herschiebe: Eine Überarbeitung und Erweiterung einer bestehenden PHP-Applikation. Sie läuft eigentlich super, das Pflichtenheft ist gut und alle sind glücklich. Leider hat sich die “Erweiterung” als Operation am Herzen herausgestellt. Der ursprüngliche Cöder hat eine ziemlich komplexe Struktur erarbeitet, in der er sich selbst ab und zu verheddert hat. Das bedeutet, dass zuerst ganz hässliche Strukturbugs als solche identifiziert und gefixt werden mussten. Im Zuge dieser Operation habe ich so ziemlich jeden Teil der Software berührt, beflucht und daran herumgewurschtelt.