Wow. I really liked this one. I ended up writing a lot of lines, but well documented. What I really wanted to showcase here is that sometimes, creating a more general function really pays off. In this case, I created a function that returns a list of all possible coin configurations (sorted by number of coins). Once I had that, I just needed to return the first solution and add the number of coins.
fromtypingimportList,Dictimportnumpydefsplit_in_denominations(amount:int,denominations:List[int])->List[Dict[int,int]]:""" Gives all distinct ways to express amount in items from denominations
The algorithm used is to find all solutions for each smaller amount and
each smaller list of (sorted) denominations. For example, for the amount
of 3 and denominations [1, 2], the following Numpy array is created:
Amount: | 0 | 1 | 2 | 3 |
Denominations: +-----------+-----------+-----------+-----------+
[1] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0}]|[{1:3,2:0}]|
[1,2] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0},|[{1:3,2:0},|
| | | {1:0,2:1}]| {1:1,2:1}]|
+-----------+-----------+-----------+-----------+
This result array is built row by row from the top left to the bottom
right. For each cell, only two (disjunct!) solution sets have to be
considered: the one directly above (not using the current denomination)
and the one 1 of the denomination value to the left. For that latter set,
you just need to count one extra of denomination.
Arguments:
amount: integer value that has to be expressed in denominations
denominations: list of values
Returns:
List with all unique dicts with denomination as key and the count
of that denomination as value. The list is sorted by the sum of
the count of all denominations (the least number of coins)
Raises:
ValueError is the amount can't be expressed by denominations
Examples:
>>> split_in_denominations(13, [1, 5, 10, 25])
[{1: 3, 5: 0, 10: 1, 25: 0}, # 3 coins
{1: 3, 5: 2, 10: 0, 25: 0}, # 5 coins
{1: 8, 5: 1, 10: 0, 25: 0}, # 9 coins
{1: 13, 5: 0, 10: 0, 25: 0}] # 13 coins
"""# Template solution: an empty dict with count 0 of each denominations
zero_denom={d:0fordindenominations}# Edge case: amount == 0
ifamount==0:return[zero_denom]# result array with all intermediate solutions
result=numpy.ndarray((amount+1,len(denominations)),dtype=list)# Loop over the sorted denominations
fordenom_idx,denominenumerate(sorted(denominations)):foramount_idxinrange(amount+1):# In the first iteration of denom, fill the first row of result
ifdenom_idx==0:# Start with a copy of the template solution
result[amount_idx,0]=[dict(zero_denom)]# If amount is divisible by denom, add that solution
ifamount_idx%denom==0:result[amount_idx,0][0][denom]=amount_idx//denom# Now add the other denominations one by one in each loop
else:# Copy the results from the previous denomination list
result[amount_idx,denom_idx]=list(result[amount_idx,denom_idx-1])# Extend the result with the solutions from
# amount_idx minus denom, with 1 extra count of denom
ifamount_idx>=denom:forsolutioninresult[amount_idx-denom,denom_idx]:new_solution=dict(solution)new_solution[denom]+=1result[amount_idx,denom_idx].append(new_solution)# Check if there is a result (result does not only contain the template)
ifresult[amount,len(denominations)-1]==[zero_denom]:raiseValueError(f"{amount} can't be expressed in {denominations}")returnsorted(result[amount,len(denominations)-1],key=lambdas:sum(s.values()))defleast_num_denominations(amount:float,denominations:List[float])->int:""" Gives the least number of denominations that is needed to sum to amount
Arguments:
amount: numeric value that has to be expressed in denominations
denominations: list of values
Returns:
The least number of denominations.
Returns None of there is no possible split into denominations.
Examples:
>>> least_num_denominations(4, [1, 2, 3]) # (2, 2) or (1, 3)
2
"""returnsum(split_in_denominations(amount,denominations)[0].values())defmain():denominations={'coins1':[1,5,10,25],'coins2':[1,2,5,10,20,50],'coins3':[1,5,20,25],}cases=[('coins1',13),# 123),
('coins2',13),# 123),
('coins1',75),('coins2',75),('coins3',40),]forden_name,amountincases:d=denominations[den_name]print(f'Least split of {amount} in {d} is: '+f'{least_num_denominations(amount,d)} (there are '+f'{len(split_in_denominations(amount,d))} ways to split)')if__name__=='__main__':main()
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Wow. I really liked this one. I ended up writing a lot of lines, but well documented. What I really wanted to showcase here is that sometimes, creating a more general function really pays off. In this case, I created a function that returns a list of all possible coin configurations (sorted by number of coins). Once I had that, I just needed to return the first solution and add the number of coins.
Try it online!