A penny saved is a penny

21

6

...counted!

You will pass your program a variable which represents a quantity of money in dollars and/or cents and an array of coin values. Your challenge is to output the number of possible combinations of the given array of coin values that would add up to the amount passed to the code. If it is not possible with the coins named, the program should return 0.

Note on American numismatic terminology:

  • 1-cent coin: penny
  • 5-cent coin: nickel
  • 10-cent coin: dime
  • 25-cent coin: quarter (quarter dollar)

Example 1:

Program is passed:

12, [1, 5, 10]

(12 cents)

Output:

4

There are 4 possible ways of combining the coins named to produce 12 cents:

  1. 12 pennies
  2. 1 nickel and 7 pennies
  3. 2 nickels and 2 pennies
  4. 1 dime and 2 pennies

Example 2:

Program is passed:

26, [1, 5, 10, 25]

(26 cents)

Output:

13

There are 13 possible ways of combining the coins named to produce 26 cents:

  1. 26 pennies
  2. 21 pennies and 1 nickel
  3. 16 pennies and 2 nickels
  4. 11 pennies and 3 nickels
  5. 6 pennies and 4 nickels
  6. 1 penny and 5 nickels
  7. 16 pennies and 1 dime
  8. 6 pennies and 2 dimes
  9. 11 pennies, 1 dime, and 1 nickel
  10. 6 pennies, 1 dime, and 2 nickels
  11. 1 penny, 1 dime, and 3 nickels
  12. 1 penny, 2 dimes, and 1 nickel
  13. 1 quarter and 1 penny

Example 3:

Program is passed:

19, [2, 7, 12]

Output:

2

There are 2 possible ways of combining the coins named to produce 19 cents:

  1. 1 12-cent coin and 1 7-cent coin
  2. 1 7-cent coin and 6 2-cent coins

Example 4:

Program is passed:

13, [2, 8, 25]

Output:

0

There are no possible ways of combining the coins named to produce 13 cents.


This has been through the Sandbox. Standard loopholes apply. This is code golf, so the answer with the fewest bytes wins.

anonymous2

Posted 2016-10-20T20:14:44.367

Reputation: 421

1s/counted/earned – mbomb007 – 2016-10-20T20:56:12.723

1Can we input the coin values in reverse order (i.e. [25, 10, 5, 1])? – ETHproductions – 2016-10-20T20:56:34.260

Can we assume that the list is not empty? – Christian Sievers – 2016-10-20T22:49:17.097

@ETHproductions, I would say yes. – anonymous2 – 2016-10-20T23:46:46.797

@ChristianSievers, again, I would say yes. – anonymous2 – 2016-10-20T23:47:02.623

4@mbomb007 For four bytes: s/count/earn. – wizzwizz4 – 2016-10-21T06:04:23.020

5For me and I guess for other people who don't pay with dollars it's not obvious what a nickel and a dime is. It wasn't hard to figure it out, but maybe you could write it a bit more international? – Kritzefitz – 2016-10-21T07:59:39.527

2@Kritzefitz. I've added that to the question. – TRiG – 2016-10-21T12:04:59.230

and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code (not i say i would post another answers ) – RosLuP – 2016-10-21T18:57:12.740

Pedantic note on terminology: The official name for the US 1-cent coin is cent. Penny only comes up in informal usage, or when talking about the UK 1-cent coin.

– jpaugh – 2016-10-21T22:50:54.663

2

@jpaugh: While coin-o-philes might agree, I'd have to disagree. A penny is the standard coin that has a value of one cent. Fifty-four cents is an amount of money. Fifty-four pennies is explicitly fifty-four coins. It's also called a "one-cent coin", or (officially) a "one-cent piece". I can't think of any formal setting where the word "penny" would be unacceptable. These people, who are specifically about collecting coins, have no problem calling it a "penny".

– MichaelS – 2016-10-22T01:20:30.457

