• 12.9k
• 2
• 71
• 55

• 12.9k
• 2
• 71
• 55

Regex (ECMAScript / Python or better), 50 bytes

^((?=(xx+?)2円+$)((?=2円+$)(?=(x+)(4円+$))5円){2})*x?$

Try it online!

This regex is explained in Match strings whose length is a fourth power. teukon and I arrived at it independently, starting on 2014年02月22日, though golfing it down to this point took him 2 days and took me 4 days. It works by dividing away squared prime factors one at a time, thus keeping the number's property of being a square at every step iff it started out being a square. This regex represents a local minimum in length; it's the shortest form that this particular algorithm can be golfed into. It can be modified to match Nth powers by changing the 2 in {2} to N.

Regex (ECMAScript), 28 bytes

^(x(x*)|)(?=(1円*)2円+$)1円*$3円

Try it online!

^ # tail = C = input number
(x(x*)|) # 1円 = A = conjectured square root of C; 2円 = A-1, or unset if A==0,
 # allowing us to match C==0 using ECMAScript NPCG behavior; tail -= A
(?=
 (1円*)2円+$ # iff A*A==C, the first match here must result in 3円==0
)
1円*$3円 # assert A divides tail, and 3円==0

This ultimate form of this was arrived upon from 2014年03月02日 to 2014年03月04日 through several rounds of golfing between teukon and me, after we had already independently come up with the coprime moduli method of generalized multiplication (which took him 3 hours and took me almost 2 days). I came up with the idea to do one of the tests as (1円*)2円+$ followed by testing if 3円==0 although it didn't improve my regex's overall length at the time, and he came up with the idea to combine the 3円==0 test and 1円*$ test into one, as 1円*$3円, thus doing the 1円*$ test at the end instead of the beginning (which sacrifices speed in the name of golf, assuming the regex engine doesn't optimize it). (That is with the group numbering of the fully golfed form mapped onto the snippets.)

I've explained the generalized multiplication algorithm in this post, but since its application to squares is simpler, I'm including an explanation for that here.

To explain why this works, let's rearrange the order of the assertions:

(?=
 1円*$ # assert that A divides C-A
)
(?=
 (1円*)2円+$ # iff A*A==C, the first match here must result in 3円==0
)
.*$3円 # assert that 3円==0

We have \$A^2 \stackrel{?}{=} C\$. If this assertion were true, we would have:

\$\begin{aligned}C &= A^2 \\ C-A &= A^2-A \\ &= (A-1)A\end{aligned}\$

This shows that the assertions made by the regex will hold true if \$C=A^2\$:

\$\begin{aligned}C-A &\equiv 0 \pmod A \\ C-A &\equiv 0 \pmod {A-1}\end{aligned}\$

Note that in regex, \0ドル \equiv 0 \pmod 0\$, so the algorithm works for \$C=1^2\$ and \$A=1\$ without any need for a special case. It also works for \$C=0\$, matching it using ECMAScript NPCG (unset/non-participating capture group) behavior – every assertion becomes \0ドル \equiv 0 \pmod 0\$ and passes.

Assuming \$A>1\$, these can be simplified into:

\$\begin{aligned}C &\equiv 0 \pmod A \\ C &\equiv 1 \pmod {A-1}\end{aligned}\$

We now have two coprime moduli, \$A\$ and \$A-1\$. By the Chinese remainder theorem, there is one and only one integer \$E\$ such that \0ドル \le E < A(A-1)\$ and the above moduli are satisfied. That applies to any window of the same length, so we can change it to \$A < E \le A^2\$.

\$A^2-A=(A-1)A\$ shows there is at least one \$E\$ satisfying the moduli: \$E=A^2\$. The Chinese remainder theorem shows that there is exactly one \$E\$ satisfying the moduli within a certain range. Thus, if we restrict our search to the range \$A < E \le A^2\$, the only value matching both moduli will be \$E=A^2\$.

The first thing the regex does is (x(x*)|) which subtracts \$A\$ from \$C\$, so instead of directly searching for a matching \$E\$, it is searching for a matching \$E-A\$.

(1円*)2円+$ will first attempt a match using the largest possible number of repetitions of 1円. Since we already asserted 1円*$, this will bring us exactly to $. But then there will be no room for 2円+, which is required to have a positive repetition count due to the +. So then it starts trying smaller repetition counts for 1円, giving 2円+ more space in incremental steps of 1円, thus resulting in incrementally larger repetition counts for 2円. Note that 1円\$=A\$ and 2円\$=A-1\$. So a successful match of 2円+$ represents a value of \$E-A\$ such that \$E-A \equiv 0 \pmod A\$ and \$E-A \equiv 0 \pmod {A-1}\$.

The regex essentially searches for the smallest \$A-1 \le E-A \le C-A\$ satisfying the moduli, or alternatively stated, the smallest \2ドルA-1 \le E \le C\$ satisfying the moduli. Thus, even if \$C > A^2\$, the first matching \$E\$ it finds will be \$E=A^2\$. Note that the range only had to be restricted to \$A < E\$ via the Chinese remainder theorem, and the regex restricts it to \2ドルA-1 \le E\$ which is a subset of that range.

If no match is found, then \$C < A^2\$ and we get a non-match. If a match is found, and if \$E-A=C-A\$, then the 1円 in (1円*) will have a repetition count of zero, and 3円 will capture a value of zero. The regex asserts that \$E=C\$ by asserting that 3円 has a value of zero; if this matches, then \$C=A^2\$ and is indeed a perfect square.

Note that in no point in this reasoning did it matter what the value of \$A\$ is. It will only match if \$A^2=C\$. Thus, it doesn't matter whether we search for a matching \$A\$ from smallest to largest or largest to smallest. The regex does the latter, starting at \$A=C\$ and going downward from there in decrements of \1ドル\$.

Regex (ECMAScript / Python or better), 30 bytes

^(x(x*))(?=(1円*)2円+$)1円*$3円|^$

Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - fast)
Try it online! - Perl
Try it online! - Java
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE (fastest)
Try it online! - .NET

