32
\$\begingroup\$

Write a program which calculates if an inputted monetary value, as an integer, can be represented by a unique combination of coins and/or notes, that meaning the same coin/note cannot be used more than once.

Your program should take a value as input, and can take a list of coin/note values either via input or via your language's equivalent of an array. The list of coins/notes should be able to change, so make sure it's clear where this is defined if you're using a constant.

Your program should output any truthy/falsy value respectively.

Please note that outputting the list of coins/notes that make up the value is not required.

EXAMPLE

Using the UK pound, (£1.00 = 100 and £420.69 = 42069)

coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]

The following will output true:

6 (1, 5) 15 (10, 5) 88 (1, 2, 5, 10, 20, 50) 512 (500, 10, 2) 7003 (5000, 2000, 2, 1)

The following will output false:

4 209 8889 4242424242 [ANYTHING ABOVE 8888]

ALTERNATIVE TEST DATA (US Dollar)

coins = [1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000]

Good luck!

Improve this question
\$\endgroup\$
12
  • 5
    \$\begingroup\$ I wish we have more newcomers like you... \$\endgroup\$ Commented May 8, 2017 at 17:41
  • \$\begingroup\$ Related \$\endgroup\$ Commented May 8, 2017 at 17:55
  • 2
    \$\begingroup\$ You should add some testcases using a different set of coin \$\endgroup\$ Commented May 8, 2017 at 18:18
  • 2
    \$\begingroup\$ I'd suggest adding test cases that cannot be solved with the greedy heuristic of taking the largest unused coin that is that is at most the remaining value. It would also be good to have ones where the input isn't sorted and where a value can be made more than one way. It's generally good for test cases to avoid the possibility that someone makes a reasonable attempt at the problem that works for the test cases without being right on everything. \$\endgroup\$ Commented May 8, 2017 at 20:17
  • 2
    \$\begingroup\$ Related. Also related. The former question is arguably a duplicate, but this question is IMO better-designed and if we're to close one as a duplicate, I'd rather close the older one. \$\endgroup\$ Commented May 8, 2017 at 21:24

23 Answers 23

Reset to default
13
\$\begingroup\$

Brachylog 2 (TIO Nexus), 2 bytes

⊇+

Try it online!

Takes the list of coins either via standard input or via prepending it to the start of the program as an array literal (either will work, so it's up to you as to which you feel is "more legitimate"; the former is allowed by default PPCG rules, the latter specifically allowed by the question); and takes the value to produce as a command-line argument.

Explanation

This program makes use of implementation details of the way TIO Nexus's wrapper for Brachylog functions; specifically, it lets you give a command-line argument to give input via the Output. (This wasn't envisaged in the original design for Brachylog; however, languages are defined by their implementation on PPCG, and if an implementation comes along that happens to do what I need, I can therefore take advantage of it.) That means the program looks like this:

⊇+ ⊇ Some subset of {standard input} + sums to {the first command-line argument}

As a full program, it returns a boolean value; true. if all the assertions in the program can be simultaneously satisfied, or false. if they can't be.

