Print all the ways to aquire specific number using only specific numbers

Question

Let's say we have some arbitrary number:

For example 25. We also have some "tokens" (poker chips, money, something similar) with different values.

Values of tokens are 2; 3; 4; 5.

"Tokens" are limitless

You need to achieve number 25 using exactly n tokens (for example, 8) and to output all possible ways of doing so.

Fragment of example expected output (25 with 8 tokens):

3 '5' tokens, 5 '2' tokens
2 '5' tokens, 1 '4' token, 1 '3' token, 4 '2' tokens
....
1 '4' token, 7 '3' tokens

You may output in any reasonable, non-ambiguous format. For instance, 3 '5' tokens, 5 '2' tokens can be represented as a single list [5,0,0,3] or as a list of tuples [[3,5],[5,2]]. And if there's no solution, you can provide empty output (or state no solution found or something among the lines)

Standard code golf rules apply, so winner is decided by shortest byte count (though you have to also provide "commented" version of your code, especially for languages such as Brainfuck, Jelly, Piet and so on)

Edit: I intended this challenge as challenge with fixed tokens, but I like universal answers more then "niche" ones even if it's not specified in challenge itself initially. As long as making tokens "third input parameter" still provides correct answer for tokens provided it's accepted for this challenge. If you are willing to rewrite your code - go on, save those precious bytes/chars.

Answer 1

Jelly, 10 bytes

ŒṗfƑƇL=¥Ƈ⁵

Try it online!

A full program that takes the total, token values and number of arguments as its arguments. Returns a list of lists of token values.

Explanation

Œṗ          | Integer partition (of first argument)
    Ƈ       | Keep only those which:
   Ƒ        | - are invariant when:
  f         |   - filtered to only include the (implicit) second argument. 
       ¥Ƈ   | Keep only those for which:
     L      | - the length
      =  ⁵  |   - is equal to the third argument

Answer 2

J, ³⁵ 32 bytes

