0
\$\begingroup\$

Your task is to create a regular expression that matches most binary numbers with an even number of 0s and an odd number of 1s (e.g. "101100011").

The full criteria for the regex are:

  • matches 90% or more of all binary numbers between 0 and 11111111 with even number of 0s and an odd number of 1s,
  • doesn't match 90% or more of all binary numbers between 0 and 11111111 with odd number of 0s or an even number of 1s,
  • works in most common programming languages.

Ideally, it should be short and creative.

The input string always has a length that is greater than 1, less than infinity, and only contains 1s and 0s.

I will upvote any answer that seriously attempts to match the above criteria. Once the activity around this question dies down, I'll accept the highest-voted answer that is at least only 1.333... times the length of the shortest answer.

|improve this question
\$\endgroup\$

closed as unclear what you're asking by Howard, Darren Stone, Peter Taylor, Iszi, Johannes Kuhn Dec 23 '13 at 23:36

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ stackoverflow.com/q/20485486/1223693 \$\endgroup\$ – Doorknob♦ Dec 23 '13 at 14:13
  • \$\begingroup\$ @DoorknobofSnow shhhhh \$\endgroup\$ – The Guy with The Hat Dec 23 '13 at 14:14
  • 3
    \$\begingroup\$ Maybe I don't understand the problem, but there are none which can match. All binaries you assume as input are exactly 8 bits long (your examples indicate that leading zeros are provided) and thus odd+even cannot be true at all. \$\endgroup\$ – Howard Dec 23 '13 at 15:55
  • 1
    \$\begingroup\$ Moreover: short and creative doesn't sound very objective. If it is popularity-contest please tag it accordingly. (note: I don't think that this is a good example of a popularity-contest). \$\endgroup\$ – Howard Dec 23 '13 at 15:56
  • 1
    \$\begingroup\$ I think there is a missing specification of "without leading zeroes" here, which would allow for 8-bit binary numbers <1111101 to match the target pattern. \$\endgroup\$ – Iszi Dec 23 '13 at 21:20
6
\$\begingroup\$

The following regex

(?=^1*(01*0)*1*$)^.(..)*$

works in many languages. It performs a perfect match for any binary of arbitrary length.

Basically, it consists of two parts which are joined via and by using a lookahead pattern:

  • ^1*(01*0)*1*$ matches if an even number of zeros is provided.
  • ^.(..)*$ tests for an odd number of digits in total.

The test run can be seen here.

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

80 characters long

^(?:(?(1)|(1))|0101|1010|(?:1{2})+|(?:0{2})+|0(?:1{2})+0|1(?:0{2})+1|)+(?(1)|a)$

Doesn't match some numbers that have an odd number over four 1s in a row, e.g 01111101

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ so does this match exactly 90% of numbers between 0 and 0b11111111? (I tried to test, but apparently this regex doesn't work in Ruby.) \$\endgroup\$ – Doorknob♦ Dec 23 '13 at 14:19
  • \$\begingroup\$ @DoorknobofSnow Whoops, edited question. \$\endgroup\$ – The Guy with The Hat Dec 23 '13 at 14:21
  • \$\begingroup\$ Ah, okay, well in that case, why the {2}s? Repeating the previous digit would be shorter. \$\endgroup\$ – Doorknob♦ Dec 23 '13 at 14:22
  • \$\begingroup\$ And what's with the a at the end? \$\endgroup\$ – Doorknob♦ Dec 23 '13 at 14:23
  • \$\begingroup\$ @DoorknobofSnow I don't quite know why I put those {2}s there... The a makes the regex fail if the the first capturing group doesn't capture anything, which should only happen if there is an even number of 1s. \$\endgroup\$ – The Guy with The Hat Dec 23 '13 at 14:28

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