Regex que solo coincide

339

Hay algunos desafíos bastante geniales relacionados con la expresión regular ( expresiones regulares de coincidencia , expresiones regulares que validan expresiones regulares )

Esto puede ser imposible, pero ¿hay una expresión regular que SOLO coincida?

NOTA: se deben incluir delimitadores:

por ejemplo /thing/debe coincidir /thing/y no thing. La única coincidencia posible para su expresión debe ser la expresión misma. Muchos lenguajes permiten la implementación de una cadena en lugar de una expresión regular. Por ejemplo en Go

package main

import "fmt"
import "regexp"

func main() {

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

pero en aras del desafío, deje que la expresión se delimite (símbolo inicial, expresión, símbolo final ej: /fancypantpattern/o @[^2048]@), si desea argumentar citas como su delimitador, que así sea. Creo que dada la aparente dificultad de este problema, no habrá mucha diferencia.

Para ayudarte a lo largo:

Hack rápido que armé para rubular.com (una página web para la edición de 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;

Aunque técnicamente se trata de un "código de golf", me impresionará mucho si alguien puede encontrar una respuesta / demostrar que es imposible.

El enlace ya está arreglado. Perdon a todos

Respuesta ganadora hasta el momento: jimmy23013 con 40 caracteres

Dylan Madisetti
fuente
3
Obviamente, cualquier expresión regular que solo incluya literales funcionará: //, / a /, / xyz /, etc. Podría ser bueno requerir que la expresión regular tenga que incluir una operación no literal.
breadbox
99
los literales no funcionarán porque es necesario que coincida con las barras diagonales inversas, por ejemplo / aaa / coincidirá aaapero no / aaa /
Dylan Madisetti
2
@DylanMadisetti ¿Tenemos que usar //delimitadores, o podemos elegir otros delimitadores (PCRE admite casi cualquier carácter, y en particular puede usar paréntesis / llaves / corchetes coincidentes como delimitadores).
Martin Ender
3
Creo que este es un problema matemático / computacional bastante bueno y la prueba podría no ser fácil ... Muchos teoremas importantes comenzaron como una simple pregunta para jugar, por lo que tal vez en 5 años habrá un artículo de Wikipedia "Problema de Madisetti";)
Paweł Tokarz
3
Sí exactamente. En algunos idiomas (piense en grep en bash) el delimitador es esencialmente una cadena vacía. Asumir que regexp requiere delimitadores ya está mal en primer lugar. De hecho, dado que grep es una de las primeras implementaciones de regexp, la definición canónica de regexp no tiene delimitadores. La manifestación más errónea de esta suposición es PHP, que requiere dos delimitadores: "/y/"
slebetman

Respuestas:

590

Sabor PCRE, 261 289 210 184 127 109 71 53 51 44 40 bytes

¡Sí, es posible!

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

Pruébalo aquí (Pero /se muestra que es el delimitador en Regex101.)

Abstenerse de realizar ediciones innecesarias (actualizaciones) en la página Regex101. Si su edición en realidad no implica mejorar, probar o probar esta expresión regular, puede bifurcarla o crear otras nuevas desde su página de inicio .

La versión funciona más correctamente en Regex101 (44 bytes):

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

Pruébalo aquí

Esto es mucho más simple que la versión original y funciona más como una quine tradicional. Intenta definir una cadena sin usarla y usarla en un lugar diferente. Por lo tanto, se puede colocar muy cerca de un extremo de la expresión regular, para reducir la cantidad de caracteres que necesitan más caracteres para definir el patrón coincidente y se repiten más veces.

Explicaciones:

  • \Q^\/()(?R){2}\/\z|\1\Qcoincide con la cadena ^\/()(?R){2}\/\z|\1\Q. Esto utiliza una peculiaridad que \Q...\Eno tiene que cerrarse, y los delimitadores sin escape funcionan \Q. Esto hizo que algunas versiones anteriores funcionaran solo en Regex101 y no localmente. Pero afortunadamente la última versión funcionó, y aproveché algunos bytes más usando esto.
  • \1antes de que \Qcoincida con el grupo capturado 1. Debido a que el grupo 1 no existe en esta opción, solo puede coincidir en llamadas recursivas. En llamadas recursivas, coincide con cadenas vacías.
  • (?R){2}llama a la expresión regular completa de forma recursiva dos veces, que coincide ^\/()(?R){2}\/\z|\1\Qpara cada vez.
  • () no hace más que capturar una cadena vacía en el grupo 1, que habilita la otra opción en llamadas recursivas.
  • ^\/()(?R){2}\/\zcoincide (?R){2}con delimitadores añadidos, desde el principio hasta el final. El \/antes de que las llamadas recursivas también se aseguró de esta opción en sí no coincide en llamadas recursivas, porque no va a estar al principio de la cadena.

51 bytes con cerrado \Q...\E:

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

Pruébalo aquí

Versión original, 188 bytes

¡Gracias a Martin Büttner por jugar unos 100 bytes!

/^(?=.{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}$/

Pruébalo aquí

O 210 bytes sin \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

Pruébalo aquí

Versión ampliada:

/^(?=.{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

Las extensiones como (?=y \1han hecho que las llamadas expresiones "regulares" ya no sean regulares, lo que también hace posible las quines. La referencia inversa no es regular, pero la búsqueda anticipada sí.

Explicación:

  • Yo uso \2\en lugar de \escapar de caracteres especiales. Si \2coincide con la cadena vacía, \2\x(donde xes un carácter especial) coincide con la xpropia. Si \2coincide \2\, \2\xcoincide con el que se escapó. \2en las dos coincidencias del grupo 1 puede ser diferente en expresiones regulares. En la primera vez \2debe coincidir con la cadena vacía, y la segunda vez \2\.
  • \Q\2\)){2}.{11}$\E\/\z(línea 1) coincide con 15 caracteres del final. Y .{11}$(línea 7) coincide con 11 caracteres del final (o antes de una nueva línea final). Por lo tanto, el patrón justo antes del segundo patrón debe coincidir con los primeros 4 o 3 caracteres del primer patrón, por lo que \2\.\2\|\2\)\2\)debe coincidir con ...\2\)o ...\2\. No puede haber una nueva línea final porque el último carácter debería ser ). Y el texto coincidente no contiene otro )antes del más a la derecha, por lo que todos los demás caracteres deben estar en el \2. \2se define como (.2.|), por lo que solo puede ser \2\.
  • La primera línea hace que la expresión completa coincida exactamente con 188 caracteres, ya que todo tiene una longitud fija. Las dos veces del grupo 1 coinciden con 45 * 2 caracteres más 29 veces \2. Y las cosas después del grupo 1 coinciden con 11 caracteres. Entonces, la longitud total de las dos veces \2debe ser exactamente 3 caracteres. Sabiendo \2por segunda vez que tiene 3 caracteres, debe estar vacío por primera vez.
  • Todo excepto la búsqueda anticipada y \2son literales en el grupo 1. Con las dos veces \2conocidas y los últimos caracteres conocidos desde la primera línea, esta expresión regular coincide exactamente con una cadena.
  • A Martin Büttner se le ocurre la idea de utilizar la búsqueda anticipada para capturar el grupo 2 y superponerlo con la parte quine. Esto eliminó los caracteres que no escaparon de la forma normal entre las dos veces del grupo 1, y ayudó a evitar que el patrón coincidiera con ellos en mi versión original, y simplificó mucho la expresión regular.

