Combine as permutações!

15

Seu desafio é criar uma regex que corresponda a todas as permutações de string em si e nada mais. A correspondência também deve fazer distinção entre maiúsculas e minúsculas.

Então, por exemplo, se o seu regex for:

ABC

Ele deve corresponder (e corresponder apenas) às seguintes strings:

ABC
ACB
BAC
BCA
CAB
CBA

Não deve corresponder a coisas 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)

Regras:

  • Você tem permissão para usar qualquer sabor de regex que desejar.
  • Aplicam-se brechas padrão.
  • Você deve ter pelo menos dois caracteres diferentes no seu código. Isso significa que soluções como 1são inválidas.
  • O regex deve conter apenas ASCII imprimível e nada mais.
clismique
fonte
3
Relacionados: Regex que corresponde apenas em si
xnor
Também relacionado: Contagem de caracteres no código-fonte
jimmy23013 22/11
Eu pensei, (ABC|ACB|BAC|BCA|CAB|CBA)mas você queria uma resposta generalizada.
Stephen Quan

Respostas:

11

JavaScript, 64 57 bytes

4 bytes removidos graças a Martin Ender.

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

Experimente aqui.

Explicações (desatualizadas)

^                                  # 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
fonte
2
Eu acho que isso funciona para 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101
Martin Ender
Isso quase funciona no .NET:^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]*
jimmy23013 23/11
O que não funciona? Trailing linefeeds?
Martin Ender
@MartinEnder Sim.
jimmy23013
2

Regex Perl e PCRE, 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

(Um pouco) mais legível:

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

Isso é executado no tempo O (2 ^ n) conforme escrito, e é incrivelmente ineficiente. A maneira mais fácil de testá-lo é substituir todas as ocorrências de .*por .*?, o que faz com que o caso em que corresponde seja verificado primeiro (o que significa que corresponde em tempo linear, mas ainda leva tempo exponencial se não corresponder).

A idéia básica é que aplicamos o comprimento do regex igual a 280 e usamos asserções lookahead para forçar cada caractere no regex a aparecer pelo menos um certo número de vezes, por exemplo, (?=(.*z){2})força o zcaractere a aparecer pelo menos duas vezes. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23é 280, então não podemos ter ocorrências "extras" de nenhum caractere.

Este é um exemplo de programação de um autograma , uma frase que se descreve listando o número de cada caractere que ele contém (e, nesse caso, também o comprimento total). Tive muita sorte em construí-lo (normalmente você precisa usar força bruta, mas me deparei com essa solução enquanto testava meu programa de força bruta antes de terminar de escrevê-lo).

Regex Perl e PCRE, 253 bytes, em colaboração com Martin Ender

Minha hipótese era de que poderia haver soluções mais curtas que omitem alguns dígitos (provavelmente 9, 8 ou 7). Martin Ender encontrou um, mostrado abaixo:

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

Versão legível:

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

fonte
Eu não acho que você precisa escapar daqueles {} nas duas últimas viseiras. Você também não precisa adicionar coisas como, (?=(.*5){1})pois não haveria um 5se você não tivesse essa aparência. Um problema é que $permite um avanço de linha à direita, então você precisará usá \z-lo em vez de $como o jimmy fez, mas isso não custará um byte, acho que desde que você salvou o \na primeira olhada.
Martin Ender
Estou ciente de que é possível omitir coisas como dígitos. No entanto, eles estão lá para fazer o autograma funcionar. A remoção de qualquer parte do programa fará com que todo o resto quebre, porque não descreve mais o programa corretamente. (As contagens para cada linha contam as contagens para cada linha! Portanto, em geral é basicamente impossível alterar o programa.) Quanto a $permitir uma nova linha no final da string, isso geralmente depende de como o regex é chamado pela região circundante. programa (normalmente são executados em código que já foi analisado em linhas).
Ou, para ser mais preciso: eu preciso do (?=(.*5){1}) neste caso. Se eu o removesse, haveria um 5 no programa, porque a (?=(.*1){6})linha agora precisaria ler (?=(.*1){5}).
Quanto ao feed de linha à direita, não parece haver nenhuma restrição no desafio sobre o tipo de entrada em sua regex, de modo que geralmente significa que ele deve funcionar para qualquer cadeia de caracteres, e mudar $para \znão causa nenhum dano (e não quebre o autograma).
Martin Ender
Ah eu vejo; você muda a \$... $a z... \z. Isso funciona; Eu vou mudar isso.