Corresponde a cadeias cujo comprimento é uma quarta potência

Dentro do escopo desta questão, consideremos apenas cadeias que consistem no caractere xrepetido número arbitrário de vezes.

Por exemplo:

<empty>
x
xx
xxxxxxxxxxxxxxxx

^{(Bem, na verdade não precisa ser x- qualquer caractere é bom desde que toda a cadeia tenha apenas 1 tipo de caractere)}

Escreva uma regex em qualquer sabor de regex de sua escolha para corresponder a todas as cadeias cujo comprimento é n ⁴ para algum número inteiro não negativo n (n> = 0). Por exemplo, cadeias de comprimento 0, 1, 16, 81, etc. são válidas; o resto é inválido.

^{Devido à limitação técnica, é difícil testar valores de n maiores que 128. No entanto, sua regex deve logicamente funcionar corretamente, independentemente.}

Observe que você não tem permissão para executar código arbitrário no seu regex (para usuários Perl). Qualquer outra sintaxe (pesquisa, referência posterior, etc.) é permitida.

Por favor, inclua também uma breve explicação sobre sua abordagem do problema.

^{(Não cole explicações de sintaxe de regex geradas automaticamente, pois elas são inúteis)}

Essa expressão regular (ir) parece funcionar.

^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

Este regex é compatível com os sabores PCRE, Perl, .NET.

Isso basicamente segue uma "árvore da diferença" (não tenho certeza se existe um nome adequado para ela), que informa ao regex quantos mais x's devem corresponder para o próximo quarto poder:

1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

\2, \3, \4Lojas e actualizações a diferença como mostrado na 2ª, 3ª e 4ª linhas, respectivamente.

Essa construção pode ser facilmente estendida para potências mais altas.

Certamente não é uma solução elegante, mas funciona.

Outra solução

Este é, na minha opinião, um dos problemas mais interessantes do site. Preciso agradecer o código morto por enviá -lo de volta ao topo.

^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

39 bytes , sem condicionais ou asserções ... mais ou menos. As alternâncias, como estão sendo usadas ( ^|), são um tipo de condicional, de certa forma, para selecionar entre "primeira iteração" e "não primeira iteração".

Esse regex pode ser visto como funcionando aqui: http://regex101.com/r/qA5pK3/1

Tanto o PCRE quanto o Python interpretam o regex corretamente, e também foi testado em Perl até n = 128 , incluindo n ⁴ -1 e n ⁴ +1 .

Definições

A técnica geral é a mesma das outras soluções já postadas: defina uma expressão de auto-referência que em cada iteração subsequente corresponda a um comprimento igual ao próximo termo da função de diferença direta, D _f , com um quantificador ilimitado ( *). Uma definição formal da função de diferença progressiva:

Além disso, funções de diferença de ordem superior também podem ser definidas:

Ou, de maneira mais geral:

A função de diferença direta possui muitas propriedades interessantes; é para sequenciar qual é a derivada para funções contínuas. Por exemplo, D _f de um n th polinomial ordem irá sempre ser uma N-1 th polinomial fim, e para qualquer i , se D _f ⁱ = D _f ^{i + 1} , então a função F é exponencial, em muito da mesma maneira que a derivada de e ^x é igual a si mesma. A função discreta mais simples para a qual f = D _f é 2 ⁿ .

f (n) = n ²

Antes de examinarmos a solução acima, vamos começar com algo um pouco mais fácil: uma regex que corresponde a cadeias cujos comprimentos são um quadrado perfeito. Examinando a função de diferença direta:

Ou seja, a primeira iteração deve corresponder a uma cadeia de comprimento 1 , a segunda uma cadeia de comprimento 3 , a terceira uma cadeia de comprimento 5 , etc. e, em geral, cada iteração deve corresponder a uma cadeia duas mais longa que a anterior. O regex correspondente segue quase diretamente dessa declaração:

^(^x|\1xx)*$

Pode-se observar que a primeira iteração corresponderá apenas a uma xe cada iteração subsequente corresponderá a uma sequência duas mais longa que a anterior, exatamente como especificado. Isso também implica um teste quadrado perfeito incrivelmente curto em perl:

(1x$_)=~/^(^1|11\1)*$/

Essa regex pode ser generalizada ainda mais para corresponder a qualquer comprimento n- diagonal:

Números triangulares:
^(^x|\1x{1})*$

Números quadrados:
^(^x|\1x{2})*$

Números pentagonais:
^(^x|\1x{3})*$

Números hexagonais:
^(^x|\1x{4})*$

etc.

f (n) = n ³

Passando para n ³ , examinando mais uma vez a função de diferença direta:

Pode não ser imediatamente aparente como implementar isso, portanto examinamos também a segunda função de diferença:

Portanto, a função de diferença para frente não aumenta em uma constante, mas em um valor linear. É bom que o valor inicial (' -1 th') de D _f ² seja zero, o que salva uma inicialização na segunda iteração. A regex resultante é a seguinte:

