0
\$\begingroup\$

Okay, the challenge is that you have to write a regex that matches half of all strings.

Some rules to clarify:

For ANY string length(>0), if I permute all strings(of that length), exactly half of them should be matched. Put more lightly, if I generate a random string of that length it should have a 50% chance of being matched. (this means that you cannot just match all even-length strings)

You may assume that strings contain only A-Z, a-z, and 0-9.

0 length strings are undefined, you can choose to either match them or not.

Shortest regex wins.

\$\endgroup\$
  • \$\begingroup\$ /^[A-Z0-4]*$/ works, doesn't it? \$\endgroup\$ – Tim Seguine Jan 16 '14 at 20:53
  • \$\begingroup\$ @TimSeguine No, if strings could have only uppercase, or only lower case it would. But since most strings have a combination of both, that misses most strings \$\endgroup\$ – Cruncher Jan 16 '14 at 20:55
  • \$\begingroup\$ /^[\w0-4]/ works, doesn't it? \$\endgroup\$ – John Dvorak Jan 16 '14 at 20:56
  • \$\begingroup\$ oh yeah sorry, it works for one character but gets worse and worse after that. If i remove the star and the $ though, it should work. It takes then half of all one character strings and all of the other strings that start with one of those characters. \$\endgroup\$ – Tim Seguine Jan 16 '14 at 20:56
  • 1
    \$\begingroup\$ @JanDvorak I know, that is exactly my point. You are matching too many one character strings. There are 62, and you match 57 of them. It does it that way in PCRE at least IIRC. Is there a dialect in which it doesn't? If there is, then I concede defeat. \$\endgroup\$ – Tim Seguine Jan 16 '14 at 21:08
9
\$\begingroup\$

6

/^[5-Z]/

In ASCII's order, there's 0-9 then A-Z then a-z So Half of the string begin with 5-Z, the other half doesn't.

\$\endgroup\$
  • \$\begingroup\$ Dang, my answer is a duplicate of this... \$\endgroup\$ – Justin Jan 16 '14 at 21:21
  • \$\begingroup\$ But thanks for posting it, it made me realize that the good answer didn't necessarily include half of the letters and half of the numbers. any 31-char subset of A-Za-z0-9 is fine \$\endgroup\$ – xem Jan 16 '14 at 21:24
  • 2
    \$\begingroup\$ @xem you are already making me regret changing my display name to my real name. :P \$\endgroup\$ – Tim Seguine Jan 16 '14 at 21:27
  • \$\begingroup\$ Oh god it's a real name? I'm sorry Tim. No more jokes. God bless you. I hope one day you'll forgive me. ='( \$\endgroup\$ – xem Jan 16 '14 at 21:30
  • \$\begingroup\$ @xem when I see you in hell ;) \$\endgroup\$ – Tim Seguine Jan 16 '14 at 21:32
5
\$\begingroup\$

6

/^[0-U]/

Ranges work for ascii values, so this matches half of the 62 combinations of first letters. Can match the empty string for one extra char:

/^[0-U]?/

For more confusion, this is also a solution:

/^[--U]/

Also this:

/^[-U]/

where the ascii 0 is right before the -.

\$\endgroup\$
  • \$\begingroup\$ /^[-U]/ is this considered 5 chars? Or still 6, just that one isn't printable? \$\endgroup\$ – Cruncher Feb 27 '14 at 14:42
  • \$\begingroup\$ @Cruncher One was unprintable. Otherwise, that would only match the characters - and U. \$\endgroup\$ – Justin Feb 27 '14 at 19:57
4
\$\begingroup\$

9 characters (not counting leaning toothpicks)

Modified mine from the comments:

 /^[A-Z0-4]/

It will match half of all 1 character strings. Every string of length greater than one starts with a one character string, half of which will match. So half match in total.

\$\endgroup\$
  • 3
    \$\begingroup\$ +1 for leaning toothpicks if I could (but that would be +2) \$\endgroup\$ – John Dvorak Jan 16 '14 at 21:07
2
\$\begingroup\$

24

You didn't ask for a max length.

So an infinity of strings can exist.

Half of infinity = infinity.

But that doesn't lead anywhere.

Anyway, I'd say that "half of this infinite number of strings" start with [A-Z0-4] and the other half with [a-z5-9]

That's why I consider this answer correct (inspired by Tim Seguine)

/^[A-Z0-4][A-Za-z0-9]*$/
\$\endgroup\$
  • \$\begingroup\$ My name is Tim by the way. ;) \$\endgroup\$ – Tim Seguine Jan 16 '14 at 21:06
  • \$\begingroup\$ I did say that you need half of them for every length. That being said, this is a correct solution. It's just the end of it is redundant. \$\endgroup\$ – Cruncher Jan 16 '14 at 21:06
  • \$\begingroup\$ But your regex isn't the shortest one by any means. Even if string anchors are required, not matching non-alphanumeric words isn't. \$\endgroup\$ – John Dvorak Jan 16 '14 at 21:06
  • 4
    \$\begingroup\$ Sorry for the typo Tam Seguine. \$\endgroup\$ – xem Jan 16 '14 at 21:07
  • 1
    \$\begingroup\$ By your logic, all that is needed is /^[A-Z0-4]/, but that is Tim's solution... \$\endgroup\$ – Justin Jan 16 '14 at 21:08

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.