Regex, który pasuje tylko do siebie

338

Istnieje kilka całkiem fajnych wyzwania tam udziałem regex ( Self-dopasowanie wyrażenia regularnego , Regex walidacji regex )

Może to być niemożliwe, ale czy istnieje wyrażenie pasujące TYLKO do siebie?

UWAGA, należy uwzględnić ograniczniki:

na przykład /thing/musi pasować, /thing/a nie pasować thing. Jedynym możliwym dopasowaniem dla Twojego wyrażenia musi być samo wyrażenie. Wiele języków pozwala na implementację łańcucha w miejsce wyrażenia regularnego. Na przykład w Go

package main

import "fmt"
import "regexp"

func main() {

    var foo = regexp.MustCompile("bar")
    fmt.Println(foo.MatchString("foobar"))
}

ale ze względu na wyzwanie pozwól, aby wyrażenie było rozdzielane (symbol początkowy, wyrażenie, symbol końcowy np .: /fancypantpattern/lub @[^2048]@), jeśli chcesz argumentować cudzysłowy jako swój ogranicznik, niech tak będzie. Myślę, że biorąc pod uwagę pozorną trudność tego problemu, nie będzie to miało większego znaczenia.

Aby ci pomóc:

Szybki hack, który przygotowałem dla rubular.com (strona do edycji ruby ​​regex):

var test = document.getElementById("test")
,regex = document.getElementById("regex")
,delimiter="/"
,options = document.getElementById("options")
,delay = function(){test.value = delimiter + regex.value + delimiter + options.value}
,update = function(e){
    // without delay value = not updated value
    window.setTimeout(delay,0);
}
regex.onkeydown = update;
options.onkeydown = update;

Choć technicznie jest to „golf golfowy”, będę pod wielkim wrażeniem, jeśli ktoś znajdzie odpowiedź / udowodni, że jest to niemożliwe.

Link jest teraz naprawiony. Przepraszam wszystkich

Dotychczasowa zwycięska odpowiedź: jimmy23013 z 40 znakami

Dylan Madisetti
źródło
3
Oczywiście każde wyrażenie regularne zawierające tylko literały będzie działać: //, / a /, / xyz / itd. Dobrze byłoby wymagać, aby wyrażenie regularne zawierało operację nieliteralną.
chleba chlebowego
9
literały nie działają, ponieważ musisz dopasować odwrotne ukośniki, na przykład / aaa / będzie pasować, aaaale nie / aaa /
Dylan Madisetti
2
@DylanMadisetti Czy musimy używać //ograniczników, czy też możemy wybierać inne ograniczniki (PCRE obsługuje prawie każdą postać, a w szczególności możesz używać dopasowanych nawiasów / nawiasów klamrowych / nawiasów jako ograniczników).
Martin Ender
3
Myślę, że to całkiem niezły problem matematyczno-obliczeniowy, a dowód może nie być łatwy ... Wiele ważnych twierdzeń powstało jako proste pytanie, więc może za 5 lat pojawi się artykuł w Wikipedii „Problem Madisettiego”;)
Paweł Tokarz
3
Tak, dokładnie. W niektórych językach (pomyśl grep w bash) separator jest zasadniczo pustym ciągiem. Więc zakładanie, że wyrażenie regularne wymaga ograniczników, jest już w pierwszej kolejności błędne. Rzeczywiście, ponieważ grep jest jedną z najwcześniejszych implementacji wyrażeń regularnych, kanoniczna definicja wyrażeń regularnych nie ma ograniczników. Niewłaściwym przejawem tego założenia jest PHP, które wymaga dwóch ograniczników: "/i/"
slebetman

Odpowiedzi:

589

Smak PCRE, 261 289 210 184 127 109 71 53 51 44 40 bajtów

Tak to mozliwe!

<^<()(?R){2}>\z|\1\Q^<()(?R){2}>\z|\1\Q>

Wypróbuj tutaj. (Ale /pokazano, że jest ogranicznikiem w Regex101.)

