Najkrótsze niedopasowane wyrażenie regularne

59

Twoim zadaniem jest napisanie najkrótszego prawidłowego wyrażenia regularnego, którego żaden ciąg nie może dopasować, włączając pusty ciąg.

Zgłoszenia muszą mieć następujący formularz („notacja dosłowna”):

/pattern/optional-flags

Najkrótsze wyrażenie regularne wygrywa. Rozmiar wyrażenia regularnego jest liczony w znakach. (w tym ukośniki i flagi)

Wyjaśnij, jak działa wyrażenie regularne (jeśli nie jest trywialne)

Dzięki i baw się dobrze!

Xem
źródło
To zainspirowało mnie do pytania. Poczekam jednak kilka dni. Nie chcę, aby 2 pytania regularne były jednocześnie aktywne
Cruncher
13
„Prawidłowe” według której realizacji? Właśnie znalazłem zabawny, z którym Perl jest w porządku (i jest to zgodne z jedyną gramatyką RE, jaką mogę znaleźć , ale ten grep i moduł ponownie Pythona odmawiają.
Josh Caswell
1
Tak, który dialekt (y) wyrażenia regularnego? Istnieje wiele różnych.
hippietrail
1
A co z nazwiskami prezydentów? xkcd.com/1313
Carl Witthoft
@CarlWitthoft Aby wziąć udział w tym konkursie, musisz być programem: codegolf.stackexchange.com/q/17718/2180
stoisko

Odpowiedzi:

53

6 znaków

Na podstawie odpowiedzi primo i Petera Taylora oraz podpowiedzi od man perlre:

/(?!)/

To wyrażenie regularne zgodne z perlem dopasowuje pusty ciąg, po którym nie następuje kolejny pusty ciąg.

Nate Eldredge
źródło
+1 - To prawdopodobnie najkrótsza odpowiedź, która jest szeroko przenośna (wraz z /x\by/, ale jeśli kiedykolwiek musiałbym użyć takiego wyrażenia regularnego - z jakiegokolwiek powodu - to odpowiedź jest również najczystsza)
Martin Ender
@ m.buettner: Dzięki. /(*FAIL)/Prawdopodobnie primo's jest wyraźniejsze. (I faktycznie man perlreto zdradził, wspominając, że moja faktycznie rozszerza się do jego wewnętrznie.)
Nate Eldredge
/(*FAIL)/nie jest jednak tak przenośny. Nawet w Perlu myślę, że jest to bardziej niejasna funkcja niż negatywne spojrzenie w przyszłość.
Martin Ender
3
Otrzymujesz dziś spojrzenia na prawie wszystkie popularne (inspirowane Perlem) smaki, podczas gdy nigdy nie widziałem tych czasowników kontrolnych nigdzie indziej niż w Perlu.
Martin Ender
1
W rzeczywistości dokumentacja Perla (i -Mre=debug) mówi, że (?!)jest zoptymalizowany (*FAIL)przez optymalizator wyrażenia regularnego Perla ( OPFAILzgodnie z -Mre=debug). Poza tym nie sądzę, że widziałem (*FAIL)poza Perlem 5 (i Perlem 6, jak się nazywa <!>).
Konrad Borowski
39

8 znaków

/(?=a)b/

Potrzebujemy łańcucha zawierającego znak, który jest jednocześnie ai boczywiście niemożliwy.

Peter Taylor
źródło
19
/(?!x)x/wygląda jeszcze bardziej niemożliwie ;-)
Howard
@PeterTaylor gdzie?
o0 ”.
@Lohoris, gdzie co?
Peter Taylor
@PeterTaylor, gdzie wprowadził te absurdalne zasady, o których mówisz, nie mogłem ich znaleźć.
o0 ”.
7
chłopaki, przepraszam za liczenie, które wybrałem, pomyślałem, że łatwiejsze będzie wstawianie ukośników z powodu opcjonalnych flag, które mogą po nich nastąpić.
xem
31

5 znaków

W przeciwieństwie do wszystkich, którzy nadużywają $i ^... to faktycznie działa w Perlu:

/V\A/

\A dopasowuje początek łańcucha.

boothby
źródło
To też działa ^.
Tomas
29

6 znaków

/x\by/

Na podstawie odpowiedzi Svena Hohensteina .

Pan Neutron
źródło
28

8 znaków

/\w\b\w/

Granica słowa ( \b) otoczona znakami „słowa” ( \w- jeden z [_a-zA-Z0-9]). Nie można go dopasować, ponieważ jeden ze znaków poprzedzających granicę słowa lub następujących po niej musi być znakiem innym niż „słowo”.

