11
\$\begingroup\$

I have $15 in my pocket. Likewise, I am in a store which doesn't give change. While browsing, I spot an item that costs $10 (tax included). Can I buy that item without losing any money?

In this case, the answer is yes. No matter how my $15 is divided up (one 10 and one 5, or three 5s, or something else), I will always have the exact $10 needed.

As a second example, I have $0.16 in my pocket. What other amounts of money must I be able to pay exactly?

Possible Divisions:
0.01, 0.05, 0.10
0.01, 0.05 x 3
0.01 x 16
Guaranteed Exact Change:
0.01, 0.05, 0.06, 0.10, 0.11, 0.15, 0.16

What if I have $0.27 in my pocket?

Possible Divisions:
0.01 x 2, 0.25
0.01 x 2, 0.05, 0.10 x 2
0.01 x 2, 0.05 x 3, 0.10
0.01 x 2, 0.05 x 5
0.01 x 27
Guaranteed Exact Change:
0.01, 0.02, 0.25, 0.26, 0.27

In the above case, there were only a few amounts of money for which I would always have perfect change.

Your task

Write the shortest program (or named function) which takes A) an integer amount of money and B) a list of possible denominations as input, and outputs a list of the amounts of money for which I must have perfect change. Input can be either STDIN or arguments for the program or function. I'm not going to be super-strict on input formatting; it can match how your language formats arrays.

Perhaps a More Detailed Explanation

I have a certain amount of money in my pocket, which is formed from a set of possible demonstrations of currency. If I have $8, and I know that the possible denominations are $2 and $3, then there's only so many different combinations of bills that could be in my pocket. These are 2+2+2+2 and 3+3+2. In order to be able to produce an exact amount of money, I have to be able to produce that quantity using the only the bills that are in my pocket. If I had four 2s, I could produce 2, 4, 6, or 8. If I had two 3s and a 2, I could produce 2, 3, 5, 6, or 8 Since I don't know which of these combinations I actually have in my pocket, my final answer is reduced to 2, 6, 8. These are the values I know I could produce from my pocket, given the total amount and the possible denominations.

Hand-Calculated Example I/O

7 [3, 4]
3, 4, 7        //only one possible division into 3 + 4

7 [3, 2]
2, 3, 4, 5, 7  //the only division is 3 + 2 + 2

6 [2, 3, 4]
6     //divisions are 2+2+2, 3+3, 2+4 

16 [1, 5, 10, 25]          //this represents one of the examples above
1, 5, 6, 10, 11, 15, 16

27 [1, 5, 10, 25]          //another example from above
1, 2, 25, 26, 27

1500 [1, 5, 10, 25, 100, 500, 1000, 2000]
500, 1000, 1500

600 [100, 500, 1000, 2000]
100, 500, 600

600 [200, 1, 5, 10, 25, 100, 500, 1000, 2000]
600
\$\endgroup\$
  • \$\begingroup\$ This is very unclear. \$\endgroup\$ – motoku Feb 27 '15 at 1:30
  • \$\begingroup\$ @FryAmTheEggman I have added a "perhaps a more detailed explanation." Let me know if it is still confusing. (I also removed an edge case because it was pretty much pointless.) \$\endgroup\$ – PhiNotPi Feb 27 '15 at 2:42
  • \$\begingroup\$ I don't see how you're getting 6 [2, 3, 4]. Can't 2+2+2 not make 3, and 3+3 not make 2 and 4? \$\endgroup\$ – xnor Feb 27 '15 at 7:44
  • \$\begingroup\$ @xnor you are correct, fixed. \$\endgroup\$ – PhiNotPi Feb 27 '15 at 12:42
  • \$\begingroup\$ Should the program run in reasonable time for all the inputs? E.g. my shortest idea is exponential in the starting amount and 2^1500 is a lot of anything. \$\endgroup\$ – randomra Feb 28 '15 at 5:21
2
\$\begingroup\$

Python 2, 200 197 193 140 bytes