Powstrzymaj się od robienia niepotrzebnych zmian (aktualizacji) na stronie Regex101. Jeśli twoja edycja nie wymaga ulepszenia, wypróbowania lub przetestowania tego wyrażenia regularnego, możesz go rozwidlić lub utworzyć nowe z ich strony głównej .

Wersja działa bardziej poprawnie na Regex101 (44 bajty):

/^\/()(?R){2}\/\z|\1\Q^\/()(?R){2}\/\z|\1\Q/

Wypróbuj tutaj.

Jest to o wiele prostsze niż oryginalna wersja i działa bardziej jak tradycyjny quine. Próbuje zdefiniować ciąg bez użycia go i użyć go w innym miejscu. Można go więc umieścić bardzo blisko jednego końca wyrażenia regularnego, aby zmniejszyć liczbę znaków potrzebujących więcej znaków do zdefiniowania pasującego wzorca i powtórzyć więcej razy.

Objaśnienia:

  • \Q^\/()(?R){2}\/\z|\1\Qdopasowuje ciąg ^\/()(?R){2}\/\z|\1\Q. Wykorzystuje to dziwactwo, które \Q...\Enie musi być zamknięte, a działają ograniczniki nieskalowane \Q. To spowodowało, że niektóre poprzednie wersje działały tylko na Regex101, a nie lokalnie. Ale na szczęście najnowsza wersja zadziałała i wykorzystałem w ten sposób trochę więcej bajtów.
  • \1przed \Qdopasowaniem przechwyconej grupy 1. Ponieważ grupa 1 nie istnieje w tej opcji, można ją dopasować tylko w połączeniach rekurencyjnych. W wywołaniach rekurencyjnych dopasowuje puste ciągi.
  • (?R){2}wywołuje rekursywnie cały regex dwukrotnie, co odpowiada ^\/()(?R){2}\/\z|\1\Qkażdorazowo.
  • () robi tylko przechwycenie pustego ciągu do grupy 1, co włącza drugą opcję w wywołaniach rekurencyjnych.
  • ^\/()(?R){2}\/\zdopasowania (?R){2}z dodanymi ogranicznikami, od początku do końca. \/Przed wywołania rekurencyjne również zadbali sama ta opcja nie pasuje w wywołań rekurencyjnych, gdyż nie będzie na początku łańcucha.

51 bajtów przy zamkniętym \Q...\E:

/\QE\1|^\/(\\)Q(?R){2}z\/\E\1|^\/(\\)Q(?R){2}z\/\z/

Wypróbuj tutaj.

Wersja oryginalna, 188 bajtów

Dzięki Martin Büttner za grę w golfa w odległości około 100 bajtów!

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.\2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{11}$/

Wypróbuj tutaj.

Lub 210 bajtów bez \Q...\E:

/^(?=.{194}\\2\\.\)\{2}\.\{12}\$\/D$)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{194}\2\\\2\\2\2\\\2\\\2\.\2\\\2\)\2\\\2\{2}\2\\\2\.\2\\\2\{12}\2\\\2\$\2\\\2\/D\2\$\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{12}$/D

Wypróbuj tutaj.

Wersja rozszerzona:

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)        # Match things near the end.
((?=(.2.|))                               # Capture an empty string or \2\ into group 2.
   \2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.
   \2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)      # 1st line escaped.
   \2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\) # 2nd line escaped.
){2}
.{11}$/x

