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).

\$\endgroup\$
  • \$\begingroup\$ If ! was an allowed character, you could've done ^((?!KORONKORO).)*$ for 19 bytes. \$\endgroup\$ – Mama Fun Roll May 12 '16 at 23:00
  • 3
    \$\begingroup\$ @MamaFunRoll I think that's why ! isn't allow. \$\endgroup\$ – Alex A. May 12 '16 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 '16 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 '16 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 '16 at 11:24
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.

\$\endgroup\$
  • \$\begingroup\$ Why did this become the best answer? \$\endgroup\$ – Bálint May 13 '16 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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