Para el propósito de este desafío, decimos que un patrón regex coincide con una cadena si todo cadena coincide con el patrón, no solo una subcadena.

Dados dos patrones de expresiones regulares  A  y  B , decimos que  A  es más especializado que  B   si cada cadena que  A  coincide también coincide con  B   pero no al revés. Decimos que  A  es equivalente a  B  si ambos patrones coinciden exactamente con el mismo conjunto de cadenas. Si ninguno de los patrones es más especializado que el otro ni son equivalentes, decimos que  A  y  B  son incomparables .

Por ejemplo, el patrón Hello, .*!es más especializado que .*, .*!; los patrones (Hello|Goodbye), World!y Hello, World!|Goodbye, World!son equivalentes; y los patrones Hello, .*!y.*, World! son incomparables.

La relación "más especializado que" define un orden parcial estricto en el conjunto de patrones de expresiones regulares. En particular, para todos los patrones  A  y  B , se cumple exactamente uno de los siguientes:

• A  es más especializado que  B  ( A < B ).
• B  es más especializado que  A  ( A > B ).
• A  y  B  son equivalentes ( A = B ).
• A  y  B  son incomparables ( A ∥ B ).

Cuando  A  y  B  son incomparables, podemos distinguir aún más entre dos casos:

• A  y  B  son disjuntos ( A ∥ B ), lo que significa que ninguna cadena coincide con ambos.
• A  y  B  se cruzan ( A ≬ B ), lo que significa que algunas cadenas coinciden con ambas.

Reto

Escriba un programa o una función que tome un par de patrones de expresiones regulares y los compare usando el orden anterior. Es decir, si los dos patrones son  A  y  B , el programa debe determinar si  A < B ,  A > B ,
A = B  o  A ∥ B .

× 92% de bonificación  Se otorga una bonificación adicional si, cuando los patrones son incomparables, el programa determina si se cruzan o no.

Entrada y salida

El programa debe aceptar dos patrones de expresiones regulares, como cadenas, en el sabor definido a continuación. Puede leer la entrada a través de STDIN , la línea de comando , como argumentos de función o un método equivalente . Puede suponer que los patrones son válidos.

El programa debe producir una de exactamente cuatro salidas distintas (o cinco salidas distintas si va a obtener la bonificación anterior), dependiendo del resultado de la comparación (las salidas exactas dependen de usted). Puede escribir la salida en STDOUT , devuélvalo como resultado de la función o use un método equivalente .

Sabor Regex

Puede admitir las funciones de expresión regular que desee, pero debe admitir las siguientes:

• Alternancia con |.
• Cuantificación con *.
• Agrupando con (y ).
• Emparejar cualquier personaje (posiblemente excluyendo nuevas líneas) con ..
• (Opcional: × 80% de bonificación)  Relacionar clases de caracteres simples y negadas con […]y [^…], respectivamente. No tiene que admitir ninguna clase de caracteres predefinida (por ejemplo [:digit:]), pero debe admitir rangos de caracteres.
• Personaje escapando con \. Al menos debería ser posible eliminar caracteres especiales (es decir |*().[^-]\) y preferiblemente también caracteres especiales comunes en otros sabores (por ejemplo {}), pero el comportamiento al escapar de caracteres no especiales no está especificado. En particular, no tiene que admitir secuencias de escape especiales, como \nuna nueva línea y similares. Una posible implementación es simplemente tomar el carácter que sigue al \literal.

Puede suponer la existencia de un carácter de entrada que no puede ser igualado por ningún literal (es decir, solo puede ser igualado por .clases de caracteres negadas).

Reglas Adicionales

• Puede usar las bibliotecas de expresiones regulares o la funcionalidad de expresiones regulares incorporadas solo con el propósito de la coincidencia y reemplazo de cadenas.
• Puede ignorar cualquier problema relacionado con la configuración regional, como las reglas de intercalación.
• Para decir lo obvio: su programa debe finalizar. Debe ejecutarse en un tiempo razonable dados los patrones típicos (definitivamente no más de una hora, preferiblemente mucho menos).

Tanteo

Este es el código de golf. Su puntaje es el producto del tamaño del código , en bytes, y cualquiera de los bonos . El puntaje más bajo gana.

Casos de prueba

El formato de los casos de prueba es el siguiente:

<Test ID>
<Pattern A>
<Ordering>
<Pattern B>

<Test ID>
<Pattern A>
<Ordering>
<Pattern B>

...