Rozszerzenia takie jak (?=i \1sprawiły, że tak zwane „wyrażenia regularne” nie są już regularne, co również umożliwia quines. Odwołanie wsteczne nie jest regularne, ale z wyprzedzeniem.

Wyjaśnienie:

  • Używam \2\zamiast \uciec od znaków specjalnych. Jeśli \2pasuje do pustego ciągu, \2\x(gdzie xjest znakiem specjalnym) pasuje do xsamego. Jeśli \2pasuje \2\, \2\xpasuje do uciekającego. \2w dwóch meczach grupy 1 może być różny w wyrażeniu regularnym. Za pierwszym razem \2powinien pasować do pustego ciągu, a za drugim razem \2\.
  • \Q\2\)){2}.{11}$\E\/\z(wiersz 1) dopasowuje 15 znaków od końca. I .{11}$(wiersz 7) dopasowuje 11 znaków od końca (lub przed końcowym znakiem nowej linii). Tak więc wzór tuż przed drugim wzorem musi pasować do pierwszych 4 lub 3 znaków w pierwszym wzorze, więc \2\.\2\|\2\)\2\)musi pasować ...\2\)lub ...\2\. Końcowy znak nowej linii nie może być, ponieważ ostatnim znakiem powinien być ). I dopasowany tekst nie zawiera drugiego )przed prawym, więc wszystkie inne znaki muszą znajdować się w \2. \2jest zdefiniowany jako (.2.|), więc może być tylko \2\.
  • Pierwszy wiersz sprawia, że ​​całe wyrażenie pasuje dokładnie 188 znaków, ponieważ wszystko ma ustaloną długość. Dwa razy w grupie 1 dopasowano 45 * 2 znaków plus 29 razy \2. A rzeczy po grupie 1 pasują do 11 znaków. Zatem łączna długość dwóch razy \2musi wynosić dokładnie 3 znaki. Wiedząc \2po raz drugi, że mają 3 znaki, po raz pierwszy muszą być puste.
  • Wszystko oprócz poprzedniej perspektywy i \2są literałami w grupie 1. Z dwoma \2znanymi czasami i kilkoma ostatnimi znakami znanymi z pierwszego wiersza, regex dopasowuje dokładnie jeden ciąg.
  • Martin Büttner wpadł na pomysł, aby użyć lookahead do przechwytywania grupy 2 i nakładania się na nią części quine. Usunęło to znaki, które nie uciekły w normalny sposób między dwoma czasami z grupy 1, i pomogło uniknąć wzorca pasującego do nich w mojej oryginalnej wersji i znacznie uprościło regex.

Regex bez rekurencji lub odwołań zwrotnych, 85 bajtów

Ktoś może argumentować, że wyrażenia z rekurencjami lub odwołaniami wstecznymi nie są prawdziwymi wyrażeniami „regularnymi”. Ale wyrażenia tylko z wyprzedzeniem mogą nadal pasować tylko do języków regularnych, chociaż mogą być znacznie dłuższe, jeśli wyrażane są przez tradycyjne wyrażenia regularne.

/(?=.*(\QE\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\E\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\z/

Wypróbuj tutaj.

610 bajtów bez \Q...\E(do gry w golfa):

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}(.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\(.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Wypróbuj tutaj.

Pomysł jest podobny.

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)
((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)
(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}
  (.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}
    (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\
    (.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}
  (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Podstawowe wyrażenie regularne

Jeśli lookahead nie jest dozwolony, najlepsze, co mogę teraz zrobić, to:

/\\(\\\(\\\\){2}/

który pasuje

\\(\\\(\\

Jeśli {m,n}kwantyfikator nie jest dozwolony, jest to niemożliwe, ponieważ nic, co może pasować tylko do jednego łańcucha, nie może pasować do łańcucha dłuższego niż on sam. Oczywiście nadal można wymyślić coś, \qco tylko pasuje /\q/, i nadal wypowiadać wyrażenia za pomocą tego wyrażenia regularnego. Ale najwyraźniej nic takiego nie jest wspierane przez główne implementacje.

jimmy23013
źródło
5
Imponujący. Spędziłem trochę czasu, próbując dopasować to do czegoś innego, ale bez powodzenia.
primo
76
jak (do diabła) człowiek może wytworzyć coś takiego?
xem
61
To zasługuje na najwyższą głosowaną odpowiedź na tej stronie.
Cruncher
44
To najbardziej absurdalna, niesamowita rzecz, jaką kiedykolwiek widziałem.
Alex A.
22
Ktoś opublikował ten post na Twitterze, więc otrzymałem 49 pozytywnych opinii w ciągu jednego dnia
jimmy23013,