CODEWITHSUNDEEP
regex
revo
revo

Reputation: 48711

Ordinal binary numbers

I wanna match ordinal binary numbers from 0 to 15, these numbers are written in a consecutive manner (no spaces between actually):

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

I need a very short way of using expressions to achieve this and it should match it as it is! I mean the matching domain! nothing more! I don't want to match a similar one:

0000 0010 0001 0011 0100 0110 0101 0111 1000 1001 1010 1011 1100 1101 1110 1111

Which I tried is ((00)[01]{2}){4}((01)[01]{2}){4}((10)[01]{2}){4}((11)[01]{2}){4}

I know that it's not accurate thus I asked it here.

Upvotes: 4

Views: 547

Answers (3)

revo
revo

Reputation: 48711

(\60){7}(100)(\2\1)(110)\3(101)01\2(111)\3(\2\4)\5\1\6\7\6\5\6

So I did it! Long time on this regular expression with 62 characters length, which is 2 characters less than the string itself.

Live demo: http://regex101.com/r/nN5uH0

Upvotes: 0

nhahtdh
nhahtdh

Reputation: 56809

This answer will serve as a hint to solve this riddle with much less characters that the string to be matched.

This solution relies heavily on the assumptions that all the binary numbers are fixed width (in this case is 4-bit).

Instead of directly counting the numbers up, we will try to compare 2 adjacent numbers.

Let us assume for now that we are at the beginning of a binary number (not somewhere arbitrary). We want the number in front to compare strictly less than the number behind.

To compare 2 binary numbers with fixed width, we can just go from left to right and remove similar digit, until all digits have been removed (equal) or there is a difference. Since the number in front is strictly less, there must be a difference, where the number in front is 0 and the number behind is 1 at the same bit. We can write a zero-width look-ahead assertion for this:

(?=([01]*)0[01]* (\1)1)

(The parentheses around \1 is needed, at least in JavaScript, to prevent formation of octal escape sequence \11).

To remove the assumption that we are at the beginning of a binary number, we only need to add anchors, and consume characters so that we end up at the beginning of the next number.

^(?=([01]*)0[01]* (\1)1)....[ ]

Since we have already assert the increasing order of the numbers, we only need to assert the number of binary numbers through the repetition.

^(?:(?=([01]*)0[01]* (\1)1).... ){15}1111$

This problem can be extended to asserting a string consisting of 2^n fixed-width n-bit-wide binary string is strictly increasing. It can also be used to assert a sequence of fixed-width binary number is increasing. The technique may also be applied to asserting words listed in lexicographic order or not, although the regex will be quite long.

Upvotes: 1

David Grayson
David Grayson

Reputation: 87396

It sounds like you want a short regex that matches the given string, but does not match any string of the same form where the binary numbers are reordered. This regex does not satisfy that, but it at least solves the "Long Count" puzzle from http://regex.alf.nu :

((\d+)0 \2[1] ?){8}

Upvotes: 3

Related Questions