Aux fins de ce défi, nous disons qu'un modèle d'expression régulière correspond à une chaîne si la chaîne entière correspond au modèle, et pas seulement à une sous-chaîne.

Étant donné deux modèles d'expression régulière  A  et  B , nous disons que  A  est plus spécialisé que  B   si chaque chaîne qui est mise en correspondance par  A  est également mise en correspondance par  B,   mais pas l'inverse. Nous disons que  A  est équivalent à  B  si les deux modèles correspondent exactement au même ensemble de chaînes. Si aucun motif n'est plus spécialisé que l'autre et qu'ils ne sont pas équivalents, nous disons que  A  et  B  sont incomparables .

Par exemple, le modèle Hello, .*!est plus spécialisé que .*, .*!; les motifs (Hello|Goodbye), World!et Hello, World!|Goodbye, World!sont équivalents; et les motifs Hello, .*!et .*, World!sont incomparables.

La relation "plus spécialisée que" définit un ordre partiel strict sur l'ensemble des motifs d'expression régulière. En particulier, pour tous les modèles  A  et  B , exactement l'une des conditions suivantes est vraie:

• A  est plus spécialisé que  B  ( A < B ).
• B  est plus spécialisé que  A  ( A > B ).
• A  et  B  sont équivalents ( A = B ).
• A  et  B  sont incomparables ( A ∥ B ).

Lorsque  A  et  B  sont incomparables, on peut encore distinguer deux cas:

• A  et  B  sont disjoints ( A ∥ B ), ce qui signifie qu'aucune chaîne n'est mise en correspondance par les deux.
• A  et  B  se croisent ( A ≬ B ), ce qui signifie que certaines chaînes sont appariées par les deux.

Défi

Écrivez un programme ou une fonction qui prend une paire de motifs d'expression régulière et les compare en utilisant l'ordre ci-dessus. Autrement dit, si les deux modèles sont  A  et  B , le programme devrait déterminer si  A < B ,  A > B ,
A = B  ou  A ∥ B .

× 92% Bonus  Un bonus supplémentaire est accordé si, lorsque les motifs sont incomparables, le programme détermine s'ils sont entrecroisés ou disjoints.

Entrée et sortie

Le programme doit accepter deux modèles d'expression régulière, sous forme de chaînes, dans la saveur définie ci-dessous. Vous pouvez lire l'entrée via STDIN , la ligne de commande , comme arguments de fonction ou une méthode équivalente . Vous pouvez supposer que les modèles sont valides.

Le programme devrait produire l'une des quatre sorties distinctes (ou cinq sorties distinctes si vous optez pour le bonus ci-dessus), selon le résultat de la comparaison (les sorties exactes dépendent de vous.) Vous pouvez écrire la sortie dans STDOUT , renvoyez-la comme résultat de la fonction ou utilisez une méthode équivalente .

Arôme Regex

Vous pouvez prendre en charge les fonctionnalités regex que vous aimez, mais vous devez prendre en charge les suivantes:

• Alternance avec |.
• Quantification avec *.
• Regroupement avec (et ).
• Faire correspondre n'importe quel caractère (éventuellement à l'exclusion des sauts de ligne) avec ..
• (Facultatif: × 80% de bonus)  Faire correspondre les classes de personnages simples et inversées avec […]et [^…], respectivement. Vous n'avez pas à prendre en charge de classes de caractères prédéfinies (par exemple [:digit:]), mais vous devez prendre en charge les plages de caractères.
• Caractère s'échappant avec \. Il devrait au moins être possible d'esacpe des caractères spéciaux (ie |*().[^-]\) et de préférence également des caractères spéciaux communs dans d'autres versions (par exemple {}), mais le comportement lors de l'échappement de caractères non spéciaux n'est pas spécifié. En particulier, vous n'avez pas à prendre en charge des séquences d'échappement spéciales telles que \npour une nouvelle ligne, etc. Une implémentation possible consiste simplement à prendre le caractère suivant le \comme un littéral.

Vous pouvez supposer l'existence d'un caractère d'entrée qui ne peut être mis en correspondance par aucun littéral (c'est-à-dire qu'il ne peut être mis en correspondance que par des .classes de caractères niées).

Règles supplémentaires

