75
\$\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\$
4
  • 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, 2014 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, 2014 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\$ Oct 27, 2014 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, 2014 at 0:15

40 Answers 40

28
+100
\$\begingroup\$

Basic Regex, 656813 bytes [safe!]

The regex to end all regexes. One final hurrah into the night.

Testable under PCRE, Perl, Python and many others.

bzip2'd and base64-encoded version on Pastebin: http://pastebin.com/9kprSWBn (Pastebin didn't want the raw version because it was too big).

To make sure you get the right regex, you can verify that its MD5 hash is

c121a7604c6f819d3805231c6241c4ef

or check that it begins with

^(?:.*[^!0-9@-Za-z].*|.{,255}|.{257,}|.[U-Za-z].{34}[12569@CDGHKLOPSTWXabefijmnqruvyz].{8}[02468@BDFHJLNPRTVXZbdfhjlnprtvxz].{210}

and ends with

.{56}[7-9@-DM-Tc-js-z].{121}[3-6A-DI-LQ-TYZabg-jo-rw-z].{28}[!0-9@-T].{48})$

The key is still a nice comfortable 256 bytes.

I tested this regex with Python, but note that this regex doesn't use any special features of Python. Indeed, with the exception of (?:) (as a grouping mechanism), it actually uses no special features of any regex engine at all: just basic character classes, repetitions, and anchoring. Thus, it should be testable in a great number of regular expression engines.

Well, actually, I can still crank the difficulty up, assuming someone doesn't just instantly solve the smaller problems...but I wager people will have trouble with a 1GB regex...


After 72 hours, this submission remains uncracked! Thus, I am now revealing the key to make the submission safe. This is the first safe submission, after over 30 submissions were cracked in a row by persistent robbers.

Match: Massive Regex Problem Survives The Night!
Non-match: rae4q9N4gMXG3QkjV1lvbfN!wI4unaqJtMXG9sqt2Tb!0eonbKx9yUt3xcZlUo5ZDilQO6Wfh25vixRzgWUDdiYgw7@J8LgYINiUzEsIjc1GPV1jpXqGcbS7JETMBAqGSlFC3ZOuCJroqcBeYQtOiEHRpmCM1ZPyRQg26F5Cf!5xthgWNiK!8q0mS7093XlRo7YJTgZUXHEN!tXXhER!Kenf8jRFGaWu6AoQpj!juLyMuUO5i0V5cz7knpDX0nsL

Regex explanation:

The regex was generated from a "hard" 3SAT problem with a deliberately-introduced random solution. This problem was generated using the algorithm from [Jia, Moore & Strain, 2007]: "Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively". Six boolean variables are packed into each byte of the key, for a total of 1536 variables.
The regex itself is quite simple: it expresses each of 7680 3SAT clauses as a an inverted condition (by de Morgan's laws), and matches any string that does not meet one of the 3SAT clauses. Therefore, the key is a string which does not match the regex, i.e. one that satisfies every one of the clauses.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ So, I just tried loading a 60MB regex into Python. Predictably, it wasn't too happy. It took several minutes to compile, but the cool part is that it was nearly instant to answer queries. I suspect loading a 1GB regex into Python will take a few hours to compile... \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 10:05
  • 3
    \$\begingroup\$ Or not so easy. Based on my first attempt to carve it down to solvable size, we'll need about 2**61 CPUs to finish in time. \$\endgroup\$
    – user15244
    Oct 18, 2014 at 0:31
  • 12
    \$\begingroup\$ The challenge begins, "You are to write a short, obfuscated regex" (emphasis added) \$\endgroup\$
    – Ypnypn
    Oct 20, 2014 at 1:29
  • 5
    \$\begingroup\$ @Ypnypn The challenge so far has been to even get any uncrackable regex on the board - this one looks like it'll be the first to break that barrier though :) \$\endgroup\$
    – Sp3000
    Oct 20, 2014 at 1:36
  • 3
    \$\begingroup\$ @MartinBüttner: Thanks! I have done so. Now I have to go off and try some of these other NP-hard regex problems... \$\endgroup\$
    – nneonneo
    Oct 20, 2014 at 11:24
19
\$\begingroup\$

.NET regex, 841 bytes [Safe!]

Now that I've got a safe entry, lets see how small I can make the regex!

^(?<a>){53}((0(((?<-a>)(?<A>){7}|){997}((?<-b>)(?<B>){7}|){997}((?<-c>)(?<C>){7}|){997}((?<-d>)(?<D>){7}|){997}((?<-e>)(?<E>){7}|){997}((?<-f>)(?<F>){7}|){997}((?<-g>)(?<G>){7}|){997}(?<A>){5})|1(((?<-a>)(?<A>){3}|){997}((?<-b>)(?<B>){3}|){997}((?<-c>)(?<C>){3}|){997}((?<-d>)(?<D>){3}|){997}((?<-e>)(?<E>){3}|){997}((?<-f>)(?<F>){3}|){997}((?<-g>)(?<G>){3}|){997}(?<A>)))((?<-A>){997}(?<B>)|){9}((?<-A>)(?<a>)|){997}((?<-B>){997}(?<C>)|){9}((?<-B>)(?<b>)|){997}((?<-C>){997}(?<D>)|){9}((?<-C>)(?<c>)|){997}((?<-D>){997}(?<E>)|){9}((?<-D>)(?<d>)|){997}((?<-E>){997}(?<F>)|){9}((?<-E>)(?<e>)|){997}((?<-F>){997}(?<G>)|){9}((?<-F>)(?<f>)|){997}((?<-G>){997}|){9}((?<-G>)(?<g>)|){997}){256}$(?<-a>){615}(?(a)(?!))(?<-b>){59}(?(b)(?!))(?<-c>){649}(?(c)(?!))(?<-d>){712}(?(d)(?!))(?<-e>){923}(?(e)(?!))(?<-f>){263}(?(f)(?!))(?<-g>){506}(?(g)(?!))

Prettified:

^(?<a>){53}
(
    (0(
        ((?<-a>)(?<A>){7}|){997}
        ((?<-b>)(?<B>){7}|){997}
        ((?<-c>)(?<C>){7}|){997}
        ((?<-d>)(?<D>){7}|){997}
        ((?<-e>)(?<E>){7}|){997}
        ((?<-f>)(?<F>){7}|){997}
        ((?<-g>)(?<G>){7}|){997}
        (?<A>){5})
    |1(
        ((?<-a>)(?<A>){3}|){997}
        ((?<-b>)(?<B>){3}|){997}
        ((?<-c>)(?<C>){3}|){997}
        ((?<-d>)(?<D>){3}|){997}
        ((?<-e>)(?<E>){3}|){997}
        ((?<-f>)(?<F>){3}|){997}
        ((?<-g>)(?<G>){3}|){997}
        (?<A>))
    )
    ((?<-A>){997}(?<B>)|){9}((?<-A>)(?<a>)|){997}
    ((?<-B>){997}(?<C>)|){9}((?<-B>)(?<b>)|){997}
    ((?<-C>){997}(?<D>)|){9}((?<-C>)(?<c>)|){997}
    ((?<-D>){997}(?<E>)|){9}((?<-D>)(?<d>)|){997}
    ((?<-E>){997}(?<F>)|){9}((?<-E>)(?<e>)|){997}
    ((?<-F>){997}(?<G>)|){9}((?<-F>)(?<f>)|){997}
    ((?<-G>){997}|){9}      ((?<-G>)(?<g>)|){997}
){256}$

(?<-a>){615}(?(a)(?!))
(?<-b>){59}(?(b)(?!))
(?<-c>){649}(?(c)(?!))
(?<-d>){712}(?(d)(?!))
(?<-e>){923}(?(e)(?!))
(?<-f>){263}(?(f)(?!))
(?<-g>){506}(?(g)(?!))

Features:

  • Short, 841 bytes
  • Golfed and written by hand
  • Not known to encode an NP-hard problem
  • Times out on most invalid input :)
  • Tested on http://regexhero.net/tester/, takes ~5 seconds for the valid input

Thanks to Sp3000 and user23013 for cluing me in to .NET regex.


After 72 hours, I am revealing the key to make this submission safe.

Match:

1110111111110010000110011000001011011110101111000011101011110011001000000111111111001010000111100011111000000100011110110111001101011001000101111110010111100000000010110001111011011111100000011001101110011111011010100111011101111001110111010001111011000000

Non-match: Aren'tHashFunctionsFun?

Explanation:

This regular expression implements a very simple and rather stupid hash function. The hash function computes a single integer x as output. x starts off equal to 53. It is adjusted based on each character encountered: if it sees a 0, it will set x = 7x + 5, and if it sees a 1, it will set x = 3x + 1. x is then reduced mod 9977. The final result is checked against a predefined constant; the regex fails to match if the hash value is not equal.

Seven capture groups (a-g) are used to store the base-997 digits of x, with seven more capture groups (A-G) serving as temporary storage. I use the "balancing capture groups" extension of .NET regex to store integers in capture groups. Technically, the integer associated with each capture group is the number of unbalanced matches captured by that group; "capturing" an empty string using (?<X>) increments the number of captures, and "balancing" the group using (?<-X>) decrements the number of captures (which will cause a match failure if the group has no captures). Both can be repeated to add and subtract fixed constants.

This hash algorithm is just one I cooked up in a hurry, and is the smallest hash algorithm I could come up with that seemed reasonably secure using only additions and multiplications. It's definitely not crypto-quality, and there are likely to be weaknesses which make it possible to find a collision in less than 9977/2 hash evaluations.

