Regex 🐇
(Perl/PCRE+(?^=)
RME), 32 28 bytes
^((?^=(\2?x))(\1|^x)x*)+,\2$
Try it on replit.com (RegexMathEngine)
Takes its input in unary, as the lengths of two strings of x
s delimited by a ,
, specifying \$(n,k)\$. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)
This simply enumerates all the partitions. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary-sized partition on the first iteration, then increasing it by an arbitrary nonnegative integer on each subsequent iteration. Each iteration increments the counter, which is then compared with \$k\$ at the end.
On each iteration, the size of the partition (arbitrarily chosen) is captured in \1
, which is accessed via a nested backreference. The counter is stored in \2
. Lookinto is used to ensure there is room to read and increment \2
on each iteration.
^ # tail = N
( # \1 = the following, looping:
(?^= # Lookinto; tail = N
( # \2 = sum of the following:
\2? # previous value of \2 if set, else 0
x # 1
)
)
# \1 = the sum of the below items
(
\1 # On subsequent iterations, \1
|
^x # On the first iteration, 1
)
x* # any nonnegative integer
# \1 = some of the above items
)+ # Iterate the above as many times as possible, min 1
, # Assert tail == 0; tail = K
\2$ # Assert tail == \2
This uses nested backreferences (supported by Java / Perl / PCRE / .NET), a branch reset group (Perl / PCRE / Pythonregex
), and a lookinto, a feature just added to RegexMathEngine. The parameterless form of it, (?^=pattern)
, is equivalent to one of the common uses of variable-length lookbehind, (?<=(?=pattern)^.*)
– it allows matching against the entire string, even after the top-level cursor has advanced past the start. It also has a parametrized form, e.g. (?^5=pattern)
will match pattern
against the current contents of \5
.
Regex 🐇
(RME / Perl / PCRE2 v10.35+), 36 34 bytes
^((?|(?=.*,(\2x))\1x*|^(x)+))+,\2$
Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - PCRE2 v10.40+ - test cases only
Without lookinto, there's still always room within \$k\$, accesible via lookahead, to count iterations.
Starting with a positive arbitrary-sized partition on the first iteration is done by ^(x)+
, which also initializes the counter to \$1\$. On subsequent iterations, \1x*
advances by the sum of \1
and any arbitrary nonnegative integer, which also gets captured in \1
. At the end, ,
asserts that the cumulative sum is equal to \$n\$.
To enforce \$k\$ as the number of partitions, it starts by setting \2
\$=1\$ on the first iteration with ^(x)+
. On subsequent iterations, (?^=(\2x))
increments \2
by \$1\$. Lookahead is used to avoid not having room for \2
\$+1\$ when nearing the end of \$n\$. The Branch Reset Group (?|
...|
...)
allows \2
to be captured/recaptured in these two places.
^ # tail = N
( # \1 = the following, looping:
(?| # Branch Reset Group
# This alternative can only match on iterations after the first, because
# it unconditionally matches \1 and \2.
(?= # Lookahead
.*, # tail = K
(\2x) # \2 += 1
)
\1x* # \1 += {any nonnegative integer}; tail -= \1
|
^ # Anchor to start, to only match on the first iteration.
(x)+ # \2 = 1; \1 = {any nonnegative integer}; tail -= \1
)
)+ # Iterate the above as many times as possible, min 1
, # Assert tail == 0; tail = K
\2$ # Assert tail == \2
Regex 🐇
(RME / Perl / PCRE2), 50 bytes
^((?=(?(3)(\3)))((?|(?=.*,(\4x))\2x*|^(x)+)))+,\4$
Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - PCRE2 v10.40+ - test cases only
PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied back and forth between \2
and \3
using only forward-declared backreferences.
This would also make the regex compatible with Pythonregex
and Ruby, but they have no way of doing 🐇
output without source code modifications.
It still doesn't work under PCRE1, probably due to its bug where in certain conditions, captures are not reverted to their earlier values when backtracking: Try it online!
^ # tail = N
( # \1 = the following, looping:
(?=
(?(3)(\3)) # If \3 is set, \2 = \3, else leave \2 unset
)
( # \3 = the following, to avoid a nested backreference
(?| # Branch Reset Group
# This alternative can only match on iterations after the first,
# because it unconditionally matches \1 and \2.
(?=
.*, # tail = K
(\4x) # \4 += 1
)
\2x* # \3 = \2 + {any nonnegative integer}; tail -= \3
|
^ # Anchor to start, to only match on the first iteration.
(x)+ # \4 = 1; \3 = {any nonnegative integer}; tail -= \3
)
)
)+ # Iterate the above as many times as possible, min 1
, # Assert tail == 0; tail = K
\4$ # Assert tail == \4
8
instead of7
. \$\endgroup\$