Donde <Test ID>es un identificador para el caso de prueba, <Pattern A>y <Pattern B>son los patrones de expresiones regulares y <Ordering>el orden entre ellos, y es uno de:

• <: <Pattern A>es más especializado que <Pattern B>.
• >: <Pattern B>es más especializado que <Pattern A>.
• =: Los patrones son equivalentes.
• |: Los patrones son incomparables y disjuntos.
• X: Los patrones son incomparables e intersectantes.

El valor especial <empty pattern>representa el patrón vacío.

A. Patrones básicos

A1
Hello
=
Hello

A2
Hello
|
World

A3
Hell(|o)
=
Hell|Hello

A4
x
<
.

A5
.
>
x

A6
\.
<
.

A7
x|y
=
y|x

A8
x|y
X
y|z

A9
x|y
|
a|b

A10
x|y|z
>
x|z

A11
x.
X
.x

A12
.*
>
<empty pattern>

A13
()*
=
<empty pattern>

A14
x*
>
xxxx

A15
x*
>
x|xx|xxxx*

A16
x*
=
|x|xx|xxxx*

A17
x*
<
.*

A19
(.|..)*
=
.*

A20
(...)*
X
(..)*

A21
...*
X
(..)*

A22
...*
<
..*

A23
(...)*
|
Four

A24
a*
X
a.*

A25
a*
|
b.*

A26
x*
=
(x|)*

A27
(((.*)*)*)*
=
.*

B. Patrones complejos

B1
aaa*
=
aa*a

B2
aa*a
=
a*aa

B3
a*
X
aaax||a|aa|aaa

B4
aaaaaaaaaaaaaa*
X
(aa)*|(aaa)*

B5
a*b*
<
(a|b)*

B6
((a|b)(a|b))*
>
(ab|ba)*

B7
((a|b)(a|b))*
=
(aa|ab|ba|bb)*

B8
.*.*
=
.*

B9
(x*y*z*)*
=
(x|y|z)*

B10
(...|.....)*
>
.........*

B11
(...|.....)*
=
|...|.....|......|.........*

B12
(...|......)*
<
|...|.......*

B13
(...|....|.....)*
=
|....*

B14
(...|x...............|x..x)*
>
(...|x..............|x..x)*

B15
(...|x...............|x..x)*
<
(..|...|x..............|x..x)*

B16
(____)*_x__(____)*
|
(____)*x___(____)*

B17
(____)*_x__(____)*
X
(_____)*x_____(_____)*

B18
(____)*_x__(____)*
|
(______)*x______(______)*

B19
(____)*_x__(____)*
<
_*x__*

C. Patrones básicos con clases de caracteres.

C1
[x]
=
x

C2
[xy]
|
xy

C3
[abc]
=
a|b|c

C4
[abc]
>
[ab]

C5
[abc]
<
[abcd]

C6
[ab]
X
[bc]

C7
[ab]
|
[cd]

C8
[abc]*
>
(a|b)*

C9
[^xyz]
>
a

C10
[^xyz]
|
x

C11
[^xyz]
|
[xyz]

C12
[^xyz]
X
[wxyz]

C13
[^xyz]
X
[^abc]

C14
[0-9]
=
[0123456789]

C15
[a-z]
>
[b-y]

C16
[a-z]
=
a|[b-y]|z

C17
[^0-9]*
>
Hello, World!

C18
[^0-9]*
|
123

C19
[^abc]
<
.

C20
[^abc]*
X
.

C21
[^a]|a
=
.

C22
[^abcd]|[a-c]|d
=
.

C23
[^a]*
X
b[^c]*

C24
[^a]*
|
a[^c]*

D. Patrones complejos con clases de caracteres.

D1
http://[^/][^/]*/.*
>
http://(www\.|)google\.com/.*

D2
http://[A-Za-z][A-Za-z]*\.wikipedia\.org/
X
(http://|)en\.wikipedia\.org/(|wiki(|/.*))

D3
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
X
[email protected]

D4
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
>
email@address\.com

D5
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
>
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@gmail\.com

D6
JohnDoe@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
<
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])

D7
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@gmail\.com
X
JohnDoe@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])

D8
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
>
One, two and three\.

D9
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
|
one, two and three\.

D10
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
|
One, two\.

D11
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
<
(.*(,|))*

D12
[A-Z][^,]*(|(, [a-z][^,]*)* & [a-z][^,]*)\.
<
[^, a-z][^,]*(|(, [^, ][^,]*)* (and|et|[&+]) [^, ][^,]*)\.

Programa de prueba

El siguiente fragmento se puede utilizar para comparar patrones de expresiones regulares:

