Matthias Goergens tem um regex de 25.604 caracteres (abaixo do original de 63.993 caracteres) para corresponder a números divisíveis por 7, mas isso inclui muitos problemas: parênteses redundantes, distribuição ( xx|xy|yx|yye não [xy]{2}) e outros problemas, embora eu tenha certeza de que um novo começo seria útil para economizar espaço. Quão pequeno isso pode ser feito?
Qualquer variedade razoável de expressões regulares é permitida, mas nenhum código executável na regex.
A expressão regular deve corresponder a todas as strings que contêm a representação decimal de um número divisível por 7 e nenhum outro. Crédito extra para uma regex que não permite 0s iniciais.
code-golf
math
regular-expression
Charles
fonte
fonte
Respostas:
10791 caracteres, zeros à esquerda permitidos
10795 caracteres, zeros à esquerda proibidos
0|((foo)0*)+, onde o regex acima é(0|foo)+.Explicação
Os números divisíveis por 7 são correspondidos pelo óbvio autômato finito com 7 estados Q = {0,…, 6}, estado inicial e final 0 e transições d: i mod (10i + d) mod 7. Eu converti esse autômato finito em uma expressão regular, usando recursão no conjunto de estados intermediários permitidos:
Dado i, j ∈ Q e S ⊆ Q, seja f (i, S, j) uma expressão regular que corresponda a todos os caminhos de autômato de i a j usando apenas estados intermediários em S.
f (i, ∅, j) = (j - 10i) mod 7,
f (i, S ∪ {k}, j) = f (i, S, j) ∣ f (i, S, k) f (k, S, k) * f (k, S, j).
Utilizei a programação dinâmica para escolher k, a fim de minimizar o comprimento da expressão resultante.
fonte
0|((foo)0*)+13.75512.69912.731 PersonagensEste regex não rejeita o zero inicial.
Isso é testado com o The Regex Coach .
Como chegamos lá
O Regex acima produzido pela primeira construção de um DFA que aceitaria a entrada que queremos (decimais divisíveis por 7) e, em seguida, convertendo para uma Expressão Regular e corrigindo a nota
Para entender isso, é melhor criar um DFA que aceite o seguinte idioma:
Ou seja, ele 'coincidirá' com números binários divisíveis por 7.
O DFA é assim:
Como funciona
Você mantém um valor atual
Aque representa o valor dos bits que o DFA leu. Quando você lê um0entãoA = 2*Ae quando você lê um1A = 2*A + 1. Em cada etapa que você calculaA mod 7, você vai para o estado que representa a resposta.Então, um teste:
Estamos lendo em
10101que é a representação binária de 21 em decimal.q0, atualmenteA=01, da 'regra' acimaA = 2*A + 1assimA = 1.A mod 7 = 1então passamos ao estadoq10,A = 2*A = 2,A mod 7 = 2para que se deslocar paraq21,A = 2*A + 1 = 5,A mod 7 = 5, mover-se paraq50,A = 2*A = 10,A mod 7 = 3, mover-se paraq31,A = 2*A + 1 = 21,A mod 7 = 0, mover-se paraq010101seja divisível por 7!Converter o DFA em uma expressão regular é uma tarefa complicada, por isso solicitei ao JFLAP que fizesse isso por mim, produzindo o seguinte:
Para números decimais
O processo é praticamente o mesmo:
Eu construí um DFA que aceita o idioma:
Aqui está o DFA:
A lógica é semelhante, o mesmo número de estados apenas muito mais transições para lidar com todos os dígitos decimais que os números extras trazem.
Agora, a regra para alterar
Aa cada passo é: quando você lê um dígito decimaln:A = 10*A + n. Então, novamente, apenasmodApor 7 e vá para o próximo estado.Revisões
Revisão 5
A expressão regular acima agora rejeita números que levam zeros - além do próprio zero, é claro.
Isso torna o DFA um pouco diferente. Basicamente, você se ramifica do nó inicial quando lê o primeiro zero. Ler outro zero coloca você em um loop infinito no estado ramificado. Eu não fixa o diagrama para mostrar isso.
Revisão 7
Fiz alguns "metaregex" e encurtou meu regex substituindo alguns dos sindicatos por classes de caracteres.
Revisões 10 e 11 (por nhahtdh)
A modificação do autor para rejeitar o zero inicial está incorreta. Isso faz com que as expressões regulares não correspondam a números válidos, como 1110 (decimal = 14) no caso da expressão regular binária e 70 no caso da expressão regular decimal. Essa revisão reverte a modificação e, conseqüentemente, permite que zeros iniciais arbitrários e seqüência vazia correspondam.
Esta revisão aumenta o tamanho da regex decimal, pois corrige um erro na regex original, causado pela falta de uma aresta (9) do estado 5 ao estado 3 no DFA original.
fonte
1110e o decimal não corresponde70. Isso foi testado em python e perl. (python necessário converter toda(a(?:primeira)Regex .NET,
119118105 bytes111 caracteres que não permitem 0s iniciais:
113 caracteres que não permitem 0s iniciais e suportam números negativos:
Experimente aqui.
Explicação (da versão anterior)
Ele usa as técnicas usadas por várias respostas nesta pergunta: Cops and Robbers: Reverse Regex Golf . O regex .NET possui um recurso chamado grupo de balanceamento, que pode ser usado para fazer aritmética.
(?<a>)empurra um grupoa.(?<-a>)aparece isso e não corresponde se não houver um grupoacorrespondente antes.(?>...)Combine e não volte mais tarde. Portanto, sempre corresponderá apenas à primeira alternativa correspondente.((?<-t>)(){3}|){6}Multiplique o número do grupo t por 3. Salve o resultado no número do grupo 2.(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d)Combine um número e esse número do grupo 2.((?<-2>){7}|){3}Remova o grupo 2 várias vezes por 7.((?<t-2>)|){6}Remova o grupo 2 e corresponda ao mesmo número do grupo t.$(?(t)a)Se ainda houver um grupo t correspondido, faça a correspondênciaaapós o final da sequência, o que é impossível.Eu pensei que esta versão de 103 bytes também deveria funcionar, mas não encontrei uma solução alternativa do bug no compilador.
fonte
468 caracteres
O sabor da expressão regular do Ruby permite recursão (embora seja uma espécie de trapaça), por isso é simples implementar um DFA que reconheça números divisíveis por 7 usando isso. Cada grupo nomeado corresponde a um estado e cada ramificação nas alternações consome um dígito e, em seguida, salta para o estado apropriado. Se o final do número for atingido, a regex corresponderá apenas se o mecanismo estiver no grupo "A", caso contrário, falhará.
Ele reconhece zeros à esquerda.
fonte
{a*b*|a and b an equal amount of times})Fiquei realmente impressionado com a resposta de Griffin e precisava descobrir como funcionava! O resultado é o seguinte JavaScript. (São 3,5 mil caracteres, que são mais curtos!) A
genfunção pega um divisor e uma base e gera uma expressão regular que corresponde aos números na base especificada que são divisíveis por esse divisor.Eu generalizei o NFA de Griffin para qualquer base: a
nfafunção pega um divisor e uma base e retorna uma matriz bidimensional de transições. A entrada necessária para passar do estado 0 ao estado 2, por exemplo, éstates[0][2] == "1".A
reducefunção pega astatesmatriz e a executa através desse algoritmo para converter o NFA em regex. As expressões regulares geradas são enormes e parecem ter muitas cláusulas redundantes, apesar das minhas tentativas de otimização. O regex para 7 base 10 tem aproximadamente 67k caracteres; O Firefox lança um "InternalError" para n> 5 tentando analisar o regex; a execução da regex no Chrome começa a ficar lenta para n> 6.Há também a
testfunção que pega uma regex e base e a executa nos números de 0 a 100, entãotest(gen(5)) == [0, 5, 10, 15, ...].Apesar do resultado subótimo, essa foi uma oportunidade fantástica de aprendizado e espero que parte desse código seja útil no futuro!
fonte
Perl / PCRE, 370 caracteres
Rejeita a cadeia vazia, bem como as cadeias com 0 iniciais (exceto "0").
fonte