15
\$\begingroup\$

Your challenge is to create a regex that matches every string permutation of itself, and nothing else. The match must also be case-sensitive.

So, for example, if your regex is:

ABC

It should match (and only match) these strings:

ABC
ACB
BAC
BCA
CAB
CBA

It shouldn't match things like:

AABC (contains an extra A)
ABCD (contains an extra D)
AC   (no B)
AAA  (no B and C, extra 2 A's)
abc  (case-sensitive)

Rules:

  • You are allowed to use any flavour of regex you like.
  • Standard loopholes apply.
  • You must have at least two different characters in your code. That means solutions like 1 are invalid.
  • The regex should contain only printable ASCII, and nothing else.
\$\endgroup\$
11
\$\begingroup\$

JavaScript, 64 57 bytes

4 bytes removed thanks to Martin Ender.

^(?!.*([^])(.*\1){3}]?)[$$[-^?!!.'''-*11{33}5577\\-]{57}$

Try it here.

Explanations (outdated)

^                                  # Beginning of the string.
(?!.*                              # Match only the strings that don't contain...
  (.)(.*\1){4}                     #     5 occurrences of the same character.
  [^1]?[^1]?                       #     Something that doesn't matter.
)
[]zzz^(?!!!.**[)\\1{{44}}666]{64}  # 64 occurrences of these 16 characters.
                                   # Some are duplicated to make sure the regex
                                   # contains 4 occurrences of each character.
\z                                 # End of the string.
\$\endgroup\$
  • 2
    \$\begingroup\$ I think this works for 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101 \$\endgroup\$ – Martin Ender Nov 22 '16 at 8:13
  • \$\begingroup\$ This almost works in .NET: ^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]* \$\endgroup\$ – jimmy23013 Nov 23 '16 at 9:40
  • \$\begingroup\$ What doesn't work? Trailing linefeeds? \$\endgroup\$ – Martin Ender Nov 23 '16 at 9:55
  • \$\begingroup\$ @MartinEnder Yes. \$\endgroup\$ – jimmy23013 Nov 23 '16 at 10:13
2
\$\begingroup\$

Perl and PCRE regex, 280 bytes

^(?=(.*z){2})(?=(.*\(){43})(?=(.*\)){43})(?=(.*\*){22})(?=(.*\.){23})(?=(.*0){2})(?=(.*1){6})(?=(.*2){16})(?=(.*3){7})(?=(.*4){4})(?=(.*5){1})(?=(.*6){3})(?=(.*7){2})(?=(.*8){2})(?=(.*9){1})(?=(.*=){22})(?=(.*\?){22})(?=(.*\\){11})(?=(.*\^){2})(?=(.*\{){23})(?=(.*\}){23}).{280}\z

(Slightly) more readable:

^
(?=(.*z){2})
(?=(.*\(){43})
(?=(.*\)){43})
(?=(.*\*){22})
(?=(.*\.){23})
(?=(.*0){2})
(?=(.*1){6})
(?=(.*2){16})
(?=(.*3){7})
(?=(.*4){4})
(?=(.*5){1})
(?=(.*6){3})
(?=(.*7){2})
(?=(.*8){2})
(?=(.*9){1})
(?=(.*=){22})
(?=(.*\?){22})
(?=(.*\\){11})
(?=(.*\^){2})
(?=(.*\{){23})
(?=(.*\}){23})
.{280}\z

This runs in O(2^n) time as written, so is incredibly inefficient. The easiest way to test it is to replace every occurrence of .* with .*?, which causes the case where it matches to be checked first (meaning that it matches in linear time, but still takes exponential time if it fails to match).

The basic idea is that we enforce the length of the regex to equal 280, and use lookahead assertions to force each character in the regex to appear at least a certain number of times, e.g. (?=(.*z){2}) forces the z character to appear at least twice. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23 is 280, so we can't have any "extra" occurrences of any characters.

This is a programming example of an autogram, a sentence that describes itself by listing the number of each character it contains (and, in this case, also the total length). I got fairly lucky in constructing it (normally you have to use brute force but I stumbled across this solution while testing my brute-force program before I'd fully finished writing it).

Perl and PCRE regex, 253 bytes, in collaboration with Martin Ender

I hypothesized that there might be shorter solutions which omit some digits (most likely 9, 8, or 7). Martin Ender found one, shown below:

^(?=(.*z){2})(?=(.*\(){39})(?=(.*\)){39})(?=(.*\*){20})(?=(.*\.){21})(?=(.*0){4})(?=(.*1){6})(?=(.*2){11})(?=(.*3){6})(?=(.*4){3})(?=(.*5){2})(?=(.*6){3})(?=(.*9){4})(?=(.*=){20})(?=(.*\?){20})(?=(.*\\){9})(?=(.*\^){2})(?=(.*{){21})(?=(.*}){21}).{253}\z

Readable version:

^
(?=(.*z){2})
(?=(.*\(){39})
(?=(.*\)){39})
(?=(.*\*){20})
(?=(.*\.){21})
(?=(.*0){4})
(?=(.*1){6})
(?=(.*2){11})
(?=(.*3){6})
(?=(.*4){3})
(?=(.*5){2})
(?=(.*6){3})
(?=(.*9){4})
(?=(.*=){20})
(?=(.*\?){20})
(?=(.*\\){9})
(?=(.*\^){2})
(?=(.*{){21})
(?=(.*}){21})
.{253}\z
\$\endgroup\$
  • \$\begingroup\$ I don't think you need to escape those {} in the last two lookaheads. You also don't need to add things like (?=(.*5){1}) since there wouldn't be a 5 if you didn't have that lookahead. One problem is that $ allows a trailing linefeed, so you'll need to use \z there instead of $ like jimmy did, but that won't cost you a byte I think since you save the \ in the first lookahead. \$\endgroup\$ – Martin Ender Nov 22 '16 at 8:52
  • \$\begingroup\$ I'm aware that it's possible to omit things like digits. However, they're there to make the autogram work. Removing any part of the program will cause all the rest to break, because it no longer describes the program correctly. (The counts for each line count the counts for each line! Thus it is in general basically impossible to change the program.) As for $ allowing a newline at the end of the string, that generally depends on how the regex is called by the surrounding program (they're normally run on code that's already been parsed into lines). \$\endgroup\$ – user62131 Nov 22 '16 at 8:58
  • \$\begingroup\$ Or to be more precise: I do need the (?=(.*5){1}) in this case. If I removed it, there would be a 5 in the program, because the (?=(.*1){6}) line would now have to read (?=(.*1){5}). \$\endgroup\$ – user62131 Nov 22 '16 at 9:00
  • \$\begingroup\$ As for the trailing linefeed there doesn't seem to be any restriction in the challenge on the kind of input to your regex, so that usually means it should work for any string whatsoever, and changing $ to \z doesn't do any harm (and doesn't break the autogram). \$\endgroup\$ – Martin Ender Nov 22 '16 at 9:10
  • \$\begingroup\$ Oh, I see; you change the \$$ to z\z. That works; I'll go change it. \$\endgroup\$ – user62131 Nov 22 '16 at 9:13

Your Answer

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

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