Cops and Robbers: Reverse Regex Golf

Question

Note: This challenge is now closed. Any future cops' submission will not be considered for the accepted answer. This is to ensure that no one can post a very simple regex in the future that only remains uncracked because no one is interested in the challenge any more.

The Cops' Challenge

You are to write a short, obfuscated regex, satisfying the following spec:

• You may choose any flavour that is freely testable online. There's a good list of online testers over on StackOverflow. In particular, Regex101 should be good to get you started, as it supports PCRE, ECMAScript and Python flavours. You can increase the timeout limit by clicking on the wrench in the top right corner if necessary. Please include the tester you choose in your answer.

  If no suitable tester is available for your flavour of choice, you may also use an online interpreter like ideone and write a little script in the host language which people can use to test your submission.

• You may use any feature of that flavour, which does not directly invoke the host language (like Perl's code evaluation features).
• Likewise, you may use any modifiers (if your flavour has them), unless they result in code evaluation.
• Your regex must accept at least one string S and reject at least one string T, each of which is at least 16 and not more than 256 characters in length, in a reasonable amount of time (not significantly longer than a minute). S and T may contain Unicode characters that aren't ASCII, as long as there's a way to enter them into the online tester. Any such pair of strings will be a key to your submission.
• Your regex may take arbitrarily long on any other input.

The core of the challenge is to craft a regex whose key is hard to find. That is, it should either be hard to tell which string it doesn't match or which string it matches (or potentially even both if the regex takes days to finish on all but the key's strings).

The Robbers' Challenge

All users, including those who have submitted their own regex(es), are encouraged to "crack" other submissions. A submission is cracked when one of its keys is posted in the associated comments section.

Important: Make sure that both strings you post are between 16 and 256 characters inclusive, even if almost any string could be used be used for one part of the key.

If a submission persists for 72 hours without being modified or cracked, the author may reveal a valid key by editing it into a spoiler-tag in his answer. This will make his answer "safe", i.e. it can no longer be cracked.

Only one cracking attempt per submission per user is permitted. For example, if I submit to user X: "Your key is 0123456789abcdef/fedcba9876543210." and I'm wrong, user X will disclaim my guess as incorrect and I will no longer be able to submit additional guesses for that submission, but I can still crack other submissions (and others can still crack that submission).

Cracked submissions are eliminated from contention (provided they are not "safe"). They should not be edited or deleted. If an author wishes to submit a new regex, (s)he should do so in a separate answer.

Do not crack your own submission!

Note: For long strings in the comments without spaces, SE inserts manual line breaks in the form of two Unicode characters. So if you post a key in backticks which is so long that it line-wraps between non-space characters, it won't be possible to copy the key straight back out into a regex tester. In this case, please provide a permalink to the relevant regex tester with the cop's regex and your key - most testers include this feature.

Scoring

A cop's score will be the size of their regex in bytes (pattern plus modifiers, potential delimiters are not counted), provided that it hasn't been cracked. The lowest score of a "safe" submission will win.

A robber's score will be the number of submissions they cracked. In the event of a tie, the total byte size of submissions they cracked will be used a tie-breaker. Here, highest byte count wins.

As stated above, any cop may participate as a robber and vice-versa.

I will maintain separate leaderboards for the two parts of the challenge.

Leaderboards

Last update: 19/10/2014, 20:33 UTC

Cops:

Submissions in italics are not yet safe.

1. nneonneo, 841 bytes
2. Wumpus Q. Wumbley, 10,602 bytes
3. Sp3000, 52,506 bytes
4. user23013, 53,884 bytes
5. nneonneo, 656,813 bytes

Robbers:

1. user23013, Cracked: 11, Total Size: 733 + 30 + 2,447 + 71 + 109 + 121 + 97 + 60 + 141 + 200,127 + 7,563 = 211,499 bytes
2. nneonneo, Cracked: 10, Total Size: 4,842 + 12,371 + 150 + 3,571 + 96 + 168 + 395 + 1,043 + 458 + 17,372 = 40,466 bytes
3. Wumpus Q. Wumbley, Cracked: 6, Total Size: 22 + 24 + 158 + 32 + 145,245 + 145,475 = 290,956 bytes
4. Dennis, Cracked: 2, Total Size: 70 + 73 = 143 bytes
5. harius, Cracked: 1, Total Size: 9,998 bytes
6. g.rocket, Cracked: 1, Total Size: 721 bytes
7. stokastic, Cracked: 1, Total Size: 211 bytes
8. Sp3000, Cracked: 1, Total Size: 133 bytes
9. TwiNight, Cracked: 1, Total Size: 39 bytes

Answer 1

Perl flavor, 109 [cracked]

The previous submission turned out easier than I intended. This one should be a little more challenging, though the short version is still very much brute-forcible.