(A reminder, or for people who don't already know: Brachylog 2 uses its own character encoding in which ⊇ is a single byte long.)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You said that ⊇ is a single byte in Brachylog, why don't you paste the bytes here? I bet there's a reason for it, I'm just interested, bit of a character-encoding nub. \$\endgroup\$ Commented May 9, 2017 at 7:07
  • 1
    \$\begingroup\$ They're encoded on disk as 08 2B (you can look the encodings up here). The reason I didn't list the specific encoding is that it's irrelevant; all that really matters is that Brachylog uses no more than 256 unique characters, so that each can be represented in a single byte. This is commonly done by golfing languages to make the code more readable; they could use an encoding like code page 437 instead, but if you did that nobody would be able to read it. \$\endgroup\$ Commented May 9, 2017 at 7:10
11
\$\begingroup\$

05AB1E, 4 bytes

æOså

Explanation:

æ Calculate the powerset of the first input O Sum each element s Put the second input at the top of the stack å Check whether the input is in the powerset sum.

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Looks like you have officially misled everyone into compressing the list ;p \$\endgroup\$ Commented May 8, 2017 at 18:16
  • \$\begingroup\$ Once you have deleted your compressed list and moved it to the input, I'll delete my answer (because by the time our answers would be the same) \$\endgroup\$ Commented May 8, 2017 at 18:19
  • \$\begingroup\$ This community is full of geniuses. \$\endgroup\$ Commented May 8, 2017 at 19:40
5
\$\begingroup\$

Mathematica, 25 bytes

!FreeQ[Tr/@Subsets@#,#2]&

Pure function taking an array of coin-values as the first argument and the target integer as the second argument, and returning True or False.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Jelly, 6 bytes

ŒPS€e@

Try it online!

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ including you \$\endgroup\$ Commented May 8, 2017 at 18:17
  • \$\begingroup\$ @LeakyNun Heh, there's a better solution, isn't there. \$\endgroup\$ Commented May 8, 2017 at 18:17
  • \$\begingroup\$ @JonathanAllan Oh, whoops. Thanks! \$\endgroup\$ Commented May 8, 2017 at 18:54
  • \$\begingroup\$ Added a TIO link ;) \$\endgroup\$ Commented May 8, 2017 at 19:10
3
\$\begingroup\$

Haskell, 28 bytes

The operator function (#) takes an integer and a list of integers (or, more generally, any Traversable container of numbers) and returns a Bool.

Use as 6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000].

c#l=elem c$sum<$>mapM(:[0])l

Try it online!

How it works

  • c is the desired value and l the list of coin values.
  • mapM(:[0])l maps (:[0]) over l, pairing each value with 0, and then constructs the cartesian product, giving lists where each element is either its corresponding value in l, or 0.
  • sum<$> sums each combination, and elem c$ checks if c is in the resulting list.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Retina, 52 31 bytes

\d+ $* ^((1+) |1+ )+(?<-2>\2)+$

Try it online! Takes input as a space-separated list of coins and notes followed by the desired value. Edit: Saved 18 bytes thanks to @Kobi who debugged my code. Explanation: The first two lines simply convert from decimal to unary. The third line then captures the list of coins and notes. The alternation allows the engine to backtrack and choose not to capture specific coins/notes. The balancing group then matches the value against all suffixes of the the capture list (unnecessary but golfier.)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ The second option doesn't work because the engine doesn't backtrack into 0-length groups (an annoying optimization). You could use ^((1+) )+(\2?(?<-2>)|){99}$ (34 bytes, with limit on number of coins), or ^((1+) |1+ )+(\2?(?<-2>))+$ (also 34 bytes). \$\endgroup\$ Commented May 9, 2017 at 5:08
  • 1
    \$\begingroup\$ @Kobi Beautiful! I saved 2 bytes from both answers because I forgot that (?<-2>\2?) works, plus a further byte from your second answer because the ? is no longer necessary. \$\endgroup\$ Commented May 9, 2017 at 8:58
2
\$\begingroup\$

Brachylog, 7 bytes

tT&h⊇+T

Try it online!

How it works

tT&h⊇+T tT the second input is T & and h the first input ⊇ is a superset of a set + that sums up to T T

Including the combination, 9 bytes

tT&h⊇.+T∧

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Java (OpenJDK 8), 125 bytes

boolean f(int[]c,int n){int l=c.length;if(l<1)return n==0;int[]a=java.util.Arrays.copyOf(c,l-1);return f(a,n-c[l-1])|f(a,n);}

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Doing this in a lambda could make it shorter. \$\endgroup\$ Commented May 8, 2017 at 19:11
  • \$\begingroup\$ @Okx It is recursive (so it would be longer), plus I don't do lambdas even if they would be shorter. \$\endgroup\$ Commented May 8, 2017 at 19:14
  • 1
    \$\begingroup\$ The iterative version of your algorithm is way shorter as you remove the need to copy the array: boolean f(int[]c,int n){for(int l=c.length;l-->0;n-=n<c[l]?0:c[l]);return n<1;} (79 bytes). With Java 8 and its lambdas, it can further be reduced to 62 bytes. Regarding your answer as it currently is, int l=c.length-1 then using l instead of l-1 is also shorter. \$\endgroup\$ Commented May 9, 2017 at 13:30
2
\$\begingroup\$

Prolog (SWI), 46 bytes

a([],0). a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).

Try it online!

Fork of my Python answer.

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can probably save 2 bytes by using GNU Prolog instead (allowing you to spell is as #=, which would let you remove some whitespace). \$\endgroup\$ Commented May 8, 2017 at 22:46
2
\$\begingroup\$

JavaScript (ES6), 81 69 67 64 bytes

Takes the list of coins c and the target amount a in currying syntax (c)(a). Returns 0 or true.

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

Test cases

let f = c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1) const pound = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]; console.log(f(pound)(6)) console.log(f(pound)(15)) console.log(f(pound)(88)) console.log(f(pound)(512)) console.log(f(pound)(7003)) console.log(f(pound)(4)) console.log(f(pound)(209)) console.log(f(pound)(8889)) console.log(f(pound)(4242424242))

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Are you allowed to take the list of coins? \$\endgroup\$ Commented May 8, 2017 at 18:12
  • \$\begingroup\$ @LeakyNun "... and can take a list of coin/note values ..." \$\endgroup\$ Commented May 8, 2017 at 18:15
  • 1
    \$\begingroup\$ So I encoded the list for nothing... \$\endgroup\$ Commented May 8, 2017 at 18:16
  • \$\begingroup\$ @LeakyNun It seems so \$\endgroup\$ Commented May 8, 2017 at 19:09
2
\$\begingroup\$

R, 88 83 bytes

