Regex: unir una serie igualitaria

18

Introducción

No veo muchos desafíos de expresiones regulares aquí, por lo que me gustaría ofrecer este engañosamente simple que se puede hacer de varias maneras usando una serie de sabores de expresiones regulares. Espero que les brinde a los entusiastas de las expresiones regulares un poco de tiempo de golf divertido.

Desafío

El desafío es hacer coincidir lo que he denominado muy libremente una serie "igualitaria": una serie de números iguales de diferentes personajes. Esto se describe mejor con ejemplos.

Partido:

aaabbbccc
xyz 
iillppddff
ggggggoooooollllllffffff
abc
banana

No coinciden:

aabc
xxxyyzzz
iilllpppddff
ggggggoooooollllllfff
aaaaaabbbccc
aaabbbc
abbaa
aabbbc

Generalizar, que queremos para que coincida con un tema de la forma ( para cualquier lista de los caracteres a , donde para todosc1)n(c2)n(c3)n...(ck)nc1ckci != ci+1i, k > 1, and n > 0.

Aclaraciones:

  • La entrada no estará vacía.

  • Un carácter puede repetirse más tarde en la cadena (por ejemplo, "banana")

  • k > 1, por lo que siempre habrá al menos 2 caracteres diferentes en la cadena.

  • Puede suponer que solo se pasarán caracteres ASCII como entrada y ningún carácter será un terminador de línea.

Reglas

(Gracias a Martin Ender por este excelente bloque de reglas)

Su respuesta debe consistir en una única expresión regular, sin ningún código adicional (excepto, opcionalmente, una lista de modificadores de expresión regular necesarios para que su solución funcione). No debe usar las características de la expresión regular de su idioma que le permiten invocar código en el idioma de alojamiento (por ejemplo, el emodificador de Perl ).

Puede usar cualquier sabor regex que existiera antes de este desafío, pero especifique el sabor.

No asuma que la expresión regular está anclada implícitamente, por ejemplo, si está utilizando Python, suponga que su expresión regular se usa con re.search y no con re.match. Su expresión regular debe coincidir con la cadena completa para cadenas igualitarias válidas y no producir coincidencias para cadenas no válidas. Puede usar tantos grupos de captura como desee.

Puede suponer que la entrada siempre será una cadena de dos o más caracteres ASCII que no contienen terminadores de línea.

Esto es regex golf, por lo que gana la expresión regular más corta en bytes. Si su lenguaje requiere delimitadores (generalmente /.../) para denotar expresiones regulares, no cuente los delimitadores. Si su solución requiere modificadores, agregue un byte por modificador.

Criterios

Este es un buen golf antiguo, así que olvídate de la eficiencia y solo trata de que tu expresión regular sea lo más pequeña posible.

Mencione qué sabor regex ha utilizado y, si es posible, incluya un enlace que muestre una demostración en línea de su expresión en acción.

jaytea
fuente
¿Es esto específicamente un golf regex? Probablemente deberías aclarar eso, junto con las reglas para ello. La mayoría de los desafíos en este sitio son campos de diversos lenguajes de programación.
Letra de
@LyricLy Gracias por el consejo! Sí, me gustaría que fuera pura expresión regular, es decir. una única expresión regular en un sabor regex a elección del remitente. ¿Hay otras reglas que debería tener en cuenta?
jaytea
No entiendo tu definición de "igualitario", que bananaes igualitario.
msh210
@ msh210 Cuando se me ocurrió el término "igualitario" para describir la serie, no consideré que permitiría que los caracteres se repitan más adelante en la serie (como en "banana" o "aaabbbcccaaa", etc.) . Solo quería que un término representara la idea de que cada fragmento de caracteres repetidos es del mismo tamaño. Como "banana" no tiene caracteres repetidos, esta definición es válida para ello.
jaytea

Respuestas:

11

Sabor .NET, 48 bytes

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

Pruébalo en línea! (usando Retina )

Bueno, resulta que no negar la lógica es más simple después de todo. Estoy respondiendo esto por separado, porque los dos enfoques son completamente diferentes.

Explicación

^            # 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
fuente
¡Me encanta que hayas descifrado entre los dos métodos! También pensé que el enfoque negativo debería haber sido más corto hasta que realmente lo intenté y lo encontré mucho más incómodo (aunque parece que debería ser más simple). Tengo 48b en PCRE y 49b en Perl con un método completamente diferente, y con su tercer método en .NET aproximadamente del mismo tamaño, diría que este es un desafío de
expresiones
@jaytea Me encantaría verlos. Si a nadie se le ocurre nada durante una semana más o menos, espero que lo publique usted mismo. :) Y sí, de acuerdo, es bueno que los enfoques estén tan cerca en el recuento de bytes.
Martin Ender
Yo solo podría! Además, Perl One ha sido reducido a 46b;)
jaytea
¡Así que pensé que querrías verlos ahora! Aquí hay 48b en PCRE: ((^.|\2(?=.*\4\3)|\4(?!\3))(?=\2*+((.)\3?)))+\3$estaba experimentando \3*en lugar de (?!\3)hacerlo 45b pero eso falla en "aabbbc" :( La versión de Perl es más fácil de entender, y ahora se reduce a 45b: ^((?=(.)\2*(.))(?=(\2(?4)?\3)(?!\3))\2+)+\3+$- la razón por la que lo llamo Perl a pesar de que parece ser válida PCRE PCRE es que piensa que (\2(?4)?\3)podría recursivo indefinidamente mientras que Perl es un poco más inteligente / perdona!
jaytea
@jaytea Ah, esas son soluciones realmente buenas. Realmente debería publicarlos en una respuesta separada. :)
Martin Ender
9

Sabor .NET, 54 bytes

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

Pruébalo en línea! (usando Retina )

Estoy bastante seguro de que esto es subóptimo, pero es lo mejor que se me ocurre para equilibrar grupos en este momento. Tengo una alternativa con el mismo número de bytes, que es casi la misma:

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

Explicación

La idea principal es invertir el problema, unir cadenas no igualitarias y poner todo el asunto en una perspectiva negativa para negar el resultado. El beneficio es que no tenemos que hacer un seguimiento de n a lo largo de toda la cadena (porque debido a la naturaleza de los grupos de equilibrio, generalmente consumes n al verificarlo), para verificar que todas las ejecuciones tengan la misma longitud. En cambio, solo buscamos un solo par de carreras adyacentes que no tengan la misma longitud. De esa manera, solo necesito usar n una vez.

Aquí hay un desglose de la expresión regular.

^(?!.*         # 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
fuente
Traté de hacer que falle en: banana, aba, bbbaaannnaaannnaaa, bbbaaannnaaannnaaaaaa, The Nineteenth Byte, 11, 110, ^(?!.*(?<=(\2)*(.))(?!\2)(?>(.)(?<-1>\3)*)(?(1)|\3)).+, bababa. Soy yo quien falló. :( +1
Erik the Outgolfer
1
En ese momento, cuando termine su explicación y luego se dé cuenta de que puede guardar 1 byte utilizando el enfoque exactamente opuesto ... Supongo que haré otra respuesta en un momento ...: |
Martin Ender
@MartinEnder ... Y luego date cuenta de que puedes jugar golf por 2 bytes jaja: P
Sr. Xcoder
@ Mr.Xcoder Tendría que tener 7 bytes ahora, así que espero estar a salvo. ;)
Martin Ender