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
    Sep 17 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
    Sep 17 at 19:27
  • \$\begingroup\$ Lol that was meant as a joke. But good points \$\endgroup\$
    – Seggan
    Sep 17 at 21:26

13 Answers 13

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
    Sep 5 at 11:08
  • \$\begingroup\$ @ovs Err ... Yes. Definitely! :-) \$\endgroup\$
    – Arnauld
    Sep 5 at 11:11
  • \$\begingroup\$ f=(n,k=10)=>n>0?k&&f(n,k>>1)+f(n-k,k):!n \$\endgroup\$
    – tsh
    Sep 6 at 9:52
4
\$\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\$ Sep 5 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
    Sep 5 at 13:18
  • \$\begingroup\$ Oh, I see thanks for enlightening me. \$\endgroup\$ Sep 5 at 13:21
  • \$\begingroup\$ This could even be 5 bytes with rs: Ṅ₀ḊvΠ \$\endgroup\$
    – Steffan
    Sep 5 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

And it's even possible to use this algorithm in such a way that works for all positive inputs, by capturing 10 in binary (95 bytes):

^(?|(?:(?=(\2))(?=(\3))(?=(\4)())){0,3}(?=(x*))\1\2\2\3{4}\4{8}(?!\5)|^(?=()(x))(?=()(x))){2,}$

Try it online! - PCRE

^
(?|
    (?:
        (?=(\2))    # \1 = \2
        (?=(\3))    # \2 = \3
        (?=(\4)())  # \3 = \4; \4 = 0
    ){0,3}
    (?=(x*))        # \5 = tail
    \1
    \2\2
    \3{4}
    \4{8}
    (?!\5)          # Assert tail < \5
|
    ^
    # \1 + \2*2 + \3*4 + \4*8 = 10
    (?=()(x))  # \1 = 0; \2 = 1
    (?=()(x))  # \3 = 0; \4 = 1
){2,}
$
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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