6
\$\begingroup\$

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.


OEIS link - A000008


Background

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:

  • 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 2
  • 1 + 2 + 2
  • 5

Note: 1 + 2 + 2 and 2 + 2 + 1 are considered to be the same in this challenge.

Your task

  • Take an input. It will be a positive integer. This is the amount (in cents).
  • Work out the number of ways to make that number from 1, 2, 5 and 10 cent coins.
  • This is a challenge, so any form of output is allowed.
  • This is , so shortest answer in bytes wins.
\$\endgroup\$
3
  • \$\begingroup\$ Who has 2 cent coins? :P \$\endgroup\$
    – Seggan
    Commented Sep 17, 2022 at 18:44
  • \$\begingroup\$ @Seggan, here in the UK we have a 1-2-5 system. It goes 1p, 2p, 5p, 10p, 20p, 50p. But yes, it's not there everywhere. On the OEIS sequence it said 1, 2, 5 and 10, so I just used those values. Also, it probably makes the challenge easier, as 1, 2, 5 and 10 are the only factors of 10. \$\endgroup\$
    – The Thonnu
    Commented Sep 17, 2022 at 19:27
  • \$\begingroup\$ Lol that was meant as a joke. But good points \$\endgroup\$
    – Seggan
    Commented Sep 17, 2022 at 21:26

14 Answers 14

6
\$\begingroup\$

JavaScript (ES6), 41 bytes

Saved 3 bytes thanks to @ovs

f=(n,k=10)=>n?k*n>0&&f(n,k>>1)+f(n-k,k):1

Try it online!

40 bytes

Suggested by @tsh

Returns true for \$f(0)\$.

f=(n,k=10)=>n>0?k&&f(n,k>>1)+f(n-k,k):!n

Try it online!

Commented

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
\$\endgroup\$
3
  • \$\begingroup\$ Fancy formula, but I think starting at k=10, and updating to k/2|0 is a bit shorter ;) \$\endgroup\$
    – ovs
    Commented Sep 5, 2022 at 11:08
  • \$\begingroup\$ @ovs Err ... Yes. Definitely! :-) \$\endgroup\$
    – Arnauld
    Commented Sep 5, 2022 at 11:11
  • \$\begingroup\$ f=(n,k=10)=>n>0?k&&f(n,k>>1)+f(n-k,k):!n \$\endgroup\$
    – tsh
    Commented Sep 6, 2022 at 9:52
5
\$\begingroup\$

Vyxal, 12 8 7 bytes

Ṅ₀$ḊvΠ∑

Try it Online! 6 bytes with s flag

Explained

Ṅ₀$ḊvΠ∑
Ṅ       # Integer partitions of the input
 ₀$Ḋ    # Does each item in each partition divide 10?
    vΠ  # Product of each partition
      ∑ # Sum that
\$\endgroup\$
4
  • \$\begingroup\$ I was just trying to figure out how to do it like this, searching the docs for something like v. Why does M not do this? \$\endgroup\$ Commented Sep 5, 2022 at 13:14
  • \$\begingroup\$ @JonathanAllan Because 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\$
    – lyxal
    Commented Sep 5, 2022 at 13:18
  • \$\begingroup\$ Oh, I see thanks for enlightening me. \$\endgroup\$ Commented Sep 5, 2022 at 13:21
  • \$\begingroup\$ This could even be 5 bytes with rs: Ṅ₀ḊvΠ \$\endgroup\$
    – naffetS
    Commented Sep 5, 2022 at 17:16
4
\$\begingroup\$

HOPS, 20 bytes

mset(x+x^2+x^5+x^10)

Attempt This Online!

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

Length[{1,2,5,10}~FrobeniusSolve~#]&

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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 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

\$\endgroup\$
3
\$\begingroup\$

Jelly, 7 bytes

Œṗḍ⁵ẠƇL

A monadic Link that accepts a positive integer and yields a positive integer.

Try it online!

How?

Œṗḍ⁵ẠƇ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
\$\endgroup\$
3
\$\begingroup\$

Python, 111 106 65 bytes

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)

Try it online!

-5 thanks to Jo King -41 thanks to Kevin Cruijssen

\$\endgroup\$
3
2
\$\begingroup\$

Python 2, 49 bytes

f=lambda n,k=10:k*n>0and f(n-k,k)+f(n,k/2)or n==0

Try it online!

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 26 bytes

Nθ⊞υ⁰F9410FυF‹κθ⊞υ⁺κ⊕ιI№υθ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

⊞υ⁰

Start with 0 as a possible amount.

F9410

Loop over the digits 9, 4, 1, and 0, which will later be incremented to represent the coins 10, 5, 2 and 1.

Fυ

Loop over each possible amount discovered so far.

F‹κθ

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.

I№υθ

Count the number of times n was reached.

Example for n=5:

  • Start with 0 as an amount.
  • Add 10 to that, resulting in a new amount of 10. This amount is now more than 5, so it is ignored.
  • Add 5 to the 0 amount, resulting in a new amount of 5. This amount is also ignored for now.
  • Add 2 to the 0 amount, resulting in a new amount of 2.
  • Add 2 to the 2 amount, resulting in a new amount of 4.
  • Add 2 to the 4 amount, resulting in a new amount of 6. This amount is now more than 5, so it is ignored.
  • Add 1 to the 0, 2 and 4 amounts, resulting in new amounts of 1, 3 and 5. The 5 amount is ignored for now.
  • Add 1 to the 1 and 3 amounts, resulting in new amounts of 2 and 4.
  • Add 1 to the 2 and 4 amounts, resulting in new amounts of 3 and 5.
  • Add 1 to the 3 amount, resulting in a new amount of 4.
  • Add 1 to the 4 amount, resulting in a new amount of 5.
  • There are no more coins, so the final count of 5s is 4 as desired.
  • The 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.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 13 10 bytes

ÅœʒTÑsåP}g

Try it online.

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)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 46 bytes

f=->n,k=10{n<0||k<1?0:n<1?1:f[n-k,k]+f[n,k/2]}

Try it online!

Shamelessly inspired by Arnauld's Javascript answer.

\$\endgroup\$
1
\$\begingroup\$

Desmos, 76 bytes

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?

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
1
\$\begingroup\$

Prolog (SWI), 66 bytes

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.

Try it online!

Port of xnor's Python answer.

\$\endgroup\$
1
\$\begingroup\$

Scala, 131 bytes

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)}")
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.