-5 bytes thanks to @Jarko Dubbeldam

returns an anonymous function. It generates all the possible combinations of coins (using expand.grid on pairs of T,F) and checks if the value(s) are present. k is coins since c is a reserved word in R. Can check multiple values at once.

function(k,v)v%in%apply(expand.grid(Map(function(x)!0:1,k)),1,function(x)sum(k[x]))

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You can replace c(T,F) by !0:1, and rep(list(!0:1),length(k)) by lapply(k,function(x)!0:1) \$\endgroup\$ Commented May 10, 2017 at 10:54
  • 1
    \$\begingroup\$ Actually, make that Map(function(x)!0:1,k) \$\endgroup\$ Commented May 10, 2017 at 11:02
2
\$\begingroup\$

Jelly, 4 bytes

ŒP§i

Try it online!

Powerset, vector sum, index.

Powerset gets all subsets, sum all the subsets, and check for the occurrence of the second argument

Returns 0 as the falsy value, and anything else otherwise.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 7 bytes

à mx èN

Try it online! Outputs 0 for falsy, a positive integer for truthy.

Explanation

à mx èN // Implicit: U = input array, V = input integer, N = array of all inputs à // Take all combinations of U. mx // Map each combination to its sum. è // Count the number of items in the result which also exist in N // the array of inputs. // This returns 0 if no combination sums to V, a positive integer otherwise. // Implicit: output result of last expression
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3, 52 bytes

5 bytes thanks to ovs.

f=lambda c,n:c and f(c[1:],n-c[0])|f(c[1:],n)or n==0

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Ruby, 39 bytes

Returns nil as the falsy value, and the smallest coin value in the list that makes up the number as truthy (all numbers are truthy in Ruby).

f=->c,n{n!=0?c.find{|i|f[c-[i],n-i]}:1}

Do beware, however, that this algorithm is insanely slow, with O(C!) time complexity, where C is the length of the coin list. It eventually finishes, but most test cases will time out on most online interpreters, even f(UK_POUND, 5).

Here is a 41-byte version that finishes much faster by adding an extra ending condition, and is much harder to actually time out

f=->c,n{n>0?c.find{|i|f[c-[i],n-i]}:n==0}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Bash + GNU utilities, 56 39

printf %$2s|egrep "^ {${1//,/\}? {}}?$"

Input denomination list (unsorted) is given as a comma-separated list. Input list and value are given as a command-line parameters.

Output given in the form of the shell return code. Inspect with echo $? after running the script. 0 means truthy, 1 means falsy.

Try it online.

  • printf %$2s outputs a string of value spaces
  • "^ {${1//,/\}? {}}?$" is a shell expansion that expands the denomination list to a regex like ^ {1}? {2}? {5}? {10}? ... $. It turns out that the egrep regex engine is smart enough to correctly match with this, regardless of what order the denominations are in
  • egrep checks if the string of spaces matches the regex
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C, 66 bytes

m;v;f(n){for(m=1e5;m/=10;)for(v=5;n-=n<v*m?0:v*m,v/=2;);return!n;}

See it work here.

C, 53 bytes

g(c,w,n)int*c;{for(;n-=n<c[--w]?0:c[w],w;);return!n;}

This variant takes the coin array, which defeats the purpose of this problem, because it comes down to simple subtraction.

The first argument is the coin array, the second is the coin count, and the third is the value.

C, 48 bytes

g(c,n)int*c;{for(;n-=n<*c?0:*c,*++c;);return!n;}

An alternative to the previous variant. It assumes that the coin array can be reversed and zero terminated.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyth, 6 bytes

/sMtyE

Test suite.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

CJam, 18 17 bytes

q~_,2\m*\f.*::+#)

Try it online!

Explanation

q~ e# Read and eval input. _, e# Duplicate the money list and take its length. 2\m* e# Take the (length)th Cartesian power of [0 1]. \f.* e# Element-wise multiplication of each set of 0's and 1's with the money e# list. This is essentially the powerset, but with 0s instead of e# missing elements. ::+ e# Sum each set. # e# Find the index of the desired amount in the list. (-1 if not found) ) e# Increment. -1 => 0 (falsy), anything else => nonzero (truthy)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 91 bytes

i,j,c[]={1,2,5};f(n){for(i=1000;i;i/=10)for(j=2;j>=0;j--)n-=n<i*c[j]?0:i*c[j];return n==0;}

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

PHP, 70 Bytes

prints 1 for true and nothing for false

<?foreach($_GET[1]as$v)$i-=$v*$r[]=($i=&$_GET[0])/$v^0;echo max($r)<2;

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Octave, 39 bytes

 @(L,n)any(cellfun(@sum,powerset(L))==n)

An anonymous function that takes an array of coin-values as the first argument and the target integer as the second argument, and returns true or false.

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 42 bytes

ListQ@NumberDecompose[#,Sort[#2,Greater]]&

input

[15,{10,5}]

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.