Regex sin recursiones o referencias posteriores, 85 bytes

Alguien puede argumentar que las expresiones con recursiones o referencias inversas no son expresiones "regulares" reales. Pero las expresiones con solo anticipación solo pueden coincidir con los lenguajes regulares, aunque pueden ser mucho más largos si se expresan mediante expresiones regulares tradicionales.

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

Pruébalo aquí

610 bytes sin \Q...\E(para jugar golf):

/^(?=.{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

Pruébalo aquí

La idea es similar.

/^(?=.{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

La expresión regular básica

Si no se permite la búsqueda anticipada, lo mejor que puedo hacer ahora es:

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

que coincide

\\(\\\(\\

Si {m,n}no se permite el cuantificador, es imposible porque nada que solo pueda coincidir con una cadena, puede coincidir con una cadena más larga que sí misma. Por supuesto, uno todavía puede inventar algo como lo \qque solo coincide /\q/, y aún decir expresiones con ese regular. Pero aparentemente nada de esto es compatible con las principales implementaciones.

jimmy23013
fuente
55
Impresionante. Pasé un tiempo tratando de que coincida con otra cosa, sin éxito.
primo
76
¿Cómo (demonios) podría un humano producir tal cosa?
xem
61
Esta merece ser la respuesta más votada en este sitio.
Cruncher
44
Esta es la cosa más absurda e increíble que he visto.
Alex A.
22
Alguien tuiteó esta publicación, así que recibí 49 votos a favor en un día ...
jimmy23013