29
\$\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!

\$\endgroup\$
  • 4
    \$\begingroup\$ I wish we have more newcomers like you... \$\endgroup\$ – Leaky Nun May 8 '17 at 17:41
  • \$\begingroup\$ Related \$\endgroup\$ – Adnan May 8 '17 at 17:55
  • 2
    \$\begingroup\$ You should add some testcases using a different set of coin \$\endgroup\$ – Leaky Nun May 8 '17 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\$ – xnor May 8 '17 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\$ – user62131 May 8 '17 at 21:24

22 Answers 22

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

\$\endgroup\$
  • \$\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\$ – theonlygusti May 9 '17 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\$ – user62131 May 9 '17 at 7:10
10
\$\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!

\$\endgroup\$
  • \$\begingroup\$ Looks like you have officially misled everyone into compressing the list ;p \$\endgroup\$ – Leaky Nun May 8 '17 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\$ – Leaky Nun May 8 '17 at 18:19
  • \$\begingroup\$ This community is full of geniuses. \$\endgroup\$ – Tobi May 8 '17 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.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 6 bytes

ŒPS€e@

Try it online!

-2 bytes thanks to Leaky Nun
-13 bytes thanks to Leaky Nun (long story)

\$\endgroup\$
  • \$\begingroup\$ including you \$\endgroup\$ – Leaky Nun May 8 '17 at 18:17
  • \$\begingroup\$ @LeakyNun Heh, there's a better solution, isn't there. \$\endgroup\$ – HyperNeutrino May 8 '17 at 18:17
  • \$\begingroup\$ @JonathanAllan Oh, whoops. Thanks! \$\endgroup\$ – HyperNeutrino May 8 '17 at 18:54
  • \$\begingroup\$ Added a TIO link ;) \$\endgroup\$ – Okx May 8 '17 at 19:10
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.)

\$\endgroup\$
  • \$\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\$ – Kobi May 9 '17 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\$ – Neil May 9 '17 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!

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

\$\endgroup\$
  • \$\begingroup\$ Doing this in a lambda could make it shorter. \$\endgroup\$ – Okx May 8 '17 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\$ – Leaky Nun May 8 '17 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\$ – Olivier Grégoire May 9 '17 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.

\$\endgroup\$
  • 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\$ – user62131 May 8 '17 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))

\$\endgroup\$
  • \$\begingroup\$ Are you allowed to take the list of coins? \$\endgroup\$ – Leaky Nun May 8 '17 at 18:12
  • \$\begingroup\$ @LeakyNun "... and can take a list of coin/note values ..." \$\endgroup\$ – Martin Ender May 8 '17 at 18:15
  • 1
    \$\begingroup\$ So I encoded the list for nothing... \$\endgroup\$ – Leaky Nun May 8 '17 at 18:16
  • \$\begingroup\$ @LeakyNun It seems so \$\endgroup\$ – Eddie Hart May 8 '17 at 19:09
2
\$\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.
\$\endgroup\$
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!

\$\endgroup\$
  • \$\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\$ – JAD May 10 '17 at 10:54
  • 1
    \$\begingroup\$ Actually, make that Map(function(x)!0:1,k) \$\endgroup\$ – JAD May 10 '17 at 11:02
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
\$\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!

\$\endgroup\$
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!

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

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

Pyth, 6 bytes

/sMtyE

Test suite.

\$\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)
\$\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!

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

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

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

Mathematica, 42 bytes

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

input

[15,{10,5}]

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