¡Combina las permutaciones!

15

Su desafío es crear una expresión regular que coincida con cada permutación de cadena de sí misma, y ​​nada más. El partido también debe ser sensible a mayúsculas y minúsculas.

Entonces, por ejemplo, si su expresión regular es:

ABC

Debe coincidir (y solo coincidir) con estas cadenas:

ABC
ACB
BAC
BCA
CAB
CBA

No debería coincidir con cosas como:

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)

Reglas:

  • Puede usar cualquier sabor de expresión regular que desee.
  • Se aplican lagunas estándar.
  • Debe tener al menos dos caracteres diferentes en su código. Eso significa que las soluciones como 1no son válidas.
  • La expresión regular debe contener solo ASCII imprimible, y nada más.
clismique
fuente
3
Relacionado: Regex que solo coincide
xnor
También relacionado: El carácter cuenta en el código fuente
jimmy23013
Pensé (ABC|ACB|BAC|BCA|CAB|CBA)pero querías una respuesta generalizada.
Stephen Quan

Respuestas:

11

JavaScript 64 57 bytes

4 bytes eliminados gracias a Martin Ender.

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

Pruébalo aquí.

Explicaciones (desactualizadas)

^                                  # 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
fuente
2
Creo que esto funciona para 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101
Martin Ender
Esto casi funciona en .NET:^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]*
jimmy23013
¿Qué no funciona? ¿Saltos de línea finales?
Martin Ender
@MartinEnder Sí.
jimmy23013
2

Perge y PCRE regex, 280 bytes

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

(Ligeramente) más legible:

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

Esto se ejecuta en tiempo O (2 ^ n) como está escrito, por lo que es increíblemente ineficiente. La forma más fácil de probarlo es reemplazar cada aparición de .*con .*?, lo que hace que se compruebe primero el caso en el que coincide (lo que significa que coincide en tiempo lineal, pero aún toma tiempo exponencial si no coincide).

La idea básica es que obliguemos a que la longitud de la expresión regular sea igual a 280, y usemos aserciones anticipadas para obligar a cada personaje de la expresión regular a aparecer al menos un cierto número de veces, por ejemplo, (?=(.*z){2})obliga al zpersonaje a aparecer al menos dos veces. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23es 280, por lo que no podemos tener ocurrencias "extra" de ningún personaje.

Este es un ejemplo de programación de un autograma , una oración que se describe a sí misma enumerando el número de cada carácter que contiene (y, en este caso, también la longitud total). Tuve bastante suerte al construirlo (normalmente tienes que usar la fuerza bruta, pero me topé con esta solución mientras probaba mi programa de fuerza bruta antes de terminar de escribirlo por completo).

Perl y PCRE regex, 253 bytes, en colaboración con Martin Ender

Supuse que podría haber soluciones más cortas que omiten algunos dígitos (muy probablemente 9, 8 o 7). Martin Ender encontró uno, que se muestra a continuación:

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

Versión legible:

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

fuente
No creo que necesites escapar de los {}de las dos últimas miradas. Tampoco necesita agregar cosas como, (?=(.*5){1})ya que no habría un 5si no tuviera esa anticipación. Un problema es que $permite un salto de línea final, por lo que deberá usarlo \zallí en lugar de lo $que hizo Jimmy, pero creo que eso no le costará un byte, ya que guarda \el primer vistazo.
Martin Ender
Soy consciente de que es posible omitir cosas como dígitos. Sin embargo, están ahí para hacer que el autograma funcione. Eliminar cualquier parte del programa hará que todo el resto se rompa, porque ya no describe el programa correctamente. (¡Los recuentos para cada línea cuentan los recuentos para cada línea! Por lo tanto, en general es básicamente imposible cambiar el programa). En cuanto a $permitir una nueva línea al final de la cadena, eso generalmente depende de cómo se llama la expresión regular por el entorno programa (normalmente se ejecutan en código que ya se ha analizado en líneas).
O para ser más precisos: necesito el (?=(.*5){1})en este caso. Si lo eliminara, habría un 5 en el programa, porque la (?=(.*1){6})línea ahora tendría que leerse (?=(.*1){5}).
En cuanto al avance de línea final, no parece haber ninguna restricción en el desafío sobre el tipo de entrada a su expresión regular, por lo que eso generalmente significa que debería funcionar para cualquier cadena, y cambiar $a \zno hace ningún daño (y no No rompa el autograma).
Martin Ender
Oh ya veo; cambia el \$... $a z... \z. Eso funciona; Iré a cambiarlo.