I wonder why you didn't make them print the combinations. That would have confounded the Froeniuses :) – GreenAsJade – 2016-10-22T11:20:33.263

@MichaelS As you say, popular usage makes the official name fairly moot, and I find that fascinating. I myself refer to this coin almost exclusively as "the penny," while referring to the amount as "one cent." I imagine the US wanted to distinguish itself from Britain at the time, but changing a long-established convention is not so easy! – jpaugh – 2016-10-23T01:19:19.633

Sorry, @jpaugh, I'm not from the US. In Canada, we definitely follow the nomenclature that MichaelS outlined. I really don't know what the facts are in the States... Sorry for the obscurity there! – anonymous2 – 2016-10-23T02:22:32.773

@anonymous2 No sweat. Just an obscure oddity of language. (In the US, we certainly follow the nomenclature MichaelS mentioned. It's just not "official.") – jpaugh – 2016-10-23T03:43:17.970

Ah, ok. I've got you. I don't know whether it's official or not in Canada... :) – anonymous2 – 2016-10-23T10:54:38.003

So i did not post a solution for this, and have the solutions... Is i'am that cancel my solution of this or who? Thanks... – RosLuP – 2017-09-02T18:38:57.287

Answers

12

Jelly (fork), 2 bytes

æf

This relies on a branch of Jelly where I was working on implementing Frobenius solve atoms so unfortunately you cannot try it online.

Usage

$ ./jelly eun 'æf' '12' '[1,5,10]'
4
$ ./jelly eun 'æf' '26' '[1,5,10,25]'
13
$ ./jelly eun 'æf' '19' '[2,7,12]'
2
$ ./jelly eun 'æf' '13' '[2,8,25]'
0

Explanation

æf  Input: total T, denominations D
æf  Frobenius count, determines the number of solutions
    of nonnegative X such that X dot-product D = T

miles

Posted 2016-10-20T20:14:44.367

Reputation: 15 654

10...that's not even fair. – ETHproductions – 2016-10-20T21:22:11.780

...and I bet it's much faster! – Jonathan Allan – 2016-10-20T22:21:43.883

18

Haskell, 37 34 bytes

s#l@(c:d)|s>=c=(s-c)#l+s#d
s#_=0^s

Usage example: 26 # [1,5,10,25] -> 13.

Simple recursive approach: try both the next number in the list (as long as it is less or equal to the amount) and skip it. If subtracting the number leads to an amount of zero, take a 1 else (or if the list runs out of elements) take a 0. Sum those 1s and 0s.

Edit: @Damien: saved 3 bytes by pointing to a shorter base case for the recursion (which also can be found in @xnors answer).

nimi

Posted 2016-10-20T20:14:44.367

Reputation: 34 639

s#l@(c:d)|s>=c=(s-c)#l+s#d;s#_=0^s – Damien – 2016-10-21T07:57:23.757

and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code – RosLuP – 2016-10-22T07:11:45.693

@RosLuP: 1209 # [1,5,10,33,48]-> 1314050. – nimi – 2016-10-22T10:09:20.910

@nimi ok for 1314050 I have the same result here... Thanks... – RosLuP – 2016-10-22T10:30:56.737

@RosLuP: ... 537min later: 6000 # [1,5,10,33] -> 22086484. – nimi – 2016-10-22T21:30:31.943

15

Mathematica, 35 22 bytes

Thanks to miles for suggesting FrobeniusSolve and saving 13 bytes.

Length@*FrobeniusSolve

Evaluates to an unnamed function, which takes the list of coins as the first argument and the target value as the second. FrobeniusSolve is a shorthand for solving Diophantine equations of the form

a1x1 + a2x2 + ... + anxn = b

for the xi over the non-negative integers and gives us all the solutions.

Martin Ender

Posted 2016-10-20T20:14:44.367

Reputation: 184 808

@RosLuP You will need access to Mathematica to run this. Also this is an anonymous function so to call it, either encapsulate it in parentheses or store it to a variable. For example, (Length@*FrobeniusSolve)[{1, 7, 9}, 18] – miles – 2016-10-21T21:07:18.160

and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code – RosLuP – 2016-10-22T07:12:04.060

@RosLuP 1314050 and 22086484, respectively. – Martin Ender – 2016-10-22T11:30:59.947

Ok here result the same, thanks... – RosLuP – 2016-10-22T11:46:05.313

16 votes for this are justified only if the programmer that wrote Length @ * FrobeniusSolve are you... – RosLuP – 2017-09-02T19:11:22.057

12

Pyth, 8 bytes

/sM{yS*E

Raw brute force, too memory intensive for actual testing. This is O(2mn), where n is the number of coins and m is the target sum. Takes input as target\n[c,o,i,n,s].

/sM{yS*EQQ      (implicit Q's)
      *EQ       multiply coin list by target
     S          sort
    y           powerset (all subsequences)
   {            remove duplicates
 sM             sum all results
/        Q      count correct sums

PurkkaKoodari

Posted 2016-10-20T20:14:44.367

Reputation: 16 699

9

JavaScript (ES6), 51 48 bytes

f=(n,a,[c,...b]=a)=>n?n>0&&c?f(n-c,a)+f(n,b):0:1

Accepts coins in any order. Tries both using and not using the first coin, recursively calculating the number of combinations either way. n==0 means a matching combination, n<0 means that the coins exceed the quantity while c==undefined means that there are no coins left. Note that the function is very slow and if you have a penny coin then the following function is faster (don't pass the penny coin in the array of coins):

f=(n,a,[c,...b]=a)=>c?(c<=n&&f(n-c,a))+f(n,b):1

Neil

Posted 2016-10-20T20:14:44.367

Reputation: 95 035

...dangit. Real nice idea. – ETHproductions – 2016-10-21T01:05:04.833

and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code – RosLuP – 2016-10-22T07:12:17.927

@RosLuP The given code eventually returns 1314050 for your first example. My interpreter can't handle the recursion necessary to evaluate the second example. – Neil – 2016-10-22T10:27:13.073

@RosLuP I modified the function to assume an additional penny coin exists and that returned 22086484 for 6000[5,10,33]. – Neil – 2016-10-22T10:31:09.590

@Neil ok 22086484 for 6000[1,5,10,33]... Instead would be 11239 here for 6000[5,10,33] (the array you wrote) – RosLuP – 2016-10-22T10:38:17.380

@RosLuP The modified function adds the penny coin to the list for you before counting the combinations, which is why it returns the value it does, but it's much quicker than using the generic function which works for sets of coins that don't include pennies. – Neil – 2016-10-22T10:44:10.863

9

Haskell, 37 bytes

s%(h:t)=sum$map(%t)[s,s-h..0]
s%_=0^s

Using some multiple of the first coin h decreases the required sum s to a non-negative value in the decreasing progression [s,s-h..0], which then must be made with the remaining coins. Once there's no coins left, check that the sum is zero arithmetically as 0^s.

xnor

Posted 2016-10-20T20:14:44.367

Reputation: 115 687

It's amazing how you hit exactly the same byte count as @nimi using a different approach. – Kritzefitz – 2016-10-21T08:03:43.667

7

Perl, 45 bytes

Byte count includes 44 bytes of code and -p flag.

s%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{

Takes the coin values on the first line, and the targeted amount on the second line :

$ perl -pE 's%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{' <<< "1 5 10 25
26"
13

Short explanations:

-p                        # Set $_ to the value of the input, 
                          # and adds a print at the end of the code.
s%\S+%(1{$&})*%g,         # Converts each number n to (1{$&})* (to prepare the regex)
                          # This pattern does half the job.
(1x<>)                    # Converts the target to unary representation.
  =~                      # Match against.. (regex)
    /^ $_ $               # $_ contains the pattern we prepared with the first line.
     (?{$\++})            # Count the number of successful matches
     ^                    # Forces a fail in the regex since the begining can't be matched here.
    /x                    # Ignore white-spaces in the regex 
                          # (needed since the available coins are space-separated)
 }{                       # End the code block to avoid the input being printed (because of -p flag) 
                          # The print will still be executed, but $_ will be empty, 
                          # and only $\ will be printed (this variable is added after every print)

Dada

Posted 2016-10-20T20:14:44.367

Reputation: 8 279

6

JavaScript (ES6), 59 bytes

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),0):1

Coins are input from highest to lowest, e.g. f(26,[100,25,10,5,1]). If you have a penny, remove it and use this much faster version instead:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

This uses a recursive formula much like @nimi's. I originally wrote this a few days ago when the challenge was still in the sandbox; it looked like this:

f=(n,c=[100,25,10,5])=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

The only differences being the default value of c (it had a set value in the original challenge), and changing the 0 in the .reduce function to 1 (this was two bytes shorter and a bazillion times faster than c=[100,25,10,5,1]).


Here's a modified version which outputs all combinations, rather than the number of combinations:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:[...x,...f(n-y,c.slice(i)).map(c=>[...c,y])],[]):[[]]

ETHproductions

Posted 2016-10-20T20:14:44.367

Reputation: 47 880

and what would be the result of 1209[1,5,10,33,48] and 6000[1,5,10,33] so i can calibrate my code – RosLuP – 2016-10-22T07:13:01.337

@RosLuP I get 1314050 (after 5 minutes) and a stack overflow (after an hour), respectively. With the faster version I just added, I get 1314050 and 22086484 within a few seconds. – ETHproductions – 2016-10-22T16:17:28.103

With my old Pentium 2.8Gh computer 6 seconds for the first result, for the second 5 minutes +or - – RosLuP – 2016-10-22T16:30:02.147

6

Jelly, 10 9 bytes

œċЀS€€Fċ

Try it online!

How?

œċЀS€€Fċ - Main link: coins, target
  Ѐ      - map over right argument, or for each n in [1,2,...,target]
œċ        - combinations with replacement, possible choices of each of n coins
    S€€   - sum for each for each (values of those selections)
       F  - flatten into one list
        ċ - count occurrences of right argument

Jonathan Allan

Posted 2016-10-20T20:14:44.367

Reputation: 67 804

2+1 for using that many Euro-symbols in a money-related question. – steenbergh – 2016-10-21T09:48:23.773

5

PHP, 327 Bytes

function c($f,$z=0){global$p,$d;if($z){foreach($p as$m){for($j=0;$j<=$f/$d[$z];){$n=$m;$n[$d[$z]]=$j++;$p[]=$n;}}}else for($p=[],$j=0;$j<=$f/$d[$z];$j++)$p[]=[$d[$z]=>$j];if($d[++$z])c($f,$z);}$d=$_GET[a];c($e=$_GET[b]);foreach($p as$u){$s=0;foreach($u as$k=>$v)$s+=$v*$k;if($s==$e&count($u)==count($d))$t[]=$u;}echo count($t);

Try it

Jörg Hülsermann

Posted 2016-10-20T20:14:44.367

Reputation: 13 026

5

Axiom, 63 62 bytes

1 byte saved by @JonathanAllan

f(n,l)==coefficient(series(reduce(*,[1/(1-x^i)for i in l])),n)

This approach uses generating functions. Probably that didn't help bring down the code size. I think this is the first time that in my playing with Axiom I went as far as defining my own function.

The first time the function is called it gives a horrendous warning, but still produces the correct result. After that, everything is fine as long as the list isn't empty.

Christian Sievers

Posted 2016-10-20T20:14:44.367

Reputation: 6 366

1I don't know Axiom - is it possible to remove the space before for? – Jonathan Allan – 2016-10-20T22:49:18.820

1@JonathanAllan Yes, it is! Good golfing instinct, thanks! – Christian Sievers – 2016-10-20T23:00:51.877

5

R, 81 76 63 bytes

Thanks to @rturnbull for golfing away 13 bytes!

function(u,v)sum(t(t(expand.grid(lapply(u/v,seq,f=0))))%*%v==u)

Example (note that c(...) is how you pass vectors of values to R):

f(12,c(1,5,10))
[1] 4

Explanation:

u is the desired value, v is the vector of coin values.

expand.grid(lapply(u/v,seq,from=0))

creates a data frame with every possible combination of 0 to k coins (k depends on the denomination), where k is the lowest such that k times the value of that coin is at least u (the value to achieve).

Normally we would use as.matrix to turns that into a matrix, but that is many characters. Instead we take the transpose of the transpose (!) which automatically coerces it, but takes fewer characters.

%*% v then calculates the monetary value of each row. The last step is to count how many of those values are equal to the desired value u.

Note that the computational complexity and memory requirements of this are horrific but hey, it's code golf.

JDL

Posted 2016-10-20T20:14:44.367

Reputation: 1 135

1Nice use of expand.grid! And I love the t(t()) trick. Since your function only involves a single line of code, you can remove the curly braces, saving you 2 bytes. Also, you can switch do.call(expand.grid,lapply(u/v,seq,from=0)) for just expand.grid(lapply(u/v,seq,f=0)), saving 11 bytes. – rturnbull – 2016-10-21T09:59:19.403

Thanks for those! I never realised expand.grid would take a list as input. It's a bit of a shame that ":" doesn't work well with non-integers otherwise lapply(u/v,":",0) would have saved a couple more. – JDL – 2016-10-21T10:08:32.817

do.call(x,y) is the same as x(y), so it's not about what kinds of input are accepted. If you really want to use :, I suppose you could use lapply(u%/%v,\:`,0)`, but it's the same byte count. – rturnbull – 2016-10-21T10:28:16.490

1"do.call(x,y) is the same as x(y)" --- only if y isn't a list, which it is in this case. Agree on your second point, though. – JDL – 2016-10-21T10:31:24.303

3

J, 27 bytes

1#.[=](+/ .*~]#:,@i.)1+<.@%

Usage

   f =: 1#.[=](+/ .*~]#:,@i.)1+<.@%
   12 f 1 5 10
4
   26 f 1 5 10 25
13
   19 f 2 7 12
2
   13 f 2 8 25
0

Explanation

1#.[=](+/ .*~]#:,@i.)1+<.@%  Input: target T (LHS), denominations D (RHS)
                          %  Divide T by each in D
                       <.@   Floor each
                             These are the maximum number of each denomination
                     1+      Add 1 to each, call these B
                ,@i.         Forms the range 0 the the product of B
             ]               Get B
              #:             Convert each in the range to mixed radix B
     ]                       Get D
       +/ .*~                Dot product between D and each mixed radix number
                             These are all combinations of denominations up to T
   [                         Get T
    =                        Test if each sum is equal to T
1#.                          Convert as base 1 digits to decimal (takes the sum)
                             This is the number of times each sum was true

miles

Posted 2016-10-20T20:14:44.367

Reputation: 15 654

J is so awesome, yet also, so insane – CommaToast – 2016-10-21T00:18:15.730

2

TSQL, 105 bytes

This can only handle up to one dollar with these 4 coin types. The ungolfed version can handle up to around 4 dollars, but very slow - on my box this takes 27 seconds. Result is 10045 combinations b.t.w.

Golfed:

DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)
;WITH c as(SELECT 0l,0s UNION ALL SELECT z,s+z FROM c,@t WHERE l<=z and s<@)SELECT SUM(1)FROM c WHERE s=@

Ungolfed:

-- input variables
DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)

-- query
;WITH c as
(
  SELECT 0l,0s
  UNION ALL
  SELECT z,s+z
  FROM c,@t
  WHERE l<=z and s<@
)
SELECT SUM(1)
FROM c
WHERE s=@
-- to allow more than 100 recursions(amounts higher than 1 dollar in this example)
OPTION(MAXRECURSION 0)

Fiddle

t-clausen.dk

Posted 2016-10-20T20:14:44.367

Reputation: 2 874

2

tinylisp repl, 66 bytes

(d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1

Recursive solution: tries using the first coin and not using the first coin, then adds the results from each. Exponential time complexity and no tail-recursion, but it computes the test cases just fine.

Ungolfed (key to builtins: d = define, q = quote, i = if, l = less-than, s = subtract, h = head, t = tail):

(d combos
 (q
  ((amount coin-values)
   (i amount
    (i (l amount 0)
     0
     (i coin-values
      (s
       (combos
        (s amount (h coin-values))
        coin-values)
       (s
        0
        (combos
         amount
         (t coin-values))))
      0))
    1))))

Example usage:

tl> (d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1
C
tl> (C 12 (q (1 5 10)))
4
tl> (C 26 (q (1 5 10 25)))
13
tl> (C 19 (q (2 7 12)))
2
tl> (C 13 (q (2 8 25)))
0
tl> (C 400 (q (1 5 10 25)))
Error: recursion depth exceeded. How could you forget to use tail calls?!

DLosc

Posted 2016-10-20T20:14:44.367

Reputation: 21 213

1

Actually, 15 bytes

Golfing suggestions welcome. Try it online!

╗;R`╜∙♂S╔♂Σi`Mc

Ungolfing

         Implicit input n, then the list of coins a.
╗        Save a to register 0.
;R       Duplicate n and create a range [1..n] from that duplicate.
`...`M   Map the following function over that range. Variable i.
  ╜        Push a from register 0.
  ∙        Push the i-th Cartesian power of a.
  ♂S       Sort each member of car_pow.
  ╔        Uniquify car_pow so we don't count too any duplicate coin arrangements.
  ♂Σ       Take the sum of each coin arrangement.
  i        Flatten the list.
c        Using the result of the map and the remaining n, push map.count(n).
         Implicit return.

Sherlock9

Posted 2016-10-20T20:14:44.367

Reputation: 11 664

1

PHP, 130 bytes

function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));

99 byte recursive function (and 31 bytes of calling it) that repeatedly removes the value of the current coin from the target and calls itself with the new value and the other coins. Counts the number of times the target reaches 0 exactly. Run like:

 php -r "function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));" 12 1 5 10

user59178

Posted 2016-10-20T20:14:44.367

Reputation: 1 007

If called with more than 97 different types of coin it will die a recursion death without returning anything but as that's far more different types of coin then we have to support it's fine. – user59178 – 2016-10-21T16:33:53.593

1

Racket 275 bytes

(set! l(flatten(for/list((i l))(for/list((j(floor(/ s i))))i))))(define oll'())(for((i(range 1(add1(floor(/ s(apply min l)))))))
(define ol(combinations l i))(for((j ol))(set! j(sort j >))(when(and(= s(apply + j))(not(ormap(λ(x)(equal? x j))oll)))(set! oll(cons j oll)))))oll

Ungolfed:

(define(f s l)
  (set! l              ; have list contain all possible coins that can be used
        (flatten
         (for/list ((i l))
           (for/list ((j              
                       (floor
                        (/ s i))))
             i))))
  (define oll '())                    ; final list of all solutions initialized
  (for ((i (range 1  
                  (add1
                   (floor             ; for different sizes of coin-set
                    (/ s
                       (apply min l)))))))
    (define ol (combinations l i))          ; get a list of all combinations
    (for ((j ol))                           ; test each combination
      (set! j (sort j >))
      (when (and
             (= s (apply + j))              ; sum is correct
             (not(ormap                     ; solution is not already in list
                  (lambda(x)
                    (equal? x j))
                  oll)))
        (set! oll (cons j oll))             ; add found solution to final list
        )))
  (reverse oll))

Testing:

(f 4 '[1 2])
(println "-------------")
(f 12 '[1 5 10])
(println "-------------")
(f 19 '[2 7 12])
(println "-------------")
(f 8 '(1 2 3))

Output:

'((2 2) (2 1 1) (1 1 1 1))
"-------------"
'((10 1 1) (5 5 1 1) (5 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1 1 1))
"-------------"
'((12 7) (7 2 2 2 2 2 2))
"-------------"
'((3 3 2) (2 2 2 2) (3 2 2 1) (3 3 1 1) (2 2 2 1 1) (3 2 1 1 1) (2 2 1 1 1 1) (3 1 1 1 1 1) (2 1 1 1 1 1 1) (1 1 1 1 1 1 1 1))

Following recursive solution has some error:

(define (f s l)                      ; s is sum needed; l is list of coin-types
  (set! l (sort l >))
  (define oll '())                   ; list of all solution lists
  (let loop ((l l)   
             (ol '()))               ; a solution list initialized
    (when (not (null? l))
        (set! ol (cons (first l) ol)))
    (define ols (apply + ol))        ; current sum in solution list
    (cond
      [(null? l) (remove-duplicates oll)]
      [(= ols s) (set! oll (cons ol oll))
                 (loop (rest l) '()) 
                 ]
      [(> ols s) (loop (rest l) (rest ol))
                 (loop (rest l) '())   
                 ]
      [(< ols s) (loop l ol) 
                 (loop (rest l) ol)
                 ])))

Does not work properly for:

(f 8 '[1 2 3])

Output:

'((1 1 1 2 3) (1 2 2 3) (1 1 1 1 1 1 1 1) (2 3 3) (1 1 1 1 1 1 2) (1 1 1 1 2 2) (1 1 2 2 2) (2 2 2 2))

(1 1 3 3) is possible but does not come in solution list.

rnso

Posted 2016-10-20T20:14:44.367

Reputation: 1 635

I'm not familiar with Racket, but I did write a solution in Clojure for a similar problem to this a few years ago that made use of reduce – miles – 2016-10-22T02:26:25.790

'reduce' is not part of base Racket language, although 'fold' is available. I have added a modified solution above since earlier solution has some error. – rnso – 2016-10-22T04:13:38.903

Looks like a bunch of Lisp enthusiasts got together...and made a racket – Joe – 2017-09-19T16:12:53.500

1

Some of Lisp enthusiasts first made a Scheme (https://groups.csail.mit.edu/mac/projects/scheme/) which finally led to full-blown Racket (http://racket-lang.org/ , https://stackoverflow.com/questions/3345397/how-is-racket-different-from-scheme) !

– rnso – 2017-09-19T16:36:48.883

1

Jelly, 15 bytes

s+\Fṁḷ
2*BW;ç/Ṫ

Try it online! or Verify all test cases.

This was more of an exercise in writing an efficient version in Jelly without using builtins. This is based on the typical dynamic programming approach used to calculate the number of ways for making change

Explanation

s+\Fṁḷ  Helper link. Input: solutions S, coin C
s       Slice the solutions into non-overlapping sublists of length C
 +\     Cumulative sum
   F    Flatten
     ḷ  Left, get S
    ṁ   Mold the sums to the shape of S

2*BW;ç/Ṫ  Main link. Input: target T, denominations D
2*        Compute 2^T
  B       Convert to binary, creates a list with 1 followed by T-1 0's
          These are the number of solutions for each value from 0 to T
          starting with no coins used
   W      Wrap it inside another array
    ;     Concatenate with D
     ç/   Reduce using the helper link
       Ṫ  Tail, return the last value which is the solution

miles

Posted 2016-10-20T20:14:44.367

Reputation: 15 654

0

Python, 120 bytes

from itertools import*
lambda t,L:[sum(map(lambda x,y:x*y,C,L))-t for C in product(range(t+1),repeat=len(L))].count(0)

Bruteforces through all combinations of coins up to target value (even if the smallest is not 1).

Karl Napf

Posted 2016-10-20T20:14:44.367

Reputation: 4 131