<style>#main {display: none;}#main[loaded] {display: inline;}.pattern_container {position: relative;}.pattern_underlay, .pattern {font: 12pt courier, monospace;overflow: hidden;white-space: pre;padding: 7px;box-sizing: border-box;}.pattern_underlay {background-color: #dddddd;color: #707070;border-radius: 4px;box-shadow: 0.5px 0.5px 2.5px #aaaaaa;}.pattern_underlay[error] {background-color: #ffccbb;}.pattern {position: absolute;left: 0px;top: 0px;background: none;border: none;width: 100%;height: 100%;resize: none;white-space: normal;}#ordering {min-width: 28pt;text-align: center;font-size: 16pt;}#status {padding: 5px;background-color: #fffdce;box-shadow: 1.5px 1.5px 3.5px #aaaaaa;font-size: 10pt;white-space: pre;display: none;}#status[error] {display: inline;background-color: #ffe8df;}#status[loading] {display: inline;}.inline_code {background-color: #dddddd;font: 12pt courier, monospace;padding: 2px;}.placeholder {visibility: hidden;}.error_text {background-color: #fffcb7};</style><span id="main"><table><tr><td><div class="pattern_container"><div class="pattern_underlay" id="pattern1_underlay"></div><textarea class="pattern" id="pattern1" oninput="compare()">Hello, .*!</textarea></div></td><td id="ordering"></td><td><div class="pattern_container"><div class="pattern_underlay" id="pattern2_underlay"></div><textarea class="pattern" id="pattern2" oninput="compare()">.*, .*!</textarea></div></td></tr></table><br></span><span id="status" loading>Loading...</span><script type='text/javascript'>var Module = {setStatus: function (status) {document.getElementById("status").innerHTML = status;if (status == "") {compare();document.getElementById("status").removeAttribute("loading");document.getElementById("main").setAttribute("loaded", 1);}}};function underlay_chars(str) {if (/^\n*$/.exec(str))return str.split("\n").map(function () { return '<span class="placeholder"> \n</span>'; });if (str.indexOf("\n") >= 0)str = str.replace(/\s*$/gm, function (m) { return m.replace(/[^\n]/g, "\0"); });return (str + "\n").split("").map(function (c) {if (c == "\0") return "·";else return '<span class="placeholder">' + c + '</span>';});}function underlay_str(str) {return underlay_chars(str).join("");}function str_to_array32(str) {a = [];for (c of str) {n = c.charCodeAt(0);a.push(n & 0xff, (n >> 8) & 0xff, (n >> 16) & 0xff, n >> 24);}a.push(0, 0, 0, 0);return a;}function compare() {try {for (e of ["pattern1_underlay", "pattern2_underlay", "status"])document.getElementById(e).removeAttribute("error");for (e of ["pattern1", "pattern2"])document.getElementById(e + "_underlay").innerHTML = underlay_str(document.getElementById(e).value);c = Module.ccall("regex_compare", "number", ["array", "array"], [str_to_array32(document.getElementById("pattern1").value),str_to_array32(document.getElementById("pattern2").value)]);if (c >= 0)document.getElementById("ordering").innerHTML = "∥≬<>="[c];else {i = Module.ccall("regex_error_index", "number", [], []);l = Module.ccall("regex_error_length", "number", [], []);e = document.getElementById("pattern" + -c + "_underlay");t = underlay_chars(document.getElementById("pattern" + -c).value);e.setAttribute("error", 1);e.innerHTML =t.slice(0, i).join("") +'<span class="error_text">' + t.slice(i, i + l).join("") + "</span>" +t.slice(i + l).join("");e.setAttribute("error", 1);throw "Pattern error: " + Module.ccall("regex_error", "string", [], []).replace(/`(.*?)'/g, '<span class="inline_code">$1</span>');}} catch (e) {document.getElementById("ordering").innerHTML = "??";document.getElementById("status").innerHTML = e;document.getElementById("status").setAttribute("error", 1);}}</script><script async type="text/javascript" src="https://gist.githack.com/anonymous/91f27d6746566c7b4e4c/raw/c563bf84a01c3a1c6e5f021369a3e730a2e74a1a/rpo.js"></script>

Python 2, 522 bytes * .92 = 480.24 537.28

Edición 2 : -60 bytes

Editar : explicación añadida.

Definida es la función fque toma las dos cadenas de patrones como argumentos y devuelve '<', '=', '>', '|', o 'X'. Se necesita menos de un minuto para procesar todos los casos de prueba.

