Regex inverse des intérêts composés

9

Koronkorko est le mot finlandais pour les intérêts composés . Nous ne voulons pas d'intérêt composé dans nos chaînes, alors trouvons l'expression régulière la plus courte possible pour l'exclure.

Étant donné une chaîne composée uniquement des caractères alphabétiques majuscules AZ, déterminez l'expression régulière la plus courte possible qui correspond à la chaîne si elle ne contient pas la sous-chaîne KORONKORKO. Toute chaîne qui contient KORONKORKOcomme sous-chaîne ne doit pas être mise en correspondance par l'expression régulière.

Seuls les caractères A- Z, [, ], -, ^, , ?, *, +, |, (et )doivent être utilisés dans l'expression.

Je pense que cela peut être fait avec 118 caractères dans l'expression. Pouvez-vous le raccourcir?

Remarque: Ce défi vient d' Ohjelmointiputka (en finnois).

client
la source
Si !c'était un caractère autorisé, vous auriez pu le faire ^((?!KORONKORO).)*$pour 19 octets.
Mama Fun Roll
3
@MamaFunRoll Je pense que c'est pourquoi ce ! n'est pas permis.
Alex A.
J'ai eu le plaisir d'essayer de contourner le site finlandais, et je crois que ce que vous recherchez, ce sont des expressions regex théoriques qui correspondent / rejettent la chaîne d'entrée. Par exemple, le site ne semble autoriser l'utilisation que des classes de caractères -et à l' ^intérieur de celles-ci (il ^ne peut donc pas être utilisé comme ancre), et une correspondance n'est comptée que si toute la chaîne est mise en correspondance par l'expression régulière (c'est-à-dire un entourage implicite ^$, comme par opposition aux "regexes" normales qui comptent une chaîne comme correspondant si une partie de celle-ci correspond à l'expression
régulière
En tant que tel, j'ai supprimé ma réponse PCRE qui, même si cela devrait fonctionner même en PHP, n'est presque certainement pas intentionnelle dans ce cas.
Sp3000
J'ai oublié de dire que le site vérifie si l'expression est valide par la fonction ereg de PHP. Il a été dit en discussion dans ohjelmointiputka.net/keskustelu/…
invité

Réponses:

6

204 caractères

(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?)?)?)?)?)?)?)?)?

Généré en se transformant .*KORONKORKO.*en une machine à états finis, en inversant la machine à états finis et en la transformant en regex.

orlp
la source
Pourquoi est-ce devenu la meilleure réponse?
Bálint
1

Python, 77 79 97 118 octets

Édition 3: réécriture. Utilise des têtes de lecture imbriquées

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

Regex 101

Edit 2: Ajout de '$ |' tout au long de l'expression régulière. Maintenant, si un préfixe de KORONKORKO a été mis en correspondance, l'élément suivant à mettre en correspondance est la fin de chaîne, un caractère qui termine le préfixe ou un caractère qui étend le préfixe s'il est suivi de quelque chose qui termine le préfixe.

Cette expression régulière fonctionne avec re.fullmatch(), qui a été ajoutée dans Python 3.4. À utiliser avec re.match(), ^et $doit être ajouté au début et à la fin du modèle, respectivement, pour 2 octets supplémentaires.

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

Lien Regex101

Solution incorrecte précédente (voir commentaires):

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

Edit: Ajout d'un seul K

RootTwo
la source
2
Je ne crois pas que cela corresponde K.
orlp
@orip - Bonne prise. Fixé.
RootTwo
La dernière mise à jour échoue maintenant pourKKORONKORKO
Sp3000
Est-il réparable? Des idées?
RootTwo
1
Le début ^et la fin $ne sont pas nécessaires. En outre, =et $ne sont pas autorisés.
LegionMammal978