8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Arnauld, Oh, sorry. I'm very new to this community. How should I add standard LoC winning criteria and probably rewrite this challenge so that input and ouput is still readable and not to limit participants to much? \$\endgroup\$ – Sheyko Dmitriy Nov 8 at 14:16
  • 5
    \$\begingroup\$ By the way: welcome to Code Golf! I hope you'll enjoy your stay here. \$\endgroup\$ – Arnauld Nov 8 at 14:33
  • 2
    \$\begingroup\$ Are 2,3,4,5 always the tokens, or is that part of the input too and that's just the example? \$\endgroup\$ – Joseph Sible Nov 10 at 6:13
  • 1
    \$\begingroup\$ @JosephSible 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. If taking tokens to "third input parameter" makes your solution shorter but still provides correct answer for tokens [2,3,4,5] - I would accept it \$\endgroup\$ – Sheyko Dmitriy Nov 11 at 12:29
  • 1
    \$\begingroup\$ @stephanmg let's limit it by MAX_INT, I don't think going for some BigInteger values will make this challenge any more intersting \$\endgroup\$ – Sheyko Dmitriy Nov 11 at 12:34

13 Answers 13

4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Wow. I'll probably never understand Jelly but it always seem to provide shortest solution. Congrats. And bonus points for providing a way to input tokens. \$\endgroup\$ – Sheyko Dmitriy Nov 11 at 7:54
  • \$\begingroup\$ @SheykoDmitriy The Jelly answer is the only one that takes the [2,3,4,5] as third input instead of hard-coding it, though. Which of the two is correct? Could you answer @JosephSible's comment on your challenge? \$\endgroup\$ – Kevin Cruijssen Nov 11 at 8:22
  • \$\begingroup\$ @KevinCruijssen I’d interpreted it as being part of the input, rightly or wrongly. \$\endgroup\$ – Nick Kennedy Nov 11 at 8:23
  • \$\begingroup\$ @NickKennedy I can understand. I also read it like that as first. But I noticed all other answers are hard-coding it instead, and I also noticed Joseph's question regarding it. If it's a third input, the 05AB1E answer for example could be 7 bytes, and I'm sure some of the other answers would be able to save some bytes as well. If it's indeed intended to be a third input as we both thought when reading the challenge. \$\endgroup\$ – Kevin Cruijssen Nov 11 at 8:25
3
\$\begingroup\$

J, 35 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: ~.@
\$\endgroup\$
2
\$\begingroup\$

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.

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

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
)                   //
\$\endgroup\$
  • \$\begingroup\$ I like the way you format your code for explanations. Do you do it by hand or use a program you've written? \$\endgroup\$ – Jonah Nov 9 at 1:53
  • 1
    \$\begingroup\$ @Jonah Every once in a while, the idea of writing a program crosses my mind. And then I say to myself: "oh well, let's do this one manually for now..." \$\endgroup\$ – Arnauld Nov 9 at 8:29
  • \$\begingroup\$ Wow. Taking off my hat. Nice formatting and thorough comments. That's the way I like to see code! \$\endgroup\$ – Sheyko Dmitriy Nov 11 at 7:56
1
\$\begingroup\$

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

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

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!

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

Charcoal, 30 bytes

NθNηΦEX⊕θ⁴⭆⮌↨ι⊕θ⭆λ⁺²μ∧⁼Lιθ⁼Σιη

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:

NθNη

Input n and the target.

ΦEX⊕θ⁴

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.

∧⁼Lιθ⁼Σιη

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

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

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

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

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

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.

\$\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.