(RGS 2/5) How many strings can you count within these character classes? 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 &gt;= 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

"" -&gt; 1
"a" -&gt; 1
"[*-0]" -&gt; 7
"[0-9][0-9]" -&gt; 100
"[a-z]d[A-z]" -&gt; 1508
"[&lt;-&gt;]" -&gt; 3
"[!-&amp;]" -&gt; 6
"[d-z]abf[d-z]fg" -&gt; 529
"[[-]]" -&gt; 3
"[a-a][b-b]cde[---]" -&gt; 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]" -&gt; 4096
"[--[][--]]" -&gt; 2303
"[[-[].[]-]]" -&gt; 1


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

This is code-golf 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 code-golf challenge, so enjoy!
CP-1610 machine code (Intellivision), &nbsp;23&nbsp; 22 DECLEs1 ≈ 28 bytes

As per the exception described in this meta answer, the exact score is 27.5 bytes (220 bits)

A routine taking a null-terminated string as an inline argument through R4 and returning the result in R1.

2B9 001     |         MVII    #1,     R1
2A0         | @@read  MVI@    R4,     R0
080         |         TSTR    R0
204 00F     |         BEQ     @@rtn
378 05B     |         CMPI    #'[',   R0
22C 007     |         BNEQ    @@read
2A0         |         MVI@    R4,     R0
00C         |         INCR    R4
320         |         SUB@    R4,     R0
020         |         NEGR    R0
008         |         INCR    R0
004 11C 1DC |         CALL    MULT
091         |         MOVR    R2,     R1
220 012     |         B       @@read
0A7         | @@rtn   JR      R4


A note about subroutine calls

The CP-1610 instruction for calling subroutines is JSR Rx, $address. This instruction saves the return address in Rx instead of pushing it on the stack as many other CPUs do.

This allows to pass a block of arguments that immediately follows the function call. This is a common practice in CP-1610 programming and that's what we use here.

        JSR     R4,     count     ; call to subroutine through R4
        STRING  "[*-0]", 0        ; argument
        ...                       ; we will return here


Obviously, the subroutine is responsible for reading the correct number of arguments and eventually jumping to the expected return address.

Full commented test code

        ROMW    10                ; use 10-bit ROM width
        ORG     $4800             ; map this program at $4800

PNUM    QEQU    $18C5             ; EXEC routine: print a number
MULT    QEQU    $1DDC             ; EXEC routine: signed multiplication

        ;; ------------------------------------------------------------- ;;
        ;;  main code                                                    ;;
        ;; ------------------------------------------------------------- ;;
main    PROC

        SDBD                      ; set up an interrupt service routine
        MVII    #isr,   R0        ; to do some minimal STIC initialization
        MVO     R0,     $100
        SWAP    R0
        MVO     R0,     $101

        EIS                       ; enable interrupts

        MVII    #$200,  R3        ; R3 = backtab pointer

        JSR     R4,     count     ; test cases
        STRING  "", 0
        CALL    print
        JSR     R4,     count
        STRING  "a", 0
        CALL    print
        JSR     R4,     count
        STRING  "[*-0]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[0-9][0-9]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[a-z]d[A-z]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[&lt;-&gt;]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[!-&amp;]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[d-z]abf[d-z]fg", 0
        CALL    print
        JSR     R4,     count
        STRING  "[[-]]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[a-a][b-b]cde[---]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1][0-1]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[--[][--]]", 0
        CALL    print
        JSR     R4,     count
        STRING  "[[-[].[]-]]", 0
        CALL    print

        DECR    R7                ; done: loop forever

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  prints the result of a test case                             ;;
        ;; ------------------------------------------------------------- ;;
print   PROC

        PSHR    R5                ; save the return address on the stack

        MOVR    R1,     R0        ; R0 = number to print
        MVII    #4,     R1        ; R1 = number of digits
        MOVR    R3,     R4        ; R4 = backtab pointer
        ADDI    #5,     R3        ; advance by 5 characters for the next one
        PSHR    R3                ; save R3
        CLRR    R3                ; R3 = attributes (black)
        CALL    PNUM              ; invoke the EXEC routine
        PULR    R3                ; restore R3

        PULR    R7                ; return

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  ISR                                                          ;;
        ;; ------------------------------------------------------------- ;;
isr     PROC

        MVO     R0,     $0020     ; enable display

        CLRR    R0
        MVO     R0,     $0030     ; no horizontal delay
        MVO     R0,     $0031     ; no vertical delay
        MVO     R0,     $0032     ; no border extension
        MVII    #$D,    R0
        MVO     R0,     $0028     ; light-blue background
        MVO     R0,     $002C     ; light-blue border

        JR      R5                ; return from ISR

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  our routine                                                  ;;
        ;; ------------------------------------------------------------- ;;
count   PROC

        MVII    #1,     R1        ; initialize R1 to 1

@@read  MVI@    R4,     R0        ; R0 = current character
        TSTR    R0                ; end of string?
        BEQ     @@rtn             ; if yes, return

        CMPI    #'[',   R0        ; is this a '['?
        BNEQ    @@read            ; if not, just go on with the next character

        MVI@    R4,     R0        ; R0 = ASCII code of the starting character
        INCR    R4                ; skip the '-'
        SUB@    R4,     R0        ; subtract the ASCII code of the ending character
        NEGR    R0                ; negate
        INCR    R0                ; increment
        CALL    MULT              ; compute R2 = R0 * R1
        MOVR    R2,     R1        ; and save the result in R1

        B       @@read            ; go on with the next character

@@rtn   JR      R4                ; return

        ENDP


Output



screenshot from jzIntv



1. A CP-1610 opcode is encoded with a 10-bit value (0x000 to 0x3FF), known as a 'DECLE'.