6
\$\begingroup\$

Problem: given any input string that does not contain null bytes, determine whether or not the input string matches glob as defined below:

null   is disallowed in both string in glob
*      matches zero or more characters
**     is disallowed in glob
?      matches exactly 1 character
[ch]   matches a character class of the specified characters
       to include ] in a class, it must be the first character
[^ch]  matches a character class of all but specified characters
       to include ] in a class, it must be the first character after ^

The empty glob only matches the empty string.

The system glob() on the target platform implements glob where * doesn't match a /, so you can't use it. This has infested all shells. You could try converting to a regex; however this won't be as easy it it looks.

You must specify an encoding for your program. Your program must be valid in that encoding. All bytes including null are allowed in cp437. Your score is the number of characters in your encoding.

Bonus: If your program is expressed in a well-known encoding that uses 6 or fewer bits, your score is multiplied by the number of bits used in the encoding and divided by 7. Your program will be passed its arguments in ASCII in that case.

Your program will receive the string to match or not as the first argument and the glob pattern as the second argument. Your return code must be 0 on match and nonzero on nonmatch.

You may leave it undefined what happens if you get passed a disallowed glob.

Standard loopholes are disallowed; however the following are allowed:

 You may compress your program but it must work if executed directly.
 Binaries are allowed. Submit a disassembly with it so I can read it.
 Using two different chars which look the same is allowed.
 You may use trigraphs (but I can't see how it helps).

Examples:

"w*c*d" matches "wildcard" but doesn't match "wildcards"
"ww*w*d" matches "wwwdwd" but doesn't match "wwd"
"ww*[w-c]?*" matches "www-" and "wwcc" but doesn't match "wwc"
"[a-c]" matches "-" but doesn't match "b"
"^[*][^]]" matches "^*[" but doesn't match "^?[" or "^*]" or "**]"
\$\endgroup\$
  • \$\begingroup\$ Are unmatched brackets like ab[cd or a]b allowed in the pattern? Can a character class have duplicate chars? \$\endgroup\$ – feersum Sep 30 '15 at 7:38
  • \$\begingroup\$ All right, removed the null bytes rule as it was pretty useless. The special case of CP437 is to allow binary files to be submitted. (It is questionable whether CP437 allows nulls or not but all non-nulls are valid anyway.) \$\endgroup\$ – Joshua Sep 30 '15 at 15:08
  • \$\begingroup\$ Yes, [a-c] matching a, -, and c is intentional. This is why converting to regex is hard. \$\endgroup\$ – Joshua Sep 30 '15 at 15:09
  • \$\begingroup\$ @feersum: ab[cd isn't valid but a]b is. You won't see duplicate characters in a pattern so don't worry about it. \$\endgroup\$ – Joshua Sep 30 '15 at 17:42
  • \$\begingroup\$ I assume, though it is not specified, that [^] matches ^ and [^]] matches anything but ]. I'm a bit confused, though: Couldn't [^]] also match ^]? I guess my question is - How does one specify a character class of just ^? \$\endgroup\$ – Not that Charles Sep 30 '15 at 19:15
4
\$\begingroup\$

Common Lisp, 368 340

Encoding is implementation-dependent, but UTF-8 is generally supported among implementations (see also the set of standard characters that must be supported).

