Cross-matching regular expressions

21

0

Your task here is to write two regular expressions, each of which matches the other one but does not match itself.

Both regular expressions should have this form:

/pattern/optional-flags

This is also the form in which they should be matched.

The shortest solution wins. The solution length is counted as the sum of characters in both regular expressions including slashes and flags.

Use a regex syntax standard of your choice, or specify a programming language, when it makes a difference.

Have fun!

GOTO 0

Posted 2014-03-02T15:15:12.037

Reputation: 752

Does the regex also have to match the slashes and flags of the other regex? – ProgramFOX – 2014-03-02T15:30:33.577

@ProgramFOX yes, I added a line to make it clear. – GOTO 0 – 2014-03-02T15:35:17.113

Can you define match? i.e. does the regex /a/ match abc? – The Guy with The Hat – 2014-03-02T20:05:55.100

2@TheGuywithTheHat well, I think so, unless you choose a language that imposes certain restrictions, like the need to match the whole string. Does this address your concern? – GOTO 0 – 2014-03-02T20:21:37.743

1To be clear: I assume that the use of different delimiters (as permitted by e.g. PHP PCRE) is not permitted? (I.e. no submitting /^%/ and %^/%) – Peter Taylor – 2014-03-03T09:27:14.117

@PeterTaylor you're right. There are ways to create a regular expression that don't even need you to use a delimiter. The syntax requirements are there to keep the rules simple and clear. They're not just arbitrary limitations. – GOTO 0 – 2014-03-03T10:02:06.213

This is very quine-like, should it be tagged quine? – Cruncher – 2014-03-03T18:56:12.603

@Cruncher, the only output produced is a couple of Booleans. It doesn't fit the current definition of the [tag:quine] tag, and that definition fits pretty well with what I understand to be the standard meaning of the term. – Peter Taylor – 2014-03-03T19:08:03.087

@PeterTaylor That's generally why we call them variants. If I had a program that returned true when the input was its own source, and false otherwise, that would be very quine-like without ever fitting the output requirements of a true quine. In fact the question exists http://codegolf.stackexchange.com/questions/11370/write-the-shortest-self-identifying-program-a-quine-variant and is tagged quine.

– Cruncher – 2014-03-03T19:11:49.933

Answers

7

PRCE with the A modifier: 9 chars

/A$/
/.A/A

Although this is a variant on Doorknob's /modifier$/ answer, I think this innovation qualifies it as a separate answer rather than a comment on his: the modifier does double-duty. Rather than being there solely for the other regex to match, it anchors.

The first regex matches any string ending in a literal A. The second regex matches any string whose second character is a literal A, using an anchor-to-start flag.

Online demo

Peter Taylor

Posted 2014-03-02T15:15:12.037

Reputation: 41 901

3To beat this requires only four non-delimiter chars, and since // matches anything that means that each of the regexes can have at most three non-delimiter chars. Using PHP PCRE there are 73339 non-self-matching regexes within that constraint, and exhaustive checking of the pairs whose length is less than 10 (on the order of 32Mpairs rather than 5.7Gpairs because most of them are 5 chars including delimiters) turns up this solution and no others. I therefore claim that it is optimal for that particular regex engine. – Peter Taylor – 2014-03-03T16:11:56.267

18

4+6=score of 10

First regex:

/i$/

Second regex:

/^.i/i

Hooray for flag abuse! :-P

The first one matches anything that ends with i (therefore, any regex with the i flag).

The second one matches anything with a second character of i.

Alternative version: /i$/g and /g$/i.

Doorknob

Posted 2014-03-02T15:15:12.037

Reputation: 68 138

3Another variation would be /x.$/ and /^.x/ for a bunch of x – shiona – 2014-03-02T21:52:25.163

Or /i$/ and /\/$/i – Peter Taylor – 2014-03-02T23:29:52.417

Or /i$/ and /i\$/i – Peter Taylor – 2014-03-03T08:16:49.370

6

JavaScript regexes, score: 18

First regex:

/^[^a]+$/

Second regex:

/^[^b]+$/

JavaScript test:

var regex1 = "/^[^a]+$/";
var regex2 = "/^[^b]+$/";
alert(/^[^a]+$/.test(regex2)); // true: regex1 matches regex2
alert(/^[^b]+$/.test(regex1)); // true: regex2 matches regex1
alert(/^[^a]+$/.test(regex1)); // false: regex1 doesn't match regex1
alert(/^[^b]+$/.test(regex2)); // false: regex2 doesn't match regex2

Test online: http://jsfiddle.net/99Sx6/

ProgramFOX

Posted 2014-03-02T15:15:12.037

Reputation: 8 017

5

Ruby regex, 15

Regular expressions:

/.{9}/
/^.{06}$/

Just counting characters...

Online version

r1 = '/.{9}/'
r2 = '/^.{06}$/'

p r1 =~ /^.{06}$/ #0:   r2 matches r1
p r2 =~ /.{9}/    #0:   r1 matches r2
p r1 =~ /.{9}/    #nil: r1 doesn't match r1
p r2 =~ /^.{06}$/ #nil: r2 doesn't match r2

David Herrmann

Posted 2014-03-02T15:15:12.037

Reputation: 1 544

5

4 + 6 = 10

First regex:

/i$/

Second regex:

/\/$/i