~.@((=1&#.)#])2+#&4/:~@#:[:i.4^]

Try it online!

• Count in base 4 from 0 up to 4 ^ num_tokens to generate all the raw possibilities: #&4/:~@#:[:i.4^]
• Add 2 to all numbers so the tokens will have 2 3 4 5 labels instead of 0 1 2 3 labels: 2+
• Sort each possibility in preparation for removing dups: /:~@
• Filter the raw possibilities to include only those with the correct sum: ((=1&#.)#])
• Take the uniqs: ~.@

Answer 3

Perl 6, 64 bytes

{grep(*.sum==$_,|($/=2..5),|(+<<[\X] $/xx$_)[*;*])>>.Bag.unique}

Try it online!

Fails for inputs above 7 due to Too many arguments in flattening array.This is because we are generating a list of every possible combination with repetition of numbers up to length n (where n is the same as the input), and not just that, but every possible ordering as well. Ah well, the price of being golfy...

This takes a number and returns a Bag, which is an unordered list of numbers and the amount in the bag.

Answer 4

Haskell, 63 bytes

n%k=[l|l<-mapM(\_->[0..n])"xnor",sum l==k,sum(scanr(+)0l)==n-k]

Try it online!

A cute trick is used to check the list sum. We're looking for for elements l=[a,b,c,d] with a+b+c+d=k (right number of tokens) and 2*a+3*b+4*c+5*d==n (right total value). Subtracting the first equation from the second gives a+2*b+3*c+4*d==n-k. To get a+2*b+3*c+4*d, we do scanr(+)0 l to get the reversed cumulative sum [a+b+c+d,b+c+d,c+d,d,0] and take the sum of its elements.

The solution brute-forces using mapM to generate all possible quadruples of token counts.

---

71 bytes

n%k=filter(all(>=0))[[a,4*k-n-2*a+d,n-3*k+a-2*d,d]|a<-[0..n],d<-[0..n]]

Try it online!

A longer direct solution. We try all a and d, and for each possibility we solve for b and c and check if they are non-negative positive.

---

68 bytes

(%)2
6%t=[[]|t==(0,0)]
x%(v,c)=do y<-[0..c];(y:)<$>(x+1)%(v-x*y,c-y)

Try it online!

Golfing Joseph Sible's solution. Takes input uncurried like (25,8).

Answer 5

JavaScript (V8),  94  82 bytes

Takes input as (sum)(n). Prints the solutions, as lists of token values.

s=>(g=(n,t=0,u=[])=>n?[2,3,4,5].map(v=>v>u[0]||g(n-1,t+v,[v,...u])):t-s||print(u))

Try it online!

Commented

s => (              // s = expected sum
  g = (             // g is a recursive function taking:
    n,              //   n   = expected number of tokens
    t = 0,          //   t   = current sum, initialized to 0
    u = []          //   u[] = list of tokens
  ) =>              //
    n ?             // if n is not equal to 0:
      [2, 3, 4, 5]  //   for each allowed token value v:
      .map(v =>     //
        v > u[0] || //     abort if u[] is non-empty and v is greater than the last
                    //     token value (which is actually stored at the beginning)
        g(          //     otherwise, do a recursive call:
          n - 1,    //       decrement n
          t + v,    //       add v to t
          [v, ...u] //       prepend v to u[]
        )           //     end of recursive call
      )             //   end of map()
    :               // else:
      t - s ||      //   if t = s:
        print(u)    //     this is a solution: print it
)                   //

Answer 6

05AB1E, 11 bytes

ÅœIùʒ5L¦ÃyQ

Try it online!

Outputs list of token values.

Explanation

Ŝ            | Take all integer partitions of the target number
  Iù          | Only keep those of length n
    ʒ         | Filter by:
     5L¦      | Push [2,3,4,5]
        ÃyQ   | Check if partition is equal to its intersection with [2,3,4,5]
              | Filter it out if not 

Answer 7

Pyth, 21 20 bytes

{mSdfqhQsT.c*hQr2 6e

Try it online!

Saved a byte because the last Q is implicit

Returns a list of token combinations (e.g. [3, 3, 4] for 2 '3' tokens and 1 '4' token) which seems like a reasonable, non-ambiguous format, so I'll leave it unless the rules are changed. Takes input as value, n. Return an empty list if there are no valid combinations (I think)

Also hopelessly slow, so dont pick a value thats too high.

How it works

{mSdfqhQsT.c*hQr2 6e (Q)
            *hQ        - Multiply the first input by...
               r2 6    - The range 2,6 (2..5)
          .c       e(Q)- All combinations of the above that are the length of the 
                        second input (Q is implicit)
    fqhQsT             - Filter to elements where the sum is equal to the first input
 mS                    - Sort all elements
{                      - Remove duplicates

Answer 8

Wolfram Language (Mathematica), 36 bytes

Not really golfed. There is a built-in for this in Mathematica.

IntegerPartitions[#,{#2},{2,3,4,5}]&

Try it online!

Answer 9

Charcoal, 30 bytes

ＮθＮηΦＥＸ⊕θ⁴⭆⮌↨ι⊕θ⭆λ⁺²μ∧⁼Ｌιθ⁼Σιη

Try it online! Link is to verbose version of code. Outputs a list of strings each of n tokens sorted in ascending order (if they had been sorted in descending order then the list itself would be in ascending order). Explanation:

ＮθＮη

Input n and the target.

ΦＥＸ⊕θ⁴

Loop over the range 0..(n+1)⁴.

⭆⮌↨ι⊕θ

Convert each value to base (n+1) as an array with least significant digit first.

⭆λ⁺²μ

Convert each array to a string of tokens 2..5 and concatenate the results.

∧⁼Ｌιθ⁼Σιη

Only output those strings with a length of n and the correct digital sum.

Answer 10

Haskell, 75 67 bytes

f(x:l)v c=do y<-[0..c];(y:)<$>f l(v-x*y)(c-y)
f[]0 0=[[]]
f[]_ _=[]

Try it online!

-8 bytes by taking the tokens as input

The last two lines could be replaced with either f[]v c=[[]|v==0,c==0] or f n v c=[n|v==0,c==0], both keeping the same byte count. Perhaps there's a way to golf one of those variants further that I'm not seeing though.

Answer 11

Julia 1.0, 67 bytes

f(s,n,q=0:n)=[[a b c d] for a=q,b=q,c=q,d=q if[a b c d]*(2:5)==[s]]

Generates values representing how many tokens there are, then uses matrix multiplication to calculate the total. It seems like there should be a way to avoid typing [a b c d] twice, but I'm not aware of it.

Try it online!

Answer 12

Japt, 22 bytes

V*4 o î6o2)àV â f_x ¥U

Try it

Returns arrays of tokens.
Not really efficent though.

(V * 4).o() // create an array of 4 times every token
.î(6 .o(2)) // repeat 2 to 5 inside it
.à(V).â() // all unique combinations
.f(function(Z) { return Z.x() == U }) // remove the wrong combinatons

Flag -Q to pretty print the result

Answer 13

Python 3, 97 bytes

lambda s,n:{(*sorted(i),)for i in product([2,3,4,5],repeat=n)if sum(i)==s}
from itertools import*

Try it online!

---

Python 3, 106 bytes

lambda s,n,r=range:{(i,j,k,n-i-j-k)for i in r(n+1)for j in r(n-i+1)for k in r(n-i-j+1)if 5*n==s+3*i+2*j+k}

Try it online!

This function iterates over 3 variables i, j and k. The fourth variable follows from the difference between the number of tokens n and ijk. A combination is valid if 2*i+3*j+4*k+5*(n-i-j-k)==s. This condition rearranges to 5*n==s+3*i+2*j+k.