^((^|\2x{6})(^x|\1))*$

A primeira iteração corresponderá a 1 , como antes, a segunda corresponderá a uma sequência 6 maior ( 7 ), a terceira corresponderá a uma sequência 12 maior ( 19 ), etc.

f (n) = n ⁴

A função de diferença direta para n ⁴ :

A segunda função de diferença de avanço:

A terceira função de diferença para a frente:

Agora isso é feio. Os valores iniciais para D _f ² e D _f ³ são diferentes de zero, 2 e 12 , respectivamente, que precisarão ser contabilizados. Você provavelmente já descobriu que a regex seguirá esse padrão:

^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

Como o D _f ³ deve corresponder a um comprimento de 12 na segunda iteração, a é necessariamente 12 . Mas, como aumenta em 24 a cada termo, o próximo aninhamento mais profundo deve usar seu valor anterior duas vezes, implicando b = 2 . A última coisa a fazer é inicializar o D _f ² . Porque D _f ² influências D que _f diretamente, o que é afinal o que queremos corresponder, seu valor pode ser inicializado, inserindo o átomo apropriado diretamente no regex, neste caso (^|xx). O regex final passa a ser:

^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

Ordens mais altas

Um polinômio de quinta ordem pode ser correspondido com o seguinte regex:
^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$

f (n) = n ⁵ é um exercício bastante fácil, pois os valores iniciais para a segunda e a quarta funções de diferença direta são zero:

^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

Para seis polinômios de ordem:
^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$

Para polinômios de sétima ordem:
^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$

etc.

Observe que nem todos os polinômios podem ser correspondidos exatamente dessa maneira, se algum dos coeficientes necessários não for um número inteiro. Por exemplo, N ⁶ requer que a = 60 , b = 8 , e c = 3/2 . Isso pode ser contornado, neste exemplo:

^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

Aqui alterei b para 6 e c para 2 , que têm o mesmo produto que os valores acima mencionados. É importante que o produto não seja alterado, pois a · b · c ·… controla a função de diferença constante, que para um polinômio de sexta ordem é D _f ⁶ . Existem dois átomos de inicialização presentes: uma para inicializar D _f a 2 , como com n ⁴ , e o outro para inicializar a quinta função de diferença para 360 , enquanto ao mesmo tempo, adicionando em dois a falta de b .

Aqui está uma solução que não usa condicionais, referências anteriores ou declarações aninhadas a frente, lookbehind, grupos de balanceamento ou recursão de regex. Ele usa apenas lookahead e referências anteriores padrão, que são amplamente suportadas. Fiquei inspirado a operar sob essas limitações devido ao Regex Golf , que usa o mecanismo de expressão regular ECMAScript.

A maneira como esse regex de 50 bytes funciona é conceitualmente bastante simples e completamente diferente de todas as outras soluções enviadas para esse quebra-cabeça. Foi surpreendente descobrir que esse tipo de lógica matemática era expressável em uma regex.

      \2                     \4  \5
^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+)$)\5){4})*x?$

(Os grupos de captura são rotulados acima da regex)

A expressão regular pode ser generalizada para qualquer poder simplesmente substituindo a 4em {4}com a potência desejada.

Experimente online!

Ele funciona dividindo repetidamente a menor quarta potência de um primo pela qual o valor atual é divisível. Como tal, o quociente em cada etapa é sempre uma quarta potência, se o valor original fosse uma quarta potência. Um quociente final de 1 indica que o valor original era de fato uma quarta potência; isso completa a partida. Zero também é correspondido.

Primeiro, ele usa um grupo de captura lenta \2para capturar o menor fator do número maior que 1. Assim, esse fator é garantido como primo. Por exemplo, com 1296 (6 ^ 4), ele capturará inicialmente \2= 2.

Em seguida, no início de um loop repetido 4 vezes, ele testa para verificar se o número atual é divisível por \2, com (?=\2+$). Na primeira vez nesse loop, esse teste é inútil, mas seu objetivo se tornará aparente mais tarde.

Próxima dentro deste loop interno, ele usa o grupo de captura ávidos \4para capturar maior fator do número menor do que a própria: (?=(x+)(\4+)$). Com efeito, isso divide o número pelo menor fator primo \2; por exemplo, 1296 será capturado inicialmente como \4= 1296/2 = 648. Observe que a divisão do número atual por \2está implícita. Embora seja possível dividir explicitamente o número atual por um número contido em um grupo de captura (que eu descobri apenas quatro dias após postar esta resposta), isso faria com que fosse uma regex mais lenta e difícil de entender, e não é necessário, uma vez que o menor fator de um número maior que 1 sempre corresponderá ao maior fator menor que ele próprio (de modo que seu produto seja igual ao próprio número).

Como esse tipo de regex só pode "corroer" a string (diminuindo), deixando um resultado no final da string, precisamos "mover" o resultado da divisão para o final da string. Isso é feito capturando o resultado da subtração (o número atual menos \4), no grupo de captura \5e, em seguida, fora da cabeça de impressão, correspondendo a uma parte do início do número atual correspondente a \5. Isso deixa a sequência não processada restante no final correspondente \4em comprimento.

