Python Forum

New to Python and Algorithims. Trying to solve this one before looking for solutions. Im having the problem towards the bottom where the coin is suppose to be appended to the list, if this doesn't happen then the condition never becomes false.

def rec_coins(target,coins):
    
    coins = sorted(coins)
    mincoinsneeded = []
    sum_of_coins = sum(mincoinsneeded)
    current_accum = target - sum_of_coins

    while sum_of_coins != target:

        for coin in reversed(coins):
            
            if coin == target:
                return coin

            elif current_accum % coin != 0:
                coins.pop()

            else:

                while current_accum % coin > 1:
                    mincoinsneeded.append(coin)

    print (mincoinsneeded)

rec_coins(20,[1,5,10])

What this function should do/return?

EDIT: if one wants to find coins needed for certain amount one can use built-in function divmod() combined with dictionary. (for quite obvious reasons one should start from largest):

def coins(amount, coins=(50, 20, 10, 5, 2, 1)):
    quantities = dict() 
    for coin in coins: 
        quantities[coin], amount = divmod(amount, coin) 
    return {k:v for k, v in quantities.items() if v !=0} # or 'return quantities', zero quantity coins are kept

One can adjust available coins for it's own currency and usage is simple:

>>> coins(121)
{50: 2, 20: 1, 1: 1}

EDIT: if total amount of coins is needed then function should return sum(quantities.values())

@perfringo, its suppose to return the minimum amount of coins needed to reach the target amount.

---

Thank you perfringo, I was trying to solve it with my solution. Its seems that the numbers append to the list but the

current_accum = target - sum_of_coins

is not working, so it gets stuck in the while loop

---

Apologies, its actually this part that doesnt seem to be working:

sum_of_coins = sum(mincoinsneeded)

This is because sum will always be 0:

>>> min_coins_needed = []
>>> sum_of_coins = sum(min_coins_needed)     # sum returns immutable numeric
>>> sum_of_coins
0
>>> min_coins_needed.append(5)
>>> min_coins_needed
[5]
>>> sum_of_coins
0

Starting to recognize that now as I editing the code, how would I go about fixing this?

One way could be:

while sum(min_coins_needed) != target:

Figured it out. Thank you!

def rec_coins(target,coins):
    
    
    mincoinsneeded = []

    while sum(mincoinsneeded) != target:

        for coin in reversed(coins):
            
            if coin == target:
                return coin

            else:

                while (target - sum(mincoinsneeded)) / coin >= 1:
                    mincoinsneeded.append(coin)

    print (mincoinsneeded)

rec_coins(37,[1,5,10])

I observe that you reverse coins list but not sort. This works well if coins list is initially sorted in ascending order but in all other cases there will be unexpected results:

>>> rec_coins(37, [1, 5, 10])                                                              
[10, 10, 10, 5, 1, 1]
>>> rec_coins(37, [5,1, 10])                                                               
[10, 10, 10, 1, 1, 1, 1, 1, 1, 1]

If there is possibility that list is not sorted ascending then sorted(coins, reverse=True) could be used

I personally not big fan of printing and returning None from function. No flow control and and probably somebody tries to print or give it a name. This code especially unpredictable as in some cases it returns integer and in some cases prints list and returns None.

>>> print(rec_coins(37, [1, 5, 10]))                                                       
[10, 10, 10, 5, 1, 1]
None
>>> coins = rec_coins(37, [1, 2, 10])                                                      
[10, 10, 10, 2, 2, 2, 1]
>>> coins        # Nothing happens as coins is None                                                                                  
>>> type(coins)                                                                            
NoneType
>>> rec_coins(10, [5,1, 10])                                                               
10
>>> print(rec_coins(10, [5,1,10]))                                                         
10
>>> coins = rec_coins(10, [5,1,10])                                                        
>>> coins                                                                                  
10

Thank you for the feedback! I added the sort before I read this, but thank you for that as well. Is there any improvements to this that can be done, or is a recursive approach better?