Regex 🐇
(RME / Perl / PCRE / Raku:P5
), 24 bytes
^x*(xx)*(x{5})*(x{10})*$
Takes its input in unary, as the length of a string of x
s. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)
Try it on replit.com! - RegexMathEngine
Try it online! - Perl
Try it online! - PCRE
Try it online! - Raku
It's also possible to use Arnauld's algorithm, but only for inputs \$≥ 10\$ (because captures are the only kind of variable available, and can only be taken from the input). Even using lookinto, this is pretty long at 42 bytes (and would be longer using variable-length lookbehind):
^(?|(?^1=(x+)\1){0,3}\1|^(?=(x{10}))){2,}$
Try it on replit.com! - RegexMathEngine
^ # tail = input number
(?|
(?^1=(x+)\1) # Assert \1 is set; \1 = floor(\1 / 2);
# assert the resulting \1 ≥ 1
{0,3} # Iterate the above 0 to 3 times
\1 # tail -= \1
| # or
^(?=(x{10})) # If on the first iteration, \1 = 10. This can be
# matched multiple times in a row, as long as nothing
# has been subtracted from tail yet, but that would
# result in a non-match when exiting this loop.
){2,} # Iterate the above at least 2 times, with no maximum.
# This allows the first alternative to get a chance to
# match after the second alternative, which is zero-
# width, has matched.
$ # Assert tail == 0
That can be made to work with all inputs by extending it to 49 bytes: ^(?|(?^1=(x+)\1){0,3}\1|^(?=((x{5}|x)\2?)|)){2,}$
- but this defeats the purpose of the 42 byte version in the first place, because if \$10\$ is not the only constant specified, you might as well go with the 24 byte version.
But it is possible to use this algorithm in its pure form (with no constants specified other than \$10\$ and \$\lfloor\log_2{10}\rfloor\$) in such a way that works for all inputs, by capturing \$10\$ in binary (89 bytes):
^(?|(?=(?=(\2))(?=(\3))(\4)()){0,3}(\1\2\2\3{4}\4{8})(?!.*$\5)|^(?=(?=()(x))()(x)|)){2,}$
Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - RegexMathEngine in PCRE mode
^ # tail = N = input number
(?| # Branch reset group - capture group numbering of each
# alternative starts at the same number, in this case \1.
(?=
# coinValue /= 2, where coinValue is defined as \1 + \2*2 + \3*4 + \4*8
(?=(\2)) # \1 = \2
(?=(\3)) # \2 = \3
(\4)() # \3 = \4; \4 = 0
){0,3} # maximum number of iterations is floor(log(10) / log(2))
( # \5 = coinValue; tail -= \5
\1
\2\2
\3{4}
\4{8}
)
(?!.*$\5) # Assert \5 != 0
|
^ # Only take this alternative on the first iteration (or, as
# explained below, also the 2nd iteration, if N==0)
# coinValue = 10
(?= # Atomic lookahead
# This can only match if tail ≥ 1
(?=()(x)) # \1 = 0; \2 = 1
()(x) # \3 = 0; \4 = 1
| # or...
# Do nothing, if tail == 0; in this case, the 2nd iteration of the
# outer loop will also end up taking this alternative, and there will
# be exactly one way N==0 can result in a match.
)
){2,} # An enforced minimum of 2 iterations is necessary, because
# the first iteration always has zero width, and would cause
# the loop to end otherwise. (In Perl, not even this trick
# can force a loop to take more than one zero-width
# iteration.)
$ # Assert that tail == 0
For compatibility with old versions of PCRE2, it is necessary to use a 93 byte version of this:
Try it online! - PCRE2 v10.33