Regex: correspondre à une série égalitaire

18

introduction

Je ne vois pas beaucoup de défis regex ici, donc je voudrais proposer celui-ci d'une simplicité trompeuse qui peut être fait de plusieurs façons en utilisant un certain nombre de saveurs regex. J'espère que cela offre aux amateurs de regex un peu de plaisir à jouer au golf.

Défi

Le défi est de faire correspondre ce que j'ai très vaguement appelé une série «égalitaire»: une série de nombres égaux de personnages différents. Ceci est mieux décrit avec des exemples.

Rencontre:

aaabbbccc
xyz 
iillppddff
ggggggoooooollllllffffff
abc
banana

Ne correspond pas:

aabc
xxxyyzzz
iilllpppddff
ggggggoooooollllllfff
aaaaaabbbccc
aaabbbc
abbaa
aabbbc

Pour généraliser, nous voulons faire correspondre un sujet du formulaire ( pour toute liste de caractères à , où pour tousc1)n(c2)n(c3)n...(ck)nc1ckci != ci+1i, k > 1, and n > 0.

Clarifications:

  • L'entrée ne sera pas vide.

  • Un caractère peut se répéter plus tard dans la chaîne (par exemple "banane")

  • k > 1, il y aura donc toujours au moins 2 caractères différents dans la chaîne.

  • Vous pouvez supposer que seuls les caractères ASCII seront transmis en entrée et aucun caractère ne sera un terminateur de ligne.

Règles

(Merci à Martin Ender pour ce bloc de règles excellemment énoncé)

