Perl, 63 60 59 57 bytes
Includes +2 for -pa
Give input parameters on STDIN
mnomial.pl <<< "3 5 6"
#!/usr/bin/perl -pa
$_=/-/^($_--,1x$F[2])=~/^(1{0,$_}){$F[1]}$(??{++$;})/+$
As a perl programmer I just know that every problem is really a regex in disguise...
Explanation:
m(3,5,6) can be seen as the number of ways you can get 6 by adding 5 integers in the range [0..2]
. You can write a regex matching such a partition using:
1 x 6 = /^(1{0,2}){5}$/
However once a single solution is found the regex stops. We need to fail the found solution to get the regex to backtrack to the next solution and count the failures. In perl this can be done by extending the regex at runtime with something that is sure to fail, e.g. by demanding that something comes after the end of the string:
1 x 6 = /^(1{0,2}){5}$(??{++$n})/
$n will count the number of failed attempts
My solution is basically this with two modifications:
- Output the counter in such a way that you get
0
instead of the empty string if there is no valid partition and the counter never gets incremented
- If the third argument is negative it would work if negative string lengths existed, but 1 x -5 is the empty string and 0 can be written exactly one way as sum of zeros, so that would output 1 instead of 0. I xor with the result of
/-/
to change the 1 back to 0
Without the need to handle a negative third argument this 49 byte solution would be good enough (give one parameter of m(x,y,z)
on each line of STDIN in order y \n z \n x \n
):
#!/usr/bin/perl -pa
$_=(1x<>)=~/^(1{0,@{[<>-1]}}){@F}$(??{++$;})/+$
2It's strange that a negative exponent gives a result of zero, since it gives a nonzero power series. – xnor – 2016-04-23T23:39:33.023
Why is m(0,0,0)=1 ? Any m(0, x, y) should be based on a polynomial with NO terms (not even 1) so it's really out of range and should give 0 (I'd even count it as invalid input) – Ton Hospel – 2016-04-24T01:13:18.733
@TonHospel Sorry, thanks, edited. – Leaky Nun – 2016-04-24T01:15:33.413
Thematically related. – Martin Ender – 2016-04-25T09:19:43.600
@MartinBüttner If you are counting "thematically related" as related, then all [tag:arithmetic] and [tag:regex-golf] are related. – Leaky Nun – 2016-04-25T10:29:54.550
@KennyLau Both challenges are motivated by the same combinatorial problem, which I think makes them quite closely related. If someone is interested in either of them, they might be interested in the other. Barring a [tag:multinomial] tag, the best way to let people find them, is to post them in a comment, such that they show up as Linked in the sidebar. – Martin Ender – 2016-04-25T11:37:07.377