76
\$\begingroup\$

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
\$\endgroup\$
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – user15244 Oct 25 '14 at 0:22
  • \$\begingroup\$ 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. \$\endgroup\$ – nneonneo Oct 27 '14 at 3:51
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Oct 27 '14 at 10:18
  • \$\begingroup\$ @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 :) \$\endgroup\$ – nneonneo Dec 16 '14 at 0:15

40 Answers 40

1 2
3
\$\begingroup\$

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+$
\$\endgroup\$
  • 1
    \$\begingroup\$ Match: aaaaaaaaaaaaa,aaaa,aaa,aa,aaaaaaaaaaaaa. Non-match: aaaabaaacaaadaaa. \$\endgroup\$ – jimmy23013 Oct 15 '14 at 8:14
  • \$\begingroup\$ Longer: Match: regex101.com/r/dT2rX8/1 Non-match: aaaabaaacaaadaaa \$\endgroup\$ – jimmy23013 Oct 15 '14 at 8:18
  • \$\begingroup\$ @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. \$\endgroup\$ – Ell Oct 15 '14 at 8:35
  • 1
    \$\begingroup\$ Shorter: regex101.com/r/lO1kX7/1 aaaabaaacaaadaaa. Longer: regex101.com/r/fD3qB4/1 aaaabaaacaaadaaa. \$\endgroup\$ – jimmy23013 Oct 15 '14 at 9:50
  • \$\begingroup\$ @Ell Posting a third submission would not have been a problem. (And feel free to do so if you come up with something else.) \$\endgroup\$ – Martin Ender Oct 15 '14 at 9:52
3
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ Yes. Uh... wait. When did you add the 256 character maximum? Was that there all the time? \$\endgroup\$ – COTO Oct 14 '14 at 18:49
  • \$\begingroup\$ No it wasn't, I added it 4 hours ago, see the second comment on the question. Sorry about the confusion. \$\endgroup\$ – Martin Ender Oct 14 '14 at 18:54
  • \$\begingroup\$ 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. \$\endgroup\$ – COTO Oct 14 '14 at 21:20
  • 2
    \$\begingroup\$ Match: aaaaaaaaaaaaaaaa -- Non-match: aaaaaaaaaaaaaaaaa \$\endgroup\$ – Dennis Oct 14 '14 at 21:55
  • \$\begingroup\$ 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." ;) \$\endgroup\$ – Martin Ender Oct 14 '14 at 22:47
2
\$\begingroup\$

Ruby flavor, 22 bytes [cracked]

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

Not so much obfuscated but a bit difficult to satisfy.

\$\endgroup\$
  • \$\begingroup\$ Match: [] followed by 254 ['s. No match: empty string \$\endgroup\$ – user15244 Oct 15 '14 at 1:26
  • 2
    \$\begingroup\$ Sorry I didn't make both of my strings in the 16..256 range. Retry: Match: [] followed by 254 ['s. No match: 16 ['s \$\endgroup\$ – user15244 Oct 15 '14 at 2:20
  • \$\begingroup\$ 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. \$\endgroup\$ – histocrat Oct 15 '14 at 13:59
2
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Match: regex101.com/r/kH2oX7/1 Non-match: aaaabaaacaaadaaa. Standard loophole? \$\endgroup\$ – jimmy23013 Oct 15 '14 at 7:40
  • \$\begingroup\$ Damn! I thought this can at least hold on for a few hours. \$\endgroup\$ – TwiNight Oct 15 '14 at 8:07
  • \$\begingroup\$ I found it because it looks too impossible. And the online tester highlighted \11. \$\endgroup\$ – jimmy23013 Oct 15 '14 at 8:24
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Oct 15 '14 at 9:45
2
\$\begingroup\$

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/

\$\endgroup\$
  • 2
    \$\begingroup\$ Match: aa\^-^\aa\^-^\aa, Non-match: aa\^-^\aa\^-b\aa \$\endgroup\$ – TwiNight Oct 16 '14 at 21:24
2
\$\begingroup\$

Ruby-flavored, 32 bytes [cracked]

^(?!.*((.).+)\1\2)[ah]{105}(?=!a*)
\$\endgroup\$
  • 2
    \$\begingroup\$ Match: aaaahaaaahhaaaahaaahhaaaahhahaaaahaaahhaaaahaahhaaaahhaahaaaahaahhaaaahaaahhaaaahahhaaaahhaaahaaaahahhaaa! copy at rubular.com/r/YPgdPbBB7U No match: heheheheheheheh! \$\endgroup\$ – user15244 Oct 16 '14 at 16:30
2
\$\begingroup\$

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:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Ismael Miguel Oct 16 '14 at 11:24
  • \$\begingroup\$ Alright, I updated the count. \$\endgroup\$ – Ismael Miguel Oct 16 '14 at 11:26
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – Dennis Oct 16 '14 at 12:52
  • \$\begingroup\$ Is it actually possible to enter that string in regex101? With the \x10 (Ctrl-P) in it? \$\endgroup\$ – user15244 Oct 16 '14 at 12:55
  • \$\begingroup\$ @WumpusQ.Wumbley You can enter it into your browser's console as a string and copy the result into regex101. \$\endgroup\$ – Martin Ender Oct 16 '14 at 12:57
1
\$\begingroup\$

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
)$
\$\endgroup\$
  • 1
    \$\begingroup\$ >____< Today is not going well for me. \$\endgroup\$ – COTO Oct 14 '14 at 22:49
  • \$\begingroup\$ As in your previous submission, the key is longer than 256 bytes, yes? \$\endgroup\$ – Dennis Oct 14 '14 at 22:55
  • \$\begingroup\$ 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. \$\endgroup\$ – COTO Oct 14 '14 at 22:57
  • 1
    \$\begingroup\$ Match: a repeated 556 times -- Non-match: a repeated 557 times \$\endgroup\$ – Dennis Oct 14 '14 at 22:59
  • \$\begingroup\$ I suppose he gave me credit because I found a key that satisfies the spec. \$\endgroup\$ – Dennis Oct 14 '14 at 23:01
-1
\$\begingroup\$

JavaScript, 78 bytes

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

\$\endgroup\$
1 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.