\$\endgroup\$
21
  • \$\begingroup\$ I had an idea... Then I gave up because I don't have 500+GB free space on my hard drive. \$\endgroup\$
    – jimmy23013
    Oct 21, 2014 at 9:12
  • 3
    \$\begingroup\$ Seeing it now in 3 uncracked submissions, I'm officially registering my complete ignorance of the purpose of the construct (?<a>){53}. It appears to be capturing the empty pattern into named group a 53 times. So set a="" then repeat 52 more times? But I don't really know if (?< means the same thing in Microsoft's idea of a regexp. Their documentation fails to even mention it. If even a regexp contest ends with undocumented Microsoft extensions rolling over the unix people, my existence has no purpose. \$\endgroup\$
    – user15244
    Oct 21, 2014 at 13:14
  • \$\begingroup\$ It is a group capture that captures nothing 53 times. .NET has an extension called balancing group captures which is their answer to paren matching. Each named group acts like a stack, so (?<a>){53} pushes the empty string 53 times. You can pop the stack using (?<-a>). Hopefully now it is clear why this construct is so useful. \$\endgroup\$
    – nneonneo
    Oct 21, 2014 at 13:52
  • 2
    \$\begingroup\$ @WumpusQ.Wumbley I'm the unix people who found this useful. \$\endgroup\$
    – jimmy23013
    Oct 21, 2014 at 14:48
  • 4
    \$\begingroup\$ @WumpusQ.Wumbley MSDN has an entire page about grouping constructs. Which can be found from the quick reference. Which is the first hit for ".net regex reference", analogously to your Perl search term. (Same for "syntax", "manual" or "specification"). \$\endgroup\$ Oct 22, 2014 at 11:30
18
\$\begingroup\$

ECMAScript (10602 bytes)

(Language note: I see a lot of posts labeled ruby, or python, or whatever, when they really don't use any language-specific features. This one only requires (?!...) and (?=...) on top of POSIX ERE with backreferences. Those features are probably in your favorite language's regexp engine, so don't be discouraged from trying the challenge because I chose to use the javascript online tester.)

Just a little bit of fun, not as computationally difficult as some of the others.

^(?!(.).*\1.|.+(.).*\2)(?=(.))(?=(((?![ҁѧѦЩ]{2}).)*(?=[ҁѧѦЩ]{2}).){2}(?!.*[ЩѦҁѧ]{2}))(?=(((?![ɿqԼϚ]{2}).)*(?=[ϚqԼɿ]{2}).){2}(?!.*[ԼϚɿq]{2}))(?=((?![ϼλҡՄ]{2}).)*(?=[ҡλϼՄ]{2}).(?!.*[Մλϼҡ]{2}))(?=(((?![ʯֆɎF]{2}).)*(?=[FֆʯɎ]{2}).){2}(?!.*[FɎֆʯ]{2}))(?=(((?![AɔbУ]{2}).)*(?=[ɔbAУ]{2}).){3}(?!.*[ɔAbУ]{2}))(?=(((?![ʈͽՄɒ]{2}).)*(?=[ͽՄɒʈ]{2}).){2}(?!.*[ͽՄɒʈ]{2}))(?=(((?![ϙшѭϢ]{2}).)*(?=[Ϣϙѭш]{2}).){2}(?!.*[ѭшϙϢ]{2}))(?=(((?![ՐɏƋѠ]{2}).)*(?=[ƋՐɏѠ]{2}).){2}(?!.*[ѠƋՐɏ]{2}))(?=(((?![Жտʓo]{2}).)*(?=[Жտʓo]{2}).){2}(?!.*[Жʓտo]{2}))(?=(((?![ƆʙƸM]{2}).)*(?=[ƆʙMƸ]{2}).){2}(?!.*[ƆʙMƸ]{2}))(?=(((?![dNѤѯ]{2}).)*(?=[ѤѯNd]{2}).){2}(?!.*[ѤѯdN]{2}))(?=(((?![ҎvȵҜ]{2}).)*(?=[vҜȵҎ]{2}).){2}(?!.*[ҎvҜȵ]{2}))(?=(((?![ҹɀҀҤ]{2}).)*(?=[ɀҤҀҹ]{2}).){2}(?!.*[ҹҤҀɀ]{2}))(?=(((?![OɄfC]{2}).)*(?=[fOɄC]{2}).){3}(?!.*[ɄOfC]{2}))(?=((?![ǷϗЋԒ]{2}).)*(?=[ЋϗԒǷ]{2}).(?!.*[ԒϗЋǷ]{2}))(?=((?![էҹϞҀ]{2}).)*(?=[ҹҀէϞ]{2}).(?!.*[ϞէҹҀ]{2}))(?=(((?![QԶϧk]{2}).)*(?=[QkϧԶ]{2}).){2}(?!.*[ϧԶkQ]{2}))(?=(((?![cիYt]{2}).)*(?=[իYct]{2}).){2}(?!.*[tcYի]{2}))(?=(((?![ɐҷCɄ]{2}).)*(?=[CɄɐҷ]{2}).){3}(?!.*[CҷɐɄ]{2}))(?=(((?![ҥմѾϢ]{2}).)*(?=[ϢѾմҥ]{2}).){2}(?!.*[մϢѾҥ]{2}))(?=((?![Ϛǝjɰ]{2}).)*(?=[Ϛǝjɰ]{2}).(?!.*[jɰϚǝ]{2}))(?=((?![ϭBѾҸ]{2}).)*(?=[ѾҸϭB]{2}).(?!.*[ѾҸBϭ]{2}))(?=((?![ϼλyՎ]{2}).)*(?=[λՎyϼ]{2}).(?!.*[λՎyϼ]{2}))(?=((?![MԋƆƻ]{2}).)*(?=[ƻƆԋM]{2}).(?!.*[MƆԋƻ]{2}))(?=(((?![uԳƎȺ]{2}).)*(?=[uԳƎȺ]{2}).){3}(?!.*[ȺƎuԳ]{2}))(?=((?![ɂƐϣq]{2}).)*(?=[qϣƐɂ]{2}).(?!.*[ɂƐϣq]{2}))(?=(((?![ϫճωƺ]{2}).)*(?=[ωϫճƺ]{2}).){2}(?!.*[ճƺϫω]{2}))(?=((?![ζɏΞƋ]{2}).)*(?=[ɏƋζΞ]{2}).(?!.*[ɏƋζΞ]{2}))(?=(((?![Ӄxԏϣ]{2}).)*(?=[Ӄxԏϣ]{2}).){2}(?!.*[ԏxϣӃ]{2}))(?=(((?![ԈʄʫԻ]{2}).)*(?=[ԻʄԈʫ]{2}).){2}(?!.*[ʫԈԻʄ]{2}))(?=(((?![ɒէƣʈ]{2}).)*(?=[ʈɒէƣ]{2}).){2}(?!.*[ʈƣɒէ]{2}))(?=(((?![Ϥϟƺϫ]{2}).)*(?=[Ϥϫϟƺ]{2}).){3}(?!.*[ƺϫϤϟ]{2}))(?=((?![ɋȡþͼ]{2}).)*(?=[ȡþͼɋ]{2}).(?!.*[þͼȡɋ]{2}))(?=((?![ҡʈԄՄ]{2}).)*(?=[ʈԄՄҡ]{2}).(?!.*[ՄԄҡʈ]{2}))(?=(((?![ʌkȿՌ]{2}).)*(?=[Ռȿkʌ]{2}).){3}(?!.*[kՌȿʌ]{2}))(?=(((?![gǝժʮ]{2}).)*(?=[ǝgʮժ]{2}).){2}(?!.*[gǝʮժ]{2}))(?=((?![ɧƸȝՊ]{2}).)*(?=[ƸɧȝՊ]{2}).(?!.*[ՊȝɧƸ]{2}))(?=(((?![ɜȶʟɀ]{2}).)*(?=[ɀȶʟɜ]{2}).){3}(?!.*[ȶɀʟɜ]{2}))(?=((?![ƅѿOf]{2}).)*(?=[ѿfƅO]{2}).(?!.*[Oѿfƅ]{2}))(?=(((?![GҠƪԅ]{2}).)*(?=[ҠGԅƪ]{2}).){2}(?!.*[GԅƪҠ]{2}))(?=(((?![Һӻѩͽ]{2}).)*(?=[ӻͽҺѩ]{2}).){2}(?!.*[ͽҺѩӻ]{2}))(?=(((?![ʊLՅϪ]{2}).)*(?=[ՅʊLϪ]{2}).){3}(?!.*[LʊϪՅ]{2}))(?=(((?![ɅՈƪԅ]{2}).)*(?=[ƪԅՈɅ]{2}).){2}(?!.*[ԅՈƪɅ]{2}))(?=((?![ʇɊƈѹ]{2}).)*(?=[Ɋƈʇѹ]{2}).(?!.*[ʇƈѹɊ]{2}))(?=(((?![նЏYI]{2}).)*(?=[IYնЏ]{2}).){2}(?!.*[նЏIY]{2}))(?=((?![ͼխɷȡ]{2}).)*(?=[ͼȡɷխ]{2}).(?!.*[ɷխȡͼ]{2}))(?=((?![ҝɞҎv]{2}).)*(?=[ɞҎvҝ]{2}).(?!.*[Ҏҝvɞ]{2}))(?=(((?![eƪGω]{2}).)*(?=[Geƪω]{2}).){3}(?!.*[ƪeGω]{2}))(?=(((?![ɂɿƱq]{2}).)*(?=[Ʊqɿɂ]{2}).){2}(?!.*[Ʊqɂɿ]{2}))(?=((?![ƣЖoɒ]{2}).)*(?=[Жɒoƣ]{2}).(?!.*[ƣoɒЖ]{2}))(?=(((?![Ҵԉձϻ]{2}).)*(?=[ձԉϻҴ]{2}).){2}(?!.*[ϻԉձҴ]{2}))(?=((?![ɆɟѧE]{2}).)*(?=[EѧɆɟ]{2}).(?!.*[ѧEɆɟ]{2}))(?=((?![ѪɝȾѸ]{2}).)*(?=[ѪѸɝȾ]{2}).(?!.*[ѪѸȾɝ]{2}))(?=(((?![ßΩԂɥ]{2}).)*(?=[ɥΩßԂ]{2}).){2}(?!.*[ɥßԂΩ]{2}))(?=(((?![ӃդƐϣ]{2}).)*(?=[ƐդӃϣ]{2}).){2}(?!.*[ϣդƐӃ]{2}))(?=(((?![ѪլѸԿ]{2}).)*(?=[ԿѪѸլ]{2}).){2}(?!.*[ԿѪլѸ]{2}))(?=((?![ɉшƻϙ]{2}).)*(?=[ɉƻшϙ]{2}).(?!.*[ϙƻɉш]{2}))(?=((?![ѹփʯΨ]{2}).)*(?=[ʯփΨѹ]{2}).(?!.*[ѹʯփΨ]{2}))(?=((?![ƕϯʮҏ]{2}).)*(?=[ƕҏʮϯ]{2}).(?!.*[ҏϯʮƕ]{2}))(?=((?![ՌȿSբ]{2}).)*(?=[բՌSȿ]{2}).(?!.*[SȿբՌ]{2}))(?=(((?![ИщɌK]{2}).)*(?=[ɌщИK]{2}).){2}(?!.*[ɌИщK]{2}))(?=(((?![aҵɸւ]{2}).)*(?=[ւҵaɸ]{2}).){2}(?!.*[aւɸҵ]{2}))(?=(((?![լѸխɷ]{2}).)*(?=[ɷѸլխ]{2}).){2}(?!.*[խɷլѸ]{2}))(?=(((?![ՉLʝϥ]{2}).)*(?=[LϥʝՉ]{2}).){2}(?!.*[ՉϥʝL]{2}))(?=((?![ʬϬȝɣ]{2}).)*(?=[Ϭɣȝʬ]{2}).(?!.*[ȝɣϬʬ]{2}))(?=(((?![ɺȴҵւ]{2}).)*(?=[ȴɺҵւ]{2}).){3}(?!.*[ҵȴɺւ]{2}))(?=(((?![ΞʇɊζ]{2}).)*(?=[ζɊʇΞ]{2}).){2}(?!.*[ΞɊζʇ]{2}))(?=(((?![դփӃΨ]{2}).)*(?=[ΨփդӃ]{2}).){2}(?!.*[ΨփդӃ]{2}))(?=((?![ԳuҦc]{2}).)*(?=[uԳҦc]{2}).(?!.*[ҦucԳ]{2}))(?=(((?![ԻЭɌщ]{2}).)*(?=[ԻɌщЭ]{2}).){2}(?!.*[ɌщԻЭ]{2}))(?=((?![ЉջѮӺ]{2}).)*(?=[ӺЉѮջ]{2}).(?!.*[ѮӺЉջ]{2}))(?=(((?![ӿѤɹN]{2}).)*(?=[ӿɹѤN]{2}).){3}(?!.*[ѤNɹӿ]{2}))(?=(((?![ƕʮBg]{2}).)*(?=[Bʮgƕ]{2}).){3}(?!.*[Bʮgƕ]{2}))(?=((?![կƛȸԓ]{2}).)*(?=[ƛȸԓկ]{2}).(?!.*[կԓƛȸ]{2}))(?=(((?![ɥДȸh]{2}).)*(?=[ɥhДȸ]{2}).){2}(?!.*[ɥhȸД]{2}))(?=(((?![ʁԺեW]{2}).)*(?=[եWԺʁ]{2}).){2}(?!.*[ԺʁWե]{2}))(?=((?![ɮςϿʢ]{2}).)*(?=[ʢϿɮς]{2}).(?!.*[ɮςʢϿ]{2}))(?=(((?![ձУAƾ]{2}).)*(?=[ƾУձA]{2}).){2}(?!.*[УAձƾ]{2}))(?=(((?![ԻϠɌʄ]{2}).)*(?=[ʄɌԻϠ]{2}).){2}(?!.*[ϠɌʄԻ]{2}))(?=((?![ɜҥմȶ]{2}).)*(?=[ҥȶɜմ]{2}).(?!.*[ҥȶɜմ]{2}))(?=(((?![ƏՀթϞ]{2}).)*(?=[թՀƏϞ]{2}).){2}(?!.*[ƏՀթϞ]{2}))(?=((?![ҩɃȽϛ]{2}).)*(?=[ɃȽϛҩ]{2}).(?!.*[ҩϛɃȽ]{2}))(?=((?![ҠȺԃD]{2}).)*(?=[ȺҠԃD]{2}).(?!.*[DԃҠȺ]{2}))(?=((?![ɆʊLϥ]{2}).)*(?=[LϥʊɆ]{2}).(?!.*[ʊϥɆL]{2}))(?=(((?![ͽѩɒЖ]{2}).)*(?=[ͽɒѩЖ]{2}).){2}(?!.*[ѩɒЖͽ]{2}))(?=(((?![ςϪʢƩ]{2}).)*(?=[ƩʢςϪ]{2}).){3}(?!.*[ςƩϪʢ]{2}))(?=(((?![ҁϥѧɆ]{2}).)*(?=[ϥѧҁɆ]{2}).){2}(?!.*[ѧҁϥɆ]{2}))(?=((?![Жϗѩʓ]{2}).)*(?=[ʓϗЖѩ]{2}).(?!.*[ʓЖϗѩ]{2}))(?=(((?![ʁեɋþ]{2}).)*(?=[ʁɋեþ]{2}).){2}(?!.*[þեʁɋ]{2}))(?=((?![Mnƻɉ]{2}).)*(?=[Mɉƻn]{2}).(?!.*[ƻMnɉ]{2}))(?=(((?![HʬϬѺ]{2}).)*(?=[HѺʬϬ]{2}).){2}(?!.*[ϬѺʬH]{2}))(?=(((?![cիըҦ]{2}).)*(?=[ըҦիc]{2}).){2}(?!.*[cիҦը]{2}))(?=((?![ȸɥկΩ]{2}).)*(?=[ɥΩկȸ]{2}).(?!.*[ɥȸկΩ]{2}))(?=(((?![ʫҝԲɞ]{2}).)*(?=[ʫԲɞҝ]{2}).){2}(?!.*[ʫɞԲҝ]{2}))(?=(((?![ҺЋϗѩ]{2}).)*(?=[ѩҺϗЋ]{2}).){3}(?!.*[ҺѩЋϗ]{2}))(?=((?![ʯΨɎч]{2}).)*(?=[ʯΨɎч]{2}).(?!.*[ʯΨɎч]{2}))(?=(((?![ѮɔЉA]{2}).)*(?=[ЉɔѮA]{2}).){2}(?!.*[ѮɔAЉ]{2}))(?=(((?![ʞӶdN]{2}).)*(?=[dNʞӶ]{2}).){2}(?!.*[ӶNdʞ]{2}))(?=(((?![ԀŋҔɴ]{2}).)*(?=[ŋԀҔɴ]{2}).){3}(?!.*[ҔɴŋԀ]{2}))(?=(((?![ΠЪƏթ]{2}).)*(?=[ƏΠթЪ]{2}).){3}(?!.*[ΠթЪƏ]{2}))(?=(((?![OՌѿբ]{2}).)*(?=[ՌOբѿ]{2}).){2}(?!.*[OբՌѿ]{2}))(?=((?![ɮȾʢѪ]{2}).)*(?=[ɮȾʢѪ]{2}).(?!.*[ѪȾɮʢ]{2}))(?=((?![ЪϤՋΠ]{2}).)*(?=[ϤΠЪՋ]{2}).(?!.*[ՋΠЪϤ]{2}))(?=((?![Մͽӻϼ]{2}).)*(?=[ͽϼՄӻ]{2}).(?!.*[ϼͽՄӻ]{2}))(?=((?![ԋҳѦЩ]{2}).)*(?=[ѦԋЩҳ]{2}).(?!.*[ѦЩҳԋ]{2}))(?=((?![gҶҸB]{2}).)*(?=[BҶgҸ]{2}).(?!.*[ҸBgҶ]{2}))(?=(((?![ɢλҡѥ]{2}).)*(?=[λҡɢѥ]{2}).){2}(?!.*[ѥλɢҡ]{2}))(?=(((?![AϻЉձ]{2}).)*(?=[ϻձЉA]{2}).){2}(?!.*[ϻձЉA]{2}))(?=((?![tRիp]{2}).)*(?=[Rtpի]{2}).(?!.*[tpRի]{2}))(?=(((?![ɮȹϿÞ]{2}).)*(?=[ϿɮÞȹ]{2}).){2}(?!.*[ϿɮȹÞ]{2}))(?=((?![ϯժʮџ]{2}).)*(?=[ժџϯʮ]{2}).(?!.*[џϯʮժ]{2}))(?=(((?![HʬȠҨ]{2}).)*(?=[HҨȠʬ]{2}).){2}(?!.*[ȠҨʬH]{2}))(?=((?![ՒԉPϻ]{2}).)*(?=[ԉϻPՒ]{2}).(?!.*[PϻԉՒ]{2}))((?=Գ[նƎuc]|ƕ[Bʮȴҏ]|ϣ[ԏɂӃƐ]|Ʊ[ɿϬӄɂ]|Ѿ[ϭϢҸҥ]|ͽ[ѩӻՄɒ]|ɷ[խͼլ]|փ[դiѹΨ]|ϛ[ɅɃȽՀ]|Ԃ[ɥѭմß]|խ[ȡɐѸɷ]|P[ȠՒԉ]|ӷ[ЩEՊƆ]|Ə[ΠթƣϞ]|ч[xɎΨ]|ʄ[ԈϠԻҺ]|Љ[AѮϻջ]|ɒ[ʈƣЖͽ]|ʞ[ӶɔNЦ]|Ɛ[ϣɰqդ]|ʮ[ϯժƕg]|ɥ[ȸДԂΩ]|Ҕ[ŋՐɺɴ]|χ[Ԏѯ]|Ջ[ΠϤԾտ]|Ɏ[чʯֆ]|ҥ[մѬѾȶ]|ɞ[ҝҎԲ]|ҏ[ƕՐϯɺ]|Հ[ϛթϞw]|y[ϼԈҝՎ]|λ[ѥՎϼҡ]|Մ[ͽҡϼʈ]|ϟ[ϫϤԾ]|Ћ[ǷϠҺϗ]|ʫ[ԲԈҝԻ]|ǝ[gjɰժ]|Ԅ[ҡҹʟʈ]|ʌ[kՌэC]|ȶ[ҥЊɜʟ]|Ɍ[щИԻϠ]|ի[Rtըc]|Ո[ƪƺЪɅ]|ƺ[ՈϤϫω]|ß[ԂΩɜҤ]|I[նЏљ]|ҷ[ȡэCɐ]|Ц[ςbʞɹ]|Ǝ[ǂȺԳG]|ӄ[ƱӾѺ]|ʇ[ζiɊѹ]|ֆ[ɎF]|ɏ[ѠΞƋ]|Բ[ɞʫЭ]|Ի[ɌЭʫʄ]|ƪ[ԅωGՈ]|ȡ[խɋͼҷ]|Ϡ[ɌдʄЋ]|ɋ[эʁþȡ]|U[ɝɄՅʝ]|ɺ[ҵȴҏҔ]|Ƚ[ԅϛDҩ]|Ɋ[ƈʇΞ]|ժ[Φʮǝџ]|Ӿ[ӄɂԏ]|Ψ[Ӄчʯփ]|Ω[Ղկßɥ]|щ[KɌЭ]|ɉ[nҶшƻ]|Ժ[WԱե]|G[ƎeҠƪ]|ղ[կՂՑɃ]|Ӷ[ԷʞdѮ]|u[ȺԳQҦ]|Ѡ[ɴɏՐ]|ƛ[ԓՑѿկ]|ɜ[ɀմßȶ]|Ҵ[ԉձʡɧ]|ȿ[kSՌԃ]|ɂ[qӾϣƱ]|Պ[ӷɧƸʡ]|Щ[ѧѦӷԋ]|Ⱦ[ѪɝʢՅ]|Ƀ[ղҩwϛ]|Ҏ[vҜɞ]|ɐ[ҷɄɝխ]|ԏ[ϣxӾ]|Ҁ[ҹϞҤw]|մ[ԂҥɜϢ]|ҳ[ДԋϙѦ]|Ϛ[jɰqԼ]|w[ҀՀɃՂ]|E[ӷɟѧʡ]|У[μAbƾ]|ձ[ҴϻƾA]|ɟ[ɆμEƾ]|Ҥ[ҀßՂɀ]|v[ȵҎՎҝ]|ш[ϢϙɉҸ]|Ͽ[ɹɮςÞ]|O[fCՌѿ]|ʁ[ԶեWɋ]|ȹ[ÞԿɮ]|Ϟ[ՀէҀƏ]|ԋ[ƻҳЩƆ]|ƅ[fԓՉѿ]|ω[ƺeճƪ]|ʈ[ɒԄՄէ]|Ԉ[ʫʄӻy]|Ƌ[ζՐϯɏ]|ɰ[ǝƐΦϚ]|ȴ[ƕϭւɺ]|Δ[Չhҁԓ]|Π[ՋЪoƏ]|Ϫ[ʢƩʊՅ]|ӻ[ҺԈͽϼ]|ʝ[ՉLfU]|Ծ[ϟrՋ]|þ[ɋեͼ]|ӿ[ѤɹÞ]|բ[ՌՑSѿ]|ҡ[λՄɢԄ]|ɸ[ȻՃaҵ]|д[ϠИǷ]|ճ[ωϫл]|ɀ[ҹҤʟɜ]|л[ճeљ]|Ϥ[ϟЪƺՋ]|c[ԳYҦի]|Ռ[Oʌբȿ]|ն[ԳǂYI]|Ʌ[ԅϛՈթ]|ҝ[yɞʫv]|p[ƜRt]|ƣ[էƏɒo]|Ҷ[Ҹɉgj]|A[УձɔЉ]|Þ[ȹϿӿ]|Ƿ[дЋԒ]|k[QԶȿʌ]|ջ[ՒӺЉ]|Ɇ[ʊѧϥɟ]|ʢ[ςϪɮȾ]|ѭ[ДϢϙԂ]|ʘ[ЏƜt]|ѹ[ʇʯփƈ]|ʟ[Ԅȶɀɢ]|ϯ[ҏƋʮџ]|լ[ԿɷѸ]|Ƹ[ՊʙƆȝ]|N[ɹʞdѤ]|ς[ЦϿʢƩ]|ǂ[eƎљն]|ѧ[ɆEҁЩ]|ɴ[ѠҔԀ]|Ʉ[ɐfCU]|ҹ[ԄҀէɀ]|Ւ[ջPϻ]|ѥ[ɢλaՃ]|o[ΠտЖƣ]|g[BҶʮǝ]|Կ[լѪȹ]|Џ[ʘIY]|Y[ctЏն]|Ҡ[ȺDGԅ]|Ѧ[Щҁҳh]|Ѻ[HϬӄ]|ɹ[NЦϿӿ]|ԓ[ƛƅΔȸ]|f[OƅɄʝ]|L[ʝʊՅϥ]|ϼ[yӻλՄ]|џ[ζժiϯ]|ҩ[SɃȽՑ]|Ʃ[Ϫμbς]|դ[փƐӃΦ]|Ѯ[ӶӺЉɔ]|ƻ[ɉԋϙM]|ѩ[ҺϗͽЖ]|ʊ[μɆϪL]|Ж[ɒʓѩo]|B[ƕҸgϭ]|ԅ[ҠɅƪȽ]|ɔ[ʞѮAb]|ϗ[ЋʓԒѩ]|Ɔ[ӷMƸԋ]|љ[лǂI]|ȸ[ɥԓhկ]|q[ƐɿϚɂ]|Ҹ[шҶBѾ]|ʡ[ҴƾEՊ]|Ԏ[dχԷ]|j[ϚnǝҶ]|Ҧ[uըcϧ]|ϻ[ՒЉԉձ]|ʙ[ƸԼɣM]|ե[ʁþԺ]|Ƞ[PHҨ]|Φ[ɰդiժ]|Њ[ɢaѬȶ]|b[ɔƩЦУ]|Չ[ʝƅϥΔ]|ϧ[ԶҦWQ]|Ճ[ѥɸȵՎ]|Ҩ[ɧԉȠʬ]|ҁ[ΔѧѦϥ]|Ց[ҩƛղբ]|ɿ[qԼɣƱ]|μ[УƩɟʊ]|e[ωǂGл]|Һ[Ћʄѩӻ]|ѯ[dѤχ]|Ԓ[Ƿюϗ]|ҵ[ɸɺŋւ]|տ[Ջʓro]|ϙ[ѭƻҳш]|R[իԱp]|Ɯ[pʘ]|r[Ծюտ]|ƈ[ɊѹF]|M[ʙnƆƻ]|i[փʇΦџ]|ƾ[ձУʡɟ]|ɝ[ѸȾɐU]|ю[Ԓʓr]|Д[hҳѭɥ]|a[Њѥւɸ]|Յ[LUϪȾ]|ϭ[ѬBѾȴ]|Ѹ[Ѫɝխլ]|D[ԃȽҠS]|Ⱥ[ԃuƎҠ]|Ȼ[ŋȵɤɸ]|э[ʌԶҷɋ]|Ѥ[ѯӿN]|ԃ[ȺDȿQ]|ȵ[ҜȻՃv]|S[բȿҩD]|Ղ[ҤwΩղ]|ɢ[ѥҡʟЊ]|ɣ[Ϭɿȝʙ]|Վ[yvλՃ]|Ϭ[ɣʬƱѺ]|Ӄ[ϣxΨդ]|թ[ƏɅЪՀ]|ȝ[ʬƸɧɣ]|Ԁ[ɤɴŋ]|ѿ[ƅOƛբ]|H[ȠʬѺ]|F[ֆƈʯ]|Ѫ[ѸȾɮԿ]|է[ʈƣϞҹ]|ʯ[ѹFɎΨ]|ŋ[ȻҔԀҵ]|ɤ[ԀҜȻ]|ԉ[ҴPҨϻ]|ͼ[ȡɷþ]|t[իʘpY]|Ϣ[ѭմѾш]|Э[щԲԻ]|ɮ[ʢѪϿȹ]|ϫ[ƺճϟ]|Ѭ[Њւϭҥ]|Լ[Ϛnɿʙ]|Ξ[ζɊɏ]|Է[ԎӺӶ]|Q[ϧkԃu]|ւ[ҵaѬȴ]|Ր[ѠҏҔƋ]|ը[իԱWҦ]|ʓ[տϗюЖ]|K[щИ]|Ӻ[ԷѮջ]|x[чӃԏ]|И[KɌд]|ʬ[HҨȝϬ]|Ա[RըԺ]|ɧ[ȝҴՊҨ]|n[jɉMԼ]|C[ʌҷɄO]|W[ϧըʁԺ]|h[ДѦΔȸ]|ϥ[ՉLɆҁ]|Ъ[ΠՈϤթ]|կ[Ωղƛȸ]|ζ[џΞʇƋ]|Ҝ[ɤҎȵ]|Զ[ϧkʁэ]|d[ԎNѯӶ]).){3,}\3

Test here: http://regex101.com/r/kF2oQ3/1

(crickets chirping)

No takers? It's oddly disappointing to think of posting the spoiler with no evidence that anyone looked at it long enough to understand what type of problem it is.

I'm writing a complete explanation to post later but I think I'd be happier if someone beat me.

When I said it was not "computationally difficult"... it is an instance of an NP-complete problem, but not a big instance.

Hint: it's a type of pencil-and-paper puzzle. But I'd be quite impressed if you can solve this one with pencil and paper alone (after decoding the regexp into a form suitable for printing).

Spoiler time

There are multiple levels of spoilers here. If you didn't solve the regexp yet, you might want to try again after reading just the first spoiler block. The actual key that matches the regexp is after the last spoiler block.

This regexp encodes a Slitherlink puzzle.

Once you figure out what's going on and convert the regexp into a Slitherlink grid, you'll quickly discover that it's harder than the average Slitherlink. It's on a 16x16 square grid, larger than the usual 10x10. It is also slightly unusual in having no 0 clues and a relative shortage of 3's. 0's and 3's are the easiest clues to work with, so I didn't want to give you a lot of them.

slitherlink puzzle

Second layer of spoilage:

When you're solving the Slitherlink puzzle, an extra surprise kicks in: this Slitherlink has more than one solution. If you're a regular Slitherlink solver, and you have a habit of making deductions based on the assumption of a unique solution, you might have been confused by that. If so, you're a cheater and this is your punishment! Part of the job of a puzzle solver is to find out how many solutions there are.

Final layer of spoilage:

The final twist: the 2 solutions to the Slitherlink are mostly identical, but one is slightly longer than the other. You need to find the short one. If you only found the long one and encoded it as a string to match the regexp, the string would be 257 characters long. The path goes through 256 nodes, but you have to repeat the first node at the end to close the loop. And if you got that far, you might have thought I made a mistake and forgot to count that extra character. Nope! and/or Gotcha! (and/or Boosh! and/or Kakow!)

The short solution is 254 segments long and encodes to a string of 255 characters which is the key. Since you can start at any node on the loop and proceed clockwise or counterclockwise, there are 254*2=508 possible answers.

slitherlink solution

Non-match: bananabananabanana
Match: ƜpRԱԺեþɋэʌkȿՌOfɄCҷɐխɷլԿѪɮȹÞӿѤNɹЦʞӶdѯχԎԷӺջՒϻЉAɔbУƾձҴԉҨʬHѺӄӾԏxчɎֆFƈɊΞζџiփΨӃϣɂƱϬɣɿqϚɰƐդΦժʮgBƕȴւҵɺҏϯƋՐѠɴҔŋԀɤȻɸaЊѬҥѾҸшɉҶjnMʙƸՊʡEɟμƩςʢϪʊLՅȾɝUʝՉϥҁѧЩӷƆԋҳϙѭϢմԂɥȸhΔԓƛѿբՑҩSDȽԅҠGeωƪՈɅϛɃwҀҤՂΩßɜȶʟɀҹԄҡλѥՃȵҜҎɞԲЭщɌИдϠʄԻʫҝyϼӻҺЋϗѩͽɒʈէϞՀթЪΠƏƣoտʓюrԾϟϤƺϫճлљIնǂƎԳuȺԃQϧԶʁWըիcYЏʘƜ
Proof: http://regex101.com/r/pJ3uM9/2

\$\endgroup\$
2
  • \$\begingroup\$ Congratulations on making it through the 72 hours! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked. \$\endgroup\$ Oct 23, 2014 at 8:06
  • \$\begingroup\$ I tried but didn't find it is planar... \$\endgroup\$
    – jimmy23013
    Oct 24, 2014 at 6:13
14
\$\begingroup\$

Perl flavour, 158 [cracked]

Here's my first attempt:

(?(R)|^(?=[a-z]))((?!.*(?&K))(((?|([?-K])|(?'K'$)|(?'k'j'k'?)|(?'k'C[^_^]{3,33}))(?(3)\3|3)){3}(?(R)R(-.-)|(?R))(?'k'<grc>-(?!(?&k))\4(?(R)|\$\4(?5)$)))|(?R))

Test it on ideone.com

(?(R)|^(?=[a-z])) the very first character must be a lowercase letter
(?!.*(?&K)) the string cannot contain letters in the ASCII range [?-K]
(?|...|(?'k'j'k'?)|...) matches j'k (the other groups are essentially red herrings)
(?(3)\3|3){3} recursively match the 3rd group, or '3' after 3 levels of recursion, repeated 3 times
(?(R)...|(?R)) recurse over the entire regex once or match a few characters
...(?!(?&k))... I think this is [?-K] again, but I can't remember
(?(R)|...$) after recursion, match some groups and end the string
|(?R) if anything fails to match, then it's time for infinite recursion :D

\$\endgroup\$
8
  • 4
    \$\begingroup\$ Match: j'k3j'kj'k3j'kj'kj'k3j'k3j'kj'k3j'kj'kj'k3R-k-<grc>-j'k<grc>-j'k$j'k-k- Non-match: HOLYCRAPTHATWASEVIL (match available at ideone.com/pXaGaX for proof) \$\endgroup\$
    – user15244
    Oct 16, 2014 at 0:14
  • 16
    \$\begingroup\$ Everybody who tried to solve this and got even halfway there is now prepared to send 2 bug reports and 3 documentation patches for the perl regexp engine. (And all of us for different things) \$\endgroup\$
    – user15244
    Oct 16, 2014 at 0:24
  • 7
    \$\begingroup\$ +1 for cool key and having emoticon in your regex [^_^] (-.-) \$\endgroup\$
    – justhalf
    Oct 16, 2014 at 2:24
  • \$\begingroup\$ @WumpusQ.Wumbley Well done! I think the robbers are winning this one :( \$\endgroup\$
    – grc
    Oct 16, 2014 at 3:42
  • 3
    \$\begingroup\$ My previous comment was mostly a joke, but maybe some explanation would be nice. The use of named capture groups inside (?|...) is tricky, but it is documented. See the passage in perlre that starts with Be careful when using the branch reset pattern in combination with named captures. The trick is that groups that have the same number but different names are the same group, while groups that have the same name but different numbers are different groups. \$\endgroup\$
    – user15244
    Oct 22, 2014 at 13:22
12
\$\begingroup\$

JS flavor, 9998 bytes [cracked]

^(?!.*(.).*\1)(?=M)((?=!7|!D|!a|!§|!¾|!Ö|!ù|!Ě|!į|!Ň|"C|"s|"t|"¡|"°|"»|"è|"ñ|"÷|"ķ|"ļ|"Œ|#W|#k|#l|#o|#q|#¶|#À|#Â|#Æ|#č|%!|%1|%O|%ÿ|%Ĕ|%Ğ|%Ī|%ĭ|&e|&q|&Õ|&æ|&ü|&đ|&Ĩ|'%|'`|'k|'¯|'É|'í|'þ|'ė|'Ğ|'ĩ|'IJ|'ļ|'ł|,%|,'|,l|,ª|,®|,¸|,¹|,ã|,õ|,Ċ|,Ġ|,Ī|,İ|,Ņ|-U|-V|-»|-Ï|-Þ|-ì|0_|0u|0°|0Ġ|0İ|0ł|1#|1-|1g|1å|1é|1ą|1Ļ|1ń|2B|2O|2¬|2ë|2ò|2õ|2Ğ|2ĩ|2į|2IJ|2ļ|3d|3²|3Ï|3Þ|3ß|3ç|3ø|3ĉ|3ķ|3ĸ|3Ŀ|4c|4£|4ß|4ã|4Ċ|4ģ|4Ĩ|4ő|4Œ|5&|5Q|5û|5Ā|5ě|5ĩ|6ú|6Ķ|6Ł|7Q|7V|7e|7²|7Á|7Þ|7à|7đ|7Ġ|7ĵ|8w|8¯|8¾|8ņ|8ő|9H|9Y|9i|:6|:s|:¬|:ð|:ü|:Ĉ|:Ċ|:Ĵ|:ĸ|:Ŀ|;X|;®|;¯|;²|;¸|;Ó|;à|;ĥ|;Œ|<-|<t|<å|<ø|<Į|<Ľ|<ō|=&|=l|=¨|=Á|=Ý|=Č|=Ĩ|=Ń|>-|>±|>¸|>Ä|>à|>ð|>ó|>Ī|@B|@F|@_|@³|@´|@Ó|@Ü|@ã|@û|@Ğ|@ğ|@Ĭ|@İ|@Ŀ|A5|AV|A_|Ax|A¹|AÅ|AĞ|AĶ|Aņ|Aō|B¼|BÂ|Bä|Bç|BĊ|Bį|Bİ|BĻ|BŅ|C1|C<|CG|Cy|C~|C¼|Cì|Cù|Cō|DT|DU|Dc|Dj|D¤|DÂ|DÑ|DĀ|Dİ|E,|E¬|E¼|E×|Eā|Eė|Eń|FZ|Ft|F»|F¿|FÈ|FØ|Fç|Fì|Fć|FĬ|Fı|FŅ|Gj|Gl|Gv|G¯|Gâ|Gï|GĖ|Gę|GĦ|Gĭ|H8|HB|HS|Hu|H¥|HÃ|HÌ|Hø|HĆ|HĒ|HĬ|Hĭ|I=|It|I©|Iæ|IĿ|Iō|J1|J3|J5|JQ|JÉ|JÔ|J×|Jă|JIJ|K-|KP|KÄ|Kî|Kā|KĐ|Kġ|KĨ|KĴ|L!|LÐ|Lá|LĚ|LĠ|M5|M¿|MÅ|Må|MĈ|MŊ|N,|N2|N5|NB|Nh|NÂ|NØ|NÜ|NĖ|Nĝ|NŃ|O;|Of|O¯|O¸|Oå|OĈ|Oď|Oē|OIJ|P7|PQ|Pp|P£|Pđ|PĴ|Pŀ|Q7|QR|Q¥|QÝ|Qî|Qī|Qĸ|Qŀ|Qő|R0|RA|RI|RN|R¥|R¼|Rö|Rû|RĬ|RĮ|RŎ|S;|SC|ST|Sd|Sy|S§|TX|Td|Tw|Tª|T¿|Tõ|U0|U:|UÊ|Uĉ|Uę|UĢ|UĦ|Uį|UĶ|Uň|V:|Vq|Vs|V¦|VÂ|Vó|Vþ|Wh|WÅ|WÉ|Wê|Wô|Wģ|Wň|X:|XI|XS|X`|Xâ|Xċ|Xė|XĠ|Xģ|Y"|YX|Yb|Yn|Yo|Y£|Y§|YÌ|YÎ|YÚ|Yá|Yă|YĜ|Yĥ|YĿ|Yʼn|Z6|Z:|Z;|Z¶|Zå|Zæ|Zċ|Zĺ|ZŊ|_,|_-|_c|_g|_à|_ĉ|_Ħ|_ł|`I|`z|`ð|`ă|`IJ|`ij|a4|a9|aF|a½|aä|añ|aď|aĝ|aĸ|b&|b7|b¸|bÝ|bë|bĺ|bņ|bŊ|c&|cP|cr|cÄ|cÑ|cÖ|cČ|cę|cĩ|cIJ|cķ|cĿ|d"|dI|d¥|d¦|dä|dģ|eK|e²|eý|eą|eČ|eĔ|eIJ|eĶ|eń|fM|fm|f¥|fÇ|fÒ|fæ|fì|fć|fě|fĝ|g!|gN|gx|gz|gÍ|gĚ|gĞ|h"|h¬|h¶|hä|hì|hï|hĆ|hņ|hŋ|hŏ|i'|i9|i¢|i¤|iÓ|iÖ|iā|iĕ|iĝ|iį|iĶ|jH|jT|j£|jµ|j·|jø|jĸ|jŐ|k0|k2|kA|k~|k¨|k½|kÙ|l&|lX|lc|ln|l£|l¥|lµ|lÃ|lå|lé|lĩ|lŌ|lŒ|m-|mW|mÐ|mĘ|mĮ|mĸ|n!|n2|nJ|nU|n¬|n½|nĆ|nĒ|nĔ|nĭ|nŇ|o5|o<|oD|oM|oÖ|oĂ|ps|pz|pº|pê|pĢ|pĥ|pIJ|qK|qa|q§|qÛ|qç|qý|qă|qĒ|qĴ|qĶ|qń|rA|re|rj|r§|r«|r¿|rÃ|rß|rò|rĔ|rĖ|rĢ|rķ|sD|sc|sÍ|sĀ|tT|tW|ta|t£|t¯|t±|tÊ|tÑ|tĚ|tļ|uV|ua|ub|uf|u¦|u´|u»|u¾|uË|uØ|uĞ|uĪ|uĹ|v:|vi|vw|v§|v½|vÄ|vÈ|vÌ|vù|vĮ|vļ|vʼn|vŎ|w!|w0|wZ|wg|wÞ|wæ|wò|wù|wĥ|wħ|wŎ|xD|x©|x®|xá|xû|xģ|xľ|xł|yC|ya|yr|y²|yÉ|yò|yĆ|yĠ|yĵ|yŒ|zM|zi|z¯|zø|zú|zć|zđ|~5|~Y|~¨|~º|~Û|~å|~ê|~ô|~ü|~ą|~ĥ|~Ī|~İ|~Ľ|~ō|¡J|¡±|¡¼|¡Ê|¡Ë|¡Ñ|¡ã|¡Ă|¡Ġ|¡Ĩ|¡ī|¡Œ|¢@|¢G|¢±|¢º|¢ç|¢Đ|¢İ|¢Ŀ|£F|£e|£Þ|£ä|£Ĵ|¤P|¤p|¤¯|¤µ|¤þ|¤ď|¤Ģ|¤ī|¥Z|¥¤|¥È|¥Ñ|¥û|¥Ď|¦T|¦Y|¦Z|¦a|¦b|¦e|¦q|¦r|¦¡|¦³|¦ĩ|¦IJ|¦ĺ|§b|§n|§w|§¿|§Ç|§Đ|¨3|¨Ã|¨Ë|¨Î|¨ë|¨÷|¨Č|¨ġ|¨Ī|¨Ĺ|¨ł|¨Œ|©I|©Z|©Ý|©ë|©ü|©ġ|©ŋ|ªP|ªo|ªr|ª¨|ª¯|ª²|ª¾|ªÇ|ªÔ|ªÙ|ªĉ|«K|«p|«£|«¨|«©|«¬|«®|«Õ|«Þ|«ß|«ö|«Đ|¬!|¬j|¬ª|¬¼|¬À|¬Ã|¬Ì|¬ú|¬ő|®#|®´|®É|®č|®đ|®ī|®ʼn|¯9|¯g|¯n|¯¹|¯È|¯Ē|¯ę|¯ġ|°N|°d|°k|°m|°s|°²|°È|°Î|°ê|°ó|°ʼn|±%|±R|±Y|±r|±æ|±Ŀ|±ń|²D|²H|²U|²×|²ã|²ä|²ç|²ą|²ħ|³`|³Ë|³ã|³ë|³ò|³ô|³ø|³Ċ|³Ĥ|³Ŀ|´~|´§|´Ê|´è|´Ķ|´Ŏ|µ:|µC|µ¢|µØ|µó|µĠ|µģ|µĤ|¶!|¶0|¶7|¶Y|¶¤|¶À|¶Ö|¶Ħ|¶ő|·p|·Á|·Ç|·ë|·î|·Ļ|·Ŋ|¸X|¸Z|¸¦|¸÷|¸ú|¸Đ|¸ĝ|¹,|¹>|¹M|¹Z|¹a|¹¢|¹Ì|¹×|¹Ø|¹þ|¹ĉ|¹Ĩ|º>|ºj|ºá|ºç|ºý|ºć|»2|»c|»°|»Ä|»ñ|»Ġ|»Ŋ|¼3|¼F|¼c|¼d|¼x|¼y|¼Ä|¼É|¼û|¼Č|¼ē|¼Ĩ|¼Ĭ|¼Ĵ|¼Ĺ|½k|½Ø|½ø|½ħ|¾2|¾:|¾L|¾¿|¾Á|¾ñ|¾ô|¾÷|¾đ|¾ĥ|¾Ń|¿D|¿«|¿ö|¿ø|¿Ĕ|¿ę|¿Ļ|¿ō|À3|ÀW|À°|ÀÆ|Àđ|ÀĘ|ÀĞ|Àģ|Àİ|Á§|Áé|Áõ|ÁĜ|Áĝ|ÁĪ|Áʼn|Â&|ÂB|ÂM|¿|Âø|Âħ|Âĺ|ÂĻ|ÂŁ|Âʼn|Ã`|Ãt|â|é|ÃĆ|ÃĖ|Ãĥ|Ãĩ|Ä_|Ä¥|ÄÌ|ÄÞ|Äð|ÄĆ|Äİ|ÄŁ|Å@|ÅY|Å«|ÅĄ|Åı|Åĸ|Æ;|ÆK|Æv|Ƶ|ƹ|ƽ|ÆÇ|ÆÛ|Æõ|Æü|ÆĆ|ÆĤ|Çd|Ǻ|ÇĔ|Çě|Çģ|ÇĶ|ÇĽ|Èd|Èz|È~|È´|Ƚ|ÈÂ|Èæ|Èõ|ÈŅ|ÉH|ÉO|ÉÌ|Éï|ÉČ|Éę|ÉĬ|Éĭ|ÉĴ|ÉŎ|Ê%|Ê6|ÊI|Êk|Êy|ʳ|ÊÁ|Êñ|Êą|ÊŃ|Ë!|ËH|Ëh|˺|Ë»|ËÆ|Ëğ|ËŌ|Ì3|Ì7|ÌG|Ìp|Ì«|Ìè|Ìï|ÌĮ|ÌŎ|ÍZ|Íd|Í©|ÍÖ|Íá|Íê|Íø|Íā|ÍŊ|Î-|Î_|ÎÊ|Îæ|Îó|Îù|ÎĀ|ÎĐ|Îġ|Îĭ|ÎŇ|Ï"|Ï5|Ï7|ÏA|ÏH|Ïl|ϱ|Ϲ|ÏÈ|ÏØ|ÏÚ|ÏÛ|ÏĻ|Ïʼn|ÐR|з|ÐÀ|ÐÓ|ÐĒ|Ðě|ÐĶ|Ðľ|Ñ©|ѵ|ÑÅ|ÑÈ|Ñʼn|ÒV|ÒÇ|Òĉ|Òħ|ÒŃ|Ó2|ÓD|ÓÎ|Óç|Ó÷|Óù|ÓĈ|Óķ|ÔE|ÔJ|Ôf|Ôy|ÔÆ|ÔÞ|Ôâ|ÔĂ|ÔĨ|Õ3|ÕG|Õh|Õ¹|ÕÁ|ÕÐ|Õÿ|Õğ|Õī|Ö7|ÖB|Öª|Ö¼|Öÿ|Öħ|Öij|×6|×>|×f|×¢|×µ|×·|×Â|×Ê|×Ñ|×ã|ØG|د|ØÄ|ØÊ|Øé|Øë|ØĊ|ØŇ|ØŐ|Øő|Ù:|Ùh|Ùx|Ù²|Ùč|Ùē|Ùę|Ùě|ÙĨ|ÙŇ|ÚE|Úq|Ú®|ÚÄ|ÚÒ|ÚÜ|Úä|Úí|Úı|Úķ|Û'|ÛW|Ûo|Ût|ÛÓ|Ûô|Ûõ|Ûû|Ûʼn|Ûŋ|Ü!|ÜJ|ÜÆ|ÜŐ|ÝR|Ýg|Ýq|Ýu|ÝÜ|Ýß|Ýð|Ýø|Ýč|ÝĶ|Ýʼn|Þº|ÞÝ|ÞĂ|Þą|Þć|ÞĠ|ÞĨ|ßu|ßÀ|ßė|à4|àS|à`|àk|à§|àé|àø|àĊ|àę|àģ|àĬ|á3|á£|á¶|áÄ|áÏ|áÑ|áâ|áü|áČ|áĽ|áņ|áŌ|â#|âY|â£|âº|âÓ|âġ|âĭ|âı|âŐ|âŒ|ã,|ã1|ã7|ã8|ãé|ãĭ|ä3|ä6|äN|ä¢|ä©|ä¬|äÏ|äĖ|äį|äŏ|åN|å¡|å¾|åØ|åë|åû|åč|åě|æ7|æT|æt|æ¸|æá|æï|æā|æij|ç2|çA|çJ|çl|ç¥|ç¬|çĝ|çĸ|èl|èq|èÓ|èÙ|èČ|èĖ|èĩ|èņ|èʼn|èő|éV|éZ|é®|é´|éí|éó|éû|éą|éě|éĭ|éŃ|ê5|êv|ê«|ê¶|êº|êÃ|êÔ|êİ|ëB|ëb|ë¤|ë¨|ëÎ|ëę|ëĞ|ì#|ì,|ì=|ì>|ìQ|ìS|ìV|ìº|ìā|ìġ|íJ|íV|í~|í¶|íò|íø|íă|íė|íĭ|î<|î=|îD|îR|îµ|îÚ|îÛ|îå|îê|îþ|îĒ|îĜ|îğ|ï%|ï,|ïa|ïu|ïÀ|ïÁ|ïá|ïĄ|ïą|ïċ|ïġ|ïĿ|ïŁ|ïŌ|ð6|ðE|ðp|ð¬|ðÞ|ðä|ðĚ|ðğ|ðļ|ñ1|ñ2|ñX|ñi|ñá|ñú|ñû|ñü|ñį|ñŊ|òB|ò«|ò¿|òÝ|òê|òď|ó5|óÄ|óÇ|óÈ|óÓ|óÕ|óĨ|óļ|ô4|ôh|ôÖ|ôî|ôþ|ôğ|ôŅ|õo|õ¢|õ¶|õÆ|õÓ|õä|õČ|õĕ|õģ|ö7|ö@|ön|ö¢|öÉ|öÒ|öÛ|öâ|öĝ|÷-|÷J|÷p|÷Ò|÷Ģ|÷ĭ|÷ı|÷ʼn|ø,|øo|ø¥|øÆ|øç|øè|øù|øĤ|øĥ|øħ|øň|ù7|ù9|ùs|ùu|ù¹|ùÍ|ùĆ|ùę|ùě|ùĹ|úG|úÅ|úÕ|úÖ|úÜ|úã|úç|úĂ|úĦ|û%|û;|ûR|ûh|ûu|ûz|û´|ûÐ|ûë|ûń|ûŊ|ü_|ü²|üê|üē|üğ|üł|üŅ|ý8|ý¨|ý©|ýÍ|ýÜ|ýĄ|ýċ|ýĩ|ýı|ýIJ|ýĸ|ýł|ýň|ýŎ|þ;|þD|þJ|þT|þr|þ·|þè|þĆ|ÿO|ÿÒ|ÿæ|ÿð|ÿć|ÿğ|ÿŇ|ĀA|ĀR|Ā_|Āv|Āá|ĀĘ|Āģ|Āİ|ā6|āM|ā¸|āä|āĮ|ĂX|ĂÁ|ĂÕ|ĂĚ|Ăķ|ĂĹ|ă"|ă°|ă¸|ăÉ|ăĆ|ăĚ|ăğ|ăĸ|ăĻ|ăŃ|ĄG|ĄJ|ĄK|Ą`|Ąc|Ąd|Ąg|Ąl|Ą³|ĄÄ|ĄÊ|ĄÌ|Ąú|ĄĽ|ą;|ąL|ąc|ąd|ąo|ąr|ą®|ą±|ąÄ|ąÅ|ąÇ|ąÍ|ą×|ąĈ|ąĎ|ąĐ|ąĩ|ąŌ|Ć´|Ƹ|Ć¼|ĆÑ|ĆØ|Ćí|ĆĊ|Ćņ|ĆŌ|ć4|ćx|ćy|ć¦|ć«|ćù|ćŃ|Ĉ&|Ĉ8|ĈE|ĈK|Ĉn|Ĉ¨|Ĉà|Ĉé|Ĉû|Ĉđ|Ĉĥ|ĈĪ|Ĉī|Ĉņ|ĉ@|ĉa|ĉÇ|ĉ×|ĉĩ|ĉň|Ċ#|Ċb|Ċt|Ċ»|ĊÁ|ĊÚ|Ċä|Ċÿ|Ċĝ|Ċĩ|Ċį|ċ'|ċD|ċ¶|ċÖ|ċê|ċþ|ċğ|ċņ|ČM|Čs|Č£|ČĨ|Čį|č±|čÖ|čè|čć|čğ|čń|čʼn|Ď`|Ď¡|Ď·|Ď¾|Ď¿|Ďą|Ďij|Ďŋ|ď"|ď5|ď8|ď=|ďD|ďs|ďØ|ďÚ|ďí|ďġ|ďĩ|ďļ|ĐF|ĐS|Đg|Đk|Đn|Đv|Đ~|ĐÖ|ĐÚ|ĐÜ|Đâ|ĐĞ|đA|đf|đ´|đ¸|đ¿|đÈ|đÖ|đà|đĽ|đŀ|đŌ|Ē%|ĒH|ĒÍ|ĒĹ|ĒĻ|ĒŁ|ĒŃ|ĒŇ|ē;|ēG|ēa|ēe|ēq|ē¶|ē»|ē÷|ēň|Ĕ"|Ĕ4|ĔÃ|Ĕý|Ĕą|ĔĆ|ĔĚ|ĔĞ|ĔĨ|ĕ"|ĕm|ĕw|ĕ¨|ĕ®|ĕÌ|ĕÑ|ĕĤ|Ė#|ĖR|Ėe|Ėu|Ė~|Ė¯|Ėĩ|ĖĬ|ėH|ė¹|ėö|ėú|ėÿ|ėĨ|Ęs|ĘÝ|Ęą|ĘČ|Ęĝ|Ęī|Ęĺ|Ęʼn|ęA|ęk|ęp|ę»|ęè|ęą|ęĐ|ęĨ|Ě'|Ě9|Ěe|Ěm|Ěo|Ě£|Ěª|Ě¾|Ěå|Ěë|Ěă|ĚĎ|ĚĜ|ĚĞ|ěP|ěx|ěê|ěî|ěö|ěĂ|ěĤ|ěĭ|ěļ|Ĝ%|ĜÜ|ĜĽ|ĝJ|ĝh|ĝ¹|ĝÃ|ĝÈ|ĝĖ|ĝĞ|ĝŇ|ĝŒ|Ğ&|Ğe|Ğs|ĞÖ|ğX|ğ²|ğ´|ğ¼|ğÙ|ğò|ğĂ|ğđ|ğĕ|ğĨ|ğĬ|ĠB|Ġc|Ġµ|ĠÈ|Ġè|Ġì|Ġđ|Ġě|ġ5|ġ<|ġH|ġm|ġº|ġÒ|ġü|ġă|ġĶ|ġŀ|Ģ;|Ģ¤|Ģ«|ĢÍ|ĢØ|Ģù|Ģă|ĢĐ|Ģđ|ģ-|ģL|ģ«|ģë|ģþ|ģċ|ģČ|ģĨ|ģĻ|Ĥf|Ĥª|Ĥñ|ĥM|ĥN|ĥU|ĥf|ĥz|ĥ»|ĥõ|ĥň|Ħ`|Ħj|Ħu|Ħ°|Ħ´|ĦÁ|ĦÈ|ĦÕ|Ħæ|ĦĤ|ħ4|ħp|ħ¡|ħ¦|ħ¶|ħß|ħç|ħĴ|ħĵ|ĨC|Ĩ°|ĨÂ|ĨÌ|Ĩç|Ĩõ|ĨĔ|Ĩŏ|ĩ8|ĩl|ĩt|ĩw|ĩċ|ĩđ|ĩĥ|ĩī|ĩŅ|Ī4|Ī9|ĪP|Īz|Ī±|ĪÅ|ĪÈ|ĪÝ|Īä|Īđ|ĪĦ|ĪĬ|ĪĽ|īb|īl|ī¥|ī¦|īÌ|īì|īČ|īĎ|īĐ|Ĭ#|Ĭ4|ĬF|Ĭ¤|Ĭê|Ĭí|Ĭû|Ĭĝ|ĬŌ|ĭ1|ĭK|ĭL|ĭz|ĭ¡|ĭ¯|ĭÌ|ĭâ|ĭĘ|ĭě|ĭĺ|ĮM|ĮR|Įd|Įx|Į¤|ĮÃ|ĮË|ĮÚ|Įå|ĮĤ|ĮĦ|Įī|į&|įD|įI|į¥|į«|įÉ|įÕ|įÛ|įĉ|įđ|įĒ|İQ|İi|ݬ|ݾ|İÕ|İ×|İĄ|İĬ|İľ|ı4|ıa|ıd|ıe|ıf|ı¡|ıĐ|ıĖ|ıIJ|IJ:|IJT|IJU|IJm|IJÛ|IJķ|IJŎ|ij0|ijb|ij¢|ij«|ijé|ijí|ijĎ|ijĘ|ijķ|Ĵ#|ĴF|ĴG|Ĵµ|Ĵ¹|ĴÈ|ĴÏ|Ĵý|Ĵþ|ĴĖ|ĵ8|ĵE|ĵK|ĵ¦|ĵ±|ĵÙ|ĵó|ĵõ|ĵĹ|Ķ6|ĶE|Ķl|Ķm|Ķ£|Ķ²|ĶÅ|Ķ÷|ĶĀ|Ķă|ĶĆ|ķv|ķ«|ķå|ķĢ|ķŌ|ĸ9|ĸH|ĸ¼|ĸè|ĸý|ĸĕ|ĸį|ŧ|Ĺ·|ĹÇ|ĹÈ|Ĺġ|Ĺĩ|ĺ#|ĺ6|ĺp|ĺr|ĺu|ĺæ|ĺí|ĺĖ|Ļ@|ĻI|Ļn|Ļ£|Ļ¶|ĻÂ|Ļú|ĻĮ|ĻŎ|ļ=|ļK|ļO|ļ_|ļ´|ļÀ|ļÄ|ļó|Ľ>|ĽC|ĽD|ĽG|ĽZ|Ľk|Ľr|Ľ¼|ĽÌ|Ľâ|ĽĮ|ĽŒ|ľf|ľÙ|ľÞ|ľĂ|ľī|ľł|ľņ|ĿÊ|Ŀď|Ŀđ|ĿĚ|Ŀĵ|ĿĻ|Ŀŏ|ŀC|ŀM|ŀ®|ŀà|ŀð|ŀõ|ŀČ|ŁE|ŁÁ|ŁÄ|Łõ|Łķ|ŁĿ|ł4|łG|łu|ł¬|łÏ|łò|łČ|łč|łĐ|łŌ|Ń6|Ń¿|ŃÅ|ŃË|ŃÚ|Ńü|Ńě|Ńņ|ń4|ń<|ńE|ńx|ń»|ńÄ|ńď|ńĺ|Ņ,|ŅP|Ņe|Ņn|Ņo|Ņ©|Ņ¯|Ņ½|ŅÛ|ŅĂ|ņî|ņð|ņô|ņĈ|ņī|ņĬ|ņı|Ň8|Ň:|ŇD|ŇT|Ň_|Ňd|Ňu|Ňª|Ňā|Ňć|ŇĈ|Ňň|ňK|ňL|ň¬|ňÇ|ňÏ|ňþ|ňĐ|ňĠ|ňŐ|ʼnQ|ʼn_|ʼnf|ʼnÉ|ʼnË|ʼnĨ|ʼnŃ|Ŋ0|ŊM|ŊW|ŊÔ|ŊĠ|ŋC|ŋH|ŋK|ŋÍ|ŋÒ|ŋØ|ŋÞ|ŋı|ŋĹ|Ō,|Ōl|Ō³|Ōò|Ōā|ŌĖ|ŌĚ|ŌĬ|ŌĮ|Ōĸ|ŌŒ|ōJ|ō¿|ōÀ|ōÝ|ōʼn|Ŏ8|Ŏ;|ŎQ|ŎV|Ŏ§|ŎÄ|ŎÏ|ŎĎ|ŎŇ|ŏ=|ŏD|ŏV|ŏ¹|ŏÈ|ŏÒ|ŏč|ŏĐ|ŏī|ŏĿ|ŏʼn|Ő2|Ő<|ŐC|ŐX|Őg|Ől|Őp|Ő®|Őİ|ő8|ő¹|őÀ|őó|őć|őĊ|őĖ|őĦ|őķ|őĸ|őŀ|ŒB|Œv|ŒÀ|ŒÒ|Œā|Œĉ|Œė|ŒĜ|ŒĦ|Œķ|Œľ).){255}Ň$

Tested on Regex101

Each matched string is a Hamilton path from M to Ň.
I know this is not secure enough. I don't know how to generate hard Hamilton path problems either. It has too many solutions. And as Martin Büttner said, Mathematica did it instantly. But this is just another NP-complete approach other than COTO's. Feel free to improve this idea and post new answers.
The solution I have originally generated is: https://regex101.com/r/tM1vX8/2

The solution I have generated:

MĈàękÙēGâġ<øÆv:ĴÏĻĮ¤ĢùĹ·îĜĽDÂŁEā6ĶĆŌĸ¼yò¿Ĕýı¡Ë!į&qKPpzđȽħ¶YÌïÁéVþèlåN2O¸úÜŐİľfćx®čńďļ=¨3d"÷ĭ¯9i'ĞsĀAÅĄ³`ðĚmĘĝŒBç¬ő¹>-ìS§nUĉňĠěĤª¾ôŅ,ĊtÊIĿĵ±RĬíăÉČĨŏĐÖij0°²ã1gÍáÑʼnŃÚÒÇģLÐĒ%ĪĦu¦añû´~ą;ĥ»créüêºjµó5ĩċğĕwŎÄ¥ĎŋØëÎæTXėH8ņībŊÔÞÝßÀWhäĖeIJÛõÓķ«ö7QŀCōJ×¢@_ł4£FZĺ#oĂÕÿŇ
\$\endgroup\$
12
  • 3
    \$\begingroup\$ Matches: See regex101.com/r/wK9hI1/1 Doesn't match: good_job_user23013! \$\endgroup\$
    – harius
    Oct 16, 2014 at 20:25
  • 14
    \$\begingroup\$ I imagine us being divided into 2 camps right now: those burning CPU and hoping to get lucky, and those trying to prove P=NP in a couple of days. \$\endgroup\$
    – user15244
    Oct 16, 2014 at 20:26
  • 1
    \$\begingroup\$ @WumpusQ.Wumbley And those of us using Mathematica. ;) \$\endgroup\$ Oct 16, 2014 at 20:37
  • 2
    \$\begingroup\$ Since harius can't comment to elaborate how he cracked it, I'll quickly outline how I did it: the pattern indeed encodes a directed graph with 256 vertices (represented as characters) and 2270 edges (represented as pairs of characters that are allowed to be consecutive) and each match is a Hamiltonian path through that graph from M to Ň. Mathematica has a function FindHamiltonianCycle. We can turn this into a cycle that traverse Ň -> M by adding a new edge and connecting Ň and M through it. Thankfully, Mathematica finds such a cycle instantly. :) \$\endgroup\$ Oct 16, 2014 at 21:01
  • 1
    \$\begingroup\$ Well, I'm 3rd, but I felt like finishing my home-grown path-finder anyway. It gave me this: regex101.com/r/nT2xM6/1 \$\endgroup\$
    – user15244
    Oct 17, 2014 at 1:14
10
\$\begingroup\$

JS-Compatible RegEx - 3,571 bytes [cracked]

I... will... have... at least... one... uncracked.... submission. o\ __ /o

[^,;]|^(.{,255}|.{257,})$|^(?!.*,;,,;;)|^(?!.*,;;,,;)|^(?!.*..,;;;,..,.)|^(?!.*.,.;.;.,.,,)|^(?!.*....,,....;;.;.;)|^(?!.*;.{8};,;;;..)|^(?!.*.{8};;.{6};,.,;)|^(?!.*..;....,.;;.{5};;...)|^(?!.*;,.;.{7},...;.{6};...)|^(?!.*...,.,..,,...,.{7};....)|^(?!.*.,;.;.{11};.{9};..,.)|^(?!.*.,.{6},....;.{11};,...,)|^(?!.*..;.{5};....,.{6};,.{12};.)|^(?!.*,,.,,.{8};.{11};.{10})|^(?!.*...,.{9};..,....;.{6},...;.{8})|^(?!.*.{6},.{8},.{6},.{8},..;.,....)|^(?!.*.{7};..;.{5},....;.{10};...;.{9})|^(?!.*..;.{7},.{5};;.{12},.{13},.)|^(?!.*.{5},..;...;.{5};..;.{6},.{22})|^(?!.*.{10},.{8},.{6},;.{14};.;.{6})|^(?!.*..,.;...,.{19};.;..;.{22})|^(?!.*.{6};..;.{14},,.{11};....,.{13})|^(?!.*.{8},.{12};.{19},.{6},;.{6},....)|^(?!.*.,.{11},...,.{7},.{16},.{11},.{6})|^(?!.*.{15};.{7};..;..,.{24},.{7},...)|^(?!.*...,,.{25};...;...;.{19},.{7})|^(?!.*.{26},....,....,.{15},.{6},.{6};....)|^(?!.*.{6};.,.{28};.{6},.{21},.;..)|^(?!.*.{21};..;..,.{22},.{21};,..)|^(?!.*.{5};.{22};,.{17};.{18},,.{8})|^(?!.*.{9};.{25};,.{20},.{6},.{14};.)|^(?!.*.,.{9},.{8};.{8};.{10};.,.{38})|^(?!.*.{18};.{8},.,.;.{5};.{6},.{41})|^(?!.*.{15},.{16};.{7};.{17};.{8};..,.{15})|^(?!.*.{18};.,.{25};..,..;.{13};.{24})|^(?!.*.{10};.{16},.{33};...;.{17},....,..)|^(?!.*.{13},.{46},.{9},.{11},,.,.{10})|^(?!.*.{14},.{33},.{18};....,.;.{16},....)|^(?!.*.{16};....;,.{8},.{30},.{31},.{6})|^(?!.*.{9},;.{15};.{22};.{30},.{16};...)|;.,,;;.;|,;,;,.,.|.;;,.;;;|;.;,,,.;|,...;.;.,,.;.|,.,.;.{5},,;|...;;....;;;;|;..,,,.;..;..|..;;,,..;.{7};.|;..,.,,...;...,...|...;;,.,.;.;.{6}|.;...;,....;.;...,|.;.{8};,.{6},.;.;|.{5},...,...;...;.;..;|...;....;..,..,.;..;...|...;.{5};,.{5},...,.;|;.,.{12},..;;.{7};|...;.{5},..;;.{9},..;.|.;,,..;.{13};....;..|.,;.{15},,...,.,..|.{8};.,....,...,..,.{9};|...;.;.{11},..,...;....;...|.,.,.{9};;....;..,.{10}|.{5};.,;....,.{15};..,|....;.{10};.;....,.{10},;...|....;.{8};;.{6},...;.{5};.{6}|..,;;.{16};....,;.{10}|.{18};.{9};,.,.,..;.|.{11},.{10};.;.;.{10};....,|....;.{11},.{10},..;.,.;.{8}|..,....,.;.{5},.{9},.{7};.{9}|.{7};.;.{5},.{13};.;.{7};...|.{5},.{15};;.{5},.{15},..;|.{12};...;..,.,..;.{5},.{17}|.{12},..;...;.{22},.,..,|.{10},.{11},.,.;.{11};;.{8}|.{11},.{9},.{5},...,.{14};.;....|;.{22};....,.;.{10};.{10};|.{13};...;.{13},.{6};.,.{10};.|.{11};....;.{17},.{9},.{5};,.|,.{14},.{12};.{6};...;.{14};...|..;.;.{19},.{16},.{5};.{6},...|.{27};..,;.{8};;.{8};.{7}|,.{6};.,.{20},.{13},.;.{11}|.{12};.{9},.{8};,.,.{17},.{10}|;.{22};..;.{5},..;....,.{22}|.{6},.{19};.{22};;,.{5};.{5}|;.{5},.{10};..;.;;.{39}|.{11};.{7};.;.{23};.{19};.;|,.{13};.{12},.,.{27};.{6},...|...;.;.{9};.{18};.;.{27},...|...;,.{12},..;.{28},.{15};..|....;.{8};..;...;.{17},.{19},.{14}|.{8};.{29};.{17};.{5};.{5};;...|...,..;.{14},.{8};.{12};.{18},.{10}|..;.;.{7};.{17},.{11},.{24},.{5}|;.{17},.;.{29};.{9};....;.{12}|.{5},..,.{6},.{16};;.{15},.{28}|...,.{12};..;.{10};.{31};.{14};|.{24},.{6},.{22},.,..,.{10};.{7}|.{10},.{12},.{5};.{12},.{7};.{23};.{8}|.{19};.,.{6},.{22},,.{7};.{22}|.{27};,.{14},..,.{7};.{15},.{12}|....;.{18},.{22},,..,.{27};....|...,.{11},.;.;.{9},.{46},.{11}|.{19},....,.{23},.{5},.{7};.{14},.{10}|.{19};,.{11};..,.{11};.{23};.{16}|.{11};.{34},.{14},.{9},.;.{13};|.{11};....,.{41},.{9};;.{8};.{14}|.{5};.;.,.{5};...;.,.{71}|.{6};.{13};....;....;.{20};.{24},.{16}|.{26};,.{19};....;.{11},.;.{26}|.{9},.{9},.{21},.{14};.{10};.{16};.{13}|.{10},.{5},.{9};.{13},...,.{24},.{28}|.{12},.{7};.{8};.{6};;.{36};.{23}|....;.{10},.{21};.{10};.{20},.{10},.{17}|.{19},.{7},.{17},.{9};.{13},.{22};.{10}|....,.{41};.{5},..,.{21};.{6};.{18}|.{25};....;.{28},.{12},.{19};.{8};.|.{10};....,.,.{22};.{11};.{44},.{5}

Resolves on virtually any string instantaneously. Testable on any JS console.

+100 rep to anyone who cracks this beast.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Challenge accepted... \$\endgroup\$
    – Unihedron
    Oct 17, 2014 at 17:08
  • 10
    \$\begingroup\$ Match: ThatWasActuallyFun. Non-match: ,,;,;,,;,;;;,;,;,;;,,,,;,,,;,;;,,,,,,;;,,,,;;,;,,,;,;;;;,;;,;;,;,,;,,;,;;;,;,;,;;,,,;,;;;;,;,;;;,;,,;,,,;,,,,;,;;;;;;,,,,,;,;,;;;;;,;;;,;;,,,;;;,,;,;;,,,;,,,,,,;,;,,;;,,;;,,,;,;;,,,;,,;;,;,;,;;;;,,;,;,,;;;;;,,;,,;;,,;,,;;,,,,;,,;,,;;,;;;,,,,,;,,,,,,,,;,,,,. \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 19:56
  • 5
    \$\begingroup\$ PLEASE! DON'T! BE! SO! QUICK! \$\endgroup\$
    – TwiNight
    Oct 17, 2014 at 20:24
  • 6
    \$\begingroup\$ dude, you're insane, this RegExp has 122 alternations, 40 of which are negative lookaheads, WTG++ \$\endgroup\$
    – CSᵠ
    Oct 17, 2014 at 20:29
  • 2
    \$\begingroup\$ @nneonneo: Lousy efficient SAT solvers. >___< But props for transforming the problem and making use of the tools available out there. I'll award the 100 rep to one of your answers ASAP, which is about 19 hours. \$\endgroup\$
    – COTO
    Oct 17, 2014 at 20:30
10
\$\begingroup\$

PCRE - 96bytes UTF8, no delimiters, no flags

[Defeated] because nneonneo is a wise-guy

(?<Warning>[You] \Will (*FAIL)!|\So just (*SKIP)this one!|\And (*ACCEPT)defeat!|[^\d\D]{16,255})

Nothing to see here, move along...

\$\endgroup\$
12
  • 1
    \$\begingroup\$ Match: So just *SKIPthis one!; No Match: This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is still not accepted. Snow leopards FTW. \$\endgroup\$
    – COTO
    Oct 17, 2014 at 21:56
  • \$\begingroup\$ This isn't PCRE syntax; it's plain Perl syntax. (The backtracking modifiers don't work on PCRE, AFAIK) \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 21:59
  • 6
    \$\begingroup\$ Match: Do just this one!. Non-match: WellThatWasTooEasy. (Tested with both Perl 5.12 and Perl 5.18 on my machine) \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 22:03
  • \$\begingroup\$ @nneonneo correct! PS: *VERBS exist in PCRE for at least 5 years, not enough documented indeed. \$\endgroup\$
    – CSᵠ
    Oct 17, 2014 at 22:06
  • \$\begingroup\$ @COTO the match is incorrect, NonMatch is ok. \$\endgroup\$
    – CSᵠ
    Oct 17, 2014 at 22:06
8
\$\begingroup\$

JS-Compatible RegEx - 733 bytes [cracked]

Let's try this a second time with the metrics reversed: a hulking regular expression but a relatively tiny key (most importantly, within the 256-byte limit).

[^a-e]|^(?:.{0,33}|.{35,}|.{11}.(?!babcde).{22}|.{17}.(?!daacde).{16}|.{23}.(?!ecacbd).{10}|.{29}.(?!ab).{4}|.{31}.(?!cd)..|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).(?!\4\8\1\2\3\10|\6\3\11\2\9\1|\6\2\9\3\4\11|\8\10\6\5\3\1|\1\8\4\5\3\7).{22}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{6}.(?!\15\14\16\19\21\12|\17\12\22\13\16\15|\19\14\12\20\18\21|\16\22\19\14\20\12|\21\19\13\18\15\22).{16}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{12}.(?!\31\32\24\28\26\23|\33\25\30\29\27\32|\28\27\23\24\29\30|\31\33\23\29\26\32|\26\28\25\24\23\33).{10}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{18}.(?!\34\39|\37\38|\34\37|\36\42|\43\41|\35\38|\40\35|\44\42).{4}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{20}.(?!\51\45|\53\54|\47\46|\45\54|\50\51|\53\45|\52\51|\52\48|\48\55)..)$

Resolves on virtually any string instantaneously. Tested on RegExr.

Expanded (for convenience):

[^a-e] |
^(?:
    .{0,33}|
    .{35,}|
    .{11}.(?!babcde).{22}|
    .{17}.(?!daacde).{16}|
    .{23}.(?!ecacbd).{10}|
    .{29}.(?!ab).{4}|
    .{31}.(?!cd)..|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).(?!\4\8\1\2\3\10|\6\3\11\2\9\1|\6\2\9\3\4\11|\8\10\6\5\3\1|\1\8\4\5\3\7).{22}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{6}.(?!\15\14\16\19\21\12|\17\12\22\13\16\15|\19\14\12\20\18\21|\16\22\19\14\20\12|\21\19\13\18\15\22).{16}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{12}.(?!\31\32\24\28\26\23|\33\25\30\29\27\32|\28\27\23\24\29\30|\31\33\23\29\26\32|\26\28\25\24\23\33).{10}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{18}.(?!\34\39|\37\38|\34\37|\36\42|\43\41|\35\38|\40\35|\44\42).{4}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{20}.(?!\51\45|\53\54|\47\46|\45\54|\50\51|\53\45|\52\51|\52\48|\48\55)..
)$

Best of luck to all. ;)

\$\endgroup\$
3
  • 5
    \$\begingroup\$ Match: aaaabaaacaaadaaa, Non-match: cacdbbcabdeababcdedaacdeecacbdabcd \$\endgroup\$
    – jimmy23013
    Oct 14, 2014 at 22:37
  • \$\begingroup\$ @user23013: I expected a crack, but not quite that quickly. Did you do it on paper? \$\endgroup\$
    – COTO
    Oct 14, 2014 at 22:53
  • 1
    \$\begingroup\$ Yes. There are only two possibilities left after the first two long expressions. And there is only one character not known after three, so I can simply try a few times to get the solution. \$\endgroup\$
    – jimmy23013
    Oct 14, 2014 at 23:09
8
\$\begingroup\$

.NET flavor, 60 bytes [cracked]

^((\d)(?!(|(\d\d)*\d|(\d{3})*\d\d|(\d{5})*\d{4}|\d{6})\2))+$

Tested with Regex Storm.

\$\endgroup\$
3
  • 4
    \$\begingroup\$ Match: 1234567890012345. Non-match: 1111222233334444. \$\endgroup\$
    – jimmy23013
    Oct 16, 2014 at 7:10
  • 8
    \$\begingroup\$ ٠߀०০੦૦୦௦౦೦൦๐໐༠၀႐០᠐᥆᧐᭐᮰᱀᱐꘠꣐꤀꩐0 So these are all considered digits in .NET... \$\endgroup\$
    – jimmy23013
    Oct 16, 2014 at 7:31
  • 2
    \$\begingroup\$ That's insane, half of those aren't even showing up right in my browser \$\endgroup\$
    – Sp3000
    Oct 16, 2014 at 8:52
7
\$\begingroup\$

Python flavour: 211 bytes [cracked]

Note: This answer was posted before the rule change about maximum key length

Thought I'd get the ball rolling with this:

(((((((((((((((\)\\\(58\)5\(58\(\\5\))\15\)9)\14\\919\)\)4992\)5065\14\(5)\13\\\14\\71\13\(\13\)4\\\13\\)\12\12\\28\13)\11)\10\\7217)\9\\)\8\\04)\7\)\(\8\()\6\(183)\5)\4\)65554922\\7624\)7)\3\)8\(0)\2\4\\8\\8)\1