El código consiste en lo siguiente, pero con \r, \n \ty los escapes hexadecimales (pero no \0) reemplazados con sus valores de bytes reales.

#encoding=Latin
exec"""x\xda]RMo\xdb0\x0c\xbd\xe7Wx\'K\x96\x92\xc5mOR\xb8\xdf1@%|\x98%X\x80a\x19\x96\x02\x03n\xf2\xdfG:i;\xec$\x92z|\x8f_\x1b\x84%m~\xca\xbe\x1c\x0e\xbd\x0fU\x10Agi\x0e\x87\xea\n\x1f\xf9n{=\xea\0\x93\x08\xd2\xaez\xd0\x99\xcc,m\x07g\xbb\x80s\x9b\x08\xee\x8cRo"\xf3\x8bHy!-\x95\xd7\xa9\x8aS\xb50O5\xc3&\xb68\x0b\xe7\xb1\x19t\x92\x8a\x1d\xaf]\xc2f\x94\x92\x111T\xf3\xf1j\xba\x1b\x081r\xa2\x97\xea\xa5\x11\x03\x9bI\xca\xe6\xed\xe7\xab\xbd\xde`\xb6\x8b"\xd1\xc5\xf7\xd7?^l\xa7\xaeKK\xd7i\x91\x92\x8b\xaaE\x16\x8e\x9c\x12#3\x86\xe0"\xc6\xc9\x15\xfd\x86\xae\\\xde\xcc^\xa7\x94;,\xea\x94t\x08\x84\xa6J\x82\xee%\xb1\xe8\xacW\xb9\xb3\x14f\xd9\x84\xeb\x89\xe1\x8b\xd5\xa3r\xeb\xbf\x81D\rS\xf5\x8b/\xd7e\xaao\xf0\xeb\xf2\xbbv\xdd\xf1\x15\x1f\x93\xe4Aq\xff\x19\xc6\x98\x8b\xa8E\xad\xb2\xaae-m\x843\xc5\xd7!\x8e\xbe\xca.\x1a4\x01\xe8E;@-\xe4\xad9\xd5\xa7\x10\xa7\x9eg\xcea\x10\x83\x0e\xd2\r\x973\xb2o\xb8\xd7\x06\xc2\x0f\xa8\xdf\xdfk\x1b\x15\xb4v\x84H\xc9\xad]\xc1\x83C;\x03m\xc3\x16p\x1f\xe3\x1d\xbf\xa4\xe2\xbe\x8d\x1eX)\x1e\t\x9dv\xf3\xa9\xcd\xe8xGU\x9e\x0b\t\x97\xd6\x0c\x8c\xf2\nxa\xa9\x19u\xaf\xf2iN3\r\xd1\xae\x0f\xe3\x13\x0c@h\xb5W\xb0\xaad3\xef\t\x91s]R=~\xc3^Lv\xc7\x16\x15\xf4\xfb\xa7\x88ze_~B\x06\x80\x99\x03\x86\x7f\x0bY\x06U\xd2.\xeaV\x95\x87$\xd1\xce\xff\x8b\xbf\x9a\x99\xe0\x03u\xa1 =o0<n\xd0\xef]s`b\xb7\x98\x89\xael\xd2\x85\xceO:>\x80j\xfa\xdeb\x95\x95k\x91N\xbe\xfc'5\xac\xe7\xe8\x15""".decode('zip')

La declaración anterior hace que se ejecute el siguiente código:

z=frozenset
def f(f,s):
 u={s};d,l,f=n(f);w,h,s=n(s);_=0;r=[[z(f[0]),z(s[0])]]
 for e,o in r:
  p=z(zip([e]*h,o)+zip(e,[o]*l))
  if p-u:_|=((l in e)+2*(h in o))*4/3;u|=p;r+=[[reduce(z.__or__,(oo[i+1]for i in ii if ff[i]in[t,4][t<4:]),z())for ii,oo,ff in(e,f,d),(o,s,w)]for t in z([d[i]for i in e]+[w[i]for i in o])]
 return'|=><X'[_-3]
def n(s):
 s=list('('+s+')');i=0
 while s[i:]:f=s[i];h='()|*.'.find(f);s[i]=(h,f)[h<0];s[i:i+1]*=f!='\\';i+=1;l=i;h=1;w=e=[];p=[0];t=[{l}]
 while i:
  d=[i];i-=1;o=[i];f=s[i];t=[{i}]+t
  if f<1:h-=1;e+=zip(o*l,d+s.pop());w.pop()
  if f==1:h+=1;w=w+o;s+=[[]];e+=[o+d]
  if f==2:s[-1]+=d;e+=[(i,w[-1])]
  if h==p[-1]:e+=[t[-1:]+o,[i,1+t.pop()]];p.pop()
  if f==3:p+=[h];t+=o
 for f,o in e:
  for n in t:n|=(n,t[o])[f in n]
 return s+[1],l,t