Nawiasem mówiąc: jest to podobne do niedopasowanego wyrażenia

/\W\b\W/

gdzie \Woznacza znak inny niż „słowo”.

Sven Hohenstein
źródło
Jest to 8 znaków zgodnie z regulaminem zawodów, ponieważ /liczą się kreski opakowaniowe . Zobacz na przykład wpis PO . Ale to świetny wpis!
Josh Caswell
Może to być również zwycięzca (lub związany z wpisem Petera Taylora ), biorąc pod uwagę problemy związane z implementacją niektórych krótszych wpisów!
Josh Caswell
Bardzo elegancko! Myślałem, że musi być coś takiego!
Tomas
22

4 znaki

/$a/

wyszukuje „a” po końcu ciągu.

lub

/a^/

wyszukuje przed początkiem ciągu.

Xem
źródło
20
Po co publikować pytanie, jeśli wiesz, że istnieje rozwiązanie dwuznakowe?
Peter Taylor
3
@Howard: Pasuje do pustego ciągu: jsfiddle.net/RjLxJ
ProgramFOX
10
Dlaczego zawsze znajduję te problemy po zapewnieniu bezkonkurencyjnego rozwiązania :(
Cruncher
43
-1: Kładzenie ^i $w „nielegalnych” pozycjach tylko powoduje ich być traktowane jako zwykłe znaki. Twój pierwszy przykład pasuje do literału $aw sedi prawdopodobnie innych programów.
Ben Jackson
2
@Ben Jackson, to nie jest prawda w przypadku POSIX ERE. Spróbuj echo 'a^b' | grep 'a^b'kontra echo 'a^b' | grep -E 'a^b'. Sprawdź 9.4.9 Zakotwiczanie wyrażeń ERE
laindir
21

5 znaków

/$.^/

/$^/ dopasuje pusty ciąg, a wymaganie znaku pomiędzy nimi nie będzie.

Brian Glaz
źródło
6
To niestety pasuje "$a^"(lub cokolwiek w miejsce 'a') w Perlu ( i być może sed ). Jednak wciąż miło!
Josh Caswell
@JoshCaswell: Myślę, że Perl może interpretować $.jako bieżącą zmienną numeru wiersza. Który może być pusty, w którym to przypadku będzie /^/.
MvG
Znak „pomiędzy” oznacza po prostu łańcuch jednoznakowy.
jwg
3
@jwg zauważ zamienione ^i$
mniip
Próbowałem wzoru '$^'z grep, ale niestety pasował do łańcucha '$^'. Smartass grep.
joeytwiddle
19

9 znaków

Nie jestem pewien, ale /[^\S\s]/powinienem być nieporównywalny, ponieważ nie oznacza żadnej postaci, ale przynajmniej jedną z nich.

użytkownik14325
źródło
Nie potrzebujesz +.
Peter Taylor
10
/ [^ \ S \ s] / = 9 znaków
xem
19

6 znaków

Myślę, że ten regex, który stworzyłem, zadziała:

/\b\B/

Pasuje do granicy słowa ( \b), która nie jest granicą słowa ( \B). Czym jest impos - czy naprawdę muszę ci to wyjaśniać?

Facet z kapeluszem
źródło
czy to nie szuka granicy słowa, po której nie ma granicy słów?
grexter89
1
@ grexter89 Tak, ale nie mogą między nimi znajdować się żadne znaki. tj. Granica i bez granicy muszą zajmować tę samą przestrzeń.
Facet z kapeluszem
2
Ten mi się podoba. Dobry chwyt
primo
18

4 znaki

(Tylko smak ECMAScript)

/[]/

W innych odmianach nie jest to poprawna klasa znaków ( ]byłaby uznana za znak w klasie, więc wyrażenie nie jest poprawne, ponieważ klasa nigdy nie jest zamknięta), ale standard ECMAScript akceptuje puste klasy znaków. Ponieważ jest to klasa, musi ona pasować do znaku (więc puste łańcuchy nie pasują), ale ponieważ nie zawiera pojedynczego znaku, żaden rzeczywisty znak również nie będzie pasował.

Martin Ender
źródło
Czy to nie pasuje do pustego ciągu, nawet jeśli mówisz, że musi pasować do znaku? A może uważasz, że to niezgodne z prawem: /[]{0}/. (Ps. Chociaż moja własna odpowiedź częściowo wygląda jak twoja, faktycznie czytam twoją po napisaniu mojej.)
nl-x
@ nl-x wkleić do konsoli przeglądarki: /[]/.test(""). zwraca false. klasa znaków nigdy nie może dopasować pustego łańcucha, nawet jeśli nie zawiera znaków (wyobrażam sobie, że są one zaimplementowane tak, jakby „JEŚLI następny znak w łańcuchu jest jednym z wymienionych, dopasuj; ELSE nie powiedzie się”). /[]{0}/jest legalny (w ECMAScript) i pasuje do pustego ciągu ... jednak nie jestem pewien, w jaki sposób ma to związek z moją odpowiedzią.
Martin Ender
Nie
działa
@Nakilon oczywiście, że tak. Ruby nie implementuje smaku ECMAScript.
Martin Ender
15

