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