Faites correspondre les permutations!

15

Votre défi est de créer une expression régulière qui correspond à chaque permutation de chaîne de lui-même, et rien d'autre. La correspondance doit également être sensible à la casse.

Ainsi, par exemple, si votre expression régulière est:

ABC

Il doit correspondre (et uniquement correspondre) à ces chaînes:

ABC
ACB
BAC
BCA
CAB
CBA

Cela ne devrait pas correspondre à des choses comme:

AABC (contains an extra A)
ABCD (contains an extra D)
AC   (no B)
AAA  (no B and C, extra 2 A's)
abc  (case-sensitive)

Règles:

  • Vous êtes autorisé à utiliser n'importe quelle saveur de regex que vous aimez.
  • Des échappatoires standard s'appliquent.
  • Vous devez avoir au moins deux caractères différents dans votre code. Cela signifie que les solutions comme ne 1sont pas valides.
  • L'expression régulière ne doit contenir que de l'ASCII imprimable et rien d'autre.
clismique
la source
Également lié:
Nombre de
J'ai pensé (ABC|ACB|BAC|BCA|CAB|CBA)mais vous vouliez une réponse généralisée.
Stephen Quan

Réponses:

11

JavaScript, 64 57 octets

4 octets supprimés grâce à Martin Ender.

^(?!.*([^])(.*\1){3}]?)[$$[-^?!!.'''-*11{33}5577\\-]{57}$

Essayez-le ici.

Explications (obsolètes)

^                                  # Beginning of the string.
(?!.*                              # Match only the strings that don't contain...
  (.)(.*\1){4}                     #     5 occurrences of the same character.
  [^1]?[^1]?                       #     Something that doesn't matter.
)
[]zzz^(?!!!.**[)\\1{{44}}666]{64}  # 64 occurrences of these 16 characters.
                                   # Some are duplicated to make sure the regex
                                   # contains 4 occurrences of each character.
\z                                 # End of the string.
jimmy23013
la source
2
Je pense que cela fonctionne pour 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101
Martin Ender
Cela fonctionne presque dans .NET:^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]*
jimmy23013
Qu'est-ce qui ne marche pas? Sauts de ligne arrière?
Martin Ender
@MartinEnder Oui.
jimmy23013
2

Perl et PCRE regex, 280 octets

^(?=(.*z){2})(?=(.*\(){43})(?=(.*\)){43})(?=(.*\*){22})(?=(.*\.){23})(?=(.*0){2})(?=(.*1){6})(?=(.*2){16})(?=(.*3){7})(?=(.*4){4})(?=(.*5){1})(?=(.*6){3})(?=(.*7){2})(?=(.*8){2})(?=(.*9){1})(?=(.*=){22})(?=(.*\?){22})(?=(.*\\){11})(?=(.*\^){2})(?=(.*\{){23})(?=(.*\}){23}).{280}\z

(Légèrement) plus lisible:

^
(?=(.*z){2})
(?=(.*\(){43})
(?=(.*\)){43})
(?=(.*\*){22})
(?=(.*\.){23})
(?=(.*0){2})
(?=(.*1){6})
(?=(.*2){16})
(?=(.*3){7})
(?=(.*4){4})
(?=(.*5){1})
(?=(.*6){3})
(?=(.*7){2})
(?=(.*8){2})
(?=(.*9){1})
(?=(.*=){22})
(?=(.*\?){22})
(?=(.*\\){11})
(?=(.*\^){2})
(?=(.*\{){23})
(?=(.*\}){23})
.{280}\z

Cela s'exécute en temps O (2 ^ n) tel qu'il est écrit, il est donc incroyablement inefficace. Le moyen le plus simple de le tester est de remplacer chaque occurrence de .*par .*?, ce qui entraîne la vérification en premier du cas où il correspond (ce qui signifie qu'il correspond en temps linéaire, mais prend toujours un temps exponentiel s'il ne correspond pas).

L'idée de base est que nous appliquons la longueur de l'expression régulière à 280 et que nous utilisons des assertions d'anticipation pour forcer chaque caractère dans l'expression régulière à apparaître au moins un certain nombre de fois, par exemple (?=(.*z){2})force le zcaractère à apparaître au moins deux fois. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23est 280, donc nous ne pouvons pas avoir d'occurrences "supplémentaires" d'aucun personnage.

Il s'agit d'un exemple de programmation d'un autogramme , une phrase qui se décrit en listant le numéro de chaque caractère qu'il contient (et, dans ce cas, également la longueur totale). J'ai eu assez de chance de le construire (normalement, vous devez utiliser la force brute mais je suis tombé sur cette solution tout en testant mon programme de force brute avant d'avoir complètement fini de l'écrire).

Perl et PCRE regex, 253 octets, en collaboration avec Martin Ender

J'ai émis l'hypothèse qu'il pourrait y avoir des solutions plus courtes qui omettent certains chiffres (très probablement 9, 8 ou 7). Martin Ender en a trouvé un, illustré ci-dessous:

^(?=(.*z){2})(?=(.*\(){39})(?=(.*\)){39})(?=(.*\*){20})(?=(.*\.){21})(?=(.*0){4})(?=(.*1){6})(?=(.*2){11})(?=(.*3){6})(?=(.*4){3})(?=(.*5){2})(?=(.*6){3})(?=(.*9){4})(?=(.*=){20})(?=(.*\?){20})(?=(.*\\){9})(?=(.*\^){2})(?=(.*{){21})(?=(.*}){21}).{253}\z

Version lisible:

^
(? = (. * z) {2})
(? = (. * \ () {39})
(? = (. * \)) {39})
(? = (. * \ *) {20})
(? = (. * \.) {21})
(? = (. * 0) {4})
(? = (. * 1) {6})
(? = (. * 2) {11})
(? = (. * 3) {6})
(? = (. * 4) {3})
(? = (. * 5) {2})
(? = (. * 6) {3})
(? = (. * 9) {4})
(? = (. * =) {20})
(? = (. * \?) {20})
(? = (. * \\) {9})
(? = (. * \ ^) {2})
(? = (. * {) {21})
(? = (. *}) {21})
. {253} \ z

la source
Je ne pense pas que vous ayez besoin d'échapper à ceux {}des deux derniers accrochages. Vous n'avez pas non plus besoin d'ajouter des choses comme (?=(.*5){1})car il n'y en aurait pas 5si vous n'aviez pas ce lookahead. Un problème est que cela $permet un saut de ligne en fin de ligne, vous devrez donc l'utiliser à la \zplace de $Jimmy, mais cela ne vous coûtera pas un octet, je pense, car vous enregistrez le \dans le premier lookahead.
Martin Ender
Je suis conscient qu'il est possible d'omettre des choses comme les chiffres. Cependant, ils sont là pour faire fonctionner l' autogramme . La suppression d'une partie du programme entraînera la rupture de tout le reste, car elle ne décrit plus correctement le programme. (Les décomptes pour chaque ligne comptent les décomptes pour chaque ligne! Il est donc en général fondamentalement impossible de changer le programme.) Quant à $autoriser une nouvelle ligne à la fin de la chaîne, cela dépend généralement de la façon dont l'expression régulière est appelée par l'entourage. (ils sont normalement exécutés sur du code qui a déjà été analysé en lignes).
Ou pour être plus précis: j'ai besoin du (?=(.*5){1})dans ce cas. Si je le supprimais, il y aurait un 5 dans le programme, car la (?=(.*1){6})ligne devrait maintenant être lue (?=(.*1){5}).
En ce qui concerne le saut de ligne de fin, il ne semble pas y avoir de restriction dans le défi sur le type d'entrée dans votre expression régulière, ce qui signifie généralement que cela devrait fonctionner pour n'importe quelle chaîne, et le fait de changer $pour \zne fait aucun mal (et ne ne cassez pas l'autogramme).
Martin Ender
Oh je vois; vous changez le \$$en z\z. Ça marche; Je vais le changer.