^([^,]+),(?!\1)([^,]{2,}),(?!\1|\2+,)([^,]{2,}),(?!\1|(?:\2+|\3+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)\1+$

And a longer version, not part of the challenge:

^([^,]+),(?!\1)([^,]{2,}),(?!\1|\2+,)([^,]{2,}),(?!\1|(?:\2+|\3+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+|\5+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+|\5+|\6+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+|\5+|\6+|\7+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$

---

EDIT: The above version turned out too simple as well. Here's a final attempt to make this more challenging.

Perl flavor, 121 [cracked]

Short version:

^([^,]+),(?!\1)([^,]{2,}),(?=\2)(?!\1|\2+,)([^,]{2,}),(?=\3)(?!\1|(?:\2+|\3+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)\1+$

Long version:

^([^,]+),(?!\1)([^,]{2,}),(?=\2)(?!\1|\2+,)([^,]{2,}),(?=\3)(?!\1|(?:\2+|\3+),)([^,]{2,}),(?=\4)(?!\1|(?:\2+|\3+|\4+),)([^,]{2,}),(?=\5)(?!\1|(?:\2+|\3+|\4+|\5+),)([^,]{2,}),(?=\6)(?!\1|(?:\2+|\3+|\4+|\5+|\6+),)([^,]{2,}),(?=\7)(?!\1|(?:\2+|\3+|\4+|\5+|\6+|\7+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$

Answer 2

Python, 145245 bytes [cracked]

Credit to sp3000 & COTO for the idea

Uncompressed Pastebin copy: http://pastebin.com/jtp82dY9

EDIT: I screwed up the regex generator and made most of my clauses invalid. Congratulations Wumpus for finding and exploiting it :) I've submitted a fixed version, so I'll explain how these submissions work after they are cracked or the time-limit expires.

Answer 3

JS-Compatible RegEx - 70 bytes [cracked]

Auch, I'm bad at this. :P

[^a]|^(a{0,16}|(?:(?=((a{9,275})\1\2\3))\2)+(a?){6}|(a{3181}){902}a+)$

Resolves on virtually any string instantaneously. Tested on RegExr.

Answer 4

Ruby flavor, 22 bytes [cracked]

^(?!(.+)\1)[\[\\\]]{256}$

Not so much obfuscated but a bit difficult to satisfy.

Answer 5

PCRE, 71 [cracked]

(((?!\3)(1++)​\3){5,})​(((1++)​\3\6\2(?!\3)(?=1\6)){5,}1+)‮1\11

There are 3 zero-width spaces (after both (1++)s and between the two big capture groups), and a right-to-left override before the last 4 characters so the last 4 characters are actually 1\11 (literal 1 then horizontal tab). Once you notice those all you have to do is put zero-width spaces at the right places (which I thought would be quite a challenge in itself).

In hindsight I should have used 1+ instead of 1++

Answer 6

ECMAScript flavor, 39 bytes [cracked :(]

^.(.)\\\^-\^\\.(.)\\\^-\^\\.(?=\1*$)\2$

My first regex, hopefully it's not too easy. You can test it at http://www.regexr.com/

Answer 7

Ruby-flavored, 32 bytes [cracked]

^(?!.*((.).+)\1\2)[ah]{105}(?=!a*)

Answer 8

PHP and Javascript compatible (73 bytes + delimiters)[cracked]:

/^(((\xf4)\x65)\2(\x80)(\4\2))((\2(\x45\5)\x0A)(\2\x10\3))(\3(\\xf4\4)\2)$/

This was tested using the website http://regex101.com/ and http://www.gethifi.com/tools/regex .

Only matches one string. Have fun finding which!

To back up my answer, here is the last sentence of OP's comment, explaining the challenge:

In most cases, this means, either your regex accepts pretty much nothing except some non-obvious string, or it accepts pretty much everything except some non-obvious string. Cops and Robbers: Reverse Regex Golf

Please, don't crack it!

---

Well, @Dennis doesn't play by the rules and decided to break it.

Here is a printscreen of the matching string, using FireFox:

Answer 9

JS-Compatible RegEx - 70 bytes [cracked]

[^a]|^(a{0,25}|(?:(?=((a{9,275})\1\2\3))\2)+(a?){6}|(a{3181}){902}a+)$

Resolves on virtually any string instantaneously. Tested on RegExr. Identical to the previous 70 byte submission except an error is fixed.

Broken for some reason. :(

Intended functionality:

[^a]                   # match any string containing anything except "a"s
 | or
^(
    a{0,25}            # match any string of 25 or fewer "a"s
 | or
    (?:                # block matches (or _should_ match) any string of "a"s with
                       # length n such that n ≢ {0,1,2,3,4,5,6} (mod x)
                       # for all x ∈ [9:275].  The 3 smallest n that satisfy this property
                       # are n = 7, n = 1,346,407 and n = 2,914,919.
                       # Strings of length < 26 are matched by the first alternate, and
                       # strings of length > 2,869,262 are matched by the third alternate,
                       # hence the sole key should be 1,346,407.

                       # Capture groups \1 and \2 are undefined and should be empty in
                       # the \1\2\3 sequence.
                       # The problem is with the lookahead. It seems to be making
                       # the parser treat a{9,275} as atomic in some cases and not in
                       # others ???
        (?=((a{9,275}) \1\2\3))\2
    )+
    (a?){6}
 | or
    (a{3181}){902}a+   # match any string of 2,869,263+ "a"s
)$

Answer 10

JavaScript, 78 bytes

^(([a-z])*[0-2]?[7-9]+[3-6]*^{5892}+^x?[A-Z]?[A-G]*)^{6Q}*^{2}+{\{\}}*{\[\]}+