Wyrażenia regularne Perl i PCRE, 280 bajtów
^(?=(.*z){2})(?=(.*\(){43})(?=(.*\)){43})(?=(.*\*){22})(?=(.*\.){23})(?=(.*0){2})(?=(.*1){6})(?=(.*2){16})(?=(.*3){7})(?=(.*4){4})(?=(.*5){1})(?=(.*6){3})(?=(.*7){2})(?=(.*8){2})(?=(.*9){1})(?=(.*=){22})(?=(.*\?){22})(?=(.*\\){11})(?=(.*\^){2})(?=(.*\{){23})(?=(.*\}){23}).{280}\z
(Nieco) bardziej czytelny:
^
(?=(.*z){2})
(?=(.*\(){43})
(?=(.*\)){43})
(?=(.*\*){22})
(?=(.*\.){23})
(?=(.*0){2})
(?=(.*1){6})
(?=(.*2){16})
(?=(.*3){7})
(?=(.*4){4})
(?=(.*5){1})
(?=(.*6){3})
(?=(.*7){2})
(?=(.*8){2})
(?=(.*9){1})
(?=(.*=){22})
(?=(.*\?){22})
(?=(.*\\){11})
(?=(.*\^){2})
(?=(.*\{){23})
(?=(.*\}){23})
.{280}\z
Działa to w czasie O (2 ^ n), jak napisano, więc jest niezwykle nieefektywne. Najprostszym sposobem, aby go przetestować ma zastąpić wszystkie wystąpienia .*
z .*?
, co powoduje sytuację, w której to pasuje do sprawdzenia pierwszy (co oznacza, że mecze w czasie liniowym, ale nadal trwa wykładniczą czasu, jeżeli nie pasuje).
Podstawową ideą jest to, że wymuszamy długość wyrażenia regularnego równego 280 i używamy twierdzeń typu lookahead, aby zmusić każdy znak w wyrażeniu regularnym do pojawienia się co najmniej pewną liczbę razy, np. (?=(.*z){2})
Zmusza z
postać do pojawienia się co najmniej dwa razy. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23
wynosi 280, więc nie możemy mieć żadnych „dodatkowych” wystąpień żadnych znaków.
To jest przykład programowania autogramu , zdanie, które opisuje się, wymieniając liczbę każdego znaku, który zawiera (a w tym przypadku także całkowitą długość). Miałem dość szczęścia w jego tworzeniu (zwykle musisz użyć brutalnej siły, ale natknąłem się na to rozwiązanie podczas testowania mojego programu brutalnej siły, zanim w pełni go napisałem).
Wyrażenia regularne Perl i PCRE, 253 bajty, we współpracy z Martinem Enderem
Postawiłem hipotezę, że mogą istnieć krótsze rozwiązania pomijające niektóre cyfry (najprawdopodobniej 9, 8 lub 7). Martin Ender znalazł taki, pokazany poniżej:
^(?=(.*z){2})(?=(.*\(){39})(?=(.*\)){39})(?=(.*\*){20})(?=(.*\.){21})(?=(.*0){4})(?=(.*1){6})(?=(.*2){11})(?=(.*3){6})(?=(.*4){3})(?=(.*5){2})(?=(.*6){3})(?=(.*9){4})(?=(.*=){20})(?=(.*\?){20})(?=(.*\\){9})(?=(.*\^){2})(?=(.*{){21})(?=(.*}){21}).{253}\z
Wersja do odczytu:
^
(? = (. * z) {2})
(? = (. * \ () {39})
(? = (. * \)) {39})
(? = (. * \ *) {20})
(? = (. * \.) {21})
(? = (. * 0) {4})
(? = (. * 1) {6})
(? = (. * 2) {11})
(? = (. * 3) {6})
(? = (. * 4) {3})
(? = (. * 5) {2})
(? = (. * 6) {3})
(? = (. * 9) {4})
(? = (. * =) {20})
(? = (. * \?) {20})
(? = (. * \\) {9})
(? = (. * \ ^) {2})
(? = (. * {) {21})
(? = (. *}) {21})
. {253} \ z