Skip to main content
6 of 14
add PCRE1 test harnesses
Deadcode
  • 11.9k
  • 1
  • 66
  • 52

Perl / Java / PCRE, 39 bytes

^((((\3|^x)xx)*)x?+)(?=(\1*)\2+$)\1*$\5

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! - PCRE2

This is the same as the 40 byte regex below, but drops .NET support by using a possessive quantifier, x?+ instead of |^$, to match \$0^4\$. This works because x?+ will always consume 1 x if it can, and will only consume 0 xs if \$\it\text{tail}=0\$, which can only happen if either the input is not a square in the first place (in which case the second half of the regex can't match), or if the input is \$0\$.

Perl / Java / PCRE / .NET, 42 40 bytes

^((((\3|^x)xx)*)x)(?=(\1*)\2+$)\1*$\5|^$

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - .NET

This uses the equivalent of ^(\1xx|^x)*$ to match a perfect square using a nested backreference (made more complicated by needing to capture that square minus \$1\$), and then uses a square-testing algorithm which works thanks to the Chinese remainder theorem (which only requires ECMAScript or better, and is the reason for needing to capture the square minus \$1\$), to assert that the captured perfect square is the square root of the inputted number. The latter algorithm is explained in this post, and this exact square-testing regex is used in the second answer in this post.

If it did not need to match \$0^4\$, the regex would be 39 37 bytes, beating primo's excellent solution.

    ^                    # tail = N = input number
    (                    # \1 = the largest perfect square for which the
                         #      subsequent expression matches; tail -= \1
        (                # \2 = \1 - 1
            (            # \3 = nested backreference
                # On the first iteration,   \3 =  1 + 2 = 3;
                # on subsequent iterations, \3 = \3 + 2
                (\3|^x)
                xx
            )*           # iterate \3 any number of times (may be zero); \2
                         # becomes the total of all these iterations
        )
        x                # \1 = \2 + 1
    )
    # Assert that N == \1^2
    (?=
        (\1*)\2+$        # iff \1*\1 == N, the first match here must capture \5=0
    )
    \1*$\5               # assert \1 divides N-\1, and \5==0
|
    ^$                   # Allow us to match N=0, which can't be matched above
Deadcode
  • 11.9k
  • 1
  • 66
  • 52