17
\$\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\$
3

3 Answers 3

14
\$\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\$
4
  • 2
    \$\begingroup\$ I think this works for 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101 \$\endgroup\$ Commented Nov 22, 2016 at 8:13
  • \$\begingroup\$ This almost works in .NET: ^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]* \$\endgroup\$
    – jimmy23013
    Commented Nov 23, 2016 at 9:40
  • \$\begingroup\$ What doesn't work? Trailing linefeeds? \$\endgroup\$ Commented Nov 23, 2016 at 9:55
  • \$\begingroup\$ @MartinEnder Yes. \$\endgroup\$
    – jimmy23013
    Commented Nov 23, 2016 at 10:13
6
\$\begingroup\$

JavaScript, 50 bytes

^(?!([^])+.*\1.*\1)[?!ZZ-__==''-22+,,//{50}$]{50}$

Try it on regex101

The key to beating jimmy23013's solution was to reduce the number of repetitions of each character from 3 to 2.

Explanation

^(?!([^])+.*\1.*\1) - assert that no character in the string is repeated at least 3 times

([^])+ is equivalent to .*([^]).

[^] works because JavaScript allows empty character classes (unlike most other regex engines, at least by default). It is equivalent to [\W\w] or . with the /s flag, i.e. it matches any character including newlines. For our purposes here, newlines don't matter, so it's equivalent to ..

Using ^(?!([^])+.*\1.*\1) instead of (?!.*([^])(.*\1){2}) or ^(?!(.)+.*\1.*\1) eliminates the need for a third (, ), or ., and this is the key to reducing the number of repetitions of every character from 3 to 2.

^...[?!ZZ-__==''-22+,,//{50}$]{50}$ - assert that the entire string consists of the 25 characters ? ! Z [ \ ] ^ _ = ' ( ) * + , - . / 0 1 2 { 5 } $ and is 50 characters in length. Combined with the first assertion this guarantees that every character occurs exactly twice (due to the generalized pigeonhole principle, if any character occurred only once, some other character would have to occur three times).

Z-_ is the range Z[\]^_. It's essential, because we already used [, \, ], and ^ twice each. We need to double the Z and _, because they aren't used elsewhere.

'-2 is the range '()*+,-./012. It's essential, because we already used (, ), *, ., and 1 twice each. We need to double the ', ,, /, and 2, because they aren't used elsewhere.

There is no other way besides ranges to include the above in our character class, because octal or hexadecimal escape codes would require using \, and a negative character class would require using ^.

== is extra padding to get us to 50 characters. It could be any arbitrary doubled character. We need it because if we went for {48}, we'd need to include two 0 somewhere, which would bring our 48 back up to 50.

Note that this can be trivially rearranged to include the delimiters:

/^(?!([^])+.*\1.*\1)[?!ZZ-__==''-22+,,{50}$]{50}$/

Try it on regex101

Perl / PCRE, 57 bytes

I'm pretty sure it's impossible to do 2 repetitions in Perl/PCRE, because [^] is not available (except with the PCRE2_ALLOW_EMPTY_CLASS flag), and the only other alternatives use \ – for example \C, \N, \X, \S, and [^\0]. So, with 3 repetitions:

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

Try it on regex101

This is very similar to jimmy23013's JavaScript solution. It doesn't work under JavaScript however, because ^(?!(.)*(.*\1){3}) can always match on any string; it would capture an unset \1 by doing zero repetitions on (.)*, and then \1 would match an empty string 3 times.

Making it portable to both JavaScript and Perl/PCRE by using (.)+ instead of (.)* would end up making it 60 bytes, due to adding the + character.

Alternatively:

((.)+(.*\2){3})?+^[[[-\]\]^^??+'''-**.22{335577}$$-]{57}$

Try it on regex101

This uses the possessive quantifier ?+ to atomically try to match a character repeated 4 times. If such a match is not found, it will be forced to do zero repeats (instead of one) and the ^ will match. Otherwise it will match something non-empty, and the ^ won't match.

\$\endgroup\$
3
\$\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\$
9
  • \$\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\$ Commented Nov 22, 2016 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
    Commented Nov 22, 2016 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
    Commented Nov 22, 2016 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\$ Commented Nov 22, 2016 at 9:10
  • \$\begingroup\$ Oh, I see; you change the \$$ to z\z. That works; I'll go change it. \$\endgroup\$
    – user62131
    Commented Nov 22, 2016 at 9:13

Your Answer

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

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