22
\$\begingroup\$

Task

Given a string composed of ASCII printable characters, return how many strings could fit the given pattern with character literals and regex-like ranges.

Pattern string

The pattern string follows this grammar (the | means an option and the * means 0 or more occurrences of whatever was immediately to the left):

pattern := '' | pattern_string pattern_string := (SAFE_CHAR | ASCII_RANGE) pattern_string* ASCII_RANGE := '[' CHAR '-' CHAR ']'

where CHAR is any ASCII character in the range [32, 127] and SAFE_CHAR is any CHAR except the three characters [, - and ].

Examples

Examples of pattern strings would be a, [0-*]4fj, [a-z][4-9]D[d-B].

Input

The pattern string. You can assume all ranges are well-formed and that all the second characters in the ranges have their ASCII codepoints >= than the corresponding first characters in the range.

Output

The integer corresponding to the number of strings that match the given pattern string.

Test cases

"" -> 1 "a" -> 1 "[*-0]" -> 7 "[0-9][0-9]" -> 100 "[a-z]d[A-z]" -> 1508 "[<->]" -> 3 "[!-&]" -> 6 "[d-z]abf[d-z]fg" -> 529 "[[-]]" -> 3 "[a-a][b-b]cde[---]" -> 1 "[0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1]" -> 4096 "[--[][--]]" -> 2303 "[[-[].[]-]]" -> 1

You can check this Python reference implementation that I used to generate the test cases.

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

This is the second challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 400 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this second challenge are: 05AB1E, W, Jelly, Japt, Gaia, MathGolf and Stax, so submissions in these languages are not eligible for the final prize. But they can still be posted!!

Otherwise, this is still a regular challenge, so enjoy!

Improve this question
\$\endgroup\$
2
  • 6
    \$\begingroup\$ please don't leave comments consisting of only things like "+1, good answer" -- these are noise and produce clutter when left on almost every solution \$\endgroup\$ Commented Mar 2, 2020 at 7:10
  • \$\begingroup\$ @Doorknob ok, sorry for that. It was not my intention to produce clutter! \$\endgroup\$ Commented Mar 2, 2020 at 7:42

41 Answers 41

Reset to default
1
2
1
\$\begingroup\$

QuadS, 28 bytesSBCS

×/1--/∘⎕UCS¨⍵ \[(.).(.) \1\2

Try it online!

QuadS is a language based on Dyalog APL's ⎕S (PCRE search operator). Regex operations (2nd and 3rd lines in this case) are written in plain ASCII using PCRE syntax, and post-processing (1st line) can contain arbitrary APL expression.

How it works

×/1--/∘⎕UCS¨⍵ ⍝ Post-processing function ¨⍵ ⍝ On each match, ⎕UCS ⍝ Convert to Unicode codepoint and -/∘ ⍝ take the difference (e.g. [a-c] -> -2) 1- ⍝ 1 minus each of the above ×/ ⍝ Product over all of the above (1 if no matches) \[(.).(.) ⍝ PCRE regex to match \1\2 ⍝ Extract the two significant chars from each match
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Pyth, 34 bytes

K1WgJxz\[0=*Kh-C@z+J3C@zhJ=>z+J5;K

Try it online!

I think this is my first Pyth submission.

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Wren, 124 bytes

+10 bytes due to fixing a bug.

Fn.new{|i|i.count<4?1:(i.count..1).map{|x|i[x-1]+i[x-3]+i[x-5]=="]-["?1+i[x-2].bytes[0]-i[x-4].bytes[0]:1}.reduce{|a,b|a*b}}

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Your solution currently fails for the test case [[-[].[]-]]! Let me know as soon as you fix it :) \$\endgroup\$ Commented Feb 28, 2020 at 13:38
1
\$\begingroup\$

Perl 5 -p, 42 bytes

$\=1;s/\[(.)-(.)]/$\*=1+ord($2)-ord$1/ge}{

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

05AB1E, 17 bytes

Port of Mathgeek's GolfScript answer

Δć91QićV¦ćY->ˆ]¯P

Takes input as an array of codepoints. The header code does the conversion.

Δ ] # loop until top-of-stack (initially: the input) doesn’t change: ć # extract the first character 91Qi ] # if that character is '[' (ASCII 91): ćV # extract the first character (range start), store it in Y ¦ # drop the first character ('-') ć # extract the first character (range end) Y- # subtract Y > # add 1 ˆ # append to the global array ¯P # output the product of the global array (1 if empty)

Try it online! or verify all test cases.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice one! :) I like the use of the global array. And I need to remember using that "...".V trick for test suites so I won't have to change the ] to }}. :D PS: When you add an explanation, you may want to explicitly mention you take the input as codepoints. \$\endgroup\$ Commented Feb 28, 2020 at 18:21
  • \$\begingroup\$ Isn't taking the inputs as codepoints making the problem easier..? \$\endgroup\$ Commented Feb 28, 2020 at 19:33
  • 1
    \$\begingroup\$ @RGS Well yeah it makes the problem easier, that’s why I do it. (You could ban taking string input as a list of codepoint, but then C and similar languages wouldn’t be able to participate.) \$\endgroup\$ Commented Feb 28, 2020 at 19:48
1
\$\begingroup\$

Retina, 77 74 bytes

L`\[.-. %/^\[/+/^.(.).\1/(3L$` $.'$* 3`. $&$& )3T`p`_p`. ¶ ~`^ .+¶$$.(1$*

Try it online! Link includes test cases. Explanation:

L`\[.-.

List only the ranges themselves (without the close brackets).

%

Process each range separately.

/^\[/+

Repeat while the buffer begins with a [.

/^.(.).\1/( )

If the second and fourth characters are the same...

3L$` $.'$*

... then replace that range with its length followed by a *...

3`. $&$& 3T`p`_p`.

... otherwise duplicate the 3rd character and shift it back by 1 ASCII code point.

Join all of the ranges back together again.

^ .+¶$$.(1$*

Prefix $.(1* to turn the result (if any) into a Retina multiplication, and .+ on its own line to turn that into a substitution command.

~`

Evaluate the result of the substitution command on the previous result, thus performing the multiplication.

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Go, 106 98 bytes

func f(s string)int{r,i:=1,1 for;i<len(s);i++{if s[i-1]==91{r*=1+int(s[i+2]-s[i]) i+=3}} return r}

-8 bytes thanks to RGS for catching a cleanup that I missed.

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 98 bytes \$\endgroup\$ Commented Feb 29, 2020 at 1:52
  • 1
    \$\begingroup\$ @RGS You can tell I wrote this at 6 P.M., can't you? \$\endgroup\$ Commented Feb 29, 2020 at 1:57
1
\$\begingroup\$

Jelly, 18 bytes

ṡ5Œœ€Ḣ“[-]”Ƒ$ƇOI‘P

Try it online!

A full program taking a string and printing an integer.

Thanks to @Grimmy for pointing out a problem with [[-[].[]-]]

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This incorrectly outputs -1 for the [[-[].[]-]] test case. \$\endgroup\$ Commented Feb 28, 2020 at 16:42
  • \$\begingroup\$ @Grimmy fixed at a cost of 3 bytes \$\endgroup\$ Commented Feb 29, 2020 at 9:56
1
\$\begingroup\$

M, 22 bytes

ṡ5µm2⁼“[-]”ȧOḊm2I‘µ€PḢ

Try it online!

How?

Effectively this is using M as if it were Jelly 4 years ago (except we need the trailing Ḣ as M does not have the same full-program printing as Jelly did or does). Gotta love loopholes :)

ṡ5µm2⁼“[-]”ȧOḊm2I‘µ€PḢ - Link: list of characters ṡ5 - all slices of length five µ µ€ - for each: m2 - modulo two slice ("[a-e]" -> "[-]") “[-]” - "[-]" ⁼ - equal? O - ordinals ȧ - logical AND Ḋ - dequeue (N.B. 0Ḋ -> []) m2 - modulo two slice ([97,45,101,93] -> [97,101]) I - deltas ([97,101] -> [5]) ‘ - increment ([5] -> [6]) P - product (e.g. [[2],[],[4]] -> [8]) Ḣ - head (e.g. [8] -> 8)
Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ So what is exactly the relationship between Jelly and M? \$\endgroup\$ Commented Feb 29, 2020 at 23:29
  • \$\begingroup\$ Same author, M is meant to be designed for more mathematical tasks. \$\endgroup\$ Commented Feb 29, 2020 at 23:47
  • \$\begingroup\$ Ok, nice loophole exploit :) \$\endgroup\$ Commented Feb 29, 2020 at 23:55
  • 1
    \$\begingroup\$ My Labyrinth is eligible, but not very terse; I might find something else. \$\endgroup\$ Commented Mar 1, 2020 at 15:55
  • 1
    \$\begingroup\$ ...done with husk - thought it would be shorter, possible it's still golfable. \$\endgroup\$ Commented Mar 1, 2020 at 18:09
1
\$\begingroup\$

Ruby -n, 45 bytes

x=1;gsub(/\[(.)-(.)/){x*=1+$2.ord-$1.ord};p x

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

x86 machine code, 30 bytes

Hexdump:

33 d2 f7 f0 8a 11 41 84 d2 75 01 c3 80 fa 5b 75 f3 8a 51 02 2a 11 42 f7 e2 83 c1 04 eb e6

Disassembly:

33 D2 xor edx,edx F7 F0 div eax,eax again: 8A 11 mov dl,byte ptr [ecx] ; load byte 41 inc ecx ; advance pointer 84 D2 test dl,dl ; check for end of string 75 01 jne cont ; not end? - continue C3 ret ; end of string? - return cont : 80 FA 5B cmp dl,5Bh ; check for ASCII_RANGE 75 F3 jne again ; not ASCII_RANGE? - continue 8A 51 02 mov dl,byte ptr [ecx+2] ; 2A 11 sub dl,byte ptr [ecx] ; find range size 42 inc edx ; F7 E2 mul eax,edx ; eax = eax * size 83 C1 04 add ecx,4 ; skip the ASCII_RANGE part EB E6 jmp again ; continue

A fastcall function: gets the pointer to the input in ecx and returns the result in eax. A pretty straightforward algorithm, which only uses eax, edx and ecx - no need to save and restore registers!

It initializes eax to 1 and edx to 0 by dividing the 64-bit value edx:eax by eax.

To test this with Visual Studio, use the following C++ test program:

#include <iostream> int __declspec(naked) __fastcall doit(const char* s) { _asm { xor edx, edx; div eax; again: mov dl, [ecx]; inc ecx; test dl, dl; jne cont; ret; cont: cmp dl, '['; jne again; mov dl, [ecx + 2]; sub dl, [ecx]; inc edx; mul edx; add ecx, 4; jmp again; } } int main() { std::cout << doit("[d-z]abf[d-z]fg"); }
Improve this answer
\$\endgroup\$
0
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.