(Tested on RegExr)


Simple backreference explosion of the characters \()0123456789

\$\endgroup\$
9
  • \$\begingroup\$ I can tell you that the accepted string is approx. 7 million characters in length. As for actually representing it somehow, maybe a 7 MB text file somewhere? \$\endgroup\$
    – COTO
    Oct 14, 2014 at 13:09
  • \$\begingroup\$ Yeah, that's pretty much the only way to go. I thought I'd start off with something that isn't hard to decipher, but the trick was with output generation. If the minute limit wasn't in place though this would have been much longer :P \$\endgroup\$
    – Sp3000
    Oct 14, 2014 at 13:22
  • \$\begingroup\$ Entering what I believe is the only string that matches your regex at RegExr.com reliably crashes my Chrome browser. In Safari it works but RegExr reports a 'timeout'. Have you successfully tested it online? \$\endgroup\$
    – Emil
    Oct 14, 2014 at 14:23
  • \$\begingroup\$ @Emil I tested it successfully in Firefox. And I'm still waiting to save it. \$\endgroup\$
    – jimmy23013
    Oct 14, 2014 at 14:28
  • 5
    \$\begingroup\$ The key is 5281064 bytes by my count. Uploaded file here (5 mb) mediafire.com/view/4jt41pzfp7855ax/match.txt \$\endgroup\$
    – stokastic
    Oct 14, 2014 at 17:35