(ql:quickload'cl-ppcre)(lambda(s g)(ppcre:scan(do(e(L(coerce g'list))c p)((not L)`(:sequence,@(reverse e):end-anchor))(push(case(setf c(pop L))(#\*'(:regex".*"))(#\? :everything)(#\[(prog1`(,(or(and(char=(car L)#\^)(pop L):inverted-char-class):char-class),@(subseq L 0(setf p(position #\] L :start 1))))(setf L(nthcdr(1+ p)L))))(t c))e))s))

Pretty-printed

(lambda (s g)
  (cl-ppcre:scan
   (do (e
        (l (coerce g 'list))
        c
        p)
       ((not l) `(:sequence ,@(reverse e) :end-anchor))
     (push
      (case (setf c (pop l))
        (#\* '(regex".*")
        (#\? :everything)
        (#\[
         (prog1
             `(,(if (char= (car l) #\^)
                    (prog1 :inverted-char-class (pop l))
                    :char-class)
               ,@(subseq l 0 (setf p (position #\] l :start 1))))
           (setf l (nthcdr (1+ p) l))))
        (t c))
      e))
   s))

Converting to regex is not so hard when using non-string representations of regexes. CL-PPCRE is a regular expression library by Edi Weitz which accepts two ways of defining such expressions:

  • the usual string-based syntax, or
  • a more lispy approach using a DSL

Today I answered a question about alternative syntaxes for regular expressions, and this challenge is a good example of why a structured format can be useful instead of strings.

Example

For the following glob, "ww*[w-c]?*", the regular expression being built is described by this form:

(:sequence #\w
           #\w
           (:regex ".*")
           (:char-class #\w #\- #\c)
           :everything
           (:regex ".*"))

And we match "www-". The (:char-class ...) list takes indiviudal charaters, which does not need escaping like it would if I wrote "[w-c]" as a string regex.

Test suite

(loop for (glob match no-match) in
      '(("w*c*d"      ("wildcard")    ("wildcards"))
        ("ww*w*d"     ("wwwdwd")      ("wwd"))
        ("ww*[w-c]?*" ("www-" "wwcc") ("wwc"))
        ("[a-c]"      ("-")           ("b"))
        ("^[*][^]]"   ("^*[")         ("^?[" "^*]" "**]"))
        ("w*\\*s"     ("wild\\ness")  ()))

      for matchp = (lambda(s)(funcall *fun* s glob))

      always (every matchp match)
      never (some matchp no-match))

=> T
\$\endgroup\$
3
\$\begingroup\$

MUMPS, 397 387 bytes

Note that this code uses features of Caché ObjectScript (specifically, the * designator in a $EXTRACT call) and does not conform to the ANSI MUMPS standard.

f(g,s) f i=1:1:$L(g) d
    . s c=$E(g,i) i 'm s:"*?[]"'[c p=p_"1"""_c_"""" s:c="*" p=p_".E" s:c="?" p=p_"1E"
    . i c="]" s p=p_"1"_$E(b,1,*-1)_")" s m=0
    . s:c="[" a=$E(g,i+1)="^",m=a+1,b="(",i=i+a
    . i m s:$E(g,i+1)="]" d=1 s k=$F(g,"]",i+d)-2+d,r=$E(g,i+1,k),i=k
    . f j=1:1:$L(r) s:m=1 b=b_"1"""_$E(r,j)_""","
    . i m=2 f j=0:1:127 s:r'[$C(j) b=b_"1"""_$S(j=34:"""""",1:$C(j))_""","
    q s?@p

Haha, OP! I've foiled your plans! Sure, your glob syntax might be tricky to convert to a regex, but my language has no regexes! Instead, it has a crippled form of "pattern matching" (see docs, section 5.7) that happens to be pretty much exactly powerful enough to handle these globs.

Basically, what the code does is it converts OP-style globs into a string corresponding to the pattern match, and then evals that string, and tests the input string against the result of that eval. The one tricky point is that MUMPS pattern matches don't have a notion of an inverted character class ([^abc]), so we instead have to construct a character class consisting of all the ASCII characters except the ones specified in in the inverted character class.

Here are some correspondences between OP-style globs and MUMPS pattern matches:

OP              MUMPS
-----------------------------------------------------------
w*c*d           1"w".E1"c".E1"d"
ww*w*d          1"w"1"w".E1"w".E1"d"
ww*[w-c]?*      1"w"1"w".E1(1"w",1"-",1"c")1E.E
[a-c]           1(1"a",1"-",1"c")
^[*][^]]        [doesn't print well, because of the inverted character class thing]

There is probably room for additional golfing here. Here is an ungolfed version:

match(glob,string) ;
    ; the golfed version assumes a clean symbol table; here, I've explicitly cleaned it.
    new i,pattern,char,mode,buffer,range,advance,delta,j,k
    for i=1:1:$LENGTH(glob) do
    . set char=$EXTRACT(glob,i)
    . if ("*?[]"'[char),(mode=0) do
    . . set pattern=pattern_"1"""_char_"""" ; 1 of `char`
    . if (char="*"),(mode=0) do
    . . set pattern=pattern_".E" ; 0+ of any character
    . if (char="?"),(mode=0) do
    . . set pattern=pattern_"1E" ; 1 of any character
    . if (char="]") do
    . . set pattern=pattern_"1"_$EXTRACT(buffer,1,$LENGTH(buffer)-1)_")"
    . . set mode=0
    . if (char="[") do
    . . set advance=($EXTRACT(glob,i+1)="^") ; 0 or 1
    . . set mode=advance+1 ; 1 = in a char class; 2 = in an inverted char class
    . . set buffer="(" ; begin constructing an alternation
    . . set i=i+advance
    . if (mode'=0) do
    . . if ($EXTRACT(glob,i+1)="]") do
    . . . set delta=1
    . . . set k=$FIND(glob,"]",i+delta)-2+delta
    . . . set range=$EXTRACT(glob,i+1,k)
    . . . set i=k
    . for j=1:1:$LENGTH(range) do
    . . if (mode=1) do
    . . . set buffer=buffer_"1"""_$EXTRACT(range,j)_"""," ; add a character to the alternation
    . if (mode=2) do
    . . for j=0:1:127 do
    . . . if (range'[$CHAR(j)) do
    . . . . set buffer=buffer_"1"""_$SELECT(j=34:"""""",1:$CHAR(j))_""","
    quit string?@pattern ; eval `pattern` and test `string` against it, and return the outcome (0 or 1)
\$\endgroup\$
  • \$\begingroup\$ You didn't foil my plans. you did exactly what my plans were to require -- that is, parse and rebuild the glob before passing it into any match library. \$\endgroup\$ – Joshua Sep 30 '15 at 22:41
2
\$\begingroup\$

Ceylon, 3514 2586 2360 2248 2228 2196 2059 1882 1620 1147 1130 858 830 693 658 bytes

import ceylon.language{B=Boolean,S=String,C=Character,o=false,r=process}shared void g(){B n(B(S)l,B(S)r)(S c)=>any{for(i in 0..c.size)l(c[0:i])&&r(c[i...])};B q(S c)=>c.size==1;B d({C*}s,B n)(S c){if(q(c),exists i=c[0]){return n!=i in s;}return o;}[B(S),S]h(S r){assert(exists s=r[0],exists e=r.firstOccurrence(']'));return[s=='^'then d(r[1..e],true)else d(r[...e],false),r[e+1...]];}B(S)p(S x){if(exists f=x[0]){value r=(f=='*'then[(S c)=>true,x.rest])else(f=='?'then[q,x.rest])else(f=='['then h(x.rest))else[d({f},o),x.rest];return n(r[0],p(r[1]));}else{return S.empty;}}assert(exists x=r.arguments[1],exists c=r.arguments[0]);r.exit(p(x)(c)then 0else 1);}

It seemed first that converting the glob to regular expressions is the easiest, but it also means escaping everything which is special in regular expressions but not in our globs ... I might try this in a different answer.

Due to popular demand I removed most of the the how-I-got-there .. who is interested, can have a look into the history.

So I build a new (limited) regexp-like matching engine, and a parser to convert our wildcard strings into such strings. (And some boiler plate for command line access and return code generation.)

Here is the same program formatted (i.e. with added whitespace) and with some documentation annotations:

import ceylon.language {
    B=Boolean,
    S=String,
    C=Character,
    o=false,
    r=process
}
"""A glob evaluation program.
   Takes two command line arguments, first is a candidate string,
   second one is a wildcard expression.

    Exits with code 0 if the expression is well-formed and
    matches the candidate, otherwise exits with 1. 
   """
shared void g() {
    """A string predicate build from a left and a right predicate.
       It matches a string if that can be split in two substrings
       so the first one is matched by the left expression and
       the second one by the right expression.
       """
    B n(B(S) l, B(S) r)(S c) =>
            any {
        for (i in 0..c.size) l(c[0:i]) && r(c[i...])
    };

    """An expression which matches any string of length 1 (i.e. a single character).
       This corresponds to the question mark (`?`), therefore the name.
       """
    B q(S c) => c.size == 1;

    """A character class, i.e. an expression which matches any string of length 1,
       as long at it is (or is not) in a given list of characters.
       """
    B d(
        "The characters to be matched (or excluded)"
        {C*} s,
        "Is this negated? If true, matches only characters not in the list."
        B n)
            (
        "The candidate string."
        S c) {
        if (q(c), exists i = c[0]) {
            return n != i in s;
        }
        return o;
    }

    """Parses a started character class (i.e. the stuff after the `[`).

       Returns a tuple of the constructed matching function
       and the remaining string to be parsed for further expressions.
       """
    throws (`class AssertionError`, "if the expression is not well-formed, i.e. there is no `]` following.")
    [B(S), S] h(S r) {
        assert (exists s = r[0], exists e = r.firstOccurrence(']'));
        return [s == '^' then d(r[1..e], true) else d(r[...e], false), r[e + 1 ...]];
    }

    """Parses an glob expression from a string.
       Returns a string predicate.
       """
    B(S) p(
        "The string with the wildcard expression."
        S x) {
        if (exists f = x[0]) {
            value r = (f == '*' then [(S c) => true, x.rest])
                    else (f == '?' then [q, x.rest])
                    else (f == '[' then h(x.rest))
                    else [d({ f }, o), x.rest];
            return n(r[0], p(r[1]));
        } else {
            return S.empty;
        }
    }
    assert (exists x = r.arguments[1], exists c = r.arguments[0]);
    r.exit(p(x)(c) then 0 else 1);
}

I'm not sure if this is actually readable enough ... see the history of this answer for the original version with more readable names (and which was using interfaces and objects instead of just functions).

Some used tricks to make this shorter:

  • import with alias – we use String, Boolean and Character quite often, so give them one-letter aliases. When we are already doing this, adding the renaming for process (used three times) and false (used twice) doesn't take much overhead. (This only helps for stuff used several times – the ceylon.language stuff is imported automatically, so we have some overhead here.)
  • The possibleMatchLengths method was an optimization for speed – not needed when we are code-golfing. (I guess this can make matching quite slow in some extreme cases.)
  • the Implementations of the string attribute was also removed, it was just there for debugging the initial versions.
  • Instead of the implementations of the Glob interface in the first versions, we have just functions Boolean(String) (or B(S) in our short format), which saves quite some braces and class/object, and some functions returning such functions. Ceylon has a nice syntax for defining functions which return functions, used for the GlobList g and the CharacterClass c – simply a function with multiple argument lists.
  • I unified the methods for CharacterClass and NegatedCharacterClass, passing a boolean parameter for negated. It is used as negated != i in chars (shorter n!=i in s) instead of having one function with i in s and one with !i in s (and both having the remaining conditions twice).
  • The object/function emptyGlob was replaced by the static Reference String.empty (written S.empty, of course).
  • Where a function consists of just one return statement, we can write it with the "fat arrow" notation and save the braces and the return.
  • If such a function is used just once, sometimes we can put it directly where used, as an anonymous function definition. This is used for the * implementation.
  • The function q (for the question mark) is in addition used in the definition of the character class function d, as q(c) is shorter than c.size==1.
  • Instead of first defining a value with value f = ... or even with type Character f = ... and then doing an if (exists f) { or assert(exists f);, we can move the definition into the if or assert, saving some characters.
  • If we want to pass an iterable constructed from a comprehension to a function (like the any function used in the definition of g), we can write any{...} instead of any({...}) – this is the named argument syntax, which converts its last entry, if it's a comprehension, into an iterable, if the function accepts that.
\$\endgroup\$
  • 1
    \$\begingroup\$ You could reduce your byte count by eliminating unnecessary whitespace and shortening variable names to single characters. \$\endgroup\$ – Alex A. Sep 30 '15 at 16:03
  • \$\begingroup\$ @AlexA. yes, I'll do that at the end, when I find nothing else to do. \$\endgroup\$ – Paŭlo Ebermann Sep 30 '15 at 16:47
  • 3
    \$\begingroup\$ Was your goal to make your post as long as possible? Maybe golf it first, then post it. \$\endgroup\$ – mbomb007 Sep 30 '15 at 18:33
  • \$\begingroup\$ While I appreciate explanations, I think you can remove previous versions of the code. After all, each answer's history is recorded. \$\endgroup\$ – coredump Sep 30 '15 at 19:33
  • 1
    \$\begingroup\$ @coredump Yes, in this case I guess you are right. I removed the old versions. \$\endgroup\$ – Paŭlo Ebermann Sep 30 '15 at 22:15
2
\$\begingroup\$

CJam, 125

{AC+:A;}:F;0alqW+:X;{"*?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)
^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F"N/T=S/(C#=~}fCX,(\-!

CJam has no regular expressions (yet), so I just implemented the wildcard matching directly.
The encoding here is plain old ASCII (I might try some compression tricks later).

Try it online

Explanation:

The idea is to go through the pattern (glob) and keep a list of indices possibly reached so far in the input string. Initial list is [0], ? advances all indices by 1, * goes to all indices from the minimum reached so far to the end of the string, and character sets and other non-special characters just select the indices that match and advance them by 1. At the end, the string matches if the list of indices contains the string length.

Character sets are constructed on the fly and recorded as a string A and a boolean flag B (for positive/negative match), and used when reaching the closing ].

{…}:F;      define a function F
  AC+:A;    add variable C to variable A (A+=C)
0a          push [0] (initial array of indices, let's call it I)
             it will be kept and updated on the stack
l           read the first input line (containing the pattern)
q           read the rest of the input (the string to match)
W+          append the number -1 (as an array element, following the characters)
             this is a dummy guard value that avoids costly empty-string checks
:X;         save the array in X
{…}fC       for each character C in the pattern
  "…"       push that long string, containing code to handle various cases
  N/        split into (two) lines
  T=        get the T'th line; T is 1 when parsing a character set and 0 otherwise
             (T is initially 0 by default)
  S/        split by space into an array of strings
  (         take out the first item (containing special characters to check)
  C#        find the index of C in that string
  =         get the corresponding string from the array
             (when C is not found, # returns -1 which gets the last array item)
  ~         execute that string
X,(         get the length of X and decrement it
             (to get the length of the input string)
\-          calculate the set difference between it and I (the list of indices)
             the result is empty (false) iff I contained the string length
!           negate, to obtain the final 1/0 result

Now the long string with various pieces of code. Each line has a few characters to check and then a block for handling each one, and the default case.

First line: *?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)

*?[       special characters to look for
######### first block, corresponding to character *
_         duplicate I on the stack
{…}&      if I is not empty
  0=      get the first (smallest) index from I
  X,      get the length of X (1 longer than the input string)
  ,       make an array [0 1 2 … length(input string)]
  >       slice the array starting at the smallest index from I
######### second block, corresponding to character ?
:)        increment all items of I
######### third block, corresponding to character [
1:T       set T=1, causing the next characters to be processed with the 2nd line
:B;       also set B=1, the boolean flag signifying positive match
L:A;      initialize A (the array of characters) with an empty string/array
######### last block, corresponding to other regular characters
{…},      filter I's items, using the block as a boolean condition
  X=      get the character from X at the given index (it wraps around)
           if the input string was empty, this will be -1 (the dummy value)
  C=      compare to C (the current character in the pattern)
:)        increment the remaining indices

Second line (for character sets): ^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F

^]        special characters to look for
######### first block, corresponding to character ^
A!B&      calculate not(A) & B, which is 1 (true) iff A is empty and B is 1
{…}       if true (first character and positive match, i.e. we're at "[^")
  0:B;    set B=0 (switch to negative match)
{…}       else
  F       call F, which just adds the character C to A
?         end if
######### second block, corresponding to character ]
A{…}      if A is not empty (it's a closing "]")
  0:T;    set T to 0, switching back to the first line
  {…},    filter I's items, using the block as a boolean condition
    X=    get the character from X at the given index
           if the input string was empty, this will be -1
    A-    calculate the set difference between it and A
    !     negate, obtaining 1 if the character was in A and 0 if it was not
    B=    compare to B (the positive/negative match indicator)
  :)      increment the remaining indices
{…}       else (A is empty, i.e. we're at "[]" or "[^]")
  F       call F to add the character to A
?         end if
######### last block, corresponding to other regular characters
F         call F
\$\endgroup\$
  • \$\begingroup\$ +1 This is interesting, but I am not sure I understand exactly how it works ;-) \$\endgroup\$ – coredump Oct 2 '15 at 15:25
  • 1
    \$\begingroup\$ @coredump check it now :) I also got another golfing idea while writing :p \$\endgroup\$ – aditsu Oct 2 '15 at 17:22
2
\$\begingroup\$

Python 3, 209 207 bytes

The general strategy is transforming the glob spec into a regex. That's accomplished by a function r, passed as the replacement parameter to re.sub(), (or s() in this case). If no match is found, a run-time error is thrown, causing a positive exit code.

import sys,re
_,t,g=sys.argv
s=re.sub
def r(m):a,b,c,d,e=m.groups();return a and s(r"(?=[-\\])",r"\\",a)or b and".*"or c and"."or d and"\\"+d or e
re.match(s(r"(\[\^?.+?\])|(\*)|(\?)|(\W)|(.)",r,g)+"$",t).re

The patterns produced for the example globs show how it works.

Glob            Regex pattern
w*c*d           w.*c.*d$
ww*w*d          ww.*w.*d$
ww*[w-c]?       ww.*[w\-c].$
[a-c]           [a\-c]$
^[*][^]]        \^[*][^]]$
a[\]b           a[\\]b
\$\endgroup\$
  • \$\begingroup\$ Beware of backslashes. Running python file.py 'wildcard' 'w*[\]*d' results in a traceback. \$\endgroup\$ – coredump Oct 2 '15 at 15:23
  • \$\begingroup\$ @coredump: Good find. I fixed it and made it smaller. \$\endgroup\$ – recursive Oct 2 '15 at 23:04
2
\$\begingroup\$

Perl, 88 bytes

$_=pop;s/((\*)|\?)|(\[\^?\]?)(.*?)\]|\W/$1?".$2":$3?qr#$3\Q$4\E]#:"\\$&"/eg/pop=~/^$_\z/

The encoding is ASCII. This works by translating to regular expressions with regular expressions. It exits with a division by zero error (hence, nonzero status) on match failure.

Some ideas adapted from recursive’s Python solution.

\$\endgroup\$
  • \$\begingroup\$ I was wondering when a Perl solution would appear. \$\endgroup\$ – Joshua Oct 3 '15 at 14:59

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.