f=lambda n,D,S={0}:sum([f(n-x,D,S|{x+y for y in S})for x in D],[])if n>0else[S]*-~n
g=lambda*a:(f(*a)and reduce(set.__and__,f(*a))or{0})-{0}

(Thanks to @Nabb for tips)

Here's a poorly golfed solution for now to get things started. Call with g(16, [1, 5, 10, 25]) — output is a set with the relevant denominations.

The approach is straightforward, and is broken down into two steps:

  • f looks at all ways of reaching n with denominations D (e.g. [1, 5, 10]), and for each one it works out all amounts that can be made with these denominations (e.g. set([0, 1, 5, 6, 10, 11, 15, 16])).
  • g calculates the intersections of the results of f, then removes 0 for the final answer.

The program solves cases 1-5 and 7 fine, stack overflows on 6 and takes forever on 8.

If there is no solution (e.g. g(7, [2, 4, 6])), then the program returns an empty set. If an error is allowed to be thrown for such a case, then here is a shorter g:

g=lambda*a:reduce(set.__and__,f(*a))-{0}
\$\endgroup\$
  • \$\begingroup\$ g=lambda L,c=0:L and g(L[1:],c)|g(L,c+L.pop(0))or{c} is a little shorter \$\endgroup\$ – Nabb Mar 1 '15 at 8:18
  • \$\begingroup\$ A bit more by moving -{0} into g and using [L]*-~n instead of [L][-n:] \$\endgroup\$ – Nabb Mar 1 '15 at 8:34
1
\$\begingroup\$

JavaScript (ES6) 162 203 207

Edit Changed the way to intersect result sets in array r. A bit faster, but the algorithm still stinks.

More detailed explanation will follow.
Shortly : c is a recursive function that enumerate all the possible subdivisions. k is a recursive function that enumerate all the possible sums without repetitions. Any new result set found with k function is compared with the previous set found, only the common results are kept.

Why is it so slow? Having to manage a target total of, say, 1500 and a single piece of value 1, enumerating all the possibile sums is not a good idea.

F=(s,d,r,
  c=(s,i,t=[],v,k=(i,s,v)=>{for(;v=t[i++];)k(i,s+v);o[s]=s})=>
  {for(s||(i=k(o=[],0),r=(r||o).filter(v=>o[v]));v=d[i];++i)s<v||c(s-v,i,[...t,v])}
)=>c(s,0)||r

Ungolfed

F=(s,d)=>{
  var r
  var c=(s,i,t=[])=>
  {
    var o=[],v
    var k=(i,s)=> // find all sums for the current list t, set a flag in the o array
    {
      var v
      for(;v=t[i++];)k(i,s+v)
      o[s]=s
    }

    if (s==0) {
      k(0,0)
      if (r)
        r = r.filter(v=>o[v]) // after first loop, intersect with current
      else
        r = o.filter(v=>v) // first loop, keep all results
    } 
    else
      for(;v=d[i];++i)
      { 
        if (s >= v) 
          c(s-v, i, t.concat(v))
      }
  }
  c(s,0) // enumerate all possible set of pieces
  return r
}

Test In Firefox/FireBug console

F(16,[1,5,10,25])

[1, 5, 6, 10, 11, 15, 16]

(time 84 msec)

F(27, [1, 5, 10, 25]) 

[1, 2, 25, 26, 27]

(time 147252 msec, so not sooo fast)

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

Wolfram Methematica, 104 bytes

Rest@*Intersection@@Map[Total]/@Subsets/@Union[Sort/@IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]]]&

Ungolfed (read from the end):

Rest@* // Removing 0
  Intersection@@   // Intersecting all totals
     Map[Total]/@  // Counting total of each subset
        Subsets/@  // Getting all the subsets of each partition
           Union[  // Removing duplicates 
              Sort/@ // Sorting each partition (to remove duplicates next)
                 IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]] // Getting all Integer partitions
                ]&
\$\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.