7
\$\begingroup\$

JS-Compatible RegEx - 12,371 bytes [cracked]

After some encouragement by Martin, and seeing that other cops are happily submitting 600+ KB regexes, I decided to take the plunge once more with this (and prettified version here).

Resolves on virtually any string instantaneously. Testable on any JS console. Unfortunately the size makes it untestable by many online regex testers.

\$\endgroup\$
6
  • \$\begingroup\$ Ahaha I'll try not to go nuts with the regex sizes - this challenge is hard though :/ incriminates @user23013 \$\endgroup\$
    – Sp3000
    Oct 17, 2014 at 7:34
  • 2
    \$\begingroup\$ Match: this was not NP-hard. Non-match: nerdnydeprdoypoypwwwdprelwsprwssddayaeeeysyaaaypowroplsaoprdaolasnoylaeaeadeosladnnosyoywyesorlrydwddadoeyponneeyaaapesenaalnneydaewndplredlerwaawlnrssapapaopnrdwnslowdoanlrernpwyyarpprwnrssdlaopsnnrnnnardpaessldalroleswnnooarlpllasapsesaorardwreylayrr \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 8:57
  • \$\begingroup\$ I just bruteforced it completely (took ~0.06 seconds in Python) and obtained four admissible solutions, but due to a bug in your regex, your regex rejects many more solutions. (Basically, you don't check that every character in a given "substring" gets used, and you don't check that a "substring" only consists of 84 characters) \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 9:07
  • 1
    \$\begingroup\$ (Final note: regexpal.com handles this regex just fine; I'm guessing it probably just uses the browser's regex engine). \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 9:08
  • 1
    \$\begingroup\$ With 12k bytes there's no need to link to an external source. SE answers can have up to 30k characters. \$\endgroup\$ Oct 17, 2014 at 9:24
7
\$\begingroup\$

.NET flavor, 458 bytes [cracked]

^(?=[01]{10},[01]{10}$)(0|1((?<=^.)(?<l>){512}|(?<=^..)(?<l>){256}|(?<=^...)(?<l>){128}|(?<=^.{4})(?<l>){64}|(?<=^.{5})(?<l>){32}|(?<=^.{6})(?<l>){16}|(?<=^.{7})(?<l>){8}|(?<=^.{8})(?<l>){4}|(?<=^.{9})(?<l>){2}|(?<=^.{10})(?<l>){1})(?(l)(?<-l>(?=.*,(?:0|1(?<m>){512})(?:0|1(?<m>){256})(?:0|1(?<m>){128})(?:0|1(?<m>){64})(?:0|1(?<m>){32})(?:0|1(?<m>){16})(?:0|1(?<m>){8})(?:0|1(?<m>){4})(?:0|1(?<m>){2})(?:0|1(?<m>){1})$))|){1024})*,(?<-m>){669043}(?(m)(?!)|)

This one is easy. But I'll post a harder one later.

I think I'm pretty near the cryptographically secure answer.

Tested on RegexStorm.

This is basically about integer factorization. The matched string should be the binary representation of two integers A and B. For each 1 from A, it will match 512, 256, ..., 1 times group l, which can be added to get A. And for each time l, it will match B using lookahead, and B times group m which is similar to A times l. So m is matched a total of A*B times. Finally it removes the group m 669043 times and checks if there is no more m. So A*B must be exactly 669043.

For simplicity: 669043 = 809 * 827 and the solution is the binary form of these two numbers.

This method doesn't work with too big numbers to make it secure, because the Regex engine has to increase the number that many times. But I have posted a new answer to work with base 289 big integers. It has a 1536 bit long product.

Also thanks Martin Büttner for introducing the balancing group feature of .NET Regex in his answer.

\$\endgroup\$
8
  • \$\begingroup\$ This idea, wow... \$\endgroup\$
    – Sp3000
    Oct 18, 2014 at 1:37
  • 4
    \$\begingroup\$ Match: 1100101001,1100111011. Non-match: ThatsWhatIWantedToDo,Nice \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 3:23
  • 1
    \$\begingroup\$ I think the only problem is that the match takes exponentially long, and that the target integer has to be expressed as a repeat count (so it is most likely limited to 32/64/128 bits, which are all trivial to factor). I have some ideas on surpassing these limitations using Karatsuba multiplication, but then I get log(n)^2 sized regexes... \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 3:27
  • 1
    \$\begingroup\$ @Sp3000 pastebin.com/SW0YbQar This works. I'm not sure why. Perhaps its developer thinks matching empty strings repeatedly doesn't make sense. \$\endgroup\$
    – jimmy23013
    Oct 18, 2014 at 4:05
  • 1
    \$\begingroup\$ @Sp3000: not at all a surprise; you're basically asking the regex engine to count to 800000+. This is going to be really slow (especially when the "counting" is done via a regular expression evaluator virtual machine). \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 7:18
6
\$\begingroup\$

JS-Compatible RegEx - 2,447 bytes [cracked]

My final attempt.

I'm holding out hope that this one lasts at least a few hours before being cracked. After that, I give up. :P

[^a-f]|^(?:.{0,51}|.{53,}|.{11}.(?!d).{40}|.{12}.(?!a).{39}|.{13}.(?!a).{38}|.{14}.(?!f).{37}|.{15}.(?!d).{36}|.{16}.(?!a).{35}|.{17}.(?!d).{34}|.{18}.(?!c).{33}|.{19}.(?!f).{32}|.{20}.(?!d).{31}|.{21}.(?!d).{30}|.{22}.(?!d).{29}|.{23}.(?!f).{28}|.{24}.(?!d).{27}|.{25}.(?!b).{26}|.{26}.(?!f).{25}|.{27}.(?!f).{24}|.{28}.(?!e).{23}|.{29}.(?!c).{22}|.{30}.(?!c).{21}|.{31}.(?!b).{20}|.{32}.(?!d).{19}|.{33}.(?!e).{18}|.{34}.(?!c).{17}|.{35}.(?!a).{16}|.{36}.(?!a).{15}|.{37}.(?!e).{14}|.{38}.(?!b).{13}|.{39}.(?!f).{12}|.{40}.(?!d).{11}|.{41}.(?!f).{10}|.{42}.(?!c).{9}|.{43}.(?!f).{8}|.{44}.(?!e).{7}|.{45}.(?!c).{6}|.{46}.(?!b).{5}|.{47}.(?!b).{4}|.{48}.(?!f).{3}|.{49}.(?!a).{2}|.{50}.(?!d).{1}|....(.)(.)(.).....(?!\1|\2|\3).{40}|.(.).(.)..(.).....{1}.(?!\4|\5|\6).{39}|...(.)(.).....(.).{2}.(?!\7|\8|\9).{38}|......(.)(.).(.)..{3}.(?!\10|\11|\12).{37}|....(.)(.)(.).....{4}.(?!\13|\14|\15).{36}|..(.)(.)(.).......{5}.(?!\16|\17|\18).{35}|(.).(.)......(.)..{6}.(?!\19|\20|\21).{34}|..(.).....(.).(.).{7}.(?!\22|\23|\24).{33}|(.)..(.)(.).......{8}.(?!\25|\26|\27).{32}|...(.).....(.)(.).{9}.(?!\28|\29|\30).{31}|.(.)(.).....(.)...{10}.(?!\31|\32|\33).{30}|.(.)...(.)..(.)...{11}.(?!\34|\35|\36).{29}|(.)(.).....(.)....{12}.(?!\37|\38|\39).{28}|...(.).(.).(.)....{13}.(?!\40|\41|\42).{27}|..(.)(.)..(.).....{14}.(?!\43|\44|\45).{26}|(.).(.)....(.)....{15}.(?!\46|\47|\48).{25}|(.)..(.)...(.)....{16}.(?!\49|\50|\51).{24}|(.)(.)(.).........{17}.(?!\52|\53|\54).{23}|.(.)..(.)(.)......{18}.(?!\55|\56|\57).{22}|(.)...(.)..(.)....{19}.(?!\58|\59|\60).{21}|.......(.)(.)(.)..{20}.(?!\61|\62|\63).{20}|.(.).....(.).(.)..{21}.(?!\64|\65|\66).{19}|..(.)..(.)...(.)..{22}.(?!\67|\68|\69).{18}|..(.).(.).....(.).{23}.(?!\70|\71|\72).{17}|...(.).(.)..(.)...{24}.(?!\73|\74|\75).{16}|.(.)(.)(.)........{25}.(?!\76|\77|\78).{15}|(.).(.).....(.)...{26}.(?!\79|\80|\81).{14}|.....(.)..(.).(.).{27}.(?!\82|\83|\84).{13}|(.).(.).(.).......{28}.(?!\85|\86|\87).{12}|..(.)...(.)..(.)..{29}.(?!\88|\89|\90).{11}|(.)....(.)..(.)...{30}.(?!\91|\92|\93).{10}|....(.).(.).(.)...{31}.(?!\94|\95|\96).{9}|...(.)..(.)(.)....{32}.(?!\97|\98|\99).{8}|..(.)..(.)..(.)...{33}.(?!\100|\101|\102).{7}|..(.).(.)(.)......{34}.(?!\103|\104|\105).{6}|..(.)(.)..(.).....{35}.(?!\106|\107|\108).{5}|.(.).....(.)(.)...{36}.(?!\109|\110|\111).{4}|..(.)....(.)(.)...{37}.(?!\112|\113|\114).{3}|...(.)..(.)...(.).{38}.(?!\115|\116|\117).{2}|....(.)(.)....(.).{39}.(?!\118|\119|\120).{1})$

Like all previous submissions, it resolves instantaneously. Unlike previous submissions, it's too long for RegExr.

Expanded:

[^a-f]|
^(?:
    .{0,51}|
    .{53,}|
    .{11}.(?!d).{40}|
    .{12}.(?!a).{39}|
    .{13}.(?!a).{38}|
    .{14}.(?!f).{37}|
    .{15}.(?!d).{36}|
    .{16}.(?!a).{35}|
    .{17}.(?!d).{34}|
    .{18}.(?!c).{33}|
    .{19}.(?!f).{32}|
    .{20}.(?!d).{31}|
    .{21}.(?!d).{30}|
    .{22}.(?!d).{29}|
    .{23}.(?!f).{28}|
    .{24}.(?!d).{27}|
    .{25}.(?!b).{26}|
    .{26}.(?!f).{25}|
    .{27}.(?!f).{24}|
    .{28}.(?!e).{23}|
    .{29}.(?!c).{22}|
    .{30}.(?!c).{21}|
    .{31}.(?!b).{20}|
    .{32}.(?!d).{19}|
    .{33}.(?!e).{18}|
    .{34}.(?!c).{17}|
    .{35}.(?!a).{16}|
    .{36}.(?!a).{15}|
    .{37}.(?!e).{14}|
    .{38}.(?!b).{13}|
    .{39}.(?!f).{12}|
    .{40}.(?!d).{11}|
    .{41}.(?!f).{10}|
    .{42}.(?!c).{9}|
    .{43}.(?!f).{8}|
    .{44}.(?!e).{7}|
    .{45}.(?!c).{6}|
    .{46}.(?!b).{5}|
    .{47}.(?!b).{4}|
    .{48}.(?!f).{3}|
    .{49}.(?!a).{2}|
    .{50}.(?!d).{1}|
    ....(.)(.)(.).....(?!\1|\2|\3).{40}|
    .(.).(.)..(.).....{1}.(?!\4|\5|\6).{39}|
    ...(.)(.).....(.).{2}.(?!\7|\8|\9).{38}|
    ......(.)(.).(.)..{3}.(?!\10|\11|\12).{37}|
    ....(.)(.)(.).....{4}.(?!\13|\14|\15).{36}|
    ..(.)(.)(.).......{5}.(?!\16|\17|\18).{35}|
    (.).(.)......(.)..{6}.(?!\19|\20|\21).{34}|
    ..(.).....(.).(.).{7}.(?!\22|\23|\24).{33}|
    (.)..(.)(.).......{8}.(?!\25|\26|\27).{32}|
    ...(.).....(.)(.).{9}.(?!\28|\29|\30).{31}|
    .(.)(.).....(.)...{10}.(?!\31|\32|\33).{30}|
    .(.)...(.)..(.)...{11}.(?!\34|\35|\36).{29}|
    (.)(.).....(.)....{12}.(?!\37|\38|\39).{28}|
    ...(.).(.).(.)....{13}.(?!\40|\41|\42).{27}|
    ..(.)(.)..(.).....{14}.(?!\43|\44|\45).{26}|
    (.).(.)....(.)....{15}.(?!\46|\47|\48).{25}|
    (.)..(.)...(.)....{16}.(?!\49|\50|\51).{24}|
    (.)(.)(.).........{17}.(?!\52|\53|\54).{23}|
    .(.)..(.)(.)......{18}.(?!\55|\56|\57).{22}|
    (.)...(.)..(.)....{19}.(?!\58|\59|\60).{21}|
    .......(.)(.)(.)..{20}.(?!\61|\62|\63).{20}|
    .(.).....(.).(.)..{21}.(?!\64|\65|\66).{19}|
    ..(.)..(.)...(.)..{22}.(?!\67|\68|\69).{18}|
    ..(.).(.).....(.).{23}.(?!\70|\71|\72).{17}|
    ...(.).(.)..(.)...{24}.(?!\73|\74|\75).{16}|
    .(.)(.)(.)........{25}.(?!\76|\77|\78).{15}|
    (.).(.).....(.)...{26}.(?!\79|\80|\81).{14}|
    .....(.)..(.).(.).{27}.(?!\82|\83|\84).{13}|
    (.).(.).(.).......{28}.(?!\85|\86|\87).{12}|
    ..(.)...(.)..(.)..{29}.(?!\88|\89|\90).{11}|
    (.)....(.)..(.)...{30}.(?!\91|\92|\93).{10}|
    ....(.).(.).(.)...{31}.(?!\94|\95|\96).{9}|
    ...(.)..(.)(.)....{32}.(?!\97|\98|\99).{8}|
    ..(.)..(.)..(.)...{33}.(?!\100|\101|\102).{7}|
    ..(.).(.)(.)......{34}.(?!\103|\104|\105).{6}|
    ..(.)(.)..(.).....{35}.(?!\106|\107|\108).{5}|
    .(.).....(.)(.)...{36}.(?!\109|\110|\111).{4}|
    ..(.)....(.)(.)...{37}.(?!\112|\113|\114).{3}|
    ...(.)..(.)...(.).{38}.(?!\115|\116|\117).{2}|
    ....(.)(.)....(.).{39}.(?!\118|\119|\120).{1}
)$
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Match: aaaabaaacaaadaaa. Non-match: fdeacdbfbdcadaafdadcfdddfdbffeccbdecaaebfdfcfecbbfad. \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 4:01
  • \$\begingroup\$ Replace (.) with the matching character, and sort by that character, and it will become obvious. \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 4:04
  • 1
    \$\begingroup\$ Note that this is NP-complete, but not cryptographically secure. And there are too many restrictions and too few variables to make it difficult. \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 4:24
  • 1
    \$\begingroup\$ @user23013: Well played, sir. ;) And indeed I believe this is reducible to SAT, which was my intent. Just not enough bits in there to make it difficult, as you say. \$\endgroup\$
    – COTO
    Oct 15, 2014 at 7:26
5
\$\begingroup\$

Python flavour (721 bytes) [cracked]

It's time for "Parsing Problem v2":

