26
\$\begingroup\$

This time, you are working on a regex. Your regex is meant to approximately full-match the base-10 representations of primes \$0 \le p < 1000\$, while ignoring any non-numeric string or composite in the range. You can full-match 2, 53 or 419, but not 0, 82 or example.

The approximately is important -- a minimum of 900 numbers have to produce the right output. You can match more numbers correctly (but as this is a challenge you probably shouldn't). For clarification, how numbers above 1000 are matched doesn't matter and they can produce whatever output you like.

Test cases part 1, strings which should be matched (primes under 1000):

5
739
211
617
103
503
11
13
17
23
71
89
257

Part 2: strings that shouldn't be matched

five
5o
2q11
716
102_3
42 + 1
term in A000040
16
204

Your score is the number of characters in your regex. Lowest score wins. Have fun!

\$\endgroup\$
11
  • \$\begingroup\$ If I'm understanding this correctly, you're asking us to test for primality using only RegEx. If so then this is a dupe of our catalogue primality testing challenge which has at least one RegEx solution. \$\endgroup\$
    – Shaggy
    Commented Jun 26, 2021 at 20:20
  • 4
    \$\begingroup\$ Indeed. The only other thing setting this challenge apart is that you only need to test numbers up to 3 digits and you're allowed to make 100 wrong outputs at most. \$\endgroup\$ Commented Jun 26, 2021 at 20:30
  • \$\begingroup\$ Where's Martin Ender when you need him? \$\endgroup\$
    – AviFS
    Commented Jun 26, 2021 at 20:32
  • \$\begingroup\$ Which was the only reason I didn't dupe hammer this, @AndrewTheCodegolfer; 'cause RegEx is tetchy enough that the upper bound of 1000 might actually lead to significantly different solutions. \$\endgroup\$
    – Shaggy
    Commented Jun 26, 2021 at 21:05
  • 2
    \$\begingroup\$ @Shaggy the approaches that can be used to test for primality using regex given a decimal representation of a small integer, with 90% precision, are completely different from those that can be used given an unary representation... A deterministic test for primality using regex given a decimal representation is almost certainly impossible. The only thing these questions have in common is the word "prime". \$\endgroup\$ Commented Jun 27, 2021 at 5:59

7 Answers 7

27
\$\begingroup\$

90 79 72 67 65 64 bytes

^(?!([258][0369]*[147]|[1475][258]|[147]{3}|[0369])+$)\d+[1379]$

Matches 2–3-digit numbers not divisible by 2, 3, or 5, with an added bit (the 5 in [1475]) that removes 8 false positives (527, 529, 551, 553, 559, 581, 583, 589) and adds 4 false negatives (521, 523, 557, 587).

-2 thanks to Nahuel Fouilleul; -9 by removing [258]{3}, which was not necessary; -7 by removing one [0369]*; -5, -2, -1 with successive improvements on an idea from tsh.

\$\endgroup\$
4
  • \$\begingroup\$ @Arnauld Did you copy it into a string without escaping the backslash? \$\endgroup\$
    – m90
    Commented Jun 26, 2021 at 14:37
  • \$\begingroup\$ Oh, of course. Sorry about that. \$\endgroup\$
    – Arnauld
    Commented Jun 26, 2021 at 14:39
  • 1
    \$\begingroup\$ small improvement |1$ can be removed using \d+ instead of \d* adding 7 in the last set saving 2 bytes. \$\endgroup\$ Commented Jun 26, 2021 at 18:17
  • 1
    \$\begingroup\$ 69: ^(?!([258][0369]*[147]|[147][258]|[147]{3}|[0369])*$|32|62)\d+[1379]$ \$\endgroup\$
    – tsh
    Commented Jun 28, 2021 at 4:07
7
\$\begingroup\$

 101  96 bytes

This is manually optimized and probably sub-optimal.

^((10?|19|82)[1379]|(31|46?|64|88)[137]|(6?5|8|17|23?|26|3[578]|44|5[069])[39]|(22|61|85)[379])$

Try it online!

This matches 68 prime numbers and nothing else.

\$\endgroup\$
6
\$\begingroup\$

69 primes, 831 composites, 83 bytes

^((3+|46?|60?|1[0359]?|75|9[479])[17]|(3?[78]|6?[15]|[15][069]|2[236]?|4[34])[39])$

Try it online! Link is to test suite that counts the number of correctly matched integers. (The composite number that it incorrectly detects as prime is 169.)

68 primes, 832 composites, 85 bytes

^((31?|46?|60?|1[0359]?|75|9[479])[17]|(1[079]?|2[236]?|5[069]?|73?|82?|3[578])[39])$

Try it online! Link is to test suite that counts the number of matched prime numbers.

Try it online! Link is to test suite that counts the number of correctly matched integers.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Technically, it's 829 and 830 composites. 0 and 1 are not composite, nor are they prime. \$\endgroup\$
    – Deadcode
    Commented Apr 3, 2023 at 10:18
5
\$\begingroup\$

Classic regex, 526 452 characters.

9(9(7|1)|83|7(|7|1)|67|53|4(7|1)|37|29|1(9|1)|07)|
8(9|8(7|3|1)|77|63|5(9|7|3)|3(|9)|2(9|7|3|1)|11|09)|
7(|9(|7)|87|73|6(9|1)|5(7|1)|43|3(|9|3)|27|1(|9)|0(9|1))|
6(91|83|7(|7|3)|61|5(9|3)|4(7|3|1)|31|1(|9|7|3)|0(7|1))|
5(|9(|9|3)|87|7(7|1)|6(9|3)|57|4(7|1)|3|2(3|1)|0(9|3))|
4(9(9|1)|87|7(|9)|6(7|3|1)|57|4(9|3)|3(|9|3|1)|21|1(|9)|0(9|1))|
3(|97|8(9|3)|7(|9|3)|67|5(9|3)|4(9|7)|3(7|1)|1(|7|3|1)|07)|
2(|9(|3)|8(3|1)|7(7|1)|6(9|3)|5(7|1)|41|3(|9|3)|2(9|7|3)|11)|
1(9(|9|7|3|1)|81|7(|9|3)|6(7|3)|5(7|1)|49|3(|9|7|1)|27|1(|3)|0(9|7|3|1))

This is non-competitive answer for reference, giving the accurate match.

Two more bytes ^...$ may be needed in a given implementation language/utility to anchor this.

In POSIX world, this is an "extended" regex (ERE); a basic regex (BRE) requires escaped parentheses, otherwise they are literal.

This was calculated by creating a trie structure out of the data set, applying path compression, and then converting to regex.

This can be improved by reducing patterns like (9|7|3|1) into [9731] character classes, and empty branches (|3) into 3? and such:

9(9[71]|83|7[71]?|67|53|4[71]|37|29|1[91]|07)|
8(9|8[731]|77|63|5[973]|39?|2[9731]|11|09)|
7(97?|87|73|6[91]|5[71]|43|3[93]?|27|19?|0[91])?|
6(91|83|7[73]?|61|5[93]|4[731]|31|1[973]?|0[71])|
5(9[93]?|87|7[71]|6[93]|57|4[71]|3|2[31]|0[93])?|
4(9[91]|87|79?|6[731]|57|4[93]|3[931]?|21|19?|0[91])|
3(97|8[93]|7[93]?|67|5[93]|4[97]|3[71]|1[731]?|07)?|
2(93?|8[31]|7[71]|6[93]|5[71]|41|3[93]?|2[973]|11)?|
1(9[9731]?|81|7[93]?|6[73]|5[71]|49|3[971]?|27|13?|0[9731])
\$\endgroup\$
8
  • 1
    \$\begingroup\$ It'd be really neat if you put a link to the code you used to generate this! Super cool answer. \$\endgroup\$
    – AviFS
    Commented Jun 27, 2021 at 21:21
  • \$\begingroup\$ @AviFS I will do this in a few days; unfortunately, the work depends on some private bugfixes to public code, so people wouldn't be able to reproduce the steps currently. \$\endgroup\$
    – Kaz
    Commented Jun 28, 2021 at 2:19
  • \$\begingroup\$ Although not the shortest code, I like this one because it's very easy to read and the generation of the code used other code. \$\endgroup\$ Commented Jun 28, 2021 at 10:44
  • \$\begingroup\$ Erratum: the first character count had been incorrectly given as 529. \$\endgroup\$
    – Kaz
    Commented Jun 28, 2021 at 13:13
  • \$\begingroup\$ Very nice. For the record though, I don't think it is fair to call this 452 bytes instead of 456. Most regex engines don't have an option for implied full-string-match; the only ones I know of that do are Java, Boost, Python, and PCRE2, and most of the wrappers for PCRE2 don't provide access to that functionality (pretty much just its native C interface does). \$\endgroup\$
    – Deadcode
    Commented Apr 4, 2023 at 0:46
3
\$\begingroup\$

JavaScript (Node.js), 405 bytes

1(0[1379]|13?|27|3[179]?|49|5[17]|6[37]|7[39]?|81|9[1379]?)|2(11|2[379]|3[39]?|41|5[17]|6[39]|7[17]|8[13]|93?)?|3(07|1[137]?|3[17]|4[79]|5[39]|67|7[39]?|8[39]|97)?|4(0[19]|19?|21|3[139]?|4[39]|57|6[137]|79?|87|9[19])|5(0[39]|2[13]|3|4[17]|57|6[39]|7[17]|87|9[39]?)?|6(0[17]|1[379]?|31|4[137]|5[39]|61|7[37]?|83|91)|7(0[19]|19?|27|3[39]?|43|5[17]|6[19]|73|87|97?)?|8(09|11|2[1379]|39?|5[379]|63|77|81|9)|97

Try it online!

Similar to the one below, but optimized by a simple program I wrote similar to https://github.com/noprompt/frak


JavaScript (Node.js), 578 bytes

2|3|5|7|11|13|17|19|23|29|31|37|41|43|47|53|59|61|67|71|73|79|83|89|97|101|103|107|109|113|127|131|137|139|149|151|157|163|167|173|179|181|191|193|197|199|211|223|227|229|233|239|241|251|257|263|269|271|277|281|283|293|307|311|313|317|331|337|347|349|353|359|367|373|379|383|389|397|401|409|419|421|431|433|439|443|449|457|461|463|467|479|487|491|499|503|509|521|523|541|547|557|563|569|571|577|587|593|599|601|607|613|617|619|631|641|643|647|653|659|661|673|677|683|691|701|709|719|727|733|739|743|751|757|761|769|773|787|797|809|811|821|823|827|829|839|853|857|859|863|877|881

Try it online!

contains 152 of the 168 prime numbers under 1000 ~90%

cant get simpler can it?

\$\endgroup\$
3
\$\begingroup\$

Any flavor, 148 bytes

^([389]?113?|2(39?|2[379]|[147]1|[9862]3)?|(1[023569]?|4[568]?|6[147]?|9[03469]?|3[013469]?|8[8572]|7[259]|5[4578]|)7|1?[357]|[258]9|[37]1|[4785]3)$

Try it online!

Matches 68 of the 168 primes between 0 and 1000 as being prime, and all 832 of the composites, totalling 900, or 90% of the total 1000.

\$\endgroup\$
3
\$\begingroup\$

.NET regex, 236 229 222 210 202 198 192 bytes

^(?!(?(((?<-4>(){10})|){99}((?<4-2>)|){990}(?=[6-9](?<4>){6})?(?=[3-59](?<4>){3})?([258](?<4>)|[147])?).)+$(?(5)|(\6)?()){31}(?(4)(?(6)(?<A-6>(?<-4>))){31}(?>(?<6-A>)(\4)?|){31}){499}\7|[01]$)

Try it online!
Try it online! - Kaz's 456 byte POSIX ERE compatible solution, for comparison
Try it online! - primes matched in unary, for comparison

This correctly identifies all \$168\$ primes and \$832\$ non-primes in the range \$[0,999]\$. (Processing that entire range on TIO takes 30 4 seconds.) As such it competes in the 100% category, as one other answer to this challenge has done, and not 90%-or-better as the challenge asks for.

Earlier versions of this were split into two levels of golf, one running in a reasonable amount of time, and the other experiencing exponential slowdown (being probably too slow to finish processing the entire range before the heat death of the universe). But since the 194 byte mark was reached, that version became obsolete, and now the shortest version is approximately equal in speed to the fastest version.

-8 bytes (210 → 202) by using a variant of jimmy23013's digit capture technique instead of binary

The primary challenge here is that a regex can only do its work within the space of the input. In unary, this is no problem as far as matching primes go. But in decimal, the digits don't provide enough space to do the necessary computational work – numeric variables cannot be stored in the form of captured portions of the input string, as the number of possible states of each such a capture, including the unset state, would only be \$n({n+1})/2+2\$ at best (if every digit is unique), or \$n+2\$ at worst (if all digits are identical), when it needs to be \$10^n\$ – where \$n\$ is the number of decimal digits in the input.

This regex uses .NET's Balanced Groups feature to do its magic. In .NET, each time a capture has been made to a particular group, using (...) or (?<n>...), it is pushed onto that group's capture stack, which retains the full information of every substring contained in that stack, in order. That's overkill in this case, as this regex only pushes empty strings* onto the capture stacks. Each emulated numeric variable is stored as the number of times a capture has been pushed onto the stack of a particular group. (Popping is done using (?<-n>...), which asserts the stack is non-empty and removes the capture at the top of that stack – as well as matching the enclosed pattern, which can be unrelated. As far as this regex is concerned, it simply asserts that the variable is nonzero and then decrements it.)
*Not that it makes any difference given how the regex works, but following the 210 → 202 golf, if the last digit of the input is in [124578], the topmost capture on the \4 stack will contain that digit. The rest are empty.

But even with this trick, it is impossible to do unbounded arithmetic. A repeated operation (incrementing and/or decrementing a capture stack variable) can only be either done as many times as there are characters in the input, or done a hard-coded maximum number of times. These can be combined and multiplied, but that still only means it could be repeated a number of times that is proportional to a polynomial function of the input string's length, whereas to be able to scale with decimal input (or any base besides unary), it'd need to be an exponential function.

So at the time of this posting, I had thought it impossible to match all primes up to infinity in decimal with a pure regex. But it turns out to be possible after all, by doing base-encoded arithmetic and long division; that regex is much longer.

In the commented explanation below, I use the shorthand Cn to signify the capture count of group \n:

^               # Anchor to start
(?!             # Negative lookahead - assert that none of the following two
                # alternatives can match.
    # Match any composite number in decimal

    # Parse the number, translating decimal into the capture count C4
    (?( # This entire section is wrapped inside a lookahead conditional,
        # which just acts as a golfed lookahead since it always matches.
        ((?<-4>(){10})|){99}    # C2 += C4 * 10; C4 = 0
        ((?<4-2>)     |){990}   # C4 += C2;      C2 = 0

        # Read this digit, adding it to C4
        (?=  [6-9] (?<4>){6})?  # C4 += 6, if digit is in [      6789]
        (?=  [3-59](?<4>){3})?  # C4 += 3, if digit is in [   345   9]
        (    [258] (?<4>)   |   # C4 += 2, if digit is in [  2  5  8 ]
             [147]          )?  # C4 += 1, if digit is in [ 1  4  7  ]
      )
        .           # Consume digit
    )+$             # Loop until all digits have been read.

    # C6 = any number from 2 to 31 (31 is the largest prime ≤ sqrt(999))
    (?(5)|      # Conditional - On each iteration, only do anything if \5 is
                # unset.
        (\6)?   # On any iteration after the first, \5 can be set, which
                # signals that no further iterations after the next will
                # increment C6. Doing it this way ensures that C6 will be
                # incremented at least twice.
        ()      # C6 += 1
    ){31}       # Iterate 31 times, to give C6 a possible range from 2 to 31.
                # We can't accomplish this as "{2,31}" because then .NET,
                # like Perl but unlike PCRE, would only do the minimum number
                # of iterations (i.e. 2) before exiting the loop due to a
                # zero-width match.
    # Divide C4 / C6, enforcing that the remainder is zero. The quotient is the
    # number of iterations that start with C4 != 0, i.e. the number of non-NOP
    # iterations.
    (?(4)       # Make each iteration of this loop conditional upon C4 != 0, so
                # that if the division finishes and C4 is still nonzero, the
                # loop will fail to match and will immediately backtrack to try
                # a different value of C6; this provides a huge speedup,
                # relative to putting "(?!\4)" after the end of the loop (which
                # would can't do anyway now, since it doesn't always capture
                # empty strings). Thus, the loop can only finish and exit if
                # C4 == 0 after the division has completed, which, if C7 ≥ 2,
                # means that C4's original value was composite.
        # Total effect of the following loop: C4 -= C6; CA = C6; C6 = 0
        (?(6)           # Make each iteration conditional upon C6 != 0, so that
                        # this loop can't finish without fully subtracting C6
                        # from C4. If C4 was less than C6, this loop will fail
                        # to match before it can finish, and the regex will
                        # backtrack to try a smaller value of C6.
            (?<A-6>(?<-4>))     # CA += 1; C6 -= 1; C4 -= 1
        ){31}                   # Do the above the maximum of up to 31 times,
                                # the maximum value that C6 could have had.
        (?>(?<6-A>)(\4)?|){31}  # C6 = CA; CA = 0;
                                # \7 = set if C4 != 0, i.e. if quotient ≥ 2
    ){499}                      # Handle a quotient of up to floor(999 / 2)
    \7                          # Assert that the quotient was ≥ 2
|   # or...
    # Match the decimal numbers 0 or 1
    [01]$
)

This algorithm can do \$[0,3333]\$ in 56 seconds on TIO (the regex becomes 195 bytes): Try it online!


Here is an alternative 195 byte version that does not do any direct matching against the digits after their initial reading. I'm including this not just because it's an interesting variation of the algorithm, more like ^(?>(x(x*))\1+$)\2 whereas the above version is like ^(?!(xx+)\1+$)xx, but because it just might be possible to golf to a shorter length than the above version.

^(?=(?(((?<-4>(){10})|){99}((?<4-2>)|){990}(?=[6-9](?<4>){6})?(?=[3-59](?<4>){3})?([258](?<4>)|[147])?).)+$(?(6)|(|())){31}(?(4)(?(5)(?<9-5>(?<-4>))){31}(?>(?<5-9>)(\9)?(\4)?|){31}){499}\8)(?!\7)

Try it online!

^               # Anchor to start
(?=             # Atomic lookahead
    # Parse the number, translating decimal into the capture count C4
    (?( # This entire section is wrapped inside a lookahead conditional,
        # which just acts as a golfed lookahead since it always matches.
        ((?<-4>(){10})|){99}    # C2 += C4 * 10; C4 = 0
        ((?<4-2>)     |){990}   # C4 += C2;      C2 = 0

        # Read this digit, adding it to C4
        (?=  [6-9] (?<4>){6})?  # C4 += 6, if digit is in [      6789]
        (?=  [3-59](?<4>){3})?  # C4 += 3, if digit is in [   345   9]
        (    [258] (?<4>)   |   # C4 += 2, if digit is in [  2  5  8 ]
             [147]          )?  # C4 += 1, if digit is in [ 1  4  7  ]
      )
        .           # Consume digit
    )+$             # Loop until all digits have been read.

    # C5 = any number from 1 to 31 (31 is the largest prime ≤ sqrt(999))
    (?(6)|      # Conditional - On each iteration, only do anything if \6 is
                # unset.
        (|())   # C5 += 1; if this chooses to set \6, then for the rest of the
                # loop, C5 will no longer be incremented. This has the effect of
                # trying values in the order from 31 down to 1.
    ){31}       # Iterate 31 times, to give C5 a possible range from 2 to 31.
                # We can't accomplish this as "{2,31}" because then .NET,
                # like Perl but unlike PCRE, would only do the minimum number
                # of iterations (i.e. 2) before exiting the loop due to a
                # zero-width match.
    # Divide C4 / C5, enforcing that the remainder is zero. The quotient is the
    # number of iterations that start with C4 != 0, i.e. the number of non-NOP
    # iterations.
    (?(4)       # Make each iteration of this loop conditional upon C4 != 0, so
                # that if the division finishes and C4 is still nonzero, the
                # loop will fail to match and will immediately backtrack to try
                # a different value of C5; this provides a huge speedup,
                # relative to putting "(?!\4)" after the end of the loop (which
                # would can't do anyway now, since it doesn't always capture
                # empty strings). Thus, the loop can only finish and exit if
                # C4 == 0 after the division has completed, which, if C7 ≥ 2,
                # means that C4's original value was composite.
        # Total effect of the following loop: C4 -= C5; C9 = C5; C5 = 0
        (?(5)           # Make each iteration conditional upon C5 != 0, so that
                        # this loop can't finish without fully subtracting C5
                        # from C4. If C4 was less than C5, this loop will fail
                        # to match before it can finish, and the regex will
                        # backtrack to try a smaller value of C5.
            (?<9-5>(?<-4>))     # C9 += 1; C5 -= 1; C4 -= 1
        ){31}                   # Do the above the maximum of up to 31 times,
                                # the maximum value that C5 could have had.
        # Total effect of the following loop: C5 = C9; C9 = 0
        # (as well as the possible setting of \7 and/or \8)
        (?>
            (?<5-9>)            # C5 += 1; C9 -= 1
            (\9)?               # \7 = set if C9 == 0, i.e. C5_initial ≥ 2
            (\4)?               # \8 = set if C4 != 0, i.e. if quotient ≥ 2
        |
        ){31}
    ){499}                      # Handle a quotient of up to floor(999 / 2)
    \8                          # Assert that the quotient was ≥ 2
)
(?!\7)                  # Assert C5_initial == 1, i.e. that the largest divisor
                        # resulting in a quotient ≥ 2 was 1

It should also be possible to implement a finite-bounded primality test in regex flavors that don't have balanced groups, but do have persistent backreferences (Perl / Java / Pythonregex / Ruby / PCRE); it would have to be done in emulated binary, so there'd have to be a capture group for each bit, at each location where emulated addition/subtraction is done – which means \$10\$ of them for each variable at each arithmetic location to handle \$[0,999]\$, and each one would have to implement its own copying and carry/borrow in each addition/subtraction operation – so, such a regex would probably be enormous, and would likely only pass the breaking-even point against POSIX ERE at a larger maximum range of handled primes (maybe one more decimal digit would be enough, or maybe not).

\$\endgroup\$
0

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.