Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
This is not a duplicate of Sum of combinations with repetition. This question considers 1+2 to be the same as 2+1. The other question doesn't.
If you have 4 types of coins (1, 2, 5 and 10 cents), in how many ways can you make an amount?
There are 4 ways of making 5 cents:
Note: 1 + 2 + 2 and 2 + 2 + 1 are considered to be the same in this challenge.
Saved 3 bytes thanks to @ovs
f=(n,k=10)=>n?k*n>0&&f(n,k>>1)+f(n-k,k):1
Suggested by @tsh
Returns true for \$f(0)\$.
f=(n,k=10)=>n>0?k&&f(n,k>>1)+f(n-k,k):!n
f = ( // f is a recursive function taking:
n, // n = input
k = 10 // k = current coin value
) => //
n ? // if n is not equal to 0:
k * n > 0 && // if k is not equal to 0 and n is positive:
f(n, k >> 1) + // do a recursive call where k is updated to the
// next coin value
f(n - k, k) // do a recursive call where k is subtracted from n
: // else:
1 // increment the number of solutions
k=10, and updating to k/2|0 is a bit shorter ;)
\$\endgroup\$
Ṅ₀$ḊvΠ∑
Try it Online! 6 bytes with s flag
Ṅ₀$ḊvΠ∑
Ṅ # Integer partitions of the input
₀$Ḋ # Does each item in each partition divide 10?
vΠ # Product of each partition
∑ # Sum that
v. Why does M not do this?
\$\endgroup\$
Sep 5, 2022 at 13:14
M requires a function object on the stack (you'd need something like ⁽ΠM or λΠ;M), while v takes the next element like a quick in Jelly would
\$\endgroup\$
rs: Ṅ₀ḊvΠ
\$\endgroup\$
🐇 (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 xs. 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
Œṗḍ⁵ẠƇL
A monadic Link that accepts a positive integer and yields a positive integer.
Œṗḍ⁵ẠƇL - Link: integer, Cents e.g. 4
Œṗ - integer partitions of Cents [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]
⁵ - ten 10
ḍ - divides? (vectorises) [[1,1,1,1],[1,1,1],[1,0],[1,1],[0]]
Ƈ - keep those for which:
Ạ - all? [[1,1,1,1],[1,1,1], [1,1] ]
L - length 3
f=lambda s,n=4:s==0 or s>=0<n and f(s,n-1)+f(s-(1,2,5,10)[n-1],n)
-5 thanks to Jo King -41 thanks to Kevin Cruijssen
and and or.
\$\endgroup\$
Sep 5, 2022 at 17:41
f=lambda n,k=10:k*n>0and f(n-k,k)+f(n,k/2)or n==0
Conveniently, we can iterate through the count value by starting at 10 and floor-dividing by 2 to get 10->5->2->1 and terminating at 0.
Ｎθ⊞υ⁰Ｆ9410ＦυＦ‹κθ⊞υ⁺κ⊕ιＩ№υθ
Try it online! Link is to verbose version of code. Explanation:
Ｎθ
Input n.
⊞υ⁰
Start with 0 as a possible amount.
Ｆ9410
Loop over the digits 9, 4, 1, and 0, which will later be incremented to represent the coins 10, 5, 2 and 1.
Ｆυ
Loop over each possible amount discovered so far.
Ｆ‹κθ
If this amount is less than n, then...
⊞υ⁺κ⊕ι
... add the current coin to the amount, and record this as a new possible amount. This then allows it to be considered again as a possible amount for the current coin, until the value reaches or exceeds n.
Ｉ№υθ
Count the number of times n was reached.
Example for n=5:
0 as an amount.10 to that, resulting in a new amount of 10. This amount is now more than 5, so it is ignored.5 to the 0 amount, resulting in a new amount of 5. This amount is also ignored for now.2 to the 0 amount, resulting in a new amount of 2.2 to the 2 amount, resulting in a new amount of 4.2 to the 4 amount, resulting in a new amount of 6. This amount is now more than 5, so it is ignored.1 to the 0, 2 and 4 amounts, resulting in new amounts of 1, 3 and 5. The 5 amount is ignored for now.1 to the 1 and 3 amounts, resulting in new amounts of 2 and 4.1 to the 2 and 4 amounts, resulting in new amounts of 3 and 5.1 to the 3 amount, resulting in a new amount of 4.1 to the 4 amount, resulting in a new amount of 5.5s is 4 as desired.4 5s correspond to the sums 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1 respectively.The coins are considered in descending order for efficiency but the algorithm would work with the coins in any order.
ÅœʒTÑsåP}g
A modification of Mr.Xcoder's 05AB1E answer in the related challenge would be 1 byte longer (and way slower):
TÑIиæ€{ÙOI¢
Try it online. (Too slow for TIO for \$n\ge4\$.)
Explanation:
Ŝ # Get all lists of positive integers that sum to the (implicit) input
ʒ # Filter this list of lists by:
# (implicitly push the current list)
TÑ # Push the divisors of 10: [1,2,5,10]
s # Swap so the current list is at the top of the stack
å # Check for each value whether it's in list [1,2,5,10]
P # Check if it's truthy for all of them by taking the product
}g # After the filter: pop and push the length
# (which is output implicitly as result)
TÑ # Push list [1,2,5,10]
Iи # Repeat it the input amount of times: [1,2,5,10,1,2,5,10,...]
æ # Get the powerset of this list
€{ # Sort each inner list
Ù # Uniquify the list of lists
O # Sum each inner list
I¢ # Count how many times the input occurs in the list
# (which is output implicitly as result)
f=->n,k=10{n<0||k<1?0:n<1?1:f[n-k,k]+f[n,k/2]}
Shamelessly inspired by Arnauld's Javascript answer.
f(n)=1+∑_{k=1}^{n^4}0^{(n-∑_{j=1}^4[1,2,5,10][j]mod(floor(nk/n^j),n))^2}
Inspired by @fireflame's Desmos answer to How many partitions do I have?
N+K+M:-K*N>0,N-K+K+Q,N+K//2+W,M is Q+W;N=:=0,M=1;M=0.
N+M:-N+10+M.
Port of xnor's Python answer.
Golfed version. Try it online!
def f(n:Int,p:Seq[Int]=Seq(1,2,5,10)):Int=(n,p)match{case(0,_)=>1;case(_,Nil)=>0;case(_,k::ks)=>if(n<k)0 else f(n-k,k::ks)+f(n,ks)}
Ungolfed version. Try it online!
object Main {
def a000008(n: Int): Int = {
val coins = List(1, 2, 5, 10)
def p(ks: List[Int], m: Int): Int = (ks, m) match {
case (_, 0) => 1
case (Nil, _) => 0
case (k :: ksTail, _) if m < k => 0
case (ksHead :: ksTail, _) => p(ksHead :: ksTail, m - ksHead) + p(ksTail, m)
}
p(coins, n)
}
def main(args: Array[String]): Unit = {
for (n <- 1 to 20) {
println(s"p($n) = ${a000008(n)}")
}
}
}