6 znaków

/b++b/

Kwantyfikator dzierżawczy szuka jak największej liczby b, a następnie 1 więcej. 6 znaków, ale punkty za symetrię?

VBCPP
źródło
Huh ... Właśnie nauczyłem się nowej funkcji. Najwyraźniej moje umiejętności wyrażania regularnego są bardzo nieaktualne. Dzięki i +1.
Ilmari Karonen
8

6 znaków

/(\1)/

Nie jestem zwycięzcą, ale myślałem, że to dobra zabawa. grep i Python zarówno barf na tym, ale Perl wydaje się być w porządku.

Wydaje się być bardzo zależny od implementacji (co nie jest zaskakujące, biorąc pod uwagę jego dziwność). Bob informuje poniżej, że pasuje do wszystkiego w silniku wyrażeń regularnych JavaScript.

Josh Caswell
źródło
Wydaje się, że silnik wyrażeń regularnych .NET to akceptuje.
Bob
I zawsze pasuje (pusty ciąg) bez względu na dane wejściowe w JS
Bob
8

Może trochę oszukiwania, ale…

\0

… Nie da się dopasować do wyrażenia regularnego POSIX praktycznie we wszystkich, jeśli nie we wszystkich implementacjach. PODSTAWOWE RE i ROZSZERZONE RE, nawet.

POSIX RE nie potrzebuje tych irytujących cięć i flag, które ma PCRE.

mirabilos
źródło
+1 dobrze !! Niestety podeszwa 0nie działa w języku PERL. "0"=~0jest prawdą ...
Tomas
wyłączny \0ITYM? Tak, większość implementacji perlre (1) i PCRE nie używa łańcuchów C, ale bufory o ograniczonych rozmiarach, w których ta sztuczka nie będzie działać, ale większość implementacji POSIX RE działa na łańcuchach C.
mirabilos
5

5 znaków

/^.^/

Dopasowuje ciąg, który zaczyna się dowolnym znakiem przed rozpoczęciem łańcucha.

P̲̳x͓L̳
źródło
6
".^"
Pasuje
@boothby: w jakim języku pasuje? w Pythonie nie. re.findall(r'^.^', '.^', re.DEBUG)
P̲̳x͓L̳
8
+1 za korzystanie z operatora manga (patrz stackoverflow.com/questions/3618340/… )
prototyp
@boothby ^i .są metaznakami, które nie są dosłowne, trzeba ich uciec
P̲̳x͓L̳
1
W Perlu jest zepsuty. To pytanie naprawdę powinno było ustalić podstawowe zasady dotyczące języka.
stoisko
5

4 znaki:

/.^/

Działa z GNU grep 2.5.1 i egrep.

RSFalcon7
źródło
/.^/= 4 znaki.
Aleksiej Popkow
Dlaczego potrzebne //? nie są one wymagane wszędzie ;-)
RSFalcon7
/Liczą się zawijające się ukośniki , patrz oryginalne pytanie („łącznie z ukośnikami i flagami”) oraz wpis PO .
Aleksiej Popkow
dobrze! Tęsknię za przeczytaniem :(
RSFalcon7
Nie, z tego samego powodu, co poniżej: W rzeczywistości „^” jest wyjątkowy tylko wtedy, gdy na początku wzoru. Wszelkie „^” po czymkolwiek innym nie muszą być uciekane, więc ta odpowiedź jest błędna.
mirabilos
4

Perl 6 (5 znaków)

/<!>/

Trochę nadużywanie reguł (ponieważ wyrażenia regularne Perla 6 są różne i niezgodne ze standardowymi wyrażeniami regularnymi z założenia), ale mnie to nie obchodzi. <!>reguła informuje Perla 6, że wyrażenie regularne nie pasuje.

Konrad Borowski
źródło
4

6 bajtów

/(*F)/

Skrót (*FAIL), obsługiwany przez silniki regex kompatybilne z perl. Dzięki @HamZa za zwrócenie na to uwagi.

9 bajtów

/(*FAIL)/

Powinien działać z każdym silnikiem wyrażenia regularnego, który w ogóle obsługuje czasowniki. Nie jestem przekonany, że tak naprawdę trzeba grać w golfa.

primo
źródło
1
Jak to działa?
stoisko
@boothby (*FAIL)to czasownik, który zawsze zawodzi.
primo
@primo możesz po prostu użyć /(*F)/:)
HamZa
4

