1
\$\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.

Improve this question
\$\endgroup\$
12
  • \$\begingroup\$ /^[A-Z0-4]*$/ works, doesn't it? \$\endgroup\$
    – Tim Seguine
    Jan 16, 2014 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, 2014 at 20:55
  • \$\begingroup\$ /^[\w0-4]/ works, doesn't it? \$\endgroup\$
    – John Dvorak
    Jan 16, 2014 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, 2014 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, 2014 at 21:08

4 Answers 4

Reset to default
10
\$\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.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ Dang, my answer is a duplicate of this... \$\endgroup\$
    – Justin
    Jan 16, 2014 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, 2014 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, 2014 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, 2014 at 21:30
  • \$\begingroup\$ @xem when I see you in hell ;) \$\endgroup\$
    – Tim Seguine
    Jan 16, 2014 at 21:32
5
\$\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.

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ +1 for leaning toothpicks if I could (but that would be +2) \$\endgroup\$
    – John Dvorak
    Jan 16, 2014 at 21:07
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 -.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ /^[-U]/ is this considered 5 chars? Or still 6, just that one isn't printable? \$\endgroup\$
    – Cruncher
    Feb 27, 2014 at 14:42
  • \$\begingroup\$ @Cruncher One was unprintable. Otherwise, that would only match the characters - and U. \$\endgroup\$
    – Justin
    Feb 27, 2014 at 19:57
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]*$/
Improve this answer
\$\endgroup\$
16
  • \$\begingroup\$ My name is Tim by the way. ;) \$\endgroup\$
    – Tim Seguine
    Jan 16, 2014 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, 2014 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, 2014 at 21:06
  • 5
    \$\begingroup\$ Sorry for the typo Tam Seguine. \$\endgroup\$
    – xem
    Jan 16, 2014 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, 2014 at 21:08

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.