Votre réponse doit consister en une seule expression régulière, sans code supplémentaire (sauf, éventuellement, une liste de modificateurs d'expression régulière requis pour faire fonctionner votre solution). Vous ne devez pas utiliser les fonctionnalités de la saveur regex de votre langue qui vous permettent d'invoquer du code dans le langage d'hébergement (par exemple le emodificateur de Perl ).

Vous pouvez utiliser n'importe quelle saveur regex qui existait avant ce défi, mais veuillez spécifier la saveur.

Ne supposez pas que l'expression régulière est ancrée implicitement, par exemple si vous utilisez Python, supposez que votre expression régulière est utilisée avec re.search et non avec re.match. Votre expression régulière doit correspondre à la chaîne entière pour les chaînes égalitaires valides et ne produire aucune correspondance pour les chaînes non valides. Vous pouvez utiliser autant de groupes de capture que vous le souhaitez.

Vous pouvez supposer que l'entrée sera toujours une chaîne de deux ou plusieurs caractères ASCII ne contenant aucun terminateur de ligne.

C'est le golf regex, donc le regex le plus court en octets gagne. Si votre langue nécessite (généralement /.../) des délimiteurs pour désigner des expressions régulières, ne comptez pas les délimiteurs eux-mêmes. Si votre solution nécessite des modificateurs, ajoutez un octet par modificateur.

Critères

C'est un bon golf à l'ancienne, alors oubliez l'efficacité et essayez simplement d'obtenir votre regex aussi petit que possible.

Veuillez indiquer la saveur regex que vous avez utilisée et, si possible, inclure un lien montrant une démonstration en ligne de votre expression en action.

Jaytea
la source
Est-ce spécifiquement un golf regex? Vous devriez probablement clarifier cela, ainsi que les règles pour cela. La plupart des défis sur ce site sont des golfs de langages de programmation variés.
LyricLy
@LyricLy Merci pour les conseils! Oui, je voudrais que ce soit purement regex, ie. une seule expression régulière dans une saveur regex au choix du demandeur. Y a-t-il d'autres règles que je devrais garder à l'esprit?
jaytea
Je ne comprends pas votre définition de "égalitaire", telle que banana est égalitaire.
msh210
@ msh210 Quand j'ai trouvé le terme "égalitaire" pour décrire la série, je ne pensais pas que j'autoriserais la répétition de personnages plus tard dans la série (comme dans "banane", ou "aaabbbcccaaa", etc.) . Je voulais juste un terme pour représenter l'idée que chaque bloc de caractères répétés est de la même taille. Puisque "banane" n'a pas de caractères répétés, cette définition est vraie pour lui.
jaytea

Réponses:

11

Saveur .NET, 48 octets

^(.)\1*((?<=(\5())*(.))(.)(?<-4>\6)*(?!\4|\6))+$

Essayez-le en ligne! (en utilisant Retina )

Eh bien, il s'avère que ne pas nier la logique est plus simple après tout. J'en fais une réponse distincte, car les deux approches sont complètement différentes.

Explication

^            # Anchor the match to the beginning of the string.
(.)\1*       # Match the first run of identical characters. In principle, 
             # it's possible that this matches only half, a quarter, an 
             # eighth etc of of the first run, but that won't affect the 
             # result of the match (in other words, if the match fails with 
             # matching this as the entire first run, then backtracking into
             # only matching half of it won't cause the rest of the regex to
             # match either).
(            # Match this part one or more times. Each instance matches one
             # run of identical letters.
  (?<=       #   We start with a lookbehind to record the length
             #   of the preceding run. Remember that the lookbehind
             #   should be read from the bottom up (and so should
             #   my comments).
    (\5())*  #     And then we match all of its adjacent copies, pushing an
             #     empty capture onto stack 4 each time. That means at the
             #     end of the lookbehind, we will have n-1 captures stack 4, 
             #     where n is the length of the preceding run. Due to the 
             #     atomic nature of lookbehinds, we don't have to worry 
             #     about backtracking matching less than n-1 copies here.
    (.)      #     We capture the character that makes up the preceding
             #     run in group 5.
  )
  (.)        #   Capture the character that makes up the next run in group 6.
  (?<-4>\6)* #   Match copies of that character while depleting stack 4.
             #   If the runs are the same length that means we need to be
             #   able to get to the end of the run at the same time we
             #   empty stack 4 completely.
  (?!\4|\6)  #   This lookahead ensures that. If stack 4 is not empty yet,
             #   \4 will match, because the captures are all empty, so the
             #   the backreference can't fail. If the stack is empty though,
             #   then the backreference will always fail. Similarly, if we
             #   are not at the end of the run yet, then \6 will match 
             #   another copy of the run. So we ensure that neither \4 nor
             #   \6 are possible at this position to assert that this run
             #   has the same length das the previous one.
)+
$            # Finally, we make sure that we can cover the entire string
             # by going through runs of identical lengths like this.
Martin Ender
la source
J'adore que tu aies oscillé entre les deux méthodes! J'ai également pensé que l'approche négative aurait dû être plus courte jusqu'à ce que j'essaie de le faire et que je le trouve beaucoup plus gênant (même s'il semble que cela devrait être plus simple). J'ai 48b en PCRE et 49b en Perl avec une méthode complètement différente, et avec votre 3ème méthode en .NET autour de la même taille, je dirais que c'est un défi regex assez cool: D
jaytea
@jaytea J'adorerais les voir. Si personne ne propose quoi que ce soit pendant une semaine environ, j'espère que vous les publierez vous-même. :) Et oui, d'accord, c'est bien que les approches soient si proches en nombre d'octets.
Martin Ender
Je pourrais juste! En outre, Perl One a été abaissé à 46b;)
Jaytea
J'ai donc pensé que vous voudriez peut-être les voir maintenant! Le 48b de ici à PCRE: ((^.|\2(?=.*\4\3)|\4(?!\3))(?=\2*+((.)\3?)))+\3$J'expérimentait \3*en place de le (?!\3)rendre 45b mais échoue sur « aabbbc » :( La version Perl est plus facile à comprendre, et il est jusqu'à 45b maintenant: ^((?=(.)\2*(.))(?=(\2(?4)?\3)(?!\3))\2+)+\3+$- la raison pour laquelle je l' appelle Perl , même si elle semble être valide PCRE est que PCRE pense qu'il (\2(?4)?\3)pourrait récurer indéfiniment alors que Perl est un peu plus intelligent / indulgent!
jaytea
@jaytea Ah, ce sont des solutions vraiment intéressantes. Vous devriez vraiment les publier dans une réponse séparée. :)
Martin Ender
9

Saveur .NET, 54 octets