4 znaki

/$./

Potrzebuje dowolnego znaku po zakończeniu łańcucha

c0de Freak
źródło
Podobnie jak pozostałe dwa, $jest wyjątkowy tylko na końcu wzoru.
mirabilos
3

4 znaki z ukośnikami 2 bez

W silniku wyrażeń regularnych języka TXR pusta klasa []znaków nie pasuje do żadnego znaku, a zatem nie ma łańcucha. Zachowuje się w ten sposób, ponieważ klasa znaków wymaga dopasowania znaku, a gdy jest pusta, oznacza, że ​​żadna postać nie może go spełnić.

Innym sposobem jest odwrócenie „zbiór wszystkich ciągów w tym pustym” regex /.*/przy użyciu operatora dopełniacza: /~.*/. Uzupełnienie tego zestawu nie zawiera żadnych ciągów, a zatem nie może dopasować niczego.

Wszystko to jest udokumentowane na stronie man:

   nomatch
          The  nomatch  regular  expression  represents  the empty set: it
          matches no strings at all, not even the empty string.  There  is
          no  dedicated  syntax  to  directly express nomatch in the regex
          language.  However, the empty character class []  is  equivalent
          to nomatch, and may be considered to be a notation for it. Other
          representations of nomatch are possible: for instance, the regex
          ~.* which is the complement of the regex that denotes the set of
          all possible strings, and thus denotes the empty set. A  nomatch
          has  uses;  for instance, it can be used to temporarily "comment
          out" regular expressions. The regex ([]abc|xyz) is equivalent to
          (xyz), since the []abc branch cannot match anything. Using [] to
          "block" a subexpression allows you to leave it  in  place,  then
          enable it later by removing the "block".

Ukośniki nie są częścią składni wyrażenia regularnego per se; są tylko interpunkcją, która ogranicza wyrażenia regularne w notacji wyrażenia S. Świadek:

# match line of input with x variable, and then parse that as a regex
#
$ txr -c '@x
@(do (print (regex-parse x)) (put-char #\newline))' -
ab.*c                               <- input from tty: no slashes.
(compound #\a #\b (0+ wild) #\c)    <- output: AST of regex
Kaz
źródło
dziękuję za odpowiedź i jeszcze raz przepraszam za liczenie ukośników. Pomyślałem, że łatwiej byłoby je uwzględnić, gdyby ludzie używali flag.
xem
1

6 znaków

(lub 4, w zależności od tego, jak na to spojrzysz)

/{,0}/
Tercy
źródło
Nie
działa
W których implementacjach wyrażeń regularnych nie powoduje to błędu?
Peter Taylor
Testowałem to tylko przy użyciu preg_match PHP.
Tercy
1

Jest to wyrażenie regularne o 5 znakach.

/[]+/

Pasuje do pustej grupy 1 lub więcej razy.

EDYTOWAĆ:

Usunąłem moją odpowiedź dla innych smaków:

/.{-1}/

Wszystko, co nie jest liczbą wewnątrz {}, pasuje do tekstu.

Ten będzie pasował do „. {- 1}”

Ismael Miguel
źródło
Zauważ, że działa to tylko w smaku ECMAScript. W większości (wszystkich?) Nie jest to prawidłowe wyrażenie.
Martin Ender
Czy to nie jest nieprawidłowe?
Wasi
@Wasi nie jest w wersjach zgodnych ze skryptem ECMAS
Martin Ender
0

5 znaków

Mam nadzieję, że to nie brzmi głupio: /[]+/

nl-x
źródło
Nie. Niepoprawne wyrażenie regularne.
Facet z
@RyanCarlson To jest ważne i legalne ... Przynajmniej w Ecmascript.
nl-x
-1
/$^/

Rzecz, która kończy się, zanim się zacznie ...

Szymon
źródło
7
Odpowiada pustemu ciągowi (w każdym razie w niektórych implementacjach RE).
Josh Caswell
1
Twoja implementacja jest zepsuta :)
sim
2
Lepiej daj znać Guido .
Josh Caswell
7
Co ważniejsze, jak Ben Jackson zauważył , Perl, gdzie nie pasuje "", to nie pasuje ciąg zawierający te dwa znaki dosłowne: "$^".
Josh Caswell
+1 Chciałem tylko opublikować to samo! @Josh, działa w PERL i nie pasuje do pustego łańcucha! Komentarz Bena jest zepsuty, odpowiedziałem na to.
Tomas