Cops and Robbers: Reverse Regex Golf

Question

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

The Cops' Challenge

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

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

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

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

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

The Robbers' Challenge

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

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

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

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

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

Do not crack your own submission!

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

Scoring

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

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

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

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

Leaderboards

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

Cops:

Submissions in italics are not yet safe.

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

Robbers:

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

Answer 1

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.

Answer 2

.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 997⁷. 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 997⁷/2 hash evaluations.

Answer 3

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.

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.

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

Answer 4

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

Answer 5

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ĂÕÿŇ

Answer 6

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.

Answer 7

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

Answer 8

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. ;)

Answer 9

.NET flavor, 60 bytes [cracked]

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

Tested with Regex Storm.

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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}
)$

Answer 14

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.

Answer 15

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.

Answer 16

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!

Answer 17

.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. :)

Answer 18

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.

Answer 19

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" ;)

Answer 20

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.

Answer 21

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

Answer 22

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.

Answer 23

Ruby-flavored, 24 bytes [cracked]

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

Answer 24

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.

Answer 25

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.

Answer 26

.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).

Answer 27

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

Answer 28

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.

Answer 29

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

Answer 30

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