35
1
I need to go to the bank and withdraw some money. I need to withdraw $30, $22 to pay my roommate for the internet and $8 for laundry. Since neither of these can make change, I need my $30 to be split into two partitions of the two sizes. That means when the teller asks me how I want my $30 I am going to have to make a request. I could tell them I want it in a twenty, a fiver, and five ones. But I want to make my request as simple as possible as to avoid having to repeat myself. To make my request simpler I could ask that my cash contain a twenty and at least 2 ones because the 8 is implied by the total, but better yet I could simply request that one of the bills I receive be a one dollar bill (If you are not convinced of this just try to make 29 dollars without making 8).
So that's all fine and dandy but I need to do this calculation every time I go to the bank so I thought I would write a program to do this (have you write a program to do this for me).
Your program or function should take a list of integers representing all the payments I need to make and a set of integers representing the denominations of bills available at the bank, and you must output the smallest list of denominations such that every way to make the total that includes that list of denominations can be cleanly divided into the list of payments.
Extra rules
You may assume that the denomination list will always contain a
1
or you may add it to each list yourself.Some inputs will have multiple minimal solutions. In these cases you may output either one.
This is code-golf so answers will be scored in bytes with less bytes being better.
Test Cases
Payments, denominations -> requests
{22,8} {1,2,5,10,20,50} -> {1} or {2}
{2,1,2} {1,5} -> {1}
{20,10} {1,2,5,10,20,50} -> {}
{1,1,1,1} {1,2} -> {1,1,1}
{20,6} {1,4,5} -> {1}
{2,6} {1,2,7} -> {2}
{22, 11} {1, 3, 30, 50} -> {1, 3}
{44, 22} {1, 3, 30, 50} -> {1, 3, 3, 30}
22At first I thought this was spam or off-topic or something... – Erik the Outgolfer – 2017-09-21T16:57:49.683
1@EriktheOutgolfer paragraphs hurt challenges so much >_< – Magic Octopus Urn – 2017-09-21T17:46:06.420
2I think you should include at least one test case where the request must be something other than one-dollar bills, like
{2,6} {1,2,7} -> {2}
. – Arnauld – 2017-09-22T02:49:29.167@Arnauld I've added your case – Post Rock Garf Hunter – 2017-09-22T02:50:33.287
1
(If you are not convinced of this just try to make 29 dollars without making 9)
You mean without making 8? Or did I misunderstand – undergroundmonorail – 2017-09-22T18:40:40.017@undergroundmonorail I must have mistyped. Its fixed now. – Post Rock Garf Hunter – 2017-09-22T20:01:30.787
@JonathanAllan While this is true it is not possible to avoid making 8. I had originally written what you have, but I realized I could make a stronger argument. I'll add your testcases when I've verified them. – Post Rock Garf Hunter – 2017-09-22T20:03:02.190