Regex inverso de juros compostos

9

Koronkorko é a palavra finlandesa para juros compostos . Não queremos interesse composto em nossas strings, portanto, vamos encontrar a expressão regular mais curta possível para excluí-la.

Dada uma sequência que consiste apenas nos caracteres alfabéticos maiúsculos AZ, determine a expressão regular mais curta possível que corresponda à sequência, se ela não contiver a substring KORONKORKO. Qualquer sequência que contenha KORONKORKOcomo substring não deve ser correspondida pelo regex.

Apenas os caracteres A- Z, [, ], -, ^, , ?, *, +, |, (, e )deve ser usado na expressão.

Eu acho que isso pode ser feito com 118 caracteres na expressão. Você pode torná-lo mais curto?

Nota: Este desafio é de Ohjelmointiputka (em finlandês).

code-golf regular-expression hóspede
fonte
Se !fosse um caractere permitido, você poderia ter feito ^((?!KORONKORO).)*$por 19 bytes.
Mama Fun Roll
3
@MamaFunRoll Eu acho que é por isso que ! não é permitido.
Alex A.
Diverti-me ao tentar trabalhar no site finlandês e acredito que o que você está procurando são expressões de expressões regulares que correspondam / rejeitam a string de entrada. Por exemplo, o site parece apenas permitir o uso de -e ^dentro das classes de caracteres (portanto, ^não pode ser usado como uma âncora), e uma correspondência só é contada se toda a cadeia de caracteres corresponder ao regex (ou seja, um ambiente implícito ^$, como opostos aos "regexes" normais que contam uma string como correspondente se alguma parte dela corresponder à regex)
Sp3000
Como tal, apaguei minha resposta PCRE que, embora deva funcionar mesmo em PHP, é quase definitivamente não intencional neste caso.
Sp3000
Esqueci de dizer que o site verifica se a expressão é válida pela função ereg do PHP. Foi dito em discussão em ohjelmointiputka.net/keskustelu/…
guest

Respostas:

6

204 caracteres

(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?[^KO]|[^KR])|[^KO])|[^K])|[^KN])|[^KO])|[^KR])|[^KO])|[^K])*(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?)?)?)?)?)?)?)?)?

Gerado transformando .*KORONKORKO.*- se em uma máquina de estados finitos, invertendo a máquina de estados finitos e transformando-a novamente em um regex.

orlp
fonte
Por que essa se tornou a melhor resposta?
Bálint 13/05
1

Python, 77 79 97 118 bytes

Editar 3: Reescrever. Usa lookaheads aninhados

^([^K]|K(?=$|[^O]|O(?=$|[^R]|R(?=$|[^O]|O(?=$|[^N]|N(?=$|[^K]|K(?=$|[^O]|O(?=$|[^R]|R(?=$|[^K]|K(?=$|[^O]))))))))))*$

Regex 101

Edit 2: Adicionado '$ |' em todo o regex. Agora, se um prefixo do KORONKORKO tiver sido correspondido, o próximo item a ser correspondido será o final da string, um caractere que termina o prefixo ou um caractere que estenda o prefixo, se for seguido por algo que termine o prefixo.

Este regex funciona com re.fullmatch(), que foi adicionado no Python 3.4. Para uso com re.match(), ^e $necessidade de ser adicionada ao início e no final do teste padrão, respectivamente, para mais de 2 bytes.

([^K]|K($|[^O]|O($|[^R]|R($|[^O]|O($|[^N]|N($|[^K]|K($|[^O]|O($|[^R]|R($|[^K]|K($|[^O]))))))))))*

Link Regex101

Solução incorreta anterior (ver comentários):

K|([^K]|K([^O]|O([^R]|R([^O]|O([^N]|N([^K]|K([^O]|O([^R]|R([^K]|K[^O])))))))))*

Edit: Adicionado K único

RootTwo
fonte
2
Eu não acredito nisso K.
orlp 13/05
@orip - Boa captura. Fixo.
RootTwo
Última actualização agora falhar porKKORONKORKO
SP3000
É consertável? Alguma ideia?
RootTwo 14/05
11
O começo ^e o fim $não são necessários. Além disso, =e $não são permitidos.
LegionMammal978