Cops and Robbers: Reverse Regex Golf

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.

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
• I wonder how many lines of code we've collectively written constructing these puzzles and attempting to solve them... and whether it would be worthwhile to collect it all and stick it on github when we're done. Everybody could contribute whatever they've got (encoders, decoders, solvers both successful and unsuccessful), as-is, uncommented and hackish though they may be. With a README if you feel like it. It would be like our conference proceedings.
– user15244
Oct 25, 2014 at 0:22
• While there aren't any new answers being posted anymore, it may be worth "closing" the question at some point. Otherwise, it may be possible for someone to answer when the interest has died down, and stand uncontested for a longer period. Oct 27, 2014 at 3:51
• @nneonneo Hm, I don't usually like to close my challenges, but in this case it may be a good idea. I even think the last 3 entries already benefited from getting less attention. I'll set a deadline for Friday. Oct 27, 2014 at 10:18
• @MartinBüttner: I think it will have to be standard for cops & robbers challenges to have an expiry date. Challenges only stay interesting for so long. (For the record, this challenge is probably still my personal favorite, but I may be biased in that opinion :) Dec 16, 2014 at 0:15

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+$

• Match: aaaaaaaaaaaaa,aaaa,aaa,aa,aaaaaaaaaaaaa. Non-match: aaaabaaacaaadaaa. Oct 15, 2014 at 8:14
• Longer: Match: regex101.com/r/dT2rX8/1 Non-match: aaaabaaacaaadaaa Oct 15, 2014 at 8:18
• @user23013 You're on a roll! It wasn't supposed to be that easy, but I overlooked a few things. I don't want to post a third submission, but I'll edit this one with what I hope is a "correct" version this time. Give it a shot if you feel like it.
– Ell
Oct 15, 2014 at 8:35
• Shorter: regex101.com/r/lO1kX7/1 aaaabaaacaaadaaa. Longer: regex101.com/r/fD3qB4/1 aaaabaaacaaadaaa. Oct 15, 2014 at 9:50
• @Ell Posting a third submission would not have been a problem. (And feel free to do so if you come up with something else.) Oct 15, 2014 at 9:52

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.

• Tested on pythonregex.com. Oct 17, 2014 at 3:18
• I think you can call it 145245, you don't need the newline at the end.
– user15244
Oct 17, 2014 at 3:28
• @WumpusQ.Wumbley: thanks, removed the newline Oct 17, 2014 at 3:39
• Non-match: 1657114133410330066437310300651114626477107270715027765071217477765155062115727346312156431331022432571707004067437201014346506056771002007472602676067730610061613313533367043345632652200101037575653036745227714523510655101775154755604257220747261564732730 Match: YouMessedUpMostOfYourClausesOnlyMatch255Characters
– user15244
Oct 17, 2014 at 4:59
• Ahahahah, and that's why we should test things more carefully.... Oct 17, 2014 at 5:17

[^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. • Yes. Uh... wait. When did you add the 256 character maximum? Was that there all the time? – COTO Oct 14, 2014 at 18:49 • No it wasn't, I added it 4 hours ago, see the second comment on the question. Sorry about the confusion. Oct 14, 2014 at 18:54 • Decided to undelete this since people might have fun cracking it. Readers should note that this submission is not to spec (the key is vastly longer than 256 chars), hence it won't count towards a cracking score. The key can be trivially described, however. – COTO Oct 14, 2014 at 21:20 • Match: aaaaaaaaaaaaaaaa -- Non-match: aaaaaaaaaaaaaaaaa Oct 14, 2014 at 21:55 • Sorry but: "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." ;) Oct 14, 2014 at 22:47 Ruby flavor, 22 bytes [cracked] ^(?!(.+)\1)[$\\$]{256}$


Not so much obfuscated but a bit difficult to satisfy.

• Match: [] followed by 254 ['s. No match: empty string
– user15244
Oct 15, 2014 at 1:26
• Sorry I didn't make both of my strings in the 16..256 range. Retry: Match: [] followed by 254 ['s. No match: 16 ['s
– user15244
Oct 15, 2014 at 2:20
• Oops, that did not work the way I thought it did. I'll post a modification as a separate answer to avoid messing with the score. Oct 15, 2014 at 13:59

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++

• Match: regex101.com/r/kH2oX7/1 Non-match: aaaabaaacaaadaaa. Standard loophole? Oct 15, 2014 at 7:40
• Damn! I thought this can at least hold on for a few hours. Oct 15, 2014 at 8:07
• I found it because it looks too impossible. And the online tester highlighted \11. Oct 15, 2014 at 8:24
• @user23013 Standard loophole because of Unicode? No, I'd say it's fine. This is an obfuscation contest, and I deliberately didn't disallow Unicode. Oct 15, 2014 at 9:45

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/

• Match: aa\^-^\aa\^-^\aa, Non-match: aa\^-^\aa\^-b\aa Oct 16, 2014 at 21:24

Ruby-flavored, 32 bytes [cracked]

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

• Match: aaaahaaaahhaaaahaaahhaaaahhahaaaahaaahhaaaahaahhaaaahhaahaaaahaahhaaaahaaahhaaaahahhaaaahhaaahaaaahahhaaa! copy at rubular.com/r/YPgdPbBB7U No match: heheheheheheheh!
– user15244
Oct 16, 2014 at 16:30

/^(((\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: • @MartinBüttner Actually, it's 75 :/ and I had the regex with some garbage on the same file, and checked the length of the whole file and not the selected length. I just updated with the right count. And all the chars are printable ascii chars. Oct 16, 2014 at 11:24 • Alright, I updated the count. Oct 16, 2014 at 11:26 • Match : \xf4\x65\xf4\x65\x80\x80\xf4\x65\xf4\x65\x45\x80\xf4\x65\x0A\xf4\x65\x10\xf4\xf4\\xf4\x80\xf4\x65 (JavaScript string with escapes) -- Non-match: RegExCopsandRobbers Oct 16, 2014 at 12:52 • Is it actually possible to enter that string in regex101? With the \x10 (Ctrl-P) in it? – user15244 Oct 16, 2014 at 12:55 • @WumpusQ.Wumbley You can enter it into your browser's console as a string and copy the result into regex101. Oct 16, 2014 at 12:57 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
)\$

• >____< Today is not going well for me.
– COTO
Oct 14, 2014 at 22:49
• As in your previous submission, the key is longer than 256 bytes, yes? Oct 14, 2014 at 22:55
• Yes. It's identical, technically non-spec. Martin gave you credit for the previous one. The solution can be described trivially, so it seems to still be "in the spirit" of the limit, which (as I understand it) was so that the solutions could be expressed in a matter of a few characters.
– COTO
Oct 14, 2014 at 22:57
• Match: a repeated 556 times -- Non-match: a repeated 557 times Oct 14, 2014 at 22:59
• I suppose he gave me credit because I found a key that satisfies the spec. Oct 14, 2014 at 23:01

JavaScript, 78 bytes

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