9
\$\begingroup\$

Koronkorko is the Finnish word for compound interest. We don't want compound interest in our strings, so let's find the shortest possible regular expression to exclude it.

Given a string consisting only of the uppercase alphabetic characters A-Z, determine the shortest possible regular expression that matches the string if it does not contain the substring KORONKORKO. Any string that contains KORONKORKO as a substring should not be matched by the regex.

Only the characters A-Z, [, ], -, ^, , ?, *, +, |, (, and ) should be used in the expression.

I think this can be done with 118 characters in the expression. Can you make it shorter?

Note: This challenge is from Ohjelmointiputka (in Finnish).

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ If ! was an allowed character, you could've done ^((?!KORONKORO).)*$ for 19 bytes. \$\endgroup\$
    – Mama Fun Roll
    May 12, 2016 at 23:00
  • 3
    \$\begingroup\$ @MamaFunRoll I think that's why ! isn't allow. \$\endgroup\$
    – Alex A.
    May 12, 2016 at 23:55
  • \$\begingroup\$ I had the fun of trying to work my way around the Finnish site, and I believe what you're looking for are theoretical regex expressions which match/reject the input string. For example, the site only seems to allow the use of - and ^ inside character classes (so ^ can't be used as an anchor), and a match is only counted if the whole string is matched by the regex (i.e. an implicit surrounding ^$, as opposed to normal "regexes" which count a string as matching if any part of it matches the regex) \$\endgroup\$
    – Sp3000
    May 13, 2016 at 11:15
  • \$\begingroup\$ As such I've deleted my PCRE answer which, while it should work even in PHP, is almost definitely unintended in this case. \$\endgroup\$
    – Sp3000
    May 13, 2016 at 11:16
  • \$\begingroup\$ I forgot to say that the site checks the if the expression is valid by PHP's ereg function. It was said in discussion in ohjelmointiputka.net/keskustelu/… \$\endgroup\$
    – guest
    May 13, 2016 at 11:24

2 Answers 2

Reset to default
6
\$\begingroup\$

204 characters

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

Generated by turning .*KORONKORKO.* into a finite state machine, inverting the finite state machine, and turning it back into a regex.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Why did this become the best answer? \$\endgroup\$
    – Bálint
    May 13, 2016 at 8:38
1
\$\begingroup\$

Python, 77 79 97 118 bytes

Edit 3: Rewrite. Uses nested lookaheads

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

Regex 101

Edit 2: Added '$|' throughout the regex. Now, if a prefix of KORONKORKO has been matched, the next item to match is end-of-string, a character that ends the prefix, or a character that extends the prefix if it is followed by something that ends the prefix.

This regex works with re.fullmatch(), which was added in Python 3.4. To use with re.match(), ^ and $ need to be added to the beginning and end of the pattern, respectively, for 2 more bytes.

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

Regex101 link

Previous incorrect solution (see comments):

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

Edit: Added single K

Improve this answer
\$\endgroup\$
5
  • 2
    \$\begingroup\$ I don't believe this matches K. \$\endgroup\$
    – orlp
    May 13, 2016 at 9:12
  • \$\begingroup\$ @orip - Good catch. Fixed. \$\endgroup\$
    – RootTwo
    May 13, 2016 at 14:04
  • \$\begingroup\$ Latest update now fails for KKORONKORKO \$\endgroup\$
    – Sp3000
    May 14, 2016 at 3:16
  • \$\begingroup\$ Is it fixable? Any ideas? \$\endgroup\$
    – RootTwo
    May 14, 2016 at 5:33
  • 1
    \$\begingroup\$ The starting ^ and ending $ aren't necessary. Also, = and $ aren't allowed. \$\endgroup\$
    – LegionMammal978
    May 15, 2016 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.