Si la segunda muestra de código se almacena en la cadena s, la expresión puede producir algo similar a la primera '#encoding=Latin\nexec"""%s"""'%__import__('zlib').compress(s). Puede ser necesario corregir algunos caracteres, como bytes nulos o barras diagonales inversas. El código descomprimido es de casi 1000 800 bytes, por lo que quizás esté más ofuscado que el golf ... pero al menos logré jugar un poco la codificación: de Latin1aLatin .

Explicación

El programa funciona mediante el uso de los índices de la cadena como una forma cruda de realizar un seguimiento de los estados de análisis de una cadena. La nfunción construye tablas de transición. Primero analiza la cadena y encuentra todas las instancias de dos tipos de transiciones. Primero, hay transiciones que no implican agregar otra letra a la cadena. Por ejemplo, saltar de *a al principio de una expresión cuantificada. En segundo lugar, hay transiciones de agregar un carácter, que simplemente avanzan un índice. Luego se calcula el cierre transitivo de las transiciones sin caracteres, y esos son sustituidos por los destinos de las transiciones de 1 carácter. Por lo tanto, devuelve una asignación de un índice y un carácter a un conjunto de índices.

La función principal realiza un BFS sobre posibles cadenas de entrada. Realiza un seguimiento de un conjunto de todos los índices posibles para cualquier fragmento de una cadena que esté considerando. Lo que nos interesa encontrar es estados que sean aceptados por ambas expresiones regulares, o por una y no por la otra. Para mostrar que se acepta una expresión regular, solo es necesario encontrar un posible camino de transiciones al final del patrón. Pero para mostrar que uno es rechazado, es necesario haber analizado todos los caminos posibles. Por lo tanto, para determinar si los conjuntos de estados posibles para el patrón A y el patrón B ya están cubiertos por los que se han analizado anteriormente, se registran los pares de un solo estado en una expresión regular y el conjunto de todos los estados posibles en el otro. Si no hay nuevos, entonces está bien volver. Por supuesto, también sería posible, y menos personajes,

Haskell, 560 553 618

podría obtener algunos de los bonos en el futuro.

esto aún no está totalmente golfizado.

import Data.List
c%j|'\\':h:s<-j=[s|c==h]|(a,b):_<-[(a,b)|x<-[0..length j],(a,'|':b)<-[splitAt x j],snd(k b)==[]]=c%a++c%b|'(':s<-j,(a,_:'*':b)<-k s=map(++j)(c%a)++c%b|'(':s<-j,(a,_:b)<-k s=map(++b)(c%a)|h:'*':s<-j=map(++j)(c%[h])++c%s
c%"."=[""|c>'\0']
c%s@[_]=c%('\\':s)
c%(a:b)=map(++b)(c%[a])
c%s=[""|c>'\0']
a&b=nub[(x,nub$b>>=(c%))|c<-[' '..'~'],x<-c%a]
g e(k@(a,l):r)|j<-a&l\\e=g(k:e)(j++r)
g e[]=e
a#b=or[all(null.('\0'%))m|(x,m)<-g[][(a,[b])],""<-'\0'%x]
a!b|a#b,b#a='x'|a#b='>'|b#a='<'|0<1='='
k"("=("","(")
k(c:s)|'('<-c,(x,y)<-k$tail b=('(':a++')':x,y)|')'<-c=("",')':s)|0<1=(c:a,b)where(a,b)=k s
k j=(j,j)

Una explicación manual del algoritmo:

reg!reg' devuelve el carácter requerido, uno de "= <> x".

a#bes cierto si no todas las cadenas que acoinciden también coinciden conb .

c%reges una lista de expresiones regulares que regcoincide c:ssi una de las expresiones regulares en la salida coincide s. Básicamente coincide parcialmente con la expresión regular. excepto si ces así '\0'. entonces obliga rega no recibir más información, regresando []si regdebe obtener más información para que coincida y[""] contrario.

#funciona generando una lista finita de todos los posibles "estados de expresión regular" en los que estarán las dos expresiones regulares después de una cadena arbitraria. luego, para verificar si a<bverificamos el clima, hay un "estado regex" en el que ase coincide por completo pero bno se coincide por completo.