i$ matches something that ends with i, the second one. /$ matches something that ends with /, the first one.

Justin

Posted 2014-03-02T15:15:12.037

Reputation: 19 757

2Dupe of a comment I posted to Doorknob's answer. – Peter Taylor – 2014-03-03T08:09:11.453

@PeterTaylor Didn't notice the comments until now. These were independent discoveries. – Justin – 2014-03-03T18:11:49.683

Yeah, I independently discovered shiona's version too. – Peter Taylor – 2014-03-03T19:09:00.893

3

5 + 5 = 10

Regex #1:

/0.$/

Regex #2:

/^.0/

The 0s in both regexes can be replaced with any non-metacharacter and the regex still works.

0.$ matches anything whose second last character is 0, and ^.0 matches anything whose second character is 0.

Justin

Posted 2014-03-02T15:15:12.037

Reputation: 19 757

2The first pair aren't valid regexes: you need to escape the /es. The alternative is a dupe of a comment on Doorknob's answer. – Peter Taylor – 2014-03-03T08:13:16.230

2

JavaScript regexes, score: 13

First regex:

/\d/

Second regex:

/^[^0]+$/

Explanation: the first regex matches everything that contains a digit, and the second regex matches everything that doesn't contain a 0.

JavaScript test:

var regex1 = "/\d/";
var regex2 = "/^[^0]+$/";
alert(/\d/.test(regex2)); // true: regex1 matches regex2
alert(/^[^0]+$/.test(regex1)); // true: regex2 matches regex1
alert(/\d/.test(regex1)); // false: regex1 doesn't match regex1
alert(/^[^0]+$/.test(regex2)); // false: regex2 doesn't math regex2

Test online: http://jsfiddle.net/5VYjC/1/

ProgramFOX

Posted 2014-03-02T15:15:12.037

Reputation: 8 017

2

12 chars ;) JS regex

/\d/
/0?\/$/g

Andrew Templeton

Posted 2014-03-02T15:15:12.037

Reputation: 261

2

Score: 5 + 5 = 10

Took me half-an-hour to figure out but I am really happy that I did :)

1st is: /j.$/

2nd is: /^.j/

The 1st matched a j occurring in the second position starting from the right. The 2nd matches a j occurring at the second-position starting from left.

I haven't tested but I think that these RegExs are really versatile as the j can be replaced with any \w character (or more?) and still should work fine.

P.S. This should (hopefully) work in any language. Though, if it does not work in any, please inform in the comments below :)

Test

Gaurang Tandon

Posted 2014-03-02T15:15:12.037

Reputation: 837

And I figure out now that @Quiccunx has already posted the same version as mine. I am really sorry Quiccunx and if it shall please any, I shall delete my answer. – Gaurang Tandon – 2014-03-04T13:07:29.293

1

PCRE using modifier x: 11 chars

/\s/
/ s.$/x

The first matches any string with a whitespace character, but doesn't contain whitespace. The second contains whitespace, but it's ignored because of the x modifier; it matches any string whose penultimate character is s.

PCRE and other engines using character classes: 11 chars

/\w+w/
/\Ww/

The first matches any string with a "word" character (letter, digit, underscore) followed by a literal w; the second matches any string with a non-word character followed by a literal w.

PCRE and other engines using character classes and word boundary anchor: 11 chars

/\w\w/
/\bw/

The first matches any string with two consecutive "word" characters; the second any string with a non-word character or start of string followed by a literal w.

Peter Taylor

Posted 2014-03-02T15:15:12.037

Reputation: 41 901

-1

ECMAScript (11 bytes):

/^\1?d/
/\d/

Other REGEXP Engines (14 bytes):

/^\\\\1?d/
/\d/

The 1st matches \d[..] or \1d[..].

The second matches any string with a number.

EDIT:

Originally, this answer was posted as being compatible with all engines, but it was proven to be wrong.

There was a problem with references to the capturing groups (for example, in php).

Ismael Miguel

Posted 2014-03-02T15:15:12.037

Reputation: 6 797

Many regex engines take the regex without surrounding slashes, but the question is quite clear in requiring them to be counted. – Peter Taylor – 2014-03-02T23:43:44.520

I am not counting it as an answer. Let me add the note for that. – Ismael Miguel – 2014-03-02T23:45:06.407

1@PeterTaylor I added the note. The Apache version is there just because. – Ismael Miguel – 2014-03-02T23:50:20.300

Hang on: in what engines does the first one parse with \1 not interpreted as a back-reference? – Peter Taylor – 2014-03-02T23:51:41.930

Depending on the way you use it. In php, for example, if you put inside "/^\1?d/" you will have trouble, but if you do '/^\1?d/', then it's fine. The quotes make a huge difference when the code is interpreted. – Ismael Miguel – 2014-03-02T23:53:24.983

No: in PHP if you do '/^\1?d/' you get preg_match(): Compilation failed: reference to non-existent subpattern at offset 5. – Peter Taylor – 2014-03-03T08:16:03.337

I have edited the answer and added a new solution for PHP. – Ismael Miguel – 2014-03-03T09:45:41.047

Doesn't seem to work in ECMAScript either: http://fiddle.jshell.net/e9tWs/

– Peter Taylor – 2014-03-03T09:51:45.973

The example code doesn't load on chrome and opera 12-16 on windows xp. – Ismael Miguel – 2014-03-03T10:14:36.930