Agora ele volta ao início do loop interno, onde fica evidente por que há um teste de divisibilidade pelo fator primo. Acabamos de dividir pelo menor fator primo do número; se o número ainda é divisível por esse fator, significa que o número original pode ser divisível pela quarta potência desse fator. Na primeira vez em que esse teste é realizado, é inútil, mas nas próximas três vezes, ele determina se o resultado da divisão implícita por \2ainda é divisível por \2. Se ainda é divisível \2no início de cada iteração do loop, isso prova que cada iteração dividiu o número por \2.

Em nosso exemplo, com uma entrada 1296, isso fará o loop da seguinte maneira:

\2= 2
\4= 1296/2 = 648
\4= 648/2 = 324
\4= 324/2 = 162
\4= 162/2 = 81

Agora, o regex pode voltar ao primeiro passo; é isso que a final *faz. Neste exemplo, 81 se tornará o novo número; o próximo loop será o seguinte:

\2= 3
\4= 81/3 = 27
\4= 27/3 = 9
\4= 9/3 = 3
\4= 3/3 = 1

Agora ele voltará ao primeiro passo novamente, com 1 como o novo número.

O número 1 não pode ser dividido por nenhum primo, o que o tornaria inconsistente (?=(xx+?)\2+$), portanto, ele sai do loop de nível superior (aquele com *o final). Agora chega ao x?$. Isso pode corresponder apenas a zero ou um. O número atual nesse momento será 0 ou 1 se e somente se o número original for uma quarta potência perfeita; se for 0 neste momento, significa que o loop de nível superior nunca correspondeu a nada e, se for 1, significa que o loop de nível superior dividiu uma quarta potência perfeita até que não fosse mais divisível por nada (ou era 1 em primeiro lugar, o que significa que o loop de nível superior nunca correspondia a nada).

Também é possível resolver isso em 49 bytes, fazendo divisão explícita repetida (que também é generalizada para todos os poderes - substitua o poder desejado menos um pelo {3}), mas esse método é muito, muito mais lento, e explica o algoritmo que ele usa. está além do escopo desta resposta:

^((x+)((\2(x+))(?=(\4*)\2*$)\4*(?=\5$\6)){3})?x?$

Experimente online!

Solução

^(?:(?=(^|(?<=^x)x|xx\1))(?=(^|\1\2))(^x|\3\2{12}xx))*$

Este regex é compatível com os sabores Java, Perl, PCRE e .NET. Essa regex usa uma variedade de recursos: referência futura antecipada, retrospectiva e declarada adiante. Os tipos de referência reversa declarada a frente limitam a compatibilidade desse regex a alguns mecanismos.

Explicação

Esta solução utiliza a seguinte derivação.

Expandindo completamente a soma, podemos provar a seguinte igualdade:

Vamos combinar o somatório no lado esquerdo:

Subtraia as 2 equações (equação superior menos equação inferior) e, em seguida, combine as somas no lado esquerdo e simplifique-as:

Obtemos a diferença entre os quarta potências consecutivas como soma de potência:

Isso significa que a diferença entre quarta potência consecutiva será aumentará em (12n ² + 2).

Para facilitar o pensamento, consultando o árvore diferenças na resposta da Volatilidade :

• O lado direito da equação final é a 2ª linha na árvore de diferenças.
• O incremento (12n ² + 2) é a 3ª linha na árvore de diferenças.

Chega de matemática. Voltar para a solução acima:

• O 1º grupo de captura mantém uma série de números ímpares para calcular i ² como visto na equação.

  Precisamente falando, o comprimento do 1º grupo de captura será 0 (não utilizado), 1, 3, 5, 7, ... conforme o loop iterar.

  (?<=^x)xdefine o valor inicial para a série de números ímpares. o^ está ali apenas para permitir que o olhar em frente para ser satisfeito na primeira iteração.

  xx\1 adiciona 2 e avança para o próximo número ímpar.

• O segundo grupo de captura mantém a série de números quadrados para i ² .

  Precisamente falando, a duração do 2º grupo de captura será 0, 1, 4, 9, ... conforme o loop itera.

  ^in (^|\1\2)define o valor inicial para a série de números quadrados. E \1\2adiciona o número ímpar ao número quadrado atual para avançar para o próximo número quadrado.

• O terceiro grupo de captura (fora de qualquer visualização e realmente consome texto) corresponde a todo o lado direito da equação que derivamos acima.

  ^xin (^x|\3\2{12}xx)define o valor inicial, que é + 1o lado direito da equação.

  \3\2{12}xxadiciona o aumento na diferença (12n ² + 2) usando n ² do grupo 2 de captura e corresponde à diferença ao mesmo tempo.

Essa organização é possível devido à quantidade de texto correspondida em cada iteração ser maior ou igual à quantidade de texto necessária para executar a antecipação da construção n ² .