11
\$\begingroup\$

Background

Character classes are a standard way to indicate a set of characters to match in regular expressions. For example, the class [ab] matches a or b, [a-z] matches any lower case letter, and [^a] matches everything but a. For the purpose of this question, classes can contain:

  • a sequence of characters to match, where the characters \, ], - and ^ must normally be escaped with a \.
  • a range of characters to match, indicated by separating two characters with a -: e.g. [0-9]. Note that if - is the first or last character in a class then it need not be escaped, as it's not indicating a range.
  • a combination of sequences and ranges: e.g. [ac-fhk-o]. Note that the class cannot be empty, and if ] is the first character in the class then it need not be escaped.
  • a complement match indicated by the first character in the class being ^: e.g. [^a-z]. Note that if ^ is not the first character in the class, then it need not be escaped.

Task

Given a non-empty string made up of printable ASCII characters (" " to "~" = 0x20-0x7E), output the shortest character class that matches precisely those characters. The string may contain duplicate characters. Default Input/Output methods apply.

Scoring

This is , so shortest code in bytes wins, with all the standard loopholes forbidden.

Test cases

"the"     => "[the]" or "[eht]" etc
"faced"   => "[ac-f]" or "[c-fa]"
"0-121"   => "[-0-2]" or "[012-]" etc
"]"       => "[]]"
"[-^]"    => "[][^-]" or "[]^[-]"
"[\]"     => "[[-\]]" or "[]\\[]" or "[][\\]"
\$\endgroup\$
13
  • \$\begingroup\$ Can we take input as a list of character codepoints? \$\endgroup\$
    – pxeger
    Feb 18, 2021 at 16:02
  • 3
    \$\begingroup\$ Also, I think requiring printing to STDOUT, and disallowing (for example) returning from a function, is too restrictive. I'd suggest using the IO defaults \$\endgroup\$
    – pxeger
    Feb 18, 2021 at 16:02
  • \$\begingroup\$ Yes, I copied and pasted that bit from a previous question. There's no reason not to use defaults, so I'll update it. \$\endgroup\$
    – Uri Granta
    Feb 18, 2021 at 16:07
  • \$\begingroup\$ Re taking a list of character codepoints, that's less obvious to me (unless there's another default rule I'm missing). After all, there are many ways to indicate multiple characters and we don't want to have to list them all: strings seem to be the simplest here. \$\endgroup\$
    – Uri Granta
    Feb 18, 2021 at 16:12
  • 4
    \$\begingroup\$ That's right. A challenge entry is only valid if it always returns the shortest class possible. \$\endgroup\$
    – Uri Granta
    Feb 18, 2021 at 17:05

1 Answer 1

6
\$\begingroup\$

No answers after a few days, so thought I'd have a go. Found it trickier than expected, so the answer's pretty long, but I'm reasonably confident it works. Should be able to trim it a fair bit more.

Python 3.8, 431 405 410 bytes

import re,itertools as I
B,M,C,P="\-]^"
s=sorted;x=s({*input()})
d=[ord(x)-i for i,x in enumerate(x)];l=[];i=0
for _,g in I.groupby(d):n=len([*g]);l+=[[x[i]+M+x[i+n-1]],x[i:i+n]][n<4];i+=n
o="".join(s(l,key=lambda i:2*(M in i[::2])+(P in i)-3*(i[0]==M<C not in x)-2*(C in i)))
print("["+re.sub(".",lambda m:B*((x:=m.group())==B or x==P==o[0]or x==M<M*2==o[(i:=m.start()):i+2]in o[1:-1]or x==C in o[1:])+x,o)+C)

Try it online!

Explanation

The overall approach is to:

  1. Split the letters into ranges of length at least 4 and individual characters. Note that ranges of length 3 are never necessary (eg. "[abc]" is the same length as "[a-c]" and "[]\\[]" is the same length "[[-\]]") and are sometimes worse (e.g. "]-./" is shorter as "[]./-]" than as "[]\--/]" or "[--/\]]").

  2. Sort the letters and ranges, so "]" goes first, otherwise "-" goes first, otherwise "-" goes last, and with "^" as late as posssible. There is no conflict between putting "]" first and "-" last since "]--" is not a valid range.

  3. Escape as necessary: \ always, ] unless it's first, ^ if it's first, and - if it's in the middle (which will only happen if it's the beginning of a range).

Extra test cases

"-^"      => "[-^]"
"-4]"     => "[]4-]"
"abcde^"  => "[a-e^]"
"XYZ[\\]" => "[X-\]]"
"-./0]"   => "[]\--0]"
"+*,-^"   => "[\^*--]"
"^_`a"    => "[\^-a]"
\$\endgroup\$
2
  • 2
    \$\begingroup\$ A few tips: Creating variables for most single-character string like B,M,C,P="\-]^" saves a few bytes, {*input} is shorter than set(input()) and you can append to a list by extending with a singleton list (line 4), and list.extend(v) is the same as l+=v. \$\endgroup\$
    – ovs
    Feb 20, 2021 at 14:12
  • 1
    \$\begingroup\$ Try it online! \$\endgroup\$
    – ovs
    Feb 20, 2021 at 14:12

Your Answer

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

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