^(((?(8)S)(((?(9)I|\\)(?(3)\]|Z)((?(7)l|R)(((((((?(4)p)((?(7)x)(?(1)B|Z)(?(11)\()(?(9)X)(?(8)P|T)(?(6)a|E)((?(5)E)(((?(8)3|\[)((?(3)\(|1)((?(1)M|L)(?(3)v|b)(?(2)t|l)(?(1)q)(?(1)K|H)(?(2)\)|R)(?(3)O|K)(?(5)l|l)(((?(2)\[|3)((?(2)N)((?(2)\\)((?(1)E|\])(?(1)\[)([(?(1)Q)])(?(24)\[)(?(24)q))(?(24)g))(?(22)s|U)(?(22)H)(?(23)c|U))(?(24)Q)(?(24)Q)(?(24)H)(?(23)K|\[))(?(22)e|y))(?(24)\\)(?(21)P|4)(?(19)T)(?(24)\))))(?(24)M)(?(17)\()(?(24)2))(?(19)7)(?(21)t|X)(?(22)v))(?(24)\[)(?(19)A|L)(?(16)E|1))(?(19)1|c)(?(14)K|\\)(?(19)4|5)(?(24)\\)(?(20)r)))(?(24)B)(?(24)w)(?(24)5))(?(24)\())(?(24)\\))(?(24)T))(?(9)\[))(?(15)z|w))(?(24)K)\7F(?(24)m)(?(24)R))(?(24)\[))(?(24)h))(?(14)x|t)(?(3)R|M)(?(24)\])(?(24)w))(?(21)z|6)(?(16)r)()$

Tested on Regex101.


This regex is effectively "hide a tree in a forest". The bulk of the regex consists of (?(id)yes-pattern|no-pattern) expressions, which match the appropriate pattern depending on whether or not a group with the specified id exists. Most of these expressions do not contribute to the key, but some do. However, not-so-subtly hidden in the regex was [(?(1):Q)] which is actually a character set, and \7, which requires you to keep track of the groups somehow. Both of these will show up on any editor with highlighting, but were meant to trip up anyone who wasn't cautious.

\$\endgroup\$
9
  • \$\begingroup\$ Man, this is gonna take some work. \$\endgroup\$
    – stokastic
    Oct 15, 2014 at 1:34
  • 4
    \$\begingroup\$ \ZRZTE[1LblHRKl3]?sHcKePT(7tvAE1K4r[zZTE[1LblHRKl3]?sHcKePT(7tvAE1K4rFxRzr matches. a doesn't match \$\endgroup\$ Oct 15, 2014 at 1:42
  • \$\begingroup\$ Additionally, the set of all possible matches is (my previous comment) with both of the ?'s replaced with any character in (?(1)Q) \$\endgroup\$ Oct 15, 2014 at 1:44
  • \$\begingroup\$ (on Regex101, it tells you exactly what it was trying to match when the match failed. This made finding the matching stuff somewhat easier (at least for spotting typos in my solution)). \$\endgroup\$ Oct 15, 2014 at 1:45
  • \$\begingroup\$ I was close, I was just missing the ?'s \$\endgroup\$
    – stokastic
    Oct 15, 2014 at 2:12
5
\$\begingroup\$

Python flavour (4842 bytes) [cracked]

With thanks to @COTO for ideas and advice

I liked @COTO's 3-SAT idea so much that I thought I'd try to make my own regex based off it. I'm not that familiar with the theoretics of 3-SAT though, so I'm just going to pray to the RNG gods and hope I have enough restrictions in place.

I tried to keep the regex under 5000 characters to be fair - obviously longer regexes would be impossible to crack, but they wouldn't be very fun to crack either.

[^01]|^(.{0,81}|.{83,}|....0.{10}1.{22}0.{43}|....0.{14}0.{35}0.{26}|....0.{16}0.{5}1.{54}|....0.{17}1.{34}0.{24}|....1.{11}0.{41}1.{23}|....1.{12}1.{27}1.{36}|....1.{22}1.{38}1.{15}|....1.{30}0.{35}1.{10}|....1.{46}0.1.{28}|....1.{6}1.{65}0....|...0....1.1.{71}|...0.{18}0.{23}0.{35}|...1.{11}1.{33}1.{32}|..0...0.{53}1.{21}|..0.{30}1.{17}0.{30}|..1.{41}0.{10}0.{26}|.0.{13}0.{39}1.{26}|.0.{18}0.{49}0.{11}|.0.{27}1.{36}0.{15}|.0.{31}11.{47}|.00.{37}1.{41}|.1.{32}0.{31}1.{15}|.1.{38}0.{25}0.{15}|.1.{7}0.{38}0.{33}|.{10}0.{14}0.{15}0.{40}|.{10}0.{15}1.{15}1.{39}|.{10}0.{27}1.{11}1.{31}|.{10}0.{39}0.{7}0.{23}|.{10}0.{42}10.{27}|.{10}0.{9}0.{38}0.{22}|.{10}1.{45}1.{16}0.{8}|.{10}1.{47}0.{15}0.{7}|.{10}1.{59}0.{5}1.{5}|.{11}0.{11}0.{54}0...|.{11}0.{29}1.{35}0....|.{11}1.{32}0.{25}1.{11}|.{11}1.{48}1.{6}1.{14}|.{11}11.{50}1.{18}|.{12}0.{27}1.{18}0.{22}|.{12}0.{45}1.{7}1.{15}|.{12}1.{15}0.{42}1.{10}|.{13}0.{40}1...0.{23}|.{13}1.{20}1.{5}1.{41}|.{13}1.{22}0.{31}0.{13}|.{13}1.{24}1.{39}1...|.{13}1.{58}0.{8}0|.{14}0.{22}0....1.{39}|.{14}0.{23}0.{23}1.{19}|.{14}0.{53}10.{12}|.{14}1.{19}1.{11}0.{35}|.{14}1.{19}1.{21}1.{25}|.{14}1.{23}0.{14}0.{28}|.{14}1.{24}1.{12}1.{29}|.{14}1.{35}0.{22}0.{8}|.{14}1.{48}0.{15}1..|.{14}1.{58}0....1...|.{14}1.{65}11|.{14}1.{6}1.0.{58}|.{15}0...01.{61}|.{15}0.{12}0.{30}0.{22}|.{15}0.{15}0.{34}0.{15}|.{15}0.{30}1.{25}0.{9}|.{15}0.{31}0.{32}1.|.{15}0.{36}0.{25}1...|.{15}1.{14}1.{21}1.{29}|.{15}1.{16}1.{16}1.{32}|.{15}1.{20}0.{32}1.{12}|.{16}0.{35}1.{24}0....|.{16}0.{36}1.{15}1.{12}|.{16}1.{13}1.{22}0.{28}|.{16}1.{16}1.{14}0.{33}|.{16}1.{48}1.0.{14}|.{17}1.{29}1.{31}0..|.{17}1.{47}1.{8}0.{7}|.{17}1.{9}0.{20}0.{33}|.{18}0..0.{59}1|.{18}0.{33}1.{6}0.{22}|.{18}0.{36}1.{24}1.|.{18}0.{39}0.{17}1.{5}|.{18}1..0.{35}0.{24}|.{18}1.{16}0.{7}1.{38}|.{19}0.{17}0.{8}1.{35}|.{19}1.{42}00.{18}|.{20}0.{25}1.{31}1...|.{20}0.{43}1.{12}0....|.{20}0.{8}1.{40}0.{11}|.{20}00.{56}1...|.{20}1.{38}0.{7}1.{14}|.{21}0.{39}1.{16}0...|.{22}1....0.{44}1.{9}|.{22}1..1.{20}1.{35}|.{23}0.{39}1.{8}0.{9}|.{23}0.{8}1.{41}1.{7}|.{23}1.{18}1.{25}0.{13}|.{23}1.{20}0.{6}0.{30}|.{24}0.{17}1.{16}0.{22}|.{24}0.{21}1.{13}0.{21}|.{24}1...1.{49}0...|.{24}1.{5}0.{37}0.{13}|.{24}1.{8}1.{37}0.{10}|.{25}0.{36}0....0.{14}|.{25}1....0.{29}0.{21}|.{25}1....1.{10}1.{40}|.{25}1.{13}1.{13}0.{28}|.{25}1.{40}0.{7}0.{7}|.{26}0.{13}1.{21}0.{19}|.{26}0.{13}1.{25}1.{15}|.{27}0.{20}1.{11}0.{21}|.{27}0.{36}0.{6}0.{10}|.{27}1....1.0.{47}|.{27}1...0.{13}1.{36}|.{27}1.{10}0.{26}0.{16}|.{27}1.{30}1.{15}0.{7}|.{28}0.{14}1.{37}0|.{28}0.{21}1.0.{29}|.{28}0.{26}0.{16}0.{9}|.{28}1.{18}1.{23}1.{10}|.{29}0.{17}0.0.{32}|.{29}1.{24}0.{19}1.{7}|.{29}1.{46}1....0|.{30}1.{18}1.{9}0.{22}|.{30}1.{28}0....1.{17}|.{32}0.{25}1.{6}1.{16}|.{33}0.{22}1.{12}0.{12}|.{33}0.{6}0.{11}0.{29}|.{33}1.{5}1.{31}0.{10}|.{34}0.{13}0.{8}0.{24}|.{34}1...1.{35}0.{7}|.{34}1..1.{29}1.{14}|.{34}1.{38}01.{7}|.{34}1.{5}0.{40}1|.{34}1.{6}1.{38}1.|.{34}1.{7}0.{31}0.{7}|.{34}11...1.{42}|.{35}0.{19}0..0.{23}|.{35}1.{12}1.{24}0.{8}|.{36}0.{6}1.{17}1.{20}|.{36}0.{7}1.{17}1.{19}|.{36}0.{8}0.{13}1.{22}|.{36}1.{14}0.{9}1.{20}|.{37}0.{26}1.{16}0|.{37}1.{27}0.{10}0.{5}|.{38}1.{21}1.{7}1.{13}|.{39}0..0.{20}0.{18}|.{39}0.{15}0.{19}1.{6}|.{40}0....0.{28}1.{7}|.{40}0.{15}1.0.{23}|.{40}0.{5}1.{16}0.{18}|.{40}0.{8}1.{29}1..|.{40}00.0.{38}|.{41}0.0.{20}0.{17}|.{41}00.{32}0.{6}|.{41}1.{16}1.{21}1.|.{41}1.{8}1.{18}0.{12}|.{42}1.{31}1.{6}1|.{42}11.{27}0.{10}|.{43}0.{34}10..|.{44}1.0.{10}1.{24}|.{45}0.{9}0.{5}0.{20}|.{45}1.{12}0.{22}1|.{45}1.{17}1....0.{13}|.{45}1.{9}0...0.{22}|.{46}0.{11}1.{19}1...|.{46}1.{24}0.{5}0....|.{47}11.{8}1.{24}|.{48}0.{12}1....0.{15}|.{48}0.{15}0.{13}1...|.{48}1...0.{13}0.{15}|.{48}1.{11}0..0.{18}|.{48}11.{21}0.{10}|.{49}1.{7}1.{14}0.{9}|.{51}1.{12}1.{5}1.{11}|.{54}0.{13}0.{6}1.{6}|.{54}1.{11}1.1.{13}|.{56}0.{16}0..1.{5}|.{56}1.{11}0.{6}0.{6}|.{58}1....1.{6}0.{11}|.{5}0.{17}0.{42}0.{15}|.{5}0.{23}1.{26}1.{25}|.{5}0.{34}1.{22}0.{18}|.{5}0.{6}1.{13}1.{55}|.{5}1.{12}0.{31}1.{31}|.{5}1.{16}0.{39}1.{19}|.{5}1.{16}1.1.{57}|.{5}1.{24}1.{15}1.{35}|.{5}1.{24}1.{47}1...|.{66}0.0.{5}1.{7}|.{6}0....1.{24}0.{45}|.{6}0.{19}0.{7}1.{47}|.{6}0.{23}0.{14}0.{36}|.{6}0.{25}1.{41}0.{7}|.{6}0.{46}1.{22}0.{5}|.{6}0.{52}11.{21}|.{6}1.{35}10.{38}|.{7}0.{20}0.{16}0.{36}|.{7}0.{34}1.{20}1.{18}|.{7}0.{6}0.{36}0.{30}|.{7}0.{7}0.{15}0.{50}|.{7}0.{8}1.{42}1.{22}|.{7}1.{5}1.{56}1.{11}|.{7}1.{67}0..1...|.{8}0.{10}0.{38}0.{23}|.{8}0.{41}11.{30}|.{8}0.{9}1.{37}1.{25}|.{8}1.{50}1.{14}1.{7}|.{9}0..1.{55}0.{13}|.{9}0.{21}1.{42}0.{7}|.{9}0.{59}00.{11}|.{9}0.{9}0....1.{57}|.{9}00.{41}1.{29}|.{9}1....0.{20}0.{46}|.{9}1...0.{41}1.{26}|.{9}1.{30}0.{16}1.{24}|.{9}1.{30}0.{37}1...|.{9}1.{30}1.{14}1.{26}|.{9}1.{40}01.{30}|0.{17}1.{34}0.{28}|0.{23}1.{43}1.{13}|0.{30}1.{26}1.{23}|1.{13}00.{66}|1.{28}0.{42}1.{9}|1.{36}0.{35}1.{8}|1.{42}1.{32}1.{5}|1.{49}0.{16}0.{14}|1.{52}0.{7}0.{20}|)$

And here it is in a form that's a bit easier to read:

[^01]|
^(
  .{0,81}|
  .{83,}|
  ....0.{10}1.{22}0.{43}|
  ....0.{14}0.{35}0.{26}|
  ....0.{16}0.{5}1.{54}|
  ....0.{17}1.{34}0.{24}|
  ....1.{11}0.{41}1.{23}|
  ....1.{12}1.{27}1.{36}|
  ....1.{22}1.{38}1.{15}|
  ....1.{30}0.{35}1.{10}|
  ....1.{46}0.1.{28}|
  ....1.{6}1.{65}0....|
  ...0....1.1.{71}|
  ...0.{18}0.{23}0.{35}|
  ...1.{11}1.{33}1.{32}|
  ..0...0.{53}1.{21}|
  ..0.{30}1.{17}0.{30}|
  ..1.{41}0.{10}0.{26}|
  .0.{13}0.{39}1.{26}|
  .0.{18}0.{49}0.{11}|
  .0.{27}1.{36}0.{15}|
  .0.{31}11.{47}|
  .00.{37}1.{41}|
  .1.{32}0.{31}1.{15}|
  .1.{38}0.{25}0.{15}|
  .1.{7}0.{38}0.{33}|
  .{10}0.{14}0.{15}0.{40}|
  .{10}0.{15}1.{15}1.{39}|
  .{10}0.{27}1.{11}1.{31}|
  .{10}0.{39}0.{7}0.{23}|
  .{10}0.{42}10.{27}|
  .{10}0.{9}0.{38}0.{22}|
  .{10}1.{45}1.{16}0.{8}|
  .{10}1.{47}0.{15}0.{7}|
  .{10}1.{59}0.{5}1.{5}|
  .{11}0.{11}0.{54}0...|
  .{11}0.{29}1.{35}0....|
  .{11}1.{32}0.{25}1.{11}|
  .{11}1.{48}1.{6}1.{14}|
  .{11}11.{50}1.{18}|
  .{12}0.{27}1.{18}0.{22}|
  .{12}0.{45}1.{7}1.{15}|
  .{12}1.{15}0.{42}1.{10}|
  .{13}0.{40}1...0.{23}|
  .{13}1.{20}1.{5}1.{41}|
  .{13}1.{22}0.{31}0.{13}|
  .{13}1.{24}1.{39}1...|
  .{13}1.{58}0.{8}0|
  .{14}0.{22}0....1.{39}|
  .{14}0.{23}0.{23}1.{19}|
  .{14}0.{53}10.{12}|
  .{14}1.{19}1.{11}0.{35}|
  .{14}1.{19}1.{21}1.{25}|
  .{14}1.{23}0.{14}0.{28}|
  .{14}1.{24}1.{12}1.{29}|
  .{14}1.{35}0.{22}0.{8}|
  .{14}1.{48}0.{15}1..|
  .{14}1.{58}0....1...|
  .{14}1.{65}11|
  .{14}1.{6}1.0.{58}|
  .{15}0...01.{61}|
  .{15}0.{12}0.{30}0.{22}|
  .{15}0.{15}0.{34}0.{15}|
  .{15}0.{30}1.{25}0.{9}|
  .{15}0.{31}0.{32}1.|
  .{15}0.{36}0.{25}1...|
  .{15}1.{14}1.{21}1.{29}|
  .{15}1.{16}1.{16}1.{32}|
  .{15}1.{20}0.{32}1.{12}|
  .{16}0.{35}1.{24}0....|
  .{16}0.{36}1.{15}1.{12}|
  .{16}1.{13}1.{22}0.{28}|
  .{16}1.{16}1.{14}0.{33}|
  .{16}1.{48}1.0.{14}|
  .{17}1.{29}1.{31}0..|
  .{17}1.{47}1.{8}0.{7}|
  .{17}1.{9}0.{20}0.{33}|
  .{18}0..0.{59}1|
  .{18}0.{33}1.{6}0.{22}|
  .{18}0.{36}1.{24}1.|
  .{18}0.{39}0.{17}1.{5}|
  .{18}1..0.{35}0.{24}|
  .{18}1.{16}0.{7}1.{38}|
  .{19}0.{17}0.{8}1.{35}|
  .{19}1.{42}00.{18}|
  .{20}0.{25}1.{31}1...|
  .{20}0.{43}1.{12}0....|
  .{20}0.{8}1.{40}0.{11}|
  .{20}00.{56}1...|
  .{20}1.{38}0.{7}1.{14}|
  .{21}0.{39}1.{16}0...|
  .{22}1....0.{44}1.{9}|
  .{22}1..1.{20}1.{35}|
  .{23}0.{39}1.{8}0.{9}|
  .{23}0.{8}1.{41}1.{7}|
  .{23}1.{18}1.{25}0.{13}|
  .{23}1.{20}0.{6}0.{30}|
  .{24}0.{17}1.{16}0.{22}|
  .{24}0.{21}1.{13}0.{21}|
  .{24}1...1.{49}0...|
  .{24}1.{5}0.{37}0.{13}|
  .{24}1.{8}1.{37}0.{10}|
  .{25}0.{36}0....0.{14}|
  .{25}1....0.{29}0.{21}|
  .{25}1....1.{10}1.{40}|
  .{25}1.{13}1.{13}0.{28}|
  .{25}1.{40}0.{7}0.{7}|
  .{26}0.{13}1.{21}0.{19}|
  .{26}0.{13}1.{25}1.{15}|
  .{27}0.{20}1.{11}0.{21}|
  .{27}0.{36}0.{6}0.{10}|
  .{27}1....1.0.{47}|
  .{27}1...0.{13}1.{36}|
  .{27}1.{10}0.{26}0.{16}|
  .{27}1.{30}1.{15}0.{7}|
  .{28}0.{14}1.{37}0|
  .{28}0.{21}1.0.{29}|
  .{28}0.{26}0.{16}0.{9}|
  .{28}1.{18}1.{23}1.{10}|
  .{29}0.{17}0.0.{32}|
  .{29}1.{24}0.{19}1.{7}|
  .{29}1.{46}1....0|
  .{30}1.{18}1.{9}0.{22}|
  .{30}1.{28}0....1.{17}|
  .{32}0.{25}1.{6}1.{16}|
  .{33}0.{22}1.{12}0.{12}|
  .{33}0.{6}0.{11}0.{29}|
  .{33}1.{5}1.{31}0.{10}|
  .{34}0.{13}0.{8}0.{24}|
  .{34}1...1.{35}0.{7}|
  .{34}1..1.{29}1.{14}|
  .{34}1.{38}01.{7}|
  .{34}1.{5}0.{40}1|
  .{34}1.{6}1.{38}1.|
  .{34}1.{7}0.{31}0.{7}|
  .{34}11...1.{42}|
  .{35}0.{19}0..0.{23}|
  .{35}1.{12}1.{24}0.{8}|
  .{36}0.{6}1.{17}1.{20}|
  .{36}0.{7}1.{17}1.{19}|
  .{36}0.{8}0.{13}1.{22}|
  .{36}1.{14}0.{9}1.{20}|
  .{37}0.{26}1.{16}0|
  .{37}1.{27}0.{10}0.{5}|
  .{38}1.{21}1.{7}1.{13}|
  .{39}0..0.{20}0.{18}|
  .{39}0.{15}0.{19}1.{6}|
  .{40}0....0.{28}1.{7}|
  .{40}0.{15}1.0.{23}|
  .{40}0.{5}1.{16}0.{18}|
  .{40}0.{8}1.{29}1..|
  .{40}00.0.{38}|
  .{41}0.0.{20}0.{17}|
  .{41}00.{32}0.{6}|
  .{41}1.{16}1.{21}1.|
  .{41}1.{8}1.{18}0.{12}|
  .{42}1.{31}1.{6}1|
  .{42}11.{27}0.{10}|
  .{43}0.{34}10..|
  .{44}1.0.{10}1.{24}|
  .{45}0.{9}0.{5}0.{20}|
  .{45}1.{12}0.{22}1|
  .{45}1.{17}1....0.{13}|
  .{45}1.{9}0...0.{22}|
  .{46}0.{11}1.{19}1...|
  .{46}1.{24}0.{5}0....|
  .{47}11.{8}1.{24}|
  .{48}0.{12}1....0.{15}|
  .{48}0.{15}0.{13}1...|
  .{48}1...0.{13}0.{15}|
  .{48}1.{11}0..0.{18}|
  .{48}11.{21}0.{10}|
  .{49}1.{7}1.{14}0.{9}|
  .{51}1.{12}1.{5}1.{11}|
  .{54}0.{13}0.{6}1.{6}|
  .{54}1.{11}1.1.{13}|
  .{56}0.{16}0..1.{5}|
  .{56}1.{11}0.{6}0.{6}|
  .{58}1....1.{6}0.{11}|
  .{5}0.{17}0.{42}0.{15}|
  .{5}0.{23}1.{26}1.{25}|
  .{5}0.{34}1.{22}0.{18}|
  .{5}0.{6}1.{13}1.{55}|
  .{5}1.{12}0.{31}1.{31}|
  .{5}1.{16}0.{39}1.{19}|
  .{5}1.{16}1.1.{57}|
  .{5}1.{24}1.{15}1.{35}|
  .{5}1.{24}1.{47}1...|
  .{66}0.0.{5}1.{7}|
  .{6}0....1.{24}0.{45}|
  .{6}0.{19}0.{7}1.{47}|
  .{6}0.{23}0.{14}0.{36}|
  .{6}0.{25}1.{41}0.{7}|
  .{6}0.{46}1.{22}0.{5}|
  .{6}0.{52}11.{21}|
  .{6}1.{35}10.{38}|
  .{7}0.{20}0.{16}0.{36}|
  .{7}0.{34}1.{20}1.{18}|
  .{7}0.{6}0.{36}0.{30}|
  .{7}0.{7}0.{15}0.{50}|
  .{7}0.{8}1.{42}1.{22}|
  .{7}1.{5}1.{56}1.{11}|
  .{7}1.{67}0..1...|
  .{8}0.{10}0.{38}0.{23}|
  .{8}0.{41}11.{30}|
  .{8}0.{9}1.{37}1.{25}|
  .{8}1.{50}1.{14}1.{7}|
  .{9}0..1.{55}0.{13}|
  .{9}0.{21}1.{42}0.{7}|
  .{9}0.{59}00.{11}|
  .{9}0.{9}0....1.{57}|
  .{9}00.{41}1.{29}|
  .{9}1....0.{20}0.{46}|
  .{9}1...0.{41}1.{26}|
  .{9}1.{30}0.{16}1.{24}|
  .{9}1.{30}0.{37}1...|
  .{9}1.{30}1.{14}1.{26}|
  .{9}1.{40}01.{30}|
  0.{17}1.{34}0.{28}|
  0.{23}1.{43}1.{13}|
  0.{30}1.{26}1.{23}|
  1.{13}00.{66}|
  1.{28}0.{42}1.{9}|
  1.{36}0.{35}1.{8}|
  1.{42}1.{32}1.{5}|
  1.{49}0.{16}0.{14}|
  1.{52}0.{7}0.{20}|
)$

Tested on Regex101.


The regex is looking for an 82-character string S of 0s and 1s. It performs a large number checks of the form (after applying de Morgan's) S[index1] != digit1 OR S[index2] != digit2 OR S[index3] != digit3, which make up the 3-SAT clauses. The regex size is linear in the number of clues, and logarithmic in the number of characters in the key (due to the .{n} notation). Unfortunately though, to be secure the number of clues has to go up with the size of the key, and while it's certainly possible to make an uncrackable key this way, it would end up being quite a long regex.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Match: x. Non-match: 0011001101000000000111010001101101011000010011011010000000010001011111000100010000 \$\endgroup\$
    – nneonneo
    Oct 16, 2014 at 6:30
  • \$\begingroup\$ Match: aaaabaaacaaadaaa. Non-match: 011100110010001010111101001010010011110010011010110101010001101100101111111111 + 0000. Just a few seconds slower... \$\endgroup\$
    – jimmy23013
    Oct 16, 2014 at 6:32
  • \$\begingroup\$ Wow that was fast - did you guys brute force it? \$\endgroup\$
    – Sp3000
    Oct 16, 2014 at 6:37
  • 1
    \$\begingroup\$ @Sp3000 I did it almost manually... Surprisingly the statistic method worked. \$\endgroup\$
    – jimmy23013
    Oct 16, 2014 at 6:42
  • 2
    \$\begingroup\$ @Sp3000: I would've bruteforced it but that was no fun. Instead I converted your sequence to a 3SAT and cracked it with minisat. Took 0.3 seconds (time spent converting, ~10 minutes) \$\endgroup\$
    – nneonneo
    Oct 16, 2014 at 6:49
5
\$\begingroup\$

Perl flavor, 133 [cracked]

Okay, this one should be harder to brute force:

^([^,]{2,}),([^,]{2,}),([^,]{2,}),(?=.\2+,)(?=.\3+,)\1+,(?=.\1+,)(?=.\3+,)\2+,(?=.\1+,)(?=.\2+,)\3+,(?=.{16,20}$)(\1{3}|\2{3}|\3{3})$

And a longer version, not part of the challenge:

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

Can be tested on Regex101 (pcre flavor).


The idea behind this pattern is that we can encode a simple system of congruence equations in a regex using lookaheads. For example, the regex ^(?=(..)*$)(...)*$ matches any string whose length is a common multiple of 2 and 3, that is, a multiple of 6. This can be seen as the equation 2x ≡ 0 mod 3. We can parameterize the equation using capture groups: the regex ^(.*),(.*),(?=\1*$)\2*$ matches strings where the number of characters after the last comma is a common multiple of the length of the first and second submatches. This can be seen as the parameterized equation ax ≡ 0 mod b, where a and b are the lengths of the two submatches.

The above regex begins by taking three "parameters" of length at least two, and is followed by three "systems of equations" of the from (?=.\1+,)(?=.\2+,)\3+, that correspond to {ax + 1 ≡ 0 mod c, by + 1 ≡ 0 mod c, ax = by}, where a, b and c are the lengths of the corresponding submatches. This system of equations has a solution if and only if a and b are coprime to c. Since we have three such systems, one for each submatch, the lengths of the submatches must be pairwise coprime.

The last part of the regex is there to ensure that one of the submatches is of length 6. This forces the other two submatches to be 5 and 7 characters long, since any smaller values won't be coprime and any larger values will result in a key longer than 256 characters. The smallest solutions to the equations then yield substrings of lengths 85, 36 and 91, which result in a string of length 254---about as long as we can get.

The longer regex uses the same principle, only with 6 parameters of length at least three and no additional restrictions. The smallest pairwise coprime set of six integers greater than 2 is {3, 4, 5, 7, 11, 13}, which yields substrings of minimal lengths 40041, 15016, 24025, 34321, 43681 and 23101. Therefore, the shortest string that matches the longer regex is a{3},a{4},a{5},a{7},a{11},a{13},a{40041},a{15016},a{24025},a{34321},a{43681},a{23101} (up to the order of parameters.) That's 180,239 characters!

\$\endgroup\$
5
  • \$\begingroup\$ That {16,20}. \$\endgroup\$
    – Sp3000
    Oct 15, 2014 at 14:04
  • 2
    \$\begingroup\$ Match: aaaaa,aaaaaa,aaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaa, Mismatch: aaaaaaaaaaaaaaaa \$\endgroup\$
    – Sp3000
    Oct 15, 2014 at 14:19
  • \$\begingroup\$ I think SE keeps adding extra as for some reason - there should be 5,6,7,85,36,91,18 as between the commas :/ \$\endgroup\$
    – Sp3000
    Oct 15, 2014 at 14:25
  • \$\begingroup\$ @Sp3000 Pick a card, any card ;) Yeah, you cracked it. It seems like some of the 'a's in your comment are non-ASCII, but the numbers are right. \$\endgroup\$
    – Ell
    Oct 15, 2014 at 14:30
  • \$\begingroup\$ @Ell The as are all ASCII, but there are two non-printable Unicode characters for each manual line break SE does. \$\endgroup\$ Oct 15, 2014 at 15:01
5
\$\begingroup\$

.NET flavour, 141 bytes [cracked]

(?=(?<![][])(?(c)(?!))((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!))(?![][]))^.*$(?<=(?<![][])(?(c)(?!))((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!))(?![][]))

Another one for the robbers! I'm sure this will be cracked, but I hope the person cracking it will learn something interesting about the .NET flavour in the process.

Tested on RegexStorm and RegexHero.

I figured this one would be interesting because it relies on the interplay of all three landmark regex features that you can only find in .NET: variable-length lookbehinds, balancing groups, and right-to-left matching.

Before we start into the .NET-specifics, let's clear up a simple thing about character classes. Character classes can't be empty, so if one starts with a ], that is actually part of the class without needing to be escaped. Likewise, a [ in a character class can unambiguously be treated as a member of the class without escaping. So []] is just the same matching a single \], and [[] is the same as \[ and more importantly [][] is a character class containing both brackets.

Now let's look at the structure of the regex: (?=somePattern)^.*$(?<=somePattern). So the actual match is really anything (the ^.*$) but we apply one pattern twice, anchoring it to the start once and to the end once.

Let's look at that pattern: (?<![][]) makes sure that there's no bracket before the pattern. (?![][]) (at the end) makes sure that there's no bracket after pattern. This is fulfilled at the ends of a string or adjacent to any other character.
This thing, (?(c)(?!)), at the beginning is actually redundant for now, because it only makes sure that the named capturing group c hasn't matched anything. We do need this at the end, so at least it's nice and symmetric. Now the main part of the pattern is this: ((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!)). These groups are called balancing groups, and what they do here is match a string of at least 15 balanced square brackets. There's a lot to say about balancing groups - too much for this post, but I can refer you to a rather comprehensive discussion I posted on StackOverflow a while ago.

Okay, so what the lookahead does is to ensure that the pattern starts with those balanced square brackets - and that there are no further square brackets next to that.

Now the lookbehind at the end contains exactly the same pattern. So shouldn't this be redundant? Shouldn't something like [][][][][][][][] fulfil both lookarounds and cause the pattern to match?

No. Because here is where it gets tricky. Although undocumented, .NET lookbehinds are matched from right to left. This is why .NET is the only flavour that supports variable-length lookbehinds. Usually you don't notice this because the order of matching is irrelevant. But in this particular case, it means that the opening square brackets must now come to the right of the closing square brackets. So the lookbehind actually checks for anti-matching square brackets, as in ][][][ or ]]][[[. That's why I also need the check (?(c)(?!)) at the beginning of the pattern, because that's now the end of match.

So we want 15 (or 16) matching brackets at the beginning of the string and 15 (or 16) anti-matching brackets at the end of the string. But those two can't be connected due to the (?![][]) lookarounds. So what do we do? We take a matching string and an anti-matching string and join them with an arbitrary character, giving for instance [][][][][[[[]]]]!][][][][]]]][[[[.

I guess that leaves one question... how on earth did I figure out that lookbehinds match from right to left? Well I tried some arcane regex magic once and couldn't figure out why my lookbehind wouldn't work. So I asked the friendly Q&A site next door. Now I'm really happy about this feature, because it makes balancing groups even more powerful if you know how to use them right. :)

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Match: [][][][][][][][]a][][][][][][][][. Non-match: That's interesting... \$\endgroup\$
    – jimmy23013
    Oct 16, 2014 at 13:02
  • \$\begingroup\$ @user23013 Yup! That was quick. Were you already familiar with those quirks of .NET? :) \$\endgroup\$ Oct 16, 2014 at 13:04
  • \$\begingroup\$ Wish I'd figured out the lookbehind quirk 5 mins earlier \$\endgroup\$
    – TwiNight
    Oct 16, 2014 at 13:07
  • \$\begingroup\$ No. But I already know quantifiers are not allowed in lookbehind in PCRE. I think actually looking backward is much better than that. \$\endgroup\$
    – jimmy23013
    Oct 16, 2014 at 13:09
  • \$\begingroup\$ @MartinBüttner So, to confirm, lookbehinds actually match from back to front? \$\endgroup\$
    – TwiNight
    Oct 16, 2014 at 13:11
5
\$\begingroup\$

Python flavour (200127 bytes) [cracked]

Just so that we may (hopefully) see something last a day, it's time to bring out the big guns :)

The problem with 3-SAT and Hamiltonian path is that the complexity is in terms of the key size. This time I've chosen something which is dependent on the regex, rather than the key.

Here it is: regex. You might also find this file useful. (Don't worry, I haven't hidden anything weird in there this time ;) )

I used RegexPlanet to test this one - it was tough finding something that wouldn't time out :/. To check if there was a match, see if your string appears under findall().

Good luck!


The regex is just "find a string of length 64 which appears as a common subsequence in a set of 20 strings of length 5000". There were too many solutions though, probably.

\$\endgroup\$
7
  • 5
    \$\begingroup\$ Match: d,mE~JZ0,_:3kBdLdgBSzJ!@MLrrAgKsf@Pl35N9bxsIf@ReVU>:YDg`d1MjL@_-. Non-match: { line|fold -w1 >filea; while line >filec; do fold -w1 <filec >fileb; diff -d --old-line-format= --new-line-format= --unchanged-line-format=%L filea fileb >filec;mv filec filea;done;cat filea;} <file1|tr -d $'\n'|head -c64;echo \$\endgroup\$
    – jimmy23013
    Oct 17, 2014 at 2:29
  • \$\begingroup\$ Ahaha I'm beat - I guess the sequences were too long and there were too many solutions \$\endgroup\$
    – Sp3000
    Oct 17, 2014 at 2:36
  • \$\begingroup\$ @user23013 That sounds like a lot, but it's actually not too bad, seeing that there are 5437589409196755010929519821645784067024309122301926366910354757626905801389085035074667925844349168139762829668081680641 different strings of length 64 with the available 77 characters. \$\endgroup\$ Oct 17, 2014 at 2:55
  • \$\begingroup\$ Well, I'm wrong. There are not only 718406958841 solutions. And my script has a bug so it ignored the last pattern. But the common subsequence of the first 19 patterns happened to be also a subsequence of the last one \$\endgroup\$
    – jimmy23013
    Oct 17, 2014 at 2:55
  • \$\begingroup\$ @MartinBüttner I mean I don't know exactly how many solutions there are, and that number is wrong. Their longest common subsequence has 718406958841 (corrected value: 97082021465) subsequences of length 64. But there are other CS's which are not subsequences of LCS. \$\endgroup\$
    – jimmy23013
    Oct 17, 2014 at 3:01
5
\$\begingroup\$

Python, 145475 bytes [cracked]

Thanks to the Wumpus for teaching me the importance of checking our indices :)

Same deal as last solution, only hopefully not broken this time. Raw regex: http://pastebin.com/MReS2R1k

EDIT: It wasn't broken, but apparently it was still too easy. At least it wasn't solved "instantly" ;)

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Non-match: 1040060321170122554027333022674205250442151362365165773421664173556667110413375720720711725045122733213710556062114131057357354554245723416516004761215632214223735570625116160162051407026445600345370604702671021412723536217011007021752560474402200436670402 Match: minisat2hoursCPU \$\endgroup\$
    – user15244
    Oct 17, 2014 at 10:37
  • \$\begingroup\$ Ayup. You got me. That was pretty quick. Maybe I do have to bust out my 1GB regex after all... \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 10:39
5
\$\begingroup\$

Java Pattern/Oracle implementation (75 chars/150 bytes UTF-16) [cracked]

(Code name: Bad Coffee 101)

This is the Pattern object, with CANON_EQ flag, to be used with matches() (implied anchor):

Pattern.compile("(\\Q\u1EBF\\\\E)?+[\\w&&[\\p{L1}]\\p{Z}]+|\\1[\uD835\uDC00-\uD835\uDC33]{1927027271663633,2254527117918231}", Pattern.CANON_EQ)

Test your key here on ideone

There is guaranteed to be a key. Read the spoiler if you want some confirmation.

As you can see, it is not a normal regex. However, it runs without Exception on Oracle's Java version 1.6.0u37 and Java version 1.7.0u11, and it should also run for the most current version at the time of writing.

This makes use of 4 bugs: CANON_EQ, captured text retention of failed attempt, lost character class and quantifier overflow.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ Match: "(?:e\u0302\u0301\\|\u00ea\u0301\\|\u1ebf\\|\u00ea\\\u0301|e\u0302\\\u0301|\u00ea\\\u0301|\u00ea\u0301\\|\u1ebf\\|e\\\u0302\u0301)\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00" (quoted form). Non-match: JavaRegexSoBuggy. ideone for match: ideone.com/DEesdk \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 18:12
  • \$\begingroup\$ Bugs found: (1) CANON_EQ expands precomposed characters into alternations internally, which breaks hilariously inside \Q\E; (2) repetition lengths are truncated to 32 bits; (3) there's some weird thing going on with the character class matcher that causes it to skip the alternation (didn't quite figure out what the bug was exactly). \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 18:15
  • \$\begingroup\$ @nneonneo: Your explanation is correct. But you forgot the backref \1 bug. And yes, there is a bug in the character class. How did you figure all this out in less than 2 hours? \$\endgroup\$ Oct 17, 2014 at 18:20
  • \$\begingroup\$ I started working on it 20 minutes ago. You made it pretty obvious which parts of the problem stressed which bugs (because each bug was basically in its own group), so I figured out how to satisfy each part independently, and then combined them. I got lucky that I didn't have to actually work out what the character class was doing. (I also got very lucky that Java spits out the "expanded" internal pattern when you have a syntax error :) \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 18:21
  • \$\begingroup\$ Also! I don't believe that the captured text retention is necessarily a bug. That seems to be how the possessive quantifiers work. (It's also a rather useful property for certain regex hacks...hm...) \$\endgroup\$
    – nneonneo
    Oct 17, 2014 at 18:25
5
\$\begingroup\$

.NET flavor, 17,372 bytes [cracked]

This is still an easy version. It needs more optimization to work with longer strings.

xz base64:

/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4EPbB2hdAC8KA+QKYhePb5XYF74CIWXzFZa9NcIQEk3v
/V2BJ4+pWDeuHyJglyhWD3Jp454EQmzShYGwtV0HYNg/uM7nyzGoXBbC//+zrYYUFKzVPHOpsGOG
dHt5rN7ffwyFyGP7scto6uWZ3Tlf+Udsikqx8XmtBTZxs+eKVsjWcBWYs+v27AW4AIesr2/aArhe
hagu80JX4+EYSYLfj6hqDPXA3XT9pUJLw+KESRPk+cOH0IrGx/PhNJxlv/Oq2FF3sCwq5GzIrhq2
FsOqyX4hE73pT4RI4sbY+hOveol93r3n1UZKX7/+gR3/EvS86lvgzZId0ktKQ4bZdPmlFVUB5aSM
xHPQ9KhkHAa1mxT3YhTs+CMased0tdTBeN+r/wzGzikIvCzYL0fb9YfdLt7kviJY4FC5PgS46UqY
IOpXcixcxHdznxoXf463nnUBl9p6bHyCBZSKzRLt9Tca859POZWLK3aBnBMEKve66Z/Wq08VdW3i
7XABm6Bp98O+xThLqjY3ZeiOiuUSFBOp4bXaJwW1ibgk84eVN/LUvYc+13SHEjz957RLNqzIccHT
a4Uz91v36AkbUgIzT9IaRg8OVmMR6FgFk/szxATDEKAjOGp6ugavV2UNNFQzXEklkidM0VSsKVyW
9mEwktk3msx3SUV0Wgi4ErsnQVVOE9zgHeLeYBvsXcdeOG2qFUX1u3GrUW6Q6/9cuypfOJNvrC4l
/DO0Lt/8uU1Fcs2ndF1akVS6jlYrsmTUV7Nr99BtKOv23OB8YVekWYRQWI9vEG+/4dyqK8+o5Xpl
oxgALMkQ78jWzYkT11xIemZBN8Vqj3AEla28gVteFDR11t5rug3XHkklcHq5CUQHsiB8IryWZDI7
mTdopip2ewbK92DaHNXc4rSvpcNcdNjjX9cbt0RfC3FINvw8LCMjZd3bOEc8gKWjJJUtphh7NN5p
0BIKScGcytglHzVAF3SX+MLQ4ZoOY0MK55cNb2lIi9FmYkoVZpRBA3bTG5+ts8ZdmiQRktwM5CMS
vQg8WtB5xjD7ii1G3LZ2OAKHvHix+ceia9wJQ/kYUg8xhbo8mbc3MiFMgv5lBcLbxESeOE1NATLS
+Y2R9m6l0VNl2MNjNejIKFF2X0j0I4+xA3xJd31rMpKT7stUBJ4ADmv4W16a6RQH/pAWi1U3jCdk
6p01MvfJ+FKbAlSquKuiJ3vi+nPPUXTCfWxnfOShMmgECCJTp9yzvKa6PFT1UDbeD63uPUpK9Syy
Z+KkdmhE4ieL8Ksm7ExwR+26FNC5M/Vq2LHJYSb7jcG6PgZiBncbUQv0hdV4XuC00E/6k7mOFx10
B09NuY7MWntHJXFagjdUUXUru2Fhssyf7hHXTj+9VcdWSlQimSJB1CIG4UK5qsLfqkrcHBEoiAUO
ZNAMwIez4C1C75paivtTHfO4u8oDSLPV9UPcvUlpTN31QY/PL7m6p38yOuc91vrCGjC5ZP2FKgv3
O3DEgV+uZuNQNVe4EvrNP2+LdlC2GrsNZ+0HlgPatW2FJP29awdhrt999q2o63yA2FgItq6EKqhO
55iqek4WDViZKEppGIsKY/I/pUmDrOnr5tmSVjOJur0H1YTC8P9rW54vrOkpvNFnfT1tcC0uOZ44
SiPCAEgV/dFEzF4LsBPovyDyu6PALd3RpzLX0+ETIUI1BSE6hspXaY4J2ti8FhkpG3faTD0yoY5+
dzbnsS+u+7Nf7pJTjHQe7q1iMf3bXZwMcc8vX3iabaLxVI9j/skwzijb5XPBSr95jxjj++LOx1ak
XWIyAHpQJlPtFbTFmhmS39sFEqEMGgjTaYZje1kRdNX6RvTZ/5WQLM0Y5/5qRTm5WswdLoh13OQ7
t+T1vAWvf0y3L82OQfFLJl/Apq1vRGaBLC8GYpXUpHScN8uDCsC8P/OTdqE6/bpvhEdIY/BCPjYR
jLGIzJcG9rkza8ehyVfFofet66u+1Rq7BGC0h8anVGvTAs2Hji+OccDju+GVFJ9fenrcqumDTvvx
zw0q9QoZZgjv8sU8421xNF5MXD8U2f1/rUYPd3eZBjKRkRGdV6Z9vOi0itVtkEhjhM9VG+vlPA6G
204tNGfEG0dhZJPT88fTUS1k1U1qz8lXjMi9W8Sb7NOEBUtWO3T38XTshEU6oFqyGSPzjW/E9ZGF
MYTQ5IYJcNPNW2qujI1eQcHChiCAWqBPz06/7+YJLV/5+XUqIWsV8FJPXMaGYVquN4O0RF9cq8fN
S1M5nCiFXcvYPgM9GQkUrKHUx7/h+r9LXT/jCainyDya4Bep2d6qw7MSs6Nz5TNKfXuQatPOQFKp
zxZWKpmLfBi25rioNUuSz80L0/Tp08JbixcnwkYcyywSs1+DpiBhvW/HjCOn4vUQ5eLbwFARLb9k
8ekQJecNe7GwJj8zqbsLmwMQG8BRWiUhWwvR3jW+uxNVBprkI+ngng252klBQOO1KB7lPuh7MiIe
rfUv5Al2+tep3mgGPq6wuU+e/D5uE8BwM57AQSXiSShipvBs5ya34zTYZhmiAAD/eeasymtkVgAB
hA/chwEApy/HVbHEZ/sCAAAAAARZWg==

Ungolfed:

/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4FTrB+NdAC8CgQKxGND7urrBgy10a+lq9gP9wSLgMqJb
pNHJMhYOiDHCSukpsHuQPqPd/4L4ZTIqW7+CNF2+iSlEPkpGKx8mgtz/0/0uh1K/PjpgF6CKpTao
OagiH/R/0k1JSdZny4EGQRhgjeEqcHSYN0XwYUNQ4hNcNnG9oNx89YRd+fhb0McwGItppBEJP5ly
fV0fuxawst8IqkzqRrzX3wTC1Pva//ko4PZHtZaD231oqRJeK8ed6VBqhYMUn/VakiYh9PmdVJ4N
DzDTLQz/p1pH2R3zpDsOPwjWU4zPHiqq/JNgTIzvlYwhBpjB/mxI+VqFhH+5vCWo0iei6zDvQUOp
5jFgukLYRlKrqLPG4eMLq0mfyybUyLLPV9+MrPgX/GUmewiH+VprnnLBWybIsZwq+j+dCzC0zB8I
fWKTjv6RpT7kJiIt5d5RRnoLOv2tusA5VvIpKWAhyNB7/kp2udTWJ0AH7fcbfxo/xWndV6umQK8s
efzG+KIlZyIDDa/Rnpc3avNgxVZnop1A1ZEWSvDsuRslkBkIhSpqoGh4zoAWrZjbOrOSBSS90w14
CC2t/CIrXlJJ4WyjWyh+N4RHDWCM1sCX/WFf+elMvIjxYe5cGZdWoeXmNfTYRXfhTzSNQRAhYcq5
SbpDahvq70vttfQ0lMdxtvy2IDZzJZMQgo9s0dhp+TG4zc7DK47RuPpPZffz8cKGvXGUVCvGugug
jvB9jehPbMH8UfNAiSlvQJGYU5F7POvvAoYbDcqUJGYe456+r066D5lFtsjqm8R5jMa9P3P4PMfp
VNHyYCDa7ddcwJz9umgAHjmMXMEXqwl0RLEHzug43lsl/ecvt+FdMZnlnch/3S7l7xt/uSNnYzgv
h9nP0nTuoTP6gpQy3/Gbegnbd9xFaXrUletx1mG3uKB7MBsyHGQAcldlDenw7EcE2F3zeEBOEOiZ
yniQp6cvQs34TEFIoS3y7E/34YaJ/A2GoXkW0U1wqpy9Q1wWS1yaPuUZsEoPXmt8vk/pMDTY7e8H
wh6JaoHpZ38fCc+ZT4USaQ+vG3Magsu1hEm+lYw9s9ZTU50jva1g8TmrCyJvPSkeZS1pc/UaDWpQ
mcgeQp0Gcwhgx7qW+d7JVp2YvtyoODGc9mSaypL4z3MegZu6f6p9h7cGxg3SPQrZ3HqZyiszuzsh
PPRXGM89GDrvIKbzWMx2AFSB38Jq4SdJsu9qgQ8XeYMlawRWatLPCyn8VR/kY9Bndj0M81wGr6Tm
vMtj50/Lo4efc/qhqio8NahizZtoy3gOBtYEzBcTQ3vX9CdMRP4VHDtm1mvTeGbwgFLa6HRFF7m+
YpQb2oUjdFkOc6Ntaj8xkpdVZr9HtUUwE4xZNtaGE1DawFLe4EtkQ5qoJ0RTXgLncrejbXIKc7N4
Sqk9fz/hhPczd6jJLomdiEzneIekW+Fkh/E0vh6YSnempM7fVmUsh795rASSm1OcKWLHlVKoJEIx
F5Rh33WixS39tFe8SpXn8/NAuxrG8sHrzFfaTdOVG0yIn16E00CfbWjXlNIEVIEzL8flQnVVcUiR
XrzjFnFqoZi39jowpAXHTYVa6b6HWMIrgQ0bnqwwvKrcBqJJ+AWf7DFwES/CQmTq8kLSoBwZmZ3x
Ruw4FgK5Kah1dUX2SP1z2tLFpUrZdwRRS5KragvS1rCPUOxoKjyRPC5zRGam9jZQpxSHIm1A/PU2
Iye9CqC0nvoBZumMNpGhkWd905SUdRaKGXaZ9B4/IyFu+J2s+Gwyfsiaw3EXetS0gWcpA4IN3G13
8MqzxGg8d9o0yKK9QpfTNzXVQjikiT+8tR1bYp9BLBJkoralecy2vKNr5uJFKU7UgbMxq4Mj13WA
v5qRjTKg04KtQCSGcPv6vanYfq2/Kjyiv145NNR9tDzoJSqTd9fujxOOY/aitPzSnO0Zz1iz0SQD
jixBBsfFIOhrczlRCuBSD0Eu8uG8ZvSbpjMb0BEpxTEmFGCm9WHaxhwtA7fRO8mGCSFSooxPcZrx
ThMA+9A5Zetnuo5+S74tMciJAHfZA7a6k6PP10JBP9OmcegXm/7gLUgklW2nerK+Sv5rBRuMdazE
f8h/Oh94uSTdCffdjrl3poMI/FpktngiM5vEOTvoUeJd8R25nEso9kuGJchO6DrPe03/UStAaWf2
Mpi5/ShBST8H2EpdVVzTCkHW1R/JL/YSGdJpBwiYtizNu4SfnaqUQN2dCZzAmuYofJ+gnQMR5xuG
GwDKDpjN8T7SdO/KAxMD1/1DVfAhZYbqtBaU70jbGC+6cl9XPGV3B0VfJDXKPKhDD9rWWfL4L/+0
7UsGl3kAp4nBokcF23RBQVA+f6iKlF1edQQq6OSsX+oiZlG2BghXbO0iIMIkK3Awl5Os1jmHalfS
R5G3bTIXEmYf+pQ8W0qY1i17XqailA3E3tngshbv2ffw6uYBmETgcYD4p3UOI/8gU6vLZ1AbsXdd
V0w7bBoGnc3KBQG9jm7PxVFeQ6hZY5z7cDUtytLA4SBCfUYvv7rN+7ctMbBQPO2dlT1lm7uoN5HK
JeWyFaNaWtbOA5blNwjBDH9QSxZsEjIY7FENQxW6U5dQQuPctw2EUMT9DC2M1ff3aFtbaqoK5HcI
9VeDSeBxFq1jXwOycVnNtWbMGufP3KtbJegpF1qvlDluuzY0jtJHz16hkOiFi7HcnK798ZBNWwAA
zJ7uOgG/vd8AAf8P7KkBAO5B2vaxxGf7AgAAAAAEWVo=

Tested on RegexStorm and this blog and RegExLib (with all options unchecked).

The solution to this regex is the factorization of 5122188685368916735780446744735847888756487271329 = 2147852126374329492975359 * 2384795779221263457172831, with the result encoded in base 289, least significant first.

Each digit is firstly split into two base 17 numbers to make the calculations faster. This is also how the product is encoded in the regex.

Each pair of digits in the two numbers is then multiplied into capture group a0 to a38. Each of them is a digit of the product. The current position is kept track by p and q. And the carry is processed after the multiplication, while comparing the product.

It is in base 289 because it was designed to accept two 1024 bit numbers, which has 128 base 256 digits each, and I didn't think of removing the comma so the full string with base 256 would be 257 characters.

The 1536 bit version is here. It accepts two 768 bit numbers. The numbers in this easy version each has only 81 bits.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Match: Ľê¯6Aĝ4aþĀ,lŃŝĿBİŢŞĩï (escaped: \u013d\xea\xaf6A\u011d4a\xfe\u0100,l\u0143\u015d\u013fB\u0130\u0162\u015e\u0129\xef). Non-match: VeryNiceMultiplier \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 17:15
4
\$\begingroup\$

ECMAScript flavour, 30 bytes [cracked]

^((?![\t- ]|[^\s])(.)(?!\2))+$

Here is a rather simple one for the robbers to crack. It's conceptually not too hard, but might require a little research (or scripting). I don't intend to list myself in the leaderboard, but if someone cracks it within 72 hours, this will count towards their robber's score.

Tested on Regex101 and RegExr using Chrome.

Well, that was quick!

The regex was supposed to match any string consisting of distinct non-ASCII whitespace characters. However, I forgot a .* before the \2, so it actually matches any string of non-ASCII whitespace, that doesn't contain two consecutive identical characters. There are 18 such characters in the Unicode range up to code point 0xFFFF. The match posted by user23013 is one such string, consisting of 16 characters.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Match (base64): wqDigZ/CoOKBn8Kg4oGfwqDigZ/CoOKBn8Kg4oGfwqDigZ/CoOKBnw==, Non-match: aaaabaaacaaadaaa \$\endgroup\$
    – jimmy23013
    Oct 14, 2014 at 23:46
  • \$\begingroup\$ It is not distinct but only alternating, with only two distinct characters. \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 0:01
  • \$\begingroup\$ @user23013 Damn, I forgot a .* in the lookahead. Good catch. Should have tested more thoroughly. \$\endgroup\$ Oct 15, 2014 at 0:03
4
\$\begingroup\$

Ruby-flavored, 24 bytes [cracked]

^(?!.*(.+)\1)([\[\\\]]){256}$
\$\endgroup\$
4
  • \$\begingroup\$ Please include a link to a tester where your intended key is working (like rubular.com). (Also, obfuscation/golfing pro tip: if you use PCRE instead, the character class could be written as []\\[] ;)) \$\endgroup\$ Oct 15, 2014 at 14:12
  • \$\begingroup\$ Link added. I suspect Wumpus has cracked it, could prove it with a permalink to rubular.com \$\endgroup\$
    – histocrat
    Oct 15, 2014 at 15:03
  • 2
    \$\begingroup\$ Non-match: soylentgreenispeople. Match available at rubular.com/r/TCqjcaGsU1 not posted here because of how the comment system handles long words. \$\endgroup\$
    – user15244
    Oct 15, 2014 at 15:14
  • \$\begingroup\$ @WumpusQ.Wumbley Great! If you include the non-match into that same comment, we can clean up all the mess above this. \$\endgroup\$ Oct 15, 2014 at 15:16
4
\$\begingroup\$

PHP, 168 bytes [cracked by nneonneo]

^((?![!?$]*[^!?$]))?(?:[^!]\2?+(?=(!*)(\\\3?+.(?!\3)))){4}(?(1)|Ha! No one will ever get this one...)|(?!(?1))\Q\1?!($!?)?\E\1?!($!?)?(?<!.{12})\Q(?=(?1))\E(?=(?1))!\?$

Here is a regex demo.

P.S. This game is hard.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Match: \1?!($!?)?!(?=(?1))!?. Non-match: IncrementalRegexTestingWorks \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 5:39
  • \$\begingroup\$ @nneonneo Ah, you're too good ;) \$\endgroup\$
    – Unihedron
    Oct 18, 2014 at 5:39
4
\$\begingroup\$

PCRE (1043 bytes) [cracked]

After randomly generated regexes have failed me (the ideas were good, but I couldn't generate adequate problem instances), I've decided to hand craft this one. I dub it "A whole lot of rules to satisfy".

^(?=^([^)(]*\(((?>[^)(]+)|(?1))*\)[^)(]*)*$)(?=^([^][]*\[((?>[^][]+)|(?3))*\][^][]*)*$)(?=^([^}{]*\{((?>[^}{]+)|(?5))*\}[^}{]*)*$)(?!^\(.*)(?!.*\(.{250}\).*)(?=.*\[.{250}\].*)(?=.*\{.{250}\}.*)(?=.*\[.\(\).\{\}.\].*)(?=.*\}...\[...\[...\]...\]...\{.*)(?=.*\(\(..\(\(.{68}\(\(\)\).{43}\)\)\)\).*)(?=.*\{..\{..\{.{65}\{\}\{\}.{33}\{\}.{107}\}\}.\}.*)(?=.*\[\{\{\[\(\{.*)(?=.*\[\[..\[.{6}\[.{6}\]\]...\]\].{6}\[..\]..\[\].*)(?=.*\]\]\}\}\}.\)\)\)\).{96}\]\}\}\]\]\]\}\]\]\].\)\]\].*)(?=.*\]..\).{6}\(.{7}\{.{5}\[...\[.{5}\{\[.*)(?=.*\[.{87}\{.{45}}{.{38}}.{27}\].*)(?=.*\(\{.{32}\(.{20}\{.{47}\].{43}\{\{.{25}\}\}.{18}\].{5}\}....\}.{5}\).*)(?=.*\{.{12}\(.{5}\(...\(...\{\[.\{\[\[.*)(?=.*\{\(.{21}\).{8}\}.{14}\[.{7}\]..\{.{5}\{\}....\}.*)(?=.*\(.\{.{49}\{.{16}\}.{25}\}.{66}\).*)(?!.*\(\{\(\(.*)(?!.*\(\)\[\].*)(?=(.*?\].*?\)){15,}.*)(?=(.*\[.*\(.*\{){5,9}.*)(?=.*\({3}.{105}\[{3}.{105}[^}{].*)(?=.*\(..\).{5}\(\)....\}\}\].\{\{\[.{22}\[.{35}\}\}\].*)(?!.*\(\(.{178}\])(?=(.*\[..\]){8,10}.*)(?!(.*\([^\(\)]{5}\(){4,}.*).{63}(.{6}).{130}\11.{51}$

And expanded:

^
(?=^([^)(]*\(((?>[^)(]+)|(?1))*\)[^)(]*)*$)
(?=^([^][]*\[((?>[^][]+)|(?3))*\][^][]*)*$)
(?=^([^}{]*\{((?>[^}{]+)|(?5))*\}[^}{]*)*$)
(?!^\(.*)
(?!.*\(.{250}\).*)
(?=.*\[.{250}\].*)
(?=.*\{.{250}\}.*)
(?=.*\[.\(\).\{\}.\].*)
(?=.*\}...\[...\[...\]...\]...\{.*)
(?=.*\(\(..\(\(.{68}\(\(\)\).{43}\)\)\)\).*)
(?=.*\{..\{..\{.{65}\{\}\{\}.{33}\{\}.{107}\}\}.\}.*)
(?=.*\[\{\{\[\(\{.*)
(?=.*\[\[..\[.{6}\[.{6}\]\]...\]\].{6}\[..\]..\[\].*)
(?=.*\]\]\}\}\}.\)\)\)\).{96}\]\}\}\]\]\]\}\]\]\].\)\]\].*)
(?=.*\]..\).{6}\(.{7}\{.{5}\[...\[.{5}\{\[.*)
(?=.*\[.{87}\{.{45}}{.{38}}.{27}\].*)
(?=.*\(\{.{32}\(.{20}\{.{47}\].{43}\{\{.{25}\}\}.{18}\].{5}\}....\}.{5}\).*)
(?=.*\{.{12}\(.{5}\(...\(...\{\[.\{\[\[.*)
(?=.*\{\(.{21}\).{8}\}.{14}\[.{7}\]..\{.{5}\{\}....\}.*)
(?=.*\(.\{.{49}\{.{16}\}.{25}\}.{66}\).*)
(?!.*\(\{\(\(.*)
(?!.*\(\)\[\].*)
(?=(.*?\].*?\)){15,}.*)
(?=(.*\[.*\(.*\{){5,9}.*)
(?=.*\({3}.{105}\[{3}.{105}[^}{].*)
(?=.*\(..\).{5}\(\)....\}\}\].\{\{\[.{22}\[.{35}\}\}\].*)
(?!.*\(\(.{178}\])
(?=(.*\[..\]){8,10}.*)
(?!(.*\([^\(\)]{5}\(){4,}.*)
.{63}(.{6}).{130}\11.{51}
$

Tested on Regex101 - depending on your computer you may need to up the max execution time.


This regex encodes a whole bunch of rules that just need to be satisfied. Any solution will do, it's just finding one.

  • The first three core rules require that, separately, all ([{ brackets need to be balanced within the key.
  • Most expressions require that a certain "shape" needs to be in or not be in the key. For example, the 8th row requires something of the form [.(.).].
  • Rules like (?=(.*\[.*\(.*\{){5,9}.*), for example, require that [({ alternation happens at least 5 times. Note that this line in particular is bugged on many levels, unintentionally.
  • The backreference \11 requires one six-character substring to appear twice in particular positions.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Match: [((({.[.[](){{}{].{.(({){(.[]()....}}].{{[[....).[..]()(}..[..]([....(([{((({).](){.{}{}{}....}[[()[}}][{{[({[[[.]]}()]].{}.]{[..]{.[]]}}}())))(())[(.].{[.{[[..[()].()}{{.[...[}{.]..)]...{.])))).}}..([......{.....[.]}[...}.{[.}...}})}.))).]}}]]]}]]].)]]..}. Non-match: WhatANastySetOfRulesYouHave. \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 6:40
  • \$\begingroup\$ I increased the execution time to 50 seconds. By the way, if you just use the proper non-greedy quantifiers in (?=(.*\[.*\(.*\{){5,9}.*), then you won't need to increase the maximum execution time (same result) - the matches will be instant. \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 6:43
  • \$\begingroup\$ @nneonneo Ahaha yeah, I realised that after I posted. Can you post, say, a pastebin link for your key though? SE comments seem to be acting up again \$\endgroup\$
    – Sp3000
    Oct 18, 2014 at 7:06
  • \$\begingroup\$ @nneonneo Also if you have so many dots in your solution, clearly I didn't have enough rules :P \$\endgroup\$
    – Sp3000
    Oct 18, 2014 at 7:06
  • 2
    \$\begingroup\$ Here's a regex101 link with my solution visible: regex101.com/r/gP2aX7/1 \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 7:20
4
\$\begingroup\$

.NET flavour (7563 bytes) [cracked]

Inspired by @user23013's idea

^(?:(?=1(?<1>){5632})|(?=0)).(?:(?=1(?<1>){79361})|(?=0)).(?:(?=1(?<1>){188421})|(?=0)).(?:(?=1(?<1>){164870})|(?=0)).(?:(?=1(?<1>){63496})|(?=0)).(?:(?=1(?<1>){116233})|(?=0)).(?:(?=1(?<1>){112138})|(?=0)).(?:(?=1(?<1>){47447})|(?=0)).(?:(?=1(?<1>){85005})|(?=0)).(?:(?=1(?<1>){17936})|(?=0)).(?:(?=1(?<1>){108053})|(?=0)).(?:(?=1(?<1>){88599})|(?=0)).(?:(?=1(?<1>){91672})|(?=0)).(?:(?=1(?<1>){178716})|(?=0)).(?:(?=1(?<1>){199710})|(?=0)).(?:(?=1(?<1>){166661})|(?=0)).(?:(?=1(?<1>){190496})|(?=0)).(?:(?=1(?<1>){184494})|(?=0)).(?:(?=1(?<1>){199203})|(?=0)).(?:(?=1(?<1>){116778})|(?=0)).(?:(?=1(?<1>){78891})|(?=0)).(?:(?=1(?<1>){192556})|(?=0)).(?:(?=1(?<1>){24995})|(?=0)).(?:(?=1(?<1>){1071})|(?=0)).(?:(?=1(?<1>){192561})|(?=0)).(?:(?=1(?<1>){108082})|(?=0)).(?:(?=1(?<1>){1593})|(?=0)).(?:(?=1(?<1>){26967})|(?=0)).(?:(?=1(?<1>){197983})|(?=0)).(?:(?=1(?<1>){97034})|(?=0)).(?:(?=1(?<1>){86965})|(?=0)).(?:(?=1(?<1>){60480})|(?=0)).(?:(?=1(?<1>){149571})|(?=0)).(?:(?=1(?<1>){100932})|(?=0)).(?:(?=1(?<1>){40519})|(?=0)).(?:(?=1(?<1>){173492})|(?=0)).(?:(?=1(?<1>){80972})|(?=0)).(?:(?=1(?<1>){115790})|(?=0)).(?:(?=1(?<1>){29265})|(?=0)).(?:(?=1(?<1>){91730})|(?=0)).(?:(?=1(?<1>){173140})|(?=0)).(?:(?=1(?<1>){52821})|(?=0)).(?:(?=1(?<1>){176726})|(?=0)).(?:(?=1(?<1>){170211})|(?=0)).(?:(?=1(?<1>){150105})|(?=0)).(?:(?=1(?<1>){23131})|(?=0)).(?:(?=1(?<1>){81503})|(?=0)).(?:(?=1(?<1>){77412})|(?=0)).(?:(?=1(?<1>){106086})|(?=0)).(?:(?=1(?<1>){4284})|(?=0)).(?:(?=1(?<1>){142610})|(?=0)).(?:(?=1(?<1>){167534})|(?=0)).(?:(?=1(?<1>){190577})|(?=0)).(?:(?=1(?<1>){147731})|(?=0)).(?:(?=1(?<1>){133748})|(?=0)).(?:(?=1(?<1>){194750})|(?=0)).(?:(?=1(?<1>){49257})|(?=0)).(?:(?=1(?<1>){49274})|(?=0)).(?:(?=1(?<1>){120767})|(?=0)).(?:(?=1(?<1>){172668})|(?=0)).(?:(?=1(?<1>){24703})|(?=0)).(?:(?=1(?<1>){108160})|(?=0)).(?:(?=1(?<1>){60546})|(?=0)).(?:(?=1(?<1>){56963})|(?=0)).(?:(?=1(?<1>){30340})|(?=0)).(?:(?=1(?<1>){95368})|(?=0)).(?:(?=1(?<1>){59530})|(?=0)).(?:(?=1(?<1>){53388})|(?=0)).(?:(?=1(?<1>){14477})|(?=0)).(?:(?=1(?<1>){28302})|(?=0)).(?:(?=1(?<1>){182927})|(?=0)).(?:(?=1(?<1>){59024})|(?=0)).(?:(?=1(?<1>){146200})|(?=0)).(?:(?=1(?<1>){153746})|(?=0)).(?:(?=1(?<1>){39571})|(?=0)).(?:(?=1(?<1>){134293})|(?=0)).(?:(?=1(?<1>){158362})|(?=0)).(?:(?=1(?<1>){170139})|(?=0)).(?:(?=1(?<1>){182940})|(?=0)).(?:(?=1(?<1>){7327})|(?=0)).(?:(?=1(?<1>){143525})|(?=0)).(?:(?=1(?<1>){119464})|(?=0)).(?:(?=1(?<1>){82090})|(?=0)).(?:(?=1(?<1>){170667})|(?=0)).(?:(?=1(?<1>){49522})|(?=0)).(?:(?=1(?<1>){69806})|(?=0)).(?:(?=1(?<1>){15535})|(?=0)).(?:(?=1(?<1>){16049})|(?=0)).(?:(?=1(?<1>){163358})|(?=0)).(?:(?=1(?<1>){181876})|(?=0)).(?:(?=1(?<1>){58044})|(?=0)).(?:(?=1(?<1>){16062})|(?=0)).(?:(?=1(?<1>){39616})|(?=0)).(?:(?=1(?<1>){31425})|(?=0)).(?:(?=1(?<1>){94404})|(?=0)).(?:(?=1(?<1>){86848})|(?=0)).(?:(?=1(?<1>){16589})|(?=0)).(?:(?=1(?<1>){195280})|(?=0)).(?:(?=1(?<1>){199377})|(?=0)).(?:(?=1(?<1>){43731})|(?=0)).(?:(?=1(?<1>){67534})|(?=0)).(?:(?=1(?<1>){106198})|(?=0)).(?:(?=1(?<1>){54999})|(?=0)).(?:(?=1(?<1>){52952})|(?=0)).(?:(?=1(?<1>){125828})|(?=0)).(?:(?=1(?<1>){169691})|(?=0)).(?:(?=1(?<1>){184542})|(?=0)).(?:(?=1(?<1>){177888})|(?=0)).(?:(?=1(?<1>){43233})|(?=0)).(?:(?=1(?<1>){127203})|(?=0)).(?:(?=1(?<1>){116518})|(?=0)).(?:(?=1(?<1>){117990})|(?=0)).(?:(?=1(?<1>){67815})|(?=0)).(?:(?=1(?<1>){62202})|(?=0)).(?:(?=1(?<1>){165611})|(?=0)).(?:(?=1(?<1>){197356})|(?=0)).(?:(?=1(?<1>){29933})|(?=0)).(?:(?=1(?<1>){90862})|(?=0)).(?:(?=1(?<1>){90863})|(?=0)).(?:(?=1(?<1>){149232})|(?=0)).(?:(?=1(?<1>){61681})|(?=0)).(?:(?=1(?<1>){137970})|(?=0)).(?:(?=1(?<1>){90357})|(?=0)).(?:(?=1(?<1>){47351})|(?=0)).(?:(?=1(?<1>){172509})|(?=0)).(?:(?=1(?<1>){78293})|(?=0)).(?:(?=1(?<1>){66303})|(?=0)).(?:(?=1(?<1>){66262})|(?=0)).(?:(?=1(?<1>){158471})|(?=0)).(?:(?=1(?<1>){5676})|(?=0)).(?:(?=1(?<1>){127242})|(?=0)).(?:(?=1(?<1>){51979})|(?=0)).(?:(?=1(?<1>){162060})|(?=0)).(?:(?=1(?<1>){27405})|(?=0)).(?:(?=1(?<1>){153874})|(?=0)).(?:(?=1(?<1>){150291})|(?=0)).(?:(?=1(?<1>){1814})|(?=0)).(?:(?=1(?<1>){193815})|(?=0)).(?:(?=1(?<1>){82200})|(?=0)).(?:(?=1(?<1>){59161})|(?=0)).(?:(?=1(?<1>){78620})|(?=0)).(?:(?=1(?<1>){123678})|(?=0)).(?:(?=1(?<1>){147232})|(?=0)).(?:(?=1(?<1>){71457})|(?=0)).(?:(?=1(?<1>){118562})|(?=0)).(?:(?=1(?<1>){129830})|(?=0)).(?:(?=1(?<1>){161841})|(?=0)).(?:(?=1(?<1>){60295})|(?=0)).(?:(?=1(?<1>){165426})|(?=0)).(?:(?=1(?<1>){107485})|(?=0)).(?:(?=1(?<1>){171828})|(?=0)).(?:(?=1(?<1>){166200})|(?=0)).(?:(?=1(?<1>){35124})|(?=0)).(?:(?=1(?<1>){160573})|(?=0)).(?:(?=1(?<1>){7486})|(?=0)).(?:(?=1(?<1>){169279})|(?=0)).(?:(?=1(?<1>){151360})|(?=0)).(?:(?=1(?<1>){6978})|(?=0)).(?:(?=1(?<1>){136003})|(?=0)).(?:(?=1(?<1>){56133})|(?=0)).(?:(?=1(?<1>){8520})|(?=0)).(?:(?=1(?<1>){87436})|(?=0)).(?:(?=1(?<1>){57162})|(?=0)).(?:(?=1(?<1>){197965})|(?=0)).(?:(?=1(?<1>){145230})|(?=0)).(?:(?=1(?<1>){95459})|(?=0)).(?:(?=1(?<1>){180564})|(?=0)).(?:(?=1(?<1>){157850})|(?=0)).(?:(?=1(?<1>){109399})|(?=0)).(?:(?=1(?<1>){191832})|(?=0)).(?:(?=1(?<1>){110223})|(?=0)).(?:(?=1(?<1>){75102})|(?=0)).(?:(?=1(?<1>){140639})|(?=0)).(?:(?=1(?<1>){49504})|(?=0)).(?:(?=1(?<1>){197987})|(?=0)).(?:(?=1(?<1>){52744})|(?=0)).(?:(?=1(?<1>){96615})|(?=0)).(?:(?=1(?<1>){13672})|(?=0)).(?:(?=1(?<1>){73068})|(?=0)).(?:(?=1(?<1>){104814})|(?=0)).(?:(?=1(?<1>){66929})|(?=0)).(?:(?=1(?<1>){23410})|(?=0)).(?:(?=1(?<1>){122686})|(?=0)).(?:(?=1(?<1>){44918})|(?=0)).(?:(?=1(?<1>){101752})|(?=0)).(?:(?=1(?<1>){3961})|(?=0)).(?:(?=1(?<1>){31807})|(?=0)).(?:(?=1(?<1>){54933})|(?=0)).(?:(?=1(?<1>){140096})|(?=0)).(?:(?=1(?<1>){49026})|(?=0)).(?:(?=1(?<1>){5507})|(?=0)).(?:(?=1(?<1>){96132})|(?=0)).(?:(?=1(?<1>){167303})|(?=0)).(?:(?=1(?<1>){57877})|(?=0)).(?:(?=1(?<1>){88461})|(?=0)).(?:(?=1(?<1>){111853})|(?=0)).(?:(?=1(?<1>){126531})|(?=0)).(?:(?=1(?<1>){110998})|(?=0)).(?:(?=1(?<1>){7575})|(?=0)).(?:(?=1(?<1>){7064})|(?=0)).(?:(?=1(?<1>){59289})|(?=0)).(?:(?=1(?<1>){122203})|(?=0)).(?:(?=1(?<1>){175005})|(?=0)).(?:(?=1(?<1>){28025})|(?=0)).(?:(?=1(?<1>){49057})|(?=0)).(?:(?=1(?<1>){6373})|(?=0)).(?:(?=1(?<1>){50084})|(?=0)).(?:(?=1(?<1>){70565})|(?=0)).(?:(?=1(?<1>){75178})|(?=0)).(?:(?=1(?<1>){142763})|(?=0)).(?:(?=1(?<1>){56237})|(?=0)).(?:(?=1(?<1>){32176})|(?=0)).(?:(?=1(?<1>){113073})|(?=0)).(?:(?=1(?<1>){149939})|(?=0)).(?:(?=1(?<1>){16308})|(?=0)).(?:(?=1(?<1>){12725})|(?=0)).(?:(?=1(?<1>){75190})|(?=0)).(?:(?=1(?<1>){54711})|(?=0)).(?:(?=1(?<1>){180664})|(?=0)).(?:(?=1(?<1>){68540})|(?=0)).(?:(?=1(?<1>){93117})|(?=0)).(?:(?=1(?<1>){161781})|(?=0)).(?:(?=1(?<1>){15808})|(?=0)).(?:(?=1(?<1>){130814})|(?=0)).(?:(?=1(?<1>){162379})|(?=0)).(?:(?=1(?<1>){80836})|(?=0)).(?:(?=1(?<1>){149943})|(?=0)).(?:(?=1(?<1>){16841})|(?=0)).(?:(?=1(?<1>){149452})|(?=0)).(?:(?=1(?<1>){182733})|(?=0)).(?:(?=1(?<1>){56270})|(?=0)).(?:(?=1(?<1>){163792})|(?=0)).(?:(?=1(?<1>){34770})|(?=0)).(?:(?=1(?<1>){101843})|(?=0)).(?:(?=1(?<1>){199124})|(?=0)).(?:(?=1(?<1>){129493})|(?=0)).(?:(?=1(?<1>){43990})|(?=0)).(?:(?=1(?<1>){113112})|(?=0)).(?:(?=1(?<1>){71129})|(?=0)).(?:(?=1(?<1>){61402})|(?=0)).(?:(?=1(?<1>){145852})|(?=0)).(?:(?=1(?<1>){98781})|(?=0)).(?:(?=1(?<1>){141790})|(?=0)).(?:(?=1(?<1>){163235})|(?=0)).(?:(?=1(?<1>){110566})|(?=0)).(?:(?=1(?<1>){117737})|(?=0)).(?:(?=1(?<1>){67050})|(?=0)).(?:(?=1(?<1>){68075})|(?=0)).(?:(?=1(?<1>){124047})|(?=0)).(?:(?=1(?<1>){181587})|(?=0)).(?:(?=1(?<1>){125429})|(?=0)).(?:(?=1(?<1>){112118})|(?=0)).(?:(?=1(?<1>){196088})|(?=0)).(?:(?=1(?<1>){25082})|(?=0)).(?:(?=1(?<1>){178684})|(?=0)).(?:(?=1(?<1>){13822})|(?=0)).(?<-1>){10094986}(?(1)(?!))$

We just can't have enough NP-complete problems! Here's the expanded version:

^
(?:(?=1(?<1>){5632})|(?=0)).
(?:(?=1(?<1>){79361})|(?=0)).
(?:(?=1(?<1>){188421})|(?=0)).
(?:(?=1(?<1>){164870})|(?=0)).
(?:(?=1(?<1>){63496})|(?=0)).
(?:(?=1(?<1>){116233})|(?=0)).
(?:(?=1(?<1>){112138})|(?=0)).
(?:(?=1(?<1>){47447})|(?=0)).
(?:(?=1(?<1>){85005})|(?=0)).
(?:(?=1(?<1>){17936})|(?=0)).
(?:(?=1(?<1>){108053})|(?=0)).
(?:(?=1(?<1>){88599})|(?=0)).
(?:(?=1(?<1>){91672})|(?=0)).
(?:(?=1(?<1>){178716})|(?=0)).
(?:(?=1(?<1>){199710})|(?=0)).
(?:(?=1(?<1>){166661})|(?=0)).
(?:(?=1(?<1>){190496})|(?=0)).
(?:(?=1(?<1>){184494})|(?=0)).
(?:(?=1(?<1>){199203})|(?=0)).
(?:(?=1(?<1>){116778})|(?=0)).
(?:(?=1(?<1>){78891})|(?=0)).
(?:(?=1(?<1>){192556})|(?=0)).
(?:(?=1(?<1>){24995})|(?=0)).
(?:(?=1(?<1>){1071})|(?=0)).
(?:(?=1(?<1>){192561})|(?=0)).
(?:(?=1(?<1>){108082})|(?=0)).
(?:(?=1(?<1>){1593})|(?=0)).
(?:(?=1(?<1>){26967})|(?=0)).
(?:(?=1(?<1>){197983})|(?=0)).
(?:(?=1(?<1>){97034})|(?=0)).
(?:(?=1(?<1>){86965})|(?=0)).
(?:(?=1(?<1>){60480})|(?=0)).
(?:(?=1(?<1>){149571})|(?=0)).
(?:(?=1(?<1>){100932})|(?=0)).
(?:(?=1(?<1>){40519})|(?=0)).
(?:(?=1(?<1>){173492})|(?=0)).
(?:(?=1(?<1>){80972})|(?=0)).
(?:(?=1(?<1>){115790})|(?=0)).
(?:(?=1(?<1>){29265})|(?=0)).
(?:(?=1(?<1>){91730})|(?=0)).
(?:(?=1(?<1>){173140})|(?=0)).
(?:(?=1(?<1>){52821})|(?=0)).
(?:(?=1(?<1>){176726})|(?=0)).
(?:(?=1(?<1>){170211})|(?=0)).
(?:(?=1(?<1>){150105})|(?=0)).
(?:(?=1(?<1>){23131})|(?=0)).
(?:(?=1(?<1>){81503})|(?=0)).
(?:(?=1(?<1>){77412})|(?=0)).
(?:(?=1(?<1>){106086})|(?=0)).
(?:(?=1(?<1>){4284})|(?=0)).
(?:(?=1(?<1>){142610})|(?=0)).
(?:(?=1(?<1>){167534})|(?=0)).
(?:(?=1(?<1>){190577})|(?=0)).
(?:(?=1(?<1>){147731})|(?=0)).
(?:(?=1(?<1>){133748})|(?=0)).
(?:(?=1(?<1>){194750})|(?=0)).
(?:(?=1(?<1>){49257})|(?=0)).
(?:(?=1(?<1>){49274})|(?=0)).
(?:(?=1(?<1>){120767})|(?=0)).
(?:(?=1(?<1>){172668})|(?=0)).
(?:(?=1(?<1>){24703})|(?=0)).
(?:(?=1(?<1>){108160})|(?=0)).
(?:(?=1(?<1>){60546})|(?=0)).
(?:(?=1(?<1>){56963})|(?=0)).
(?:(?=1(?<1>){30340})|(?=0)).
(?:(?=1(?<1>){95368})|(?=0)).
(?:(?=1(?<1>){59530})|(?=0)).
(?:(?=1(?<1>){53388})|(?=0)).
(?:(?=1(?<1>){14477})|(?=0)).
(?:(?=1(?<1>){28302})|(?=0)).
(?:(?=1(?<1>){182927})|(?=0)).
(?:(?=1(?<1>){59024})|(?=0)).
(?:(?=1(?<1>){146200})|(?=0)).
(?:(?=1(?<1>){153746})|(?=0)).
(?:(?=1(?<1>){39571})|(?=0)).
(?:(?=1(?<1>){134293})|(?=0)).
(?:(?=1(?<1>){158362})|(?=0)).
(?:(?=1(?<1>){170139})|(?=0)).
(?:(?=1(?<1>){182940})|(?=0)).
(?:(?=1(?<1>){7327})|(?=0)).
(?:(?=1(?<1>){143525})|(?=0)).
(?:(?=1(?<1>){119464})|(?=0)).
(?:(?=1(?<1>){82090})|(?=0)).
(?:(?=1(?<1>){170667})|(?=0)).
(?:(?=1(?<1>){49522})|(?=0)).
(?:(?=1(?<1>){69806})|(?=0)).
(?:(?=1(?<1>){15535})|(?=0)).
(?:(?=1(?<1>){16049})|(?=0)).
(?:(?=1(?<1>){163358})|(?=0)).
(?:(?=1(?<1>){181876})|(?=0)).
(?:(?=1(?<1>){58044})|(?=0)).
(?:(?=1(?<1>){16062})|(?=0)).
(?:(?=1(?<1>){39616})|(?=0)).
(?:(?=1(?<1>){31425})|(?=0)).
(?:(?=1(?<1>){94404})|(?=0)).
(?:(?=1(?<1>){86848})|(?=0)).
(?:(?=1(?<1>){16589})|(?=0)).
(?:(?=1(?<1>){195280})|(?=0)).
(?:(?=1(?<1>){199377})|(?=0)).
(?:(?=1(?<1>){43731})|(?=0)).
(?:(?=1(?<1>){67534})|(?=0)).
(?:(?=1(?<1>){106198})|(?=0)).
(?:(?=1(?<1>){54999})|(?=0)).
(?:(?=1(?<1>){52952})|(?=0)).
(?:(?=1(?<1>){125828})|(?=0)).
(?:(?=1(?<1>){169691})|(?=0)).
(?:(?=1(?<1>){184542})|(?=0)).
(?:(?=1(?<1>){177888})|(?=0)).
(?:(?=1(?<1>){43233})|(?=0)).
(?:(?=1(?<1>){127203})|(?=0)).
(?:(?=1(?<1>){116518})|(?=0)).
(?:(?=1(?<1>){117990})|(?=0)).
(?:(?=1(?<1>){67815})|(?=0)).
(?:(?=1(?<1>){62202})|(?=0)).
(?:(?=1(?<1>){165611})|(?=0)).
(?:(?=1(?<1>){197356})|(?=0)).
(?:(?=1(?<1>){29933})|(?=0)).
(?:(?=1(?<1>){90862})|(?=0)).
(?:(?=1(?<1>){90863})|(?=0)).
(?:(?=1(?<1>){149232})|(?=0)).
(?:(?=1(?<1>){61681})|(?=0)).
(?:(?=1(?<1>){137970})|(?=0)).
(?:(?=1(?<1>){90357})|(?=0)).
(?:(?=1(?<1>){47351})|(?=0)).
(?:(?=1(?<1>){172509})|(?=0)).
(?:(?=1(?<1>){78293})|(?=0)).
(?:(?=1(?<1>){66303})|(?=0)).
(?:(?=1(?<1>){66262})|(?=0)).
(?:(?=1(?<1>){158471})|(?=0)).
(?:(?=1(?<1>){5676})|(?=0)).
(?:(?=1(?<1>){127242})|(?=0)).
(?:(?=1(?<1>){51979})|(?=0)).
(?:(?=1(?<1>){162060})|(?=0)).
(?:(?=1(?<1>){27405})|(?=0)).
(?:(?=1(?<1>){153874})|(?=0)).
(?:(?=1(?<1>){150291})|(?=0)).
(?:(?=1(?<1>){1814})|(?=0)).
(?:(?=1(?<1>){193815})|(?=0)).
(?:(?=1(?<1>){82200})|(?=0)).
(?:(?=1(?<1>){59161})|(?=0)).
(?:(?=1(?<1>){78620})|(?=0)).
(?:(?=1(?<1>){123678})|(?=0)).
(?:(?=1(?<1>){147232})|(?=0)).
(?:(?=1(?<1>){71457})|(?=0)).
(?:(?=1(?<1>){118562})|(?=0)).
(?:(?=1(?<1>){129830})|(?=0)).
(?:(?=1(?<1>){161841})|(?=0)).
(?:(?=1(?<1>){60295})|(?=0)).
(?:(?=1(?<1>){165426})|(?=0)).
(?:(?=1(?<1>){107485})|(?=0)).
(?:(?=1(?<1>){171828})|(?=0)).
(?:(?=1(?<1>){166200})|(?=0)).
(?:(?=1(?<1>){35124})|(?=0)).
(?:(?=1(?<1>){160573})|(?=0)).
(?:(?=1(?<1>){7486})|(?=0)).
(?:(?=1(?<1>){169279})|(?=0)).
(?:(?=1(?<1>){151360})|(?=0)).
(?:(?=1(?<1>){6978})|(?=0)).
(?:(?=1(?<1>){136003})|(?=0)).
(?:(?=1(?<1>){56133})|(?=0)).
(?:(?=1(?<1>){8520})|(?=0)).
(?:(?=1(?<1>){87436})|(?=0)).
(?:(?=1(?<1>){57162})|(?=0)).
(?:(?=1(?<1>){197965})|(?=0)).
(?:(?=1(?<1>){145230})|(?=0)).
(?:(?=1(?<1>){95459})|(?=0)).
(?:(?=1(?<1>){180564})|(?=0)).
(?:(?=1(?<1>){157850})|(?=0)).
(?:(?=1(?<1>){109399})|(?=0)).
(?:(?=1(?<1>){191832})|(?=0)).
(?:(?=1(?<1>){110223})|(?=0)).
(?:(?=1(?<1>){75102})|(?=0)).
(?:(?=1(?<1>){140639})|(?=0)).
(?:(?=1(?<1>){49504})|(?=0)).
(?:(?=1(?<1>){197987})|(?=0)).
(?:(?=1(?<1>){52744})|(?=0)).
(?:(?=1(?<1>){96615})|(?=0)).
(?:(?=1(?<1>){13672})|(?=0)).
(?:(?=1(?<1>){73068})|(?=0)).
(?:(?=1(?<1>){104814})|(?=0)).
(?:(?=1(?<1>){66929})|(?=0)).
(?:(?=1(?<1>){23410})|(?=0)).
(?:(?=1(?<1>){122686})|(?=0)).
(?:(?=1(?<1>){44918})|(?=0)).
(?:(?=1(?<1>){101752})|(?=0)).
(?:(?=1(?<1>){3961})|(?=0)).
(?:(?=1(?<1>){31807})|(?=0)).
(?:(?=1(?<1>){54933})|(?=0)).
(?:(?=1(?<1>){140096})|(?=0)).
(?:(?=1(?<1>){49026})|(?=0)).
(?:(?=1(?<1>){5507})|(?=0)).
(?:(?=1(?<1>){96132})|(?=0)).
(?:(?=1(?<1>){167303})|(?=0)).
(?:(?=1(?<1>){57877})|(?=0)).
(?:(?=1(?<1>){88461})|(?=0)).
(?:(?=1(?<1>){111853})|(?=0)).
(?:(?=1(?<1>){126531})|(?=0)).
(?:(?=1(?<1>){110998})|(?=0)).
(?:(?=1(?<1>){7575})|(?=0)).
(?:(?=1(?<1>){7064})|(?=0)).
(?:(?=1(?<1>){59289})|(?=0)).
(?:(?=1(?<1>){122203})|(?=0)).
(?:(?=1(?<1>){175005})|(?=0)).
(?:(?=1(?<1>){28025})|(?=0)).
(?:(?=1(?<1>){49057})|(?=0)).
(?:(?=1(?<1>){6373})|(?=0)).
(?:(?=1(?<1>){50084})|(?=0)).
(?:(?=1(?<1>){70565})|(?=0)).
(?:(?=1(?<1>){75178})|(?=0)).
(?:(?=1(?<1>){142763})|(?=0)).
(?:(?=1(?<1>){56237})|(?=0)).
(?:(?=1(?<1>){32176})|(?=0)).
(?:(?=1(?<1>){113073})|(?=0)).
(?:(?=1(?<1>){149939})|(?=0)).
(?:(?=1(?<1>){16308})|(?=0)).
(?:(?=1(?<1>){12725})|(?=0)).
(?:(?=1(?<1>){75190})|(?=0)).
(?:(?=1(?<1>){54711})|(?=0)).
(?:(?=1(?<1>){180664})|(?=0)).
(?:(?=1(?<1>){68540})|(?=0)).
(?:(?=1(?<1>){93117})|(?=0)).
(?:(?=1(?<1>){161781})|(?=0)).
(?:(?=1(?<1>){15808})|(?=0)).
(?:(?=1(?<1>){130814})|(?=0)).
(?:(?=1(?<1>){162379})|(?=0)).
(?:(?=1(?<1>){80836})|(?=0)).
(?:(?=1(?<1>){149943})|(?=0)).
(?:(?=1(?<1>){16841})|(?=0)).
(?:(?=1(?<1>){149452})|(?=0)).
(?:(?=1(?<1>){182733})|(?=0)).
(?:(?=1(?<1>){56270})|(?=0)).
(?:(?=1(?<1>){163792})|(?=0)).
(?:(?=1(?<1>){34770})|(?=0)).
(?:(?=1(?<1>){101843})|(?=0)).
(?:(?=1(?<1>){199124})|(?=0)).
(?:(?=1(?<1>){129493})|(?=0)).
(?:(?=1(?<1>){43990})|(?=0)).
(?:(?=1(?<1>){113112})|(?=0)).
(?:(?=1(?<1>){71129})|(?=0)).
(?:(?=1(?<1>){61402})|(?=0)).
(?:(?=1(?<1>){145852})|(?=0)).
(?:(?=1(?<1>){98781})|(?=0)).
(?:(?=1(?<1>){141790})|(?=0)).
(?:(?=1(?<1>){163235})|(?=0)).
(?:(?=1(?<1>){110566})|(?=0)).
(?:(?=1(?<1>){117737})|(?=0)).
(?:(?=1(?<1>){67050})|(?=0)).
(?:(?=1(?<1>){68075})|(?=0)).
(?:(?=1(?<1>){124047})|(?=0)).
(?:(?=1(?<1>){181587})|(?=0)).
(?:(?=1(?<1>){125429})|(?=0)).
(?:(?=1(?<1>){112118})|(?=0)).
(?:(?=1(?<1>){196088})|(?=0)).
(?:(?=1(?<1>){25082})|(?=0)).
(?:(?=1(?<1>){178684})|(?=0)).
(?:(?=1(?<1>){13822})|(?=0)).
(?<-1>){10094986}
(?(1)(?!))
$

Each (?:(?=1(?<1>){n})|(?=0)). row pushes n empty strings to group 1 if the digit 1 is found, and does nothing if a 0 is found. (?<-1>){10094986}(?(1)(?!)) then checks that the total number of empty strings in group 1 by the end is 10094986. Hence our goal is to find a subset of the numbers such that their total is 10094986. This is exactly the subset sum problem, which is a special case of the knapsack problem, and is NP-complete.

Tested on Regex Hero (Regex Storm times out for this one).

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Match: 01111111111111111111111011001111111111011111111111111111111101111111111 11111111111111111111011111111000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000 (remove those spaces). Non-match: KnapsackAlgorithm. It is not easy to install Silverlight on my Ubuntu machine. But this worked on some other tester. \$\endgroup\$
    – jimmy23013
    Oct 18, 2014 at 11:52
  • \$\begingroup\$ @user23013 Ah oops, I forgot that required Silverlight. But honestly though, either I'm unlucky or there's a lot of solutions, because that's a stupidly long chain of 0s at the end there. Then again I'll need to get over the 32-bit int barrier first, I think I have an idea... \$\endgroup\$
    – Sp3000
    Oct 18, 2014 at 13:55
  • \$\begingroup\$ I already had 700+ bit integer in my latest answer! \$\endgroup\$
    – jimmy23013
    Oct 18, 2014 at 14:02
  • \$\begingroup\$ @user23013 And you're telling us to factorise it? So mean! :P \$\endgroup\$
    – Sp3000
    Oct 18, 2014 at 14:09
  • 2
    \$\begingroup\$ The integer to factorise is 1536 bit. \$\endgroup\$
    – jimmy23013
    Oct 18, 2014 at 14:12
4
\$\begingroup\$

.NET flavour (52506 bytes)

Subset sum, deluxe edition.

Regex here, expanded version here, tested on RegExLib and Regex Hero


Match:1000010001000000001101011000001101110101001010011101000101010011011101000001010101001000010010000111011101100101001101001111000111010101100000101000101010110001010101001100100001110010001101010101100010110011000000110110000000011111101000001000011111100010

Mismatch: Huzzah for NP-complete regexes

This regex is one giant subset sum problem, and uses 16 groups to store data. Each 1 in the string represents 16 10-bit numbers, which together represent a 160-bit integer. The last few lines of the regex carry the values in the groups so that groups 2-16 go up to 1023 (e.g. 1*1023 + 1024 becomes 2*1023 + 1), as otherwise we'd only be solving 16 simultaneous mini subset sum problems as opposed to one big one.

\$\endgroup\$
1
  • \$\begingroup\$ Congratulations on making it through the 72 hours! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked. \$\endgroup\$ Oct 21, 2014 at 18:14
4
\$\begingroup\$

PHP, 395 bytes [cracked by nneonneo]

^( *)( *)( *)(['.-])((?!\4)(?4)+?)((?!\4|\5)(?4)++)\1\3whale
(?=.(.))\6.\7\4(?!\4|\6)([_\/])\3(?!(?11))\8\2(?=\2)\3\1_((?=\4+.).\5(?!\6)\5)(?!.?')\7\4
(?=.\7)\6.([,`])\3{2}(?=.((?!\8)[_\/])\11)\Q(_\E.\4{2}(?!\.)\5((?!\10)(?10)(?!\4+|\5|\6))\1\3{3}(\\)
(\3{3})\13\2{2}\1{1}\3+(?<=\S {10})\4\1\3\|
\1(?=\12)(?12)(?!`,)\10\4(\11{2})\4\14\10\15\9\8
\14{2}(?=\6)['-]\4(?<!-)\11\8\11\4\6\11\15\.-|(?!)

A better jigsaw than my last entry.

Note: The matching key is multiline, with each line separated by the new line character \n. Rebuild some ASCII art!

Here is a regex demo.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Match: 202e272d207768616c650a2d3a3a2e2f202f205f2e27273a2e0a2d3a2c2020285f5f2e2e27602020205c0a2020205c202020202020202020202e207c0a602c2e5f5f2e2020202c5f5f2e27272f0a2020202020202d2e5f2f5f2e2d5f5f5f2e2d (hex-encoded). Non-match: IDon'tThinkIGotTheRightPicture. Proof workspace: regex101.com/r/gF9pU0/1 \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 7:15
  • 1
    \$\begingroup\$ @nneonneo Wow! You solved it :D But the right picture is here: regex101.com/r/oM9rC4/1 \$\endgroup\$
    – Unihedron
    Oct 18, 2014 at 7:21
  • 1
    \$\begingroup\$ Yeah, I figured I didn't have enough spaces (but the regex didn't check too strongly). And, it seems I have interchanged .-' at the start to .'-. In hindsight the former is much more plausible for ASCII art ;) \$\endgroup\$
    – nneonneo
    Oct 18, 2014 at 7:22
4
+100
\$\begingroup\$

.NET flavor, 53,884 bytes [safe]

Generated by GnuPG! And extracted by pgpdump. It is 1536 bit because longer versions failed on the online tester.

xz base64:

/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4NJ7EPxdAC8KA+QKYhePb5XYF74CIWXzFZa9NcIQEk3v
/V2BJ4+pWDeuHyJglyhWD3Jp454EQmzShYGwtV0HYNg/uM7nyzGoXBbC//+zrYYUFKzVPHOpsGOG
dHt5rN7ffwyFyGP7scto6uWZ3Tlf+Udsikqx8XmtBTZxs+eKVsjWcBWYs+v27AW4AIesr2/aArhe
hagu80JX4+EYSYLfj6hqDPXA3XT9pUJLw+KESRPk+cOH0IrGx/PhNJxlv/Oq2FF3sCwq5GzIrhq2
FsOqyX4hE73pT4RI4sbY+hOveol93r3n1UZKX7/+gR3/EvS86lvgzZId0ktKQ4bZdPmlFVUB5aSM
xHPQ9KhkHAa1mxT3YhTs+CMased0tdTBeN+r/wzGzikIvCzYL0fb9YfdLt7kviJY4FC5PgS46UqY
IOpXcixcxHdznxoXf463nnUBl9p6bHyCBZSKzRLt9TcCGg2DuMBie2aX3lNFYu9ZthPjiingVtjr
MdGa+7WL/iBxs7LyPXq2srCyE1TVKDtIZE1bKmt0wLB2q5Z8z03f2GAq0uI7mljCBmqYrDGVQMo4
EZKZlHzwPHqul4tQ169+wLKH3e66qLGk6q3mcIUMAGtcgzepIfgOT2Lkr23CCY3+HzbYN8CejJts
9O0YQaqmzdXaohKPbM3ntOSvMCWvwU+qBYc5bhYZA6n78p2Otz/SExWaDDdMFydim9ldYzO9y/TA
v+ofbjeaKzSASTVkUPPGfE0/SbHt5D1fK5DPsg4jRKQPaPfGNcINPu9V9yLMytJjvVod/fQvgt/k
JH0wQpXaLXeF+ihAy+GY7jT89iqVmR0X2SDAiau2s0b6Pw5lIzr/3enHNGtsr2N/Ip+VOHkVa/dK
SsucSytif5eu3NekRDhk1xroZl7Ps8E8He9kRz2fcBiWRp6LgJEDGQih8CXJ9SG/aho3H0q5d2ol
eeL8oC/Jz3S6ZsIklv1KAWy2vtfvFDKj3Zey6f+qxWnNM14cWRPXnN+t5Yhrosnk2hBHIYNABhsz
XDZyGh64wxaNuklGXBwJHmWF7ScPkw9jEUj9W5FmcVI/TvSltQXvpo/+uIZUto97cf4n0RM/CPq4
NmBYN3qlAthRJoaE+HiCZ1S5DilrryjeOjHAqQFWGuq81vAybqQ54+zqyqygStWQdMW+3dH3aTw0
oBYrXibNvVaGvBxaotgu0R9RZHgjOgt2/tX+X6T0K/c5KpARmeOLOQO23TW8KdDRcEpu6/CuJyLa
OuDMJYwu2dSCIR3EnJfjzM4w8wxaP9+Qo48kjnZDc9tnOrJOSZ8vYYKLe74qClQ/n142YR4Su3FS
yrdeVxYxZOQzl5wokLW5E/hFiO8qN1hl86j9yjJRvvKSuOaFtbc3cOtWEtI7pwdkfs79RbbnZdDp
pPte8lUUpXmZI+4CRYKPlVjvAeATGZ3G3NpV9yxYaa7I9GAgKBJ65i//NvIxVuWTDclQVyeHlkOh
Q3VqMorYxnOuC/3QNulZvKehKBCutF7UOc4V7SVYfZstUMXDABo9hW4ScMrHggCGxVwkWRwqpMZh
aknsNx7Ert3HsA/8wuNgYXg8XIhsbufmBDbCAQEm+Y+djNNrmlUBuEqxoZer6aeamAkLVaU5Nig6
FxEG0h7xzFXNzLY8v+y7Lp2lMlvfBaRyaLRibayRMfqirUfYohh41Kq3Ix/VzZD0DzFkmpW5Tbgz
0MfbuKWXLqycOT8yN9GZoA57rA1rN31/BZpewJWp+KpwxBE6hlzt8Ip2rQZYoXF46/QytrKIP4bs
bG5ruobGbdwtU1GCF8HYNSZluxGWYoHc3WcutCuC9qDv8/PRyQfkj2MnSD/pNfwSzM3QTqrp8hSQ
/ps/XbJK/y9xhXwUPtq3m/GcJKq0kxvzesggpDsxme+LznlTIVFPBwXw+XpAlUT69t/Ix9ASfgK4
GN9OMadr8CevgS2Q3uRxrO/zPdVX7yWaQ32DMEz3syzWJYob1TjfPja6/9aoyRVFZ8fBOG1uRUtq
nFKcURRUPzfRAUzs4QBUMNeC28Oal8tCmUjzXsOldAy5eIRH+hKHCLfjRQ+T9KUu8H/aM48X9p8h
KatHXHB9/oXGAYeCOEWdqWrs6g+nzTmE4UtEjLZCLaDZQROuCj0lha0InL6w2o7bBquyyqY7MCkU
LnnxxsiM7uxNGz9vvM58X8DxSC08RjcH46tqQ5ZtY/WCOcc4y6j9U/htaRXXRf5TstyjxGnLKCLi
OZmmitPCqtHW/HV9TGBFp3LSimflwlHAHa7CpthY/dMbyqqi7owmX9pfe8DzupetNQ4gWHeM711l
j9h4v/wdFQLqum+fepAfPZSL5CYPpKMbNCfSfdy7IVKOC81ZMXuEPNj75Pf75d2sGFNg5fmDuJVh
+Rxx+DMiGoRSp7+QpdAEbq4uCd9jXKgKz0Dulgvq1pKVIsvkMONbdudvM7cALF0PuIzd7i2j2K1y
mHFjgeZimEnlLGylyBTZ41jNCXh/FARbiIHWr3EO34NtDTd/nUpkndJcepRxbYoqGe+161qt8ZQm
lTbi2lYDp9LUbkMjSme6aHLyRW9znkuOchYoL9ClgiulCuD2cv0wwYoUtrhiIGZ18zXpR5UQt+lF
1QqQ/UWkS9HRdn24I1/6RszJJlv50NGT3oeklC4HrNaPiY89jJlxrUaKhPmmLjWVkeBVp6D0EkWt
2XPxiS3eysh3sCMFaWq3j20fUn9zZRPWyNTxT0GCb5ZCDD7VzxGznBFWPTzHBYswARejls6ninc9
X7tXgvXtneHRwsCm1oH03netVf4SKnNzsjJE7iqExcuj2k+/LVkXxGFHp8+RaDM1akPzvHWvqRNH
I4P8xhPK8Q+wVU0ai363mAowUjeBlVq79dNbOhMnQXuJMa8/ZQEgb5HQKHMBaExe95Mq+WJHc4ZJ
vaNYcQFfQkHedLBs0PuiM4gmtDxc/ugdM7bIS7xKJJv2hznnT9Indc5nud/kJl1wIvlUE31w1oIk
XZcxb6KeGkeBboyW+rqkwqFMuw3Dt+JYjtrxRabUA25uHnesjxio060+zjeC9/Ta8x26/VrgVs6a
I1OcrdfzSFF9uhZnr2vL5dNPTsz7FEMi//ytsLjo2xsIgAaaXKSeBfpBKws33fNs0dv9Iu6HIUi1
+uRKfG/r7Lq2uv/PuR4USLNKhGLbusTHKHTHtA6T1G0p/C2e/v0lM5wBMcAsMNnXN707M/9Yjhvw
50dib7rAKBSB1lB6l1iOB4zhouE23VUSaRFDNPzNvyKKuqU2afAl3U7gfAK6ZkyrhTxsmeAOU/XP
6eXu32MWEv6Rn5e2YmBd/a1EHmtvEBMj90Vkc4sgwke7rTPCOyHeDPzBB6nXDylgacQVuRiM9G8+
EhVcslxi2YC9SPa7XwdB4hG16ncp0jQpyLPPYEC0wf5nUbPXt5kZBFYIpU73TgT9TlkoXrCBdAiT
UKu+8fjINi27u029RamL6XbzP5KkeSyq3Fw6Nv30PIPWqdFEVtiNEfXZxRE4xDUTnqAYaAjeple0
y6GptCsz1HPhNJSh5Bkp5ju/aQ5uXPu0j1f2/zyWEDl3qHLZAn3E6L8gfg5RzB11sQiWDwZ1/SeN
iUOiTzsQQ1ouS7E0jS5/R7hzkibVaT7x4M+4RebR+1MMR9JfJHbt4PY9quzovNrkYZl4vgT31sJe
OgwefQ/JODDqStBZ/dz0gVx3CbfuyyOm6hBKSLMeVIP51X+TXZ/BKrWWhT08Wnu2GpusZlzxgyoz
wOcB1Pwpk8DDhHmdF3gceSfztrUDvPTHI4GTKNTrYUzmLVKPxn1zX5KVOZBcCCSeU/WuqpHbHEx5
4r+NhkXbFyp8woArlCwGlrFjCr+qpjm9nzi1jb33jEQ7S3y8L5RGdjVOrt3TpjLYZ4I0+G9onA7j
1SwVyusfcQfU5MnU3vPkNX607o4LWSWm9OOcjps10fjRfOhv3gXnF+aDGlujadzsZ7nRIWRea+HJ
UNcZotq/i4ShvUTFGqHacMc3DKz5wCiRxrMx/H6XMhe8rgWg6SkbsNmgGd/a7xrEOEtICG3syXl+
nO575qwzCB230JXAlhhxENyjH5b98ntA1vn6RpQ8PZaLS9QQN7gLwoMlM3SnRUaoC4yuIX+2MSpI
M0OmvOvJB4on61eF9mA+wsFCSEC6iPxM4MOqI/EaTgP7tj/AKzK/42DQpJh67RQWI0dyHYvtfoho
OJsOynYZt6MmKo23W8766DcozcO3XNhp/uBwIZenancULl3U3FimVSzXPZsdpMIRalcS2W99VWzN
ipZ8JCoV96CS1zUaLEuirON+SaDg6G7NHBOmsAMHXSThD0lGKDw8VPfr9ROCKlbRUGPluE/vmjQs
WDdk3GOZyn1Iwu0bAdn+qA/GR+3AXr1nfQ8t1cWhYWE1A8cu8OLCNpthq35uF+D0uk+0pEh7vDXB
L9GMtWs2VZWgH/AH2pagqCvbkMDmPIMEyF1vjhFyS4WQgt4vNcPmxF891G/v4O/e6RMGAUaPR8UI
y7/Eh43+/tgUrHM8sCeydcJiIXpymJqhSah+KxPtLfFb6o9UCkaYwiM5jSsi7BBNVGaHa75Qyrpk
A+qIiYinwCN6GcRxNLxdVdybZU6Qt5PA7U1CGrYyUJt3t4T/2IwmAwKyiEiK/M+D9GQ1VbBKh2NO
oegZv7HWcYNSczDAc7jXw2MO5tKEiuxNaxeTE/iydemtsaOPRyu5oJQB06NJzn/qMJKQFigOqrnj
obnG/rbz2fyBp5tg6d5VBr7YahoeB1ghHolhklUkyrcg7S7Rd8KqugjFYObjcCTviOU3zMfjzqg1
PZvIr4cz2DFeuW3BfTXwC8aEagkfRTZROhUPA0RbKk5PFucQzQN1PVSaNKrtcl8k924sOVQcqltn
bEjJf7DlMM/LHIMNRAChZ3TeL/4dBXEqsaKYi8pwVk+RLbcw48JeQnVkIs78XJp+0yW2nOHrOGv8
71ajAHjTqL+Yg+hBVUYBAVbyr9lQns3ikio3Jp+8plBx6liSpjYlVadRIOG4guZzNcSRxyt2xH4n
x5czlFKTng2cSfSoiUXmS28dDaM6GfXl3XbYTsWkseLjWDK0pKyaRXSaIBIPWZgsh4SUusUlt8zk
iPAwhMsyLzPuQMwueBMaXUDfpx+72rJ5wjLdLWO5fC19upMav+kbLmUf7x0jwKoVFdfL4eVloZnX
L10jVpm8gvELEYV5N5WkSMmioOWgSlHSytHsEuu+05+v7zxRwY3G7kaJoFPiJqavj4bsVWNQQLm6
hmeBkE2JO0Nbq4yL42mHsLnOFz49efovrHDydKcyMdEDFqPDiyzBeFx5IsgRG2egf/NEnD/W/IMv
9xb/Pdsu5dBF+sd+MJDB5WoQza8oGzcLjrkFXb1RTIG18I/R+P6UPyGX9j7ndGaUzmCm/9SAByyC
7/bAmWuKc0ylQd58T2GxRGYIF35sPRXIfj5ceQmGvnI7VmZVuEt51vYT6/sNycVDUAKOL2dZMhEe
2sMYCiPt5fFM+yGlM2TxNzIfWoTDvlorYmM2tevt6P+kUjH32hcTIfmNbEwFKVpHhXmOstTOCtxt
bP2EODaqDZaKl/1hXZE4pC8B4jOZRotLx5kzUvYc3rTzsqznYR4ViPJtNrU+EonIWSuGn7uw7yvz
zcKbjoOMHIw/W/9+E7i4eOHnUM4iFIPIu2ih6V2VZKwFeLX5boAkpKMlkHzMfZix9k29MfkM5jtG
AGbXWqTjhbXWtAAwGVQkUTcirlG5KPxMeTp4qWqcJ3NKzSCVog60pu1xSYUWI5EA4J98tjg7DOQA
AZgi/KQDAPczjbCxxGf7AgAAAAAEWVo=

Tested on RegExLib (with no options selected). I hope I didn't cause too much trouble to them.

You probably want to crack the easy version first. It is the same as this one, except for having a much shorter key.

You probably also want this number:

1877387013349538768090205114842510626651131723107399383794998450806739516994144298310401108806926034240658300213548103711527384569076779151468208082508190882390076337427064709559437854062111632001332811449146722382069400055588711790985185172254011431483115758796920145490044311800185920322455262251745973830227470485279892907738203417793535991544580378895041359393212505410554875960037474608732567216291143821804979045946285675144158233812053215704503132829164251

The key

Match:

Ëòčĵċsïݲ¤ėGâĥÓŧÿÃiTüū&0EĚĵŒR@bĵ¤¿Ĉ=ķüÙļÞďYaŃīŲĢŪÕďųïyĘŊŢĝĪĘŠćĢmtŠîĽþĽłŶāĨĩģTő!ĺw=aŧïųţĨíœą¸Ëč!,ĵţ¨ŌąŜ7ć<ůū¹"VCæ>õêqKËĖ¡ôÕÂúëdčÜÇĺřGĝ¢ÈòTdĩŤŭi§aćŎŭųä«´3ĚΦîŇĬÒÕ¥ńü½å±ì³Jõ«D>ìYũʼn5öķ@ŪĠďàÂIĭųė!

Non-match:

1111111111111111

The prime numbers:

1332079940234179614521970444786413763737753518438170921866494487346327879385305027126769158207767221820861337268140670862294914465261588406119592761408774455338383491427898155074772832852850476306153369461364785463871635843192956321
1409365126404871907363160248446313781336249368768980464167188493095028723639124224991540391841197901143131758645183823514744033123070116823118973220350307542767897614254042472660258176592286316247065295064507580468562028846326382331

Explanation is in the easy version.

The generator script (in CJam)

'~),'!i>"+.()?*\\[]{|}^$/,^-:#"-
'ǝ,'¡i>173c-+289<:T;

95:F;
95:G;

"
^
(?=["T",]{"FG+)`"}$)
(?=.{"F`"},)
(?!.*,.*,)
(?:
    (?(X)
        (?<-X>)
        (?(L)(?<-L>)(?<l>)|){16}
    |
        (?:
            "
            [T289,]z
            {[~17md["(?<l>){"\'}]["(?<L>){"@'}]]}%'|*
            "
        )
        (?<X>)
    )
    (?=.*,
        (?:
            (?(Y)
                (?<-Y>)
                (?(R)(?<-R>)(?<r>)|){16}
            |
                (?:
                    "
                    [T289,]z
                    {[~17md["(?<r>){"\'}]["(?<R>){"@'}]]}%'|*
                    "
                )
                (?<Y>)
            )

            (?(l)
                (?<-l>)(?<x>)
                (?(r)(?<-r>)(?<y>)(?<v>)|){16}
                (?(y)(?<-y>)(?<r>)|){16}
            |){16}
            (?(x)(?<-x>)(?<l>)|){16}

            (?(p)(?<-p>)(?<s>)(?<z>)|){"F2*(`"}
            (?(z)(?<-z>)(?<p>)|){"F2*(`"}
            (?(q)(?<-q>)(?<s>)(?<z>)|){"G2*(`"}
            (?(z)(?<-z>)(?<q>)|){"G2*(`"}
            "
            "
            (?(s)
                (?<-s>)
            "FG+(2**
            "
                (?(v)(?<-v>)(?<a"FG+(2*`">)|){256}
            "
            ["
            |
                (?(v)(?<-v>)(?<a"">)|){256}
            )
            "]aFG+(2*,W%m*{~\~@`\}/
            "
            (?(r)(?<-r>)|){16}
            (?<q>)
        ){"G2*`"}
        (?<-q>){"G2*`"}
    )
    (?(l)(?<-l>)|){16}
    (?<p>)
){"F2*`"},

"
[
l~17bW%_,FG+2*\- 0a*+
FG+2*,
]z
{
~:A`:B;:C;
"
(?<-a"B">){"C`"}
(?(a"B")(?<-a"B">){17}(?<a"A)`">)|){4100}
(?(a"B")(?!)|)"
}/

]:+N9c+S+-

Input should be the above number.

After you are done, the solution can be generated by this program:

'~),'!i>"+.()?*\\[]{|}^$/,^-:#"-
'ǝ,'¡i>173c-+289<:T;

95:F;
95:G;

{
r~289bW%_,FG:F;\- 0a*+
{T=}%
}2*',\

Input should be two integers.

\$\endgroup\$
4
  • \$\begingroup\$ Too bad. RegExLib is down. I think people should better use a Silverlight or local tester. But I can't test them. \$\endgroup\$
    – jimmy23013
    Oct 18, 2014 at 11:59
  • \$\begingroup\$ IIRc, RegexHero is a .NET tester in browser, using Silverlight. \$\endgroup\$ Oct 18, 2014 at 15:13
  • \$\begingroup\$ Another idea about big integers is to calculate the product mod prime numbers near 200. It should be faster. But the code would be much longer and I'm not going to do that in integer factorization answers. \$\endgroup\$
    – jimmy23013
    Oct 18, 2014 at 20:50
  • \$\begingroup\$ Congratulations on making it through the 72 hours! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked. \$\endgroup\$ Oct 24, 2014 at 16:10
3
\$\begingroup\$

Perl flavor, 97 [cracked]

I'm afraid this is going to be too easy due to the key length limit.

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

If you think you figured the idea behind it, try the longer version (not part of the challenge):

^((?:[^,]{3})+),(?!\1)([^,]+),(?!\1|\2,)([^,]+),(?!\1|(?:\2|\3),)([^,]+),(?!\1|(?:\2|\3|\4),)([^,]+),(?!\1|(?:\2|\3|\4|\5),)([^,]+),(?!\1|(?:\2|\3|\4|\5|\6),)([^,]+),(?!\1|(?:\2|\3|\4|\5|\6|\7),)([^,]+),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Match: aaaaaaa,a,aa,aaa,aaaaaaa. Non-match: aaaabaaacaaadaaa. \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 6:54
  • \$\begingroup\$ Longer version: Match: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,a,aa,(remove these chars)aaaa,aaaaaaa,aaaaaaaa,aaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaa,(remove these chars)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. Non-match: aaaabaaacaaadaaa \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 6:57
  • \$\begingroup\$ @user23013: The short version is correct! I meant for the capture groups to be at least two characters long, which would have made the key a little bit longer, but I forgot to change it :P The longer version is incorrect, though. \$\endgroup\$
    – Ell
    Oct 15, 2014 at 7:03
  • \$\begingroup\$ This site added some invisible special characters when I posted them. I think it is fixed now. (Without the (remove these characters).) \$\endgroup\$
    – jimmy23013
    Oct 15, 2014 at 7:08
  • \$\begingroup\$ @user23013 Yeah, that's a match. I really didn't plan for it to be that easy :P \$\endgroup\$
    – Ell
    Oct 15, 2014 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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