• Vous pouvez utiliser des bibliothèques regex ou des fonctionnalités regex intégrées uniquement à des fins de correspondance et de remplacement de chaînes.
• Vous pouvez ignorer tous les problèmes liés aux paramètres régionaux, tels que les règles de classement.
• Pour dire l'évidence: votre programme doit se terminer. Il devrait s'exécuter dans un délai raisonnable compte tenu des modèles typiques (certainement pas plus d'une heure, de préférence beaucoup moins).

Notation

C'est du code-golf. Votre score est le produit de la taille du code , en octets, et de l'un des bonus . Le score le plus bas l' emporte.

Cas de test

Le format des cas de test est le suivant:

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

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

...

Où <Test ID>est un identifiant pour le cas de test, <Pattern A>et <Pattern B>sont les modèles d'expression régulière et <Ordering>est l'ordre entre eux, et est l'un des:

• <: <Pattern A>est plus spécialisé que <Pattern B>.
• >: <Pattern B>est plus spécialisé que <Pattern A>.
• =: Les motifs sont équivalents.
• |: Les motifs sont incomparables et disjoints.
• X: Les motifs sont incomparables et entrecroisés.

La valeur spéciale <empty pattern>représente le motif vide.

A. Modèles de base

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
(((.*)*)*)*
=
.*

Modèles complexes

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. Modèles de base avec classes de caractères

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. Modèles complexes avec classes de caractères

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|[&+]) [^, ][^,]*)\.

Programme de test

L'extrait de code suivant peut être utilisé pour comparer des modèles d'expression régulière:

<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 octets * .92 = 480,24 537,28

Édition 2 : -60 octets

Edit : Ajout d'une explication.

Défini est la fonction fqui prend les deux chaînes de modèle comme arguments et les rendements '<', '=', '>', '|', ou 'X'. Moins d'une minute est nécessaire pour traiter tous les cas de test.

Le code se compose des éléments suivants, mais avec \r, \n \tet les échappements hexadécimaux (mais pas \0) remplacés par leurs valeurs d'octets réelles.

#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')

L'instruction ci-dessus provoque l'exécution du code suivant:

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 le deuxième exemple de code est stocké dans la chaîne s, quelque chose de similaire au premier peut être produit par l'expression '#encoding=Latin\nexec"""%s"""'%__import__('zlib').compress(s). Il peut être nécessaire de corriger certains caractères tels que les octets nuls ou les barres obliques inverses. Le code décompressé fait près de 1000 800 octets, donc il est peut-être plus obscur que le golf ... mais au moins j'ai réussi à jouer un peu à l'encodage: de Latin1à Latin.

Explication

Le programme fonctionne en utilisant les indices de la chaîne comme un moyen grossier de garder une trace des états d'analyse d'une chaîne. La nfonction crée des tables de transition. Tout d'abord, il analyse la chaîne et trouve toutes les instances de deux types de transitions. Tout d'abord, il existe des transitions qui n'impliquent pas l'ajout d'une autre lettre à la chaîne. Par exemple, passer de a *au début d'une expression quantifiée. Deuxièmement, il y a des transitions d'ajout d'un caractère, qui avancent simplement d'un index. Ensuite, la fermeture transitive des transitions sans caractère est calculée, et celles-ci sont substituées aux destinations des transitions à 1 caractère. Il renvoie donc un mappage d'un index et d'un caractère à un ensemble d'indices.

La fonction principale effectue un BFS sur les chaînes d'entrée possibles. Il suit un ensemble de tous les indices possibles pour n'importe quel fragment d'une chaîne qu'il envisage. Ce que nous voulons trouver, ce sont des états qui sont acceptés soit par les deux expressions rationnelles, soit par l'un et pas l'autre. Pour montrer qu'une expression régulière est acceptée, il suffit de trouver un chemin possible de transitions jusqu'à la fin du motif. Mais pour montrer que l'on est rejeté, il faut avoir analysé tous les chemins possibles. Par conséquent, pour déterminer si les ensembles d'états possibles pour le motif A et le motif B sont déjà couverts par ceux qui ont été analysés auparavant, des paires d'un seul état dans une expression régulière et l'ensemble de tous les états possibles dans l'autre sont enregistrés. S'il n'y en a pas de nouveau, c'est OK pour revenir en arrière. Bien sûr, il serait également possible, et moins de caractères,

Haskell, 560 553 618

pourrait obtenir certains des bonus à l'avenir.

ce n'est pas encore entièrement joué.

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)

une explication ondulée à la main de l'algorithme:

reg!reg' renvoie le caractère requis, l'un de "= <> x".

a#best vrai si toutes les chaînes qui acorrespondent ne le sont pas b.

c%regest une liste d'expressions régulières telles qu'elles regcorrespondent à l' c:sune des expressions rationnelles des correspondances de sortie s. i correspond fondamentalement partiellement à l'expression régulière. sauf si cc'est le cas '\0'. alors il force regà ne plus obtenir d'entrée, retournant []si regdoit obtenir plus d'entrée à faire correspondre et [""]autrement.

#fonctionne en générant une liste finie de tous les "états de regex" possibles dans lesquels les deux regexps se trouveront après une chaîne arbitraire. puis pour vérifier si a<bnous vérifions la météo, il y a un "état regex" dans lequel il aest entièrement mis en correspondance mais bne l'est pas complètement.