This is a port of the 28 byte version, dropping the dependence on ECMAScript NPCG behavior. Matching \0ドル^2\$ is done as a special case, the ^$ alternative at the end.

Regex (Perl / Java / PCRE / .NET), 12 bytes

^(1円xx|^x)*$

Try it online! - Perl (fastest)
Try it online! - Java
Try it online! - PCRE (fast)
Try it online! - .NET (slowest)

This works by exploiting the fact that \$(N+1)^2-N^2=2N+1\$, i.e. the differences between consecutive squares are consecutive odd numbers. The loop is initialized by subtracting \1ドル\$ from tail, which then captures 1円=\1ドル\$. Every subsequent iteration sets 1円\$=\$1円\$+2\$ and subtracts 1円 from tail. As a result, the cumulative subtraction from tail is at every step a perfect square, and the $ will only match at the end if the subtraction culminates in tail equaling zero, meaning the initial value of tail before the loop started was a perfect square.

As such, this regex relies on being able to read the last captured value of group 1 from inside group 1 – a nested backreference, which is a feature not supported by the ECMAScript, Python, or Ruby regex engines.

In this post by primo, it is explained how to extend this method to higher powers and polynomials.

An alternative 12 byte form is (1円xx|^x?)+$, but this breaks some nice properties of the form shown above. Most notably, it breaks letting the loop iteration count equal the square root of the number being matched. One of the beauties of keeping that property is that we can return the square root, for example using .NET's balanced groups feature (25 bytes):

^(?=(1円xx|^x)*$)(?<-1>x)*

Try it online! - .NET

Or using group-building with a branch reset group (19 bytes):

^(?|1円(1円x)|^(x))*$

Try it online! - Perl
Try it online! - PCRE

Regex (Python^regex / Ruby or better), 22 bytes

^((?=(3円xx|^x))(2円))*$

Try it online! - Python _{^{import regex}}
Try it online! - Ruby

In regex flavors with no support for nested backreferences, that feature must be emulated via forward-declared backreferences (which aren't supported either by ECMAScript or Python's built-in re module). This is done here by copying back and forth between 2円 and 3円.