Regex (ECMAScript+(?*)), (削除) 1169 (削除ここまで) (削除) 929 (削除ここまで) (削除) 887 (削除ここまで) (削除) 853 (削除ここまで) 849 bytes
Regex was never designed to do mathematics. It has no concept of arithmetic. However, when input is taken in the form of bijective unary, as a sequence of identical characters in which the length represents a natural number, it is possible to do a wide range of operations, building up from the simple primitives available, which basically amount to addition, comparison, multiplication by a constant, and modulo. Everything must fit inside the input; it isn't possible to directly operate on numbers larger than that.
In ECMAScript regex, it's especially difficult (and therefore interesting) to do even some of the simplest of operations, because of the limitation that all backrefs captured in a loop are reset to empty at the beginning of each iteration – which makes it impossible to count anything directly. It's nevertheless possible to match prime numbers, powers of N, Nth powers, arbitrary multiplication and exponentiation, Fibonacci numbers, factorial numbers, abundant numbers, and more, much of which is demonstrated in my other answers.
One of the operations that turns out to be far more verbose than the rest is to "calculate an irrational number". I initially discussed this with teukon back in 2014. The only known way to do this is to emulate operations on numbers larger than the input, and probably the simplest way to do this is by working in a number base chosen based on what can fit into the input.
It wasn't until late 2018 that I finally set about to implementing the theory I had sketched in 2014. Implementing it involved adapting the multiplication algorithm to work with factors of 0, which turned out to golf rather elegantly. (The underlying multiplication algorithm is explained in this post.) The basic algorithm is this:
For input \$N\$, we want to calculate \$M=\lfloor{N\over\sqrt2}\rfloor\$. So we want the largest \$M\$ such that \2ドルM^2\le N^2\$.
If we take the "number base" to be \$k=\lceil\sqrt N\rceil\$ or \$\lfloor\sqrt N\rfloor\!+\!1\$, all multiplication operations \$m\cdot n\$ on \0ドル\leq m,n\leq k\$ are guaranteed to fit in the available space.
So if \$N=A k+B\$, where \0ドル\leq A,B\lt k\$, we can calculate \$N^2\$:
$$N^2=(A k+B)^2=A^2 k^2+2 A B k+B^2$$
We must then do division, modulo, and carry to bring \$A^2\$, \2ドル A B\$, and \$B^2\$ back into the range of a base \$k\$ "digit". A similar operation is then done to calculate \2ドル M^2\$ iterated over the decreasing consecutive possible values of \$M\$, using digit-by-digit comparison to test for \2ドルM^2\le N^2\$, until the first \$M\$ is found that passes the test.
So while the basic concept is simple enough, it adds up to a lot of calculations, and the regex is huge! And this is probably the simplest calculation of an irrational number that can be done in ECMAScript regex. (It is still unknown whether it's possible to calculate a transcendental number to arbitrary precision in regex.)
This regex uses molecular lookahead, a.k.a. non-atomic lookahead, represented as (?*...). Without this feature, it would be much harder (or at least much more verbose) to implement.
Note that there is one departure from pure code golf in this version of the regex. I chose to use \$k=\lceil\sqrt N\rceil\$ because it has the very neat property of making the calculations fit perfectly into \$N\$ if \$N\$ is a perfect square, whereas \$k=\lfloor\sqrt N\rfloor\!+\!1\$ is basically chaotic for all inputs. They both yield the same final outputs, but the former is just cleaner. This only involved increasing the total length of the regex by 8 bytes, so I figured it was worth it. This change is in the git version history.
(?=(x(x*))(x)*(?=1円*$)2円+$)(?=(x(2円3円))+(x?(x*)))(?=6円(x(x*))(?=8円*$)5円9円*$)(?=.*(?=(?=6円*$)6円7円+$)(x*?)(?=4円*$)(x?(x*))(?=11円*$)((?=5円+$)5円12円*$|$11円))(?=.*(?=(?=6円*$)(?=8円*$)(?=6円9円+$)8円7円+$|$6円)(x*?)(?=4円*$)(x?(x*))(?=15円*$)((?=5円+$)5円16円*$|$15円))(?=.*(?=14円14円11円$)(x*?)(?=4円*$)(x?(x*))(?=19円*$)((?=5円+$)5円20円*$|$19円))(?*.*?(?=((?=4円*(x?(x*)))23円(x(x*))(?=25円*$)5円26円*$)))(?=.*(?=25円*$)(25円26円+$))(?=.*(?=(?=23円*$)23円24円+$)(x*?)(?=4円*$)(x?(x*))(?=29円*$)((?=5円+$)5円30円*$|$29円))(?=.*(?=(?=23円*$)(?=25円*$)(?=23円26円+$)25円24円+$|$23円)(x*?)(?=4円*$)(x?(x*))(?=33円*$)((?=5円+$)5円34円*$|$33円))(?=.*(?=32円32円29円$)(x*?)(?=4円*$)(x?(x*))(?=37円*$)((?=5円+$)5円38円*$|$37円))(?=.*(?=28円28円)(?=4円*(x*))(5円(x)|))(?=.*(?=36円36円42円)(?=4円*(x*))(5円(x)|))(?=(?=(.*)15円15円19円(?=8円*$)8円9円+$)46円(x+|(?=.*(?!18円)43円|(?!.*(?!40円)10円).*(?=18円$)43円$))(27円33円33円37円){2}45円$)22円|x\B|
This regex is on GitHub with a full version history.
# Giving an input number N in the domain ^x*,ドル this regex returns floor(N / sqrt(2))
(?=
(x(x*)) # 1円 = will be the square root of the main number, rounded down; 2円 = 1円 - 1
(x)*(?=1円*$) # 3円 = tool to round up instead of down
2円+$
)
# Step 1: Calculate N*N in base ceil(sqrt(N))
(?=(x(2円3円))+(x?(x*))) # 4円 = 1円 + 3円 = ceil(sqrt(N)), the number base to work in; 5円 = 4円-1; 6円 = N % 4円; 7円 = 6円-1, or 0 if 6円==0
(?=
6円
(x(x*)) # 8円 = floor(N / 4円); 9円 = 8円-1
(?=8円*$) # we can skip the test for divisibility by 5円 because it's guaranteed that 5円 <= 8円
5円9円*$
)
(?=
.*
(?=
(?=6円*$) # tail = 6円 * 6円
6円7円+$
)
(x*?)(?=4円*$) # 10円 = (6円 * 6円) % 4,円 the base-4円 digit in place 0 of the result for N*N
(x?(x*)) # 11円 = floor((6円 * 6円) / 4円); 12円 = 11円-1, or 0 if 11円==0
(?=11円*$)
(
(?=5円+$)
5円12円*$
|
$11円 # must make a special case for 11円==0, because 5円 is nonzero
)
)
(?=
.*
(?=
(?=6円*$) # tail = 6円 * 8円; must do symmetric multiplication, because 6円 is occasionally 1 larger than 8円
(?=8円*$)
(?=6円9円+$)
8円7円+$
|
$6円 # must make a special case for 6円==0, because 8円 might not be 0
)
(x*?)(?=4円*$) # 14円 = (6円 * 8円) % 4円
(x?(x*)) # 15円 = floor((6円 * 8円) / 4円); 16円 = 15円-1, or 0 if 15円==0
(?=15円*$)
(
(?=5円+$)
5円16円*$
|
$15円 # must make a special case for 15円==0, because 5円 is nonzero
)
)
(?=
.*(?=14円14円11円$) # tail = 2 * 14円 + 11円
(x*?)(?=4円*$) # 18円 = (2 * 14円 + 11円) % 4,円 the base-4円 digit in place 1 of the result for N*N
(x?(x*)) # 19円 = floor((2 * 14円 + 11円) / 4円); 20円 = 19円-1, or 0 if 19円==0
(?=19円*$)
(
(?=5円+$)
5円20円*$
|
$19円 # must make a special case for 19円==0, because 5円 is nonzero
)
) # {8円*8円 + 2*15円 + 19円} = the base-4円 digit in place 2 of the result for N*N, which is allowed to exceed 4円 and will always do so;
# Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base 4円
(?*
.*? # Determine value of M with backtracking, starting with largest values first
(?=
( # 22円 = M
(?=4円*(x?(x*)))23円 # 23円 = M % 4円; 24円 = 23円-1, or 0 if 23円==0
(x(x*)) # 25円 = floor(M / 4円); 26円 = 25円-1
(?=25円*$) # we can skip the test for divisibility by 5,円 but I'm not sure why; TODO: figure out why this is
5円26円*$
)
)
)
(?=
.*
(?=25円*$)
(25円26円+$) # 27円 = 25円 * 25円
)
(?=
.*
(?=
(?=23円*$) # tail = 23円 * 23円
23円24円+$
)
(x*?)(?=4円*$) # 28円 = (23円 * 23円) % 4,円 the base-4円 digit in place 0 of the result for M*M
(x?(x*)) # 29円 = floor((23円 * 23円) / 4円); 30円 = 29円-1, or 0 if 29円==0
(?=29円*$)
(
(?=5円+$)
5円30円*$
|
$29円 # must make a special case for 29円==0, because 5円 is nonzero
)
)
(?=
.*
(?=
(?=23円*$) # tail = 23円 * 25円; must do symmetric multiplication, because 23円 is occasionally 1 larger than 25円
(?=25円*$)
(?=23円26円+$)
25円24円+$
|
$23円 # must make a special case for 23円==0, because 25円 might not be 0
)
(x*?)(?=4円*$) # 32円 = (23円 * 25円) % 4円
(x?(x*)) # 33円 = floor((23円 * 25円) / 4円); 34円 = 33円-1, or 0 if 33円==0
(?=33円*$)
(
(?=5円+$)
5円34円*$
|
$33円 # must make a special case for 33円==0, because 5円 is nonzero
)
)
(?=
.*(?=32円32円29円$) # tail = 2 * 32円 + 29円
(x*?)(?=4円*$) # 36円 = (2 * 32円 + 29円) % 4,円 the base-4円 digit in place 1 of the result for M*M
(x?(x*)) # 37円 = floor((2 * 32円 + 29円) / 4円); 38円 = 37円-1, or 0 if 37円==0
(?=37円*$)
(
(?=5円+$)
5円38円*$
|
$37円 # must make a special case for 37円==0, because 5円 is nonzero
)
) # {27円 + 2*33円 + 37円} = the base-4円 digit in place 2 of the result for M*M, which is allowed to exceed 4円 and will always do so
# Step 2b: Calculate 2*M*M in base 4円
(?=
.*
(?=28円28円) # tail = 2*28円
(?=4円*(x*)) # 40円 = (2*28円) % 4,円 the base-4円 digit in place 0 of the result for 2*M*M
(5円(x)|) # 42円 = floor((2*28円) / 4円) == +1 carry if {2*28円} does not fit in a base 4円 digit
)
(?=
.*
(?=36円36円42円) # tail = 2*36円 + 42円
(?=4円*(x*)) # 43円 = (2*36円 + 42円) % 4,円 the base-4円 digit in place 1 of the result for 2*M*M
(5円(x)|) # 45円 = floor((2*36円 + 42円) / 4円) == +1 carry if {2*36円 + 42円} does not fit in a base 4円 digit
) # 2*(27円 + 2*33円 + 37円) + 45円 = the base-4円 digit in place 2 of the result for 2*M*M, which is allowed to exceed 4円 and will always do so
# Step 2c: Require that 2*M*M <= N*N
(?=
(?=
(.*) # 46円
15円15円19円
(?=8円*$) # tail = 8円 * 8円
8円9円+$
)
46円 # tail = {8円*8円 + 2*15円 + 19円}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
(
x+
|
(?=
.*(?!18円)43円 # 43円 < 18円
|
(?!.*(?!40円)10円) # 40円 <= 10円
.*(?=18円$)43円$ # 43円 == 18円
)
)
(27円33円33円37円){2}45円$ # 2*(27円 + 2*33円 + 37円) + 45円
)
22円
|x\B| # handle inputs in the domain ^x{0,2}$
Regex (ECMAScript 2018), 861 bytes
This is a direct port of the 849 byte molecular lookahead version, using variable length lookbehind.
(?=(x(x*))(x)*(?=1円*$)2円+$)(?=(x(2円3円))+(x?(x*)))(?=6円(x(x*))(?=8円*$)5円9円*$)(?=.*(?=(?=6円*$)6円7円+$)(x*?)(?=4円*$)(x?(x*))(?=11円*$)((?=5円+$)5円12円*$|$11円))(?=.*(?=(?=6円*$)(?=8円*$)(?=6円9円+$)8円7円+$|$6円)(x*?)(?=4円*$)(x?(x*))(?=15円*$)((?=5円+$)5円16円*$|$15円))(?=.*(?=14円14円11円$)(x*?)(?=4円*$)(x?(x*))(?=19円*$)((?=5円+$)5円20円*$|$19円))(?=.*?(?=((?=4円*(x?(x*)))23円(x(x*))(?=25円*$)5円26円*$))(?<=(?=(?=.*(?=25円*$)(25円26円+$))(?=.*(?=(?=23円*$)23円24円+$)(x*?)(?=4円*$)(x?(x*))(?=29円*$)((?=5円+$)5円30円*$|$29円))(?=.*(?=(?=23円*$)(?=25円*$)(?=23円26円+$)25円24円+$|$23円)(x*?)(?=4円*$)(x?(x*))(?=33円*$)((?=5円+$)5円34円*$|$33円))(?=.*(?=32円32円29円$)(x*?)(?=4円*$)(x?(x*))(?=37円*$)((?=5円+$)5円38円*$|$37円))(?=.*(?=28円28円)(?=4円*(x*))(5円(x)|))(?=.*(?=36円36円42円)(?=4円*(x*))(5円(x)|))(?=(?=(.*)15円15円19円(?=8円*$)8円9円+$)46円(x+|(?=.*(?!18円)43円|(?!.*(?!40円)10円).*(?=18円$)43円$))(27円33円33円37円){2}45円$))^.*))22円|x\B|
This regex is on GitHub.
# Giving an input number N in the domain ^x*,ドル this regex returns floor(N / sqrt(2))
(?=
(x(x*)) # 1円 = will be the square root of the main number, rounded down; 2円 = 1円 - 1
(x)*(?=1円*$) # 3円 = tool to round up instead of down
2円+$
)
# Step 1: Calculate N*N in base ceil(sqrt(N))
(?=(x(2円3円))+(x?(x*))) # 4円 = 1円 + 3円 = ceil(sqrt(N)), the number base to work in; 5円 = 4円-1; 6円 = N % 4円; 7円 = 6円-1, or 0 if 6円==0
(?=
6円
(x(x*)) # 8円 = floor(N / 4円); 9円 = 8円-1
(?=8円*$) # we can skip the test for divisibility by 5円 because it's guaranteed that 5円 <= 8円
5円9円*$
)
(?=
.*
(?=
(?=6円*$) # tail = 6円 * 6円
6円7円+$
)
(x*?)(?=4円*$) # 10円 = (6円 * 6円) % 4,円 the base-4円 digit in place 0 of the result for N*N
(x?(x*)) # 11円 = floor((6円 * 6円) / 4円); 12円 = 11円-1, or 0 if 11円==0
(?=11円*$)
(
(?=5円+$)
5円12円*$
|
$11円 # must make a special case for 11円==0, because 5円 is nonzero
)
)
(?=
.*
(?=
(?=6円*$) # tail = 6円 * 8円; must do symmetric multiplication, because 6円 is occasionally 1 larger than 8円
(?=8円*$)
(?=6円9円+$)
8円7円+$
|
$6円 # must make a special case for 6円==0, because 8円 might not be 0
)
(x*?)(?=4円*$) # 14円 = (6円 * 8円) % 4円
(x?(x*)) # 15円 = floor((6円 * 8円) / 4円); 16円 = 15円-1, or 0 if 15円==0
(?=15円*$)
(
(?=5円+$)
5円16円*$
|
$15円 # must make a special case for 15円==0, because 5円 is nonzero
)
)
(?=
.*(?=14円14円11円$) # tail = 2 * 14円 + 11円
(x*?)(?=4円*$) # 18円 = (2 * 14円 + 11円) % 4,円 the base-4円 digit in place 1 of the result for N*N
(x?(x*)) # 19円 = floor((2 * 14円 + 11円) / 4円); 20円 = 19円-1, or 0 if 19円==0
(?=19円*$)
(
(?=5円+$)
5円20円*$
|
$19円 # must make a special case for 19円==0, because 5円 is nonzero
)
) # {8円*8円 + 2*15円 + 19円} = the base-4円 digit in place 2 of the result for N*N, which is allowed to exceed 4円 and will always do so;
# Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base 4円
(?=
.*? # Determine value of M with backtracking, starting with largest values first
(?=
( # 22円 = M
(?=4円*(x?(x*)))23円 # 23円 = M % 4円; 24円 = 23円-1, or 0 if 23円==0
(x(x*)) # 25円 = floor(M / 4円); 26円 = 25円-1
(?=25円*$) # we can skip the test for divisibility by 5,円 but I'm not sure why; TODO: figure out why this is
5円26円*$
)
)
(?<= # emulate molecular lookahead for the above expressions
(?=
(?=
.*
(?=25円*$)
(25円26円+$) # 27円 = 25円 * 25円
)
(?=
.*
(?=
(?=23円*$) # tail = 23円 * 23円
23円24円+$
)
(x*?)(?=4円*$) # 28円 = (23円 * 23円) % 4,円 the base-4円 digit in place 0 of the result for M*M
(x?(x*)) # 29円 = floor((23円 * 23円) / 4円); 30円 = 29円-1, or 0 if 29円==0
(?=29円*$)
(
(?=5円+$)
5円30円*$
|
$29円 # must make a special case for 29円==0, because 5円 is nonzero
)
)
(?=
.*
(?=
(?=23円*$) # tail = 23円 * 25円; must do symmetric multiplication, because 23円 is occasionally 1 larger than 25円
(?=25円*$)
(?=23円26円+$)
25円24円+$
|
$23円 # must make a special case for 23円==0, because 25円 might not be 0
)
(x*?)(?=4円*$) # 32円 = (23円 * 25円) % 4円
(x?(x*)) # 33円 = floor((23円 * 25円) / 4円); 34円 = 33円-1, or 0 if 33円==0
(?=33円*$)
(
(?=5円+$)
5円34円*$
|
$33円 # must make a special case for 33円==0, because 5円 is nonzero
)
)
(?=
.*(?=32円32円29円$) # tail = 2 * 32円 + 29円
(x*?)(?=4円*$) # 36円 = (2 * 32円 + 29円) % 4,円 the base-4円 digit in place 1 of the result for M*M
(x?(x*)) # 37円 = floor((2 * 32円 + 29円) / 4円); 38円 = 37円-1, or 0 if 37円==0
(?=37円*$)
(
(?=5円+$)
5円38円*$
|
$37円 # must make a special case for 37円==0, because 5円 is nonzero
)
) # {27円 + 2*33円 + 37円} = the base-4円 digit in place 2 of the result for M*M, which is allowed to exceed 4円 and will always do so
# Step 2b: Calculate 2*M*M in base 4円
(?=
.*
(?=28円28円) # tail = 2*28円
(?=4円*(x*)) # 40円 = (2*28円) % 4,円 the base-4円 digit in place 0 of the result for 2*M*M
(5円(x)|) # 42円 = floor((2*28円) / 4円) == +1 carry if {2*28円} does not fit in a base 4円 digit
)
(?=
.*
(?=36円36円42円) # tail = 2*36円 + 42円
(?=4円*(x*)) # 43円 = (2*36円 + 42円) % 4,円 the base-4円 digit in place 1 of the result for 2*M*M
(5円(x)|) # 45円 = floor((2*36円 + 42円) / 4円) == +1 carry if {2*36円 + 42円} does not fit in a base 4円 digit
) # 2*(27円 + 2*33円 + 37円) + 45円 = the base-4円 digit in place 2 of the result for 2*M*M, which is allowed to exceed 4円 and will always do so
# Step 2c: Require that 2*M*M <= N*N
(?=
(?=
(.*) # 46円
15円15円19円
(?=8円*$) # tail = 8円 * 8円
8円9円+$
)
46円 # tail = {8円*8円 + 2*15円 + 19円}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
(
x+
|
(?=
.*(?!18円)43円 # 43円 < 18円
|
(?!.*(?!40円)10円) # 40円 <= 10円
.*(?=18円$)43円$ # 43円 == 18円
)
)
(27円33円33円37円){2}45円$ # 2*(27円 + 2*33円 + 37円) + 45円
)
)
^.* # emulate molecular lookahead
)
)
22円
|x\B| # handle inputs in the domain ^x{0,2}$
Regex (ECMAScript)
I have not yet ported this algorithm to basic ECMAScript. One way to do it would be to use \$k=\lceil\sqrt[\uproot{1}3]N\rceil\$ as the number base, and calculate:
$$N^2=(A k^2+B k+C)^2=A^2 k^4 + 2 A B k^3 + (2 A C + B^2)k^2 + 2 B C k + C^2$$
Another way would be to stick with \$k=\lceil\sqrt N\rceil\$, capture \$M\$ encoded into two or more backrefs, and emulate the existing calculations within the smaller available space. I'm not sure which way would be more concise.
- 12.9k
- 2
- 71
- 55