^(?!.*(?<=(\2)*(.))(?!\2)(?>(.)(?<-1>\3)*)(?(1)|\3)).+

Essayez-le en ligne! (en utilisant Retina )

Je suis presque sûr que ce n'est pas optimal, mais c'est le meilleur que je trouve pour équilibrer les groupes en ce moment. J'ai une alternative au même nombre d'octets, qui est essentiellement la même:

^(?!.*(?<=(\3())*(.))(?!\3)(?>(.)(?<-2>\4)*)(\2|\4)).+

Explication

L'idée principale est d'inverser le problème, de faire correspondre des chaînes non égalitaires et de mettre le tout dans une position négative pour annuler le résultat. L'avantage est que nous n'avons pas à garder une trace de n tout au long de la chaîne (car en raison de la nature des groupes d'équilibrage, vous consommez généralement n lors de la vérification), pour vérifier que toutes les exécutions sont de longueur égale. Au lieu de cela, nous recherchons simplement une seule paire de pistes adjacentes qui n'ont pas la même longueur. De cette façon, j'ai seulement besoin d'utiliser n qu'une seule fois.

Voici une ventilation de l'expression régulière.

^(?!.*         # This negative lookahead means that we will match
               # all strings where the pattern inside the lookahead
               # would fail if it were used as a regex on its own.
               # Due to the .* that inner regex can match from any
               # position inside the string. The particular position
               # we're looking for is between two runs (and this
               # will be ensured later).

  (?<=         #   We start with a lookbehind to record the length
               #   of the preceding run. Remember that the lookbehind
               #   should be read from the bottom up (and so should
               #   my comments).
    (\2)*      #     And then we match all of its adjacent copies, capturing
               #     them separately in group 1. That means at the
               #     end of the lookbehind, we will have n-1 captures
               #     on stack 1, where n is the length of the preceding
               #     run. Due to the atomic nature of lookbehinds, we
               #     don't have to worry about backtracking matching
               #     less than n-1 copies here.
    (.)        #     We capture the character that makes up the preceding
               #     run in group 2.
  )
  (?!\2)       #   Make sure the next character isn't the same as the one
               #   we used for the preceding run. This ensures we're at a
               #   boundary between runs.
  (?>          #   Match the next stuff with an atomic group to avoid
               #   backtracking.
    (.)        #     Capture the character that makes up the next run
               #     in group 3.
    (?<-1>\3)* #     Match as many of these characters as possible while
               #     depleting the captures on stack 1.
  )
               #   Due to the atomic group, there are three two possible
               #   situations that cause the previous quantifier to stopp
               #   matching. 
               #   Either the run has ended, or stack 1 has been depleted.
               #   If both of those are true, the runs are the same length,
               #   and we don't actually want a match here. But if the runs
               #   are of different lengths than either the run ended but
               #   the stack isn't empty yet, or the stack was depleted but
               #   the run hasn't ended yet.
  (?(1)|\3)    #   This conditional matches these last two cases. If there's
               #   still a capture on stack 1, we don't match anything,
               #   because we know this run was shorter than the previous
               #   one. But if stack 1, we want to match another copy of 
               #   the character in this run to ensure that this run is 
               #   longer than the previous one.
)
.+             # Finally we just match the entire string to comply with the
               # challenge spec.
Martin Ender
la source
J'ai essayé de le faire échouer sur: banana, aba, bbbaaannnaaannnaaa, bbbaaannnaaannnaaaaaa, The Nineteenth Byte, 11, 110, ^(?!.*(?<=(\2)*(.))(?!\2)(?>(.)(?<-1>\3)*)(?(1)|\3)).+, bababa. C'est moi qui ai échoué. :( +1
Erik l'Outgolfer
1
Ce moment où vous avez terminé votre explication, puis compris que vous pouvez enregistrer 1 octet en utilisant l'approche exactement opposée ... Je suppose que je ferai une autre réponse dans un peu ...: |
Martin Ender
@MartinEnder ... Et puis réalisez que vous pourriez jouer à celui-ci par 2 octets haha: P
M. Xcoder
@ Mr.Xcoder Devrait être de 7 octets maintenant, donc j'espère que je suis en sécurité. ;)
Martin Ender