Im Geiste dieser xkcd
Schreiben Sie ein Programm, das Regex-Golf mit beliebigen Listenpaaren spielt. Das Programm sollte zumindest versuchen, den regulären Ausdruck kurz zu halten. Ein Programm, das nur ausgibt /^(item1|item2|item3|item4)$/
oder ähnliches, ist nicht zulässig.
Die Bewertung basiert auf der Fähigkeit, den kürzesten regulären Ausdruck zu generieren. Die Testlisten sind die der erfolgreichen und erfolglosen US-Präsidentschaftskandidaten, die Sie hier finden (danke @Peter). Natürlich muss das Programm für alle disjunkten Listen funktionieren, also zählt es nicht, einfach eine Antwort für den Präsidenten zurückzugeben.
regular-expression
metagolf
Manishearth
quelle
quelle
/^item1|atem2|item3|item4$/
Hat wahrscheinlich unbeabsichtigten Vorrang (Zeichenfolge muss entweder beginnenitem1
, enthaltenatem2
, enthaltenitem3
oder enden mititem4
).Antworten:
Perl (
111110122 Zeichen)Hierbei wird das aufgerufene CPAN-Modul
Regexp::Assemble
verwendet, um die regulären Ausdrücke zu optimieren. Denn was ist die bessere Sprache für reguläre Ausdrücke als Perl.Auch lesbare Version, nur zum Spaß (mit Hilfe von
-MO=Deparse
).Beispielausgabe (ich habe danach STRG-D ausgeführt
item4
).Außerdem schreibe ich als Bonus den regulären Ausdruck für jedes Wort in der Frage.
Auch Liste der Präsidenten (262 Bytes).
quelle
Nicht meine Lösung (offensichtlich bin ich nicht Peter Norvig!), Aber hier ist eine Lösung der (leicht modifizierten) Frage mit freundlicher Genehmigung von ihm: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb
Das Programm, das er gibt, ist wie folgt (seine Arbeit, nicht meine):
Wobei Gewinner und Verlierer die Gewinner- bzw. Verliererliste sind (oder natürlich 2 Listen). Detaillierte Erläuterungen finden Sie im Artikel.
quelle
Meine Lösung in Faktor geschrieben :
Es ist der gleiche Algorithmus wie bei Norvig. Wenn es darum geht, die Lesbarkeit zu beeinträchtigen, können Sie wahrscheinlich viel mehr Zeichen weggolfen.
quelle
Mein Code ist nicht sehr golfen und komprimiert, aber Sie können ihn unter https://github.com/amitayd/regexp-golf-coffeescript/ (oder speziell unter src / regexpGolf.coffee) überprüfen.
Es basiert auf dem Algorithmus von Peter Norvig mit zwei Verbesserungen:
(Und warf auch in einer optionalen Zufälligkeit)
Für die Gruppen von Gewinnern / Verlierern in diesem Quiz habe ich einen Regex mit 76 Zeichen gefunden:
Weitere Details in meinem Blogbeitrag zum Portieren des Lösers auf coffeescript .
quelle