Matthias Goergens a une expression rationnelle de 25 604 caractères (au lieu de 63 993 caractères) pour faire correspondre les nombres divisibles par 7, mais cela inclut beaucoup de choses: parenthèses redondantes, distribution ( xx|xy|yx|yyplutôt que [xy]{2}) et autres, bien que je sois sûr Un nouveau départ serait utile pour gagner de la place. À quel point cela peut-il être réduit?
Toute variété raisonnable d'expressions régulières est autorisée, mais pas de code exécutable dans l'expression régulière.
L'expression régulière doit correspondre à toutes les chaînes contenant la représentation décimale d'un nombre divisible par 7 et aucune autre. Crédit supplémentaire pour une expression régulière ne permettant pas les 0 initiaux.
code-golf
math
regular-expression
Charles
la source
la source
Réponses:
10791 caractères, les zéros au début autorisés
10795 caractères, zéros non autorisés
0|((foo)0*)+, où la regex ci-dessus est(0|foo)+.Explication
Les nombres divisibles par 7 sont mis en correspondance par l'automate fini évident avec 7 états Q = {0,…, 6}, l'état initial et final 0, et les transitions d: i ↦ (10i + d) mod 7. J'ai converti cet automate fini en une expression régulière, en utilisant la récursivité sur l'ensemble des états intermédiaires autorisés:
Étant donné i, j ∈ Q et S ⊆ Q, soit f (i, S, j) une expression régulière qui correspond à tous les chemins d'automate de i à j en utilisant uniquement des états intermédiaires dans S. Ensuite,
f (i, ∅, j) = (j - 10i) mod 7,
f (i, S {k}, j) = f (i, S, j) f (i, S, k) f (k, S, k) * f (k, S, j).
J'ai utilisé la programmation dynamique pour choisir k afin de minimiser la longueur de l'expression résultante.
la source
0|((foo)0*)+137551269912 731 PersonnagesCette regex ne rejette pas le zéro non significatif.
Ceci est testé avec The Regex Coach .
Comment on y arrive
La regex ci-dessus est produite en construisant d’abord un DFA qui accepterait l’entrée souhaitée (décimales divisibles par 7), puis en convertissant en une expression régulière et en fixant la notaion.
Pour comprendre cela, il est utile de commencer par créer un DFA qui accepte le langage suivant:
C'est-à-dire que cela "correspond" aux nombres binaires divisibles par 7.
Le DFA ressemble à ceci:
Comment ça fonctionne
Vous conservez une valeur actuelle
Aqui représente la valeur des bits lus par DFA. Quand vous lisez un0alorsA = 2*Aet quand vous lisez un1A = 2*A + 1. A chaque étape que vous calculez,A mod 7vous passez à l'état qui représente la réponse.Donc, un test:
Nous lisons dans
10101lequel se trouve la représentation binaire pour 21 en décimal.q0, actuellementA=01, de la "règle" ci-dessus,A = 2*A + 1doncA = 1.A mod 7 = 1alors nous passons à l'étatq10,A = 2*A = 2,A mod 7 = 2donc nous passons àq21,A = 2*A + 1 = 5,A mod 7 = 5, passez àq50,A = 2*A = 10,A mod 7 = 3, passez àq31,A = 2*A + 1 = 21,A mod 7 = 0, passez àq010101est divisible par 7!La conversion de DFA en une expression régulière est une tâche délicate. JFLAP a donc été chargée de le faire pour moi, en produisant ce qui suit:
Pour les nombres décimaux
Le processus est sensiblement le même:
J'ai construit un DFA qui accepte le langage:
Voici le DFAE:
La logique est similaire, le même nombre d'états, mais beaucoup plus de transitions pour gérer tous les chiffres supplémentaires que les nombres décimaux apportent.
Maintenant , la règle de changer
Aà chaque étape est: lorsque vous lisez un chiffre décimaln:A = 10*A + n. Encore une fois, vous avez justemodA7 et passez à l'état suivant.Révisions
Révision 5
L'expression rationnelle ci-dessus rejette maintenant les nombres précédant des zéros - à l'exception bien entendu de zéro.
Cela rend le DFA légèrement différent, en gros vous vous séparez du nœud initial lorsque vous lisez le premier zéro. La lecture d'un autre zéro vous place dans une boucle infinie sur l'état ramifié. Je n'ai pas corrigé le diagramme pour le montrer.
Révision 7
Est-ce que certains "metaregex" et raccourci ma regex en remplaçant certaines des unions avec des classes de caractères.
Révision 10 et 11 (par nhahtdh)
La modification de l'auteur pour rejeter le zéro initial est incorrecte. Cela empêche les expressions rationnelles de correspondre aux nombres valides, tels que 1110 (décimal = 14) dans le cas d'une expression rationnelle binaire et 70 dans le cas d'une expression rationnelle décimale. Cette révision annule la modification et, par conséquent, permet de faire correspondre des zéros non significatifs et des chaînes vides.
Cette révision augmente la taille de la regex décimale, car elle corrige un bogue dans la regex d'origine, causée par l'absence d'un bord (9) de l'état 5 à l'état 3 dans le DFA d'origine.
la source
1110, et celui pour la décimale ne correspond pas70. Cela a été testé à la fois en python et en perl. (python nécessaire pour convertir chaque(en(?:premier)Regex .NET,
119118105 octets111 caractères refusant les 0 initiaux:
113 caractères refusant les 0 initiaux et prenant en charge les nombres négatifs:
Essayez ici.
Explication (de la version précédente)
Il utilise les techniques utilisées par diverses réponses à cette question: Cops and Robbers: Reverse Regex Golf . La regex .NET a une fonctionnalité appelée groupe d'équilibrage, qui peut être utilisée pour faire de l'arithmétique.
(?<a>)pousse un groupea.(?<-a>)apparaît et ne correspond pas s’il n’ya pas de groupeacorrespondant auparavant.(?>...)Match et ne pas revenir en arrière plus tard. Donc, il ne fera toujours correspondre que la première alternative correspondante.((?<-t>)(){3}|){6}Multipliez le nombre de groupe t par 3. Enregistrez le résultat sous le numéro de groupe 2.(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d)Faites correspondre un nombre et ce nombre de groupe 2.((?<-2>){7}|){3}Supprimer le groupe 2 un multiple de 7 fois.((?<t-2>)|){6}Supprimer le groupe 2 et faire correspondre le même nombre de groupe t.$(?(t)a)Si un groupe t correspond encore, faites-leaaprès la fin de la chaîne, ce qui est impossible.Je pensais que cette version de 103 octets devrait également fonctionner, mais je n’ai trouvé aucune solution de contournement du bogue dans le compilateur.
la source
468 caractères
La saveur regex de Ruby autorise la récursivité (bien que ce soit une sorte de tricherie). Il est donc simple de mettre en œuvre un DFA qui reconnaît les nombres divisibles par 7 en utilisant cela. Chaque groupe nommé correspond à un état et chaque branche des alternances consomme un chiffre puis passe à l'état approprié. Si la fin du nombre est atteinte, l'expression rationnelle ne correspond que si le moteur est dans le groupe "A", sinon il échoue.
Il reconnaît les zéros non significatifs.
la source
{a*b*|a and b an equal amount of times})La réponse de Griffin m'a vraiment impressionné et j'ai dû comprendre comment cela fonctionnait! Le résultat est le JavaScript suivant. (Il s'agit de 3,5 caractères, ce qui est plus court d'une manière!) La
genfonction prend un diviseur et une base et génère une expression régulière qui correspond aux nombres de la base spécifiée qui sont divisibles par ce diviseur.J'ai généralisé la NFA de Griffin pour n'importe quelle base: la
nfafonction prend un diviseur et une base et renvoie un tableau bidimensionnel de transitions. L'entrée requise pour passer de l'état 0 à l'état 2, par exemple, eststates[0][2] == "1".La
reducefonction prend dans lestatestableau et l'exécute à travers cet algorithme pour traduire NFA en regex. Les regex générées sont énormes et semblent contenir beaucoup de clauses redondantes, malgré mes tentatives d'optimisation. La regex pour 7 base 10 est d'environ 67k caractères; Firefox lance une "InternalError" pour n> 5 en essayant d'analyser la regex; L'exécution de l'expression régulière sur Chrome commence à ralentir pendant n> 6.Il y a aussi la
testfonction qui prend une expression rationnelle et une base et la compare aux nombres de 0 à 100, donctest(gen(5)) == [0, 5, 10, 15, ...].Malgré le résultat non optimal, il s’agissait là d’une formidable opportunité d’apprentissage, et j’espère que ce code sera utile dans l’avenir!
la source
Perl / PCRE, 370 caractères
Rejette la chaîne vide, ainsi que les chaînes avec un 0 (sauf "0").
la source