Lecture "Greedy algorithms", exercise 1

[essepuntato]

Implement the algorithm introduced in Section "Greedy algorithms" for returning the minimum amount of coins for a change. Accompany the implementation of the function with the appropriate test cases.

[dbrembilla]

I am not really sure why, but while trying to run this function it considered change_value, which was 0, bigger than 0. Is there some problem (maybe with the type float) that might do that?

def coins_for_change(money_to_change):
    change_value = money_to_change
    dict_change = dict()
    while change_value - 0.01 >= 0:
        if change_value >= 2:
            if "2€" not in dict_change:
                dict_change["2€"] = 1
                change_value -= 2
            else:
                dict_change["2€"] += 1
                change_value -= 2
        elif change_value >= 1:
            if "1€" not in dict_change:
                dict_change["1€"] = 1
                change_value -= 1
            else:
                dict_change["1€"] += 1
                change_value -= 1
        elif change_value >= 0.5:
            if "0,50€" not in dict_change:
                dict_change["0,50€"] = 1
                change_value -= 0.5
            else:
                dict_change["0,50€"] += 1
                change_value -= 0.5
        elif change_value >= 0.2:
            if "0,20€" not in dict_change:
                dict_change["0,20€"] = 1
                change_value -= 0.2
            else:
                dict_change["0,20€"] += 1
                change_value -= 0.2
        elif change_value >= 0.1:
            if "0,10€" not in dict_change:
                dict_change["0,10€"] = 1
                change_value -= 0.1
            else:
                dict_change["0,10€"] += 1
                change_value -= 0.1
        elif change_value >= 0.05:
            if "0,05€" not in dict_change:
                dict_change["0,05€"] = 1
                change_value -= 0.05
            else:
                dict_change["0,05€"] += 1
                change_value -= 0.05
        elif change_value >= 0.02:
            if "0,02€" not in dict_change:
                dict_change["0,02€"] = 1
                change_value -= 0.02
            else:
                dict_change["0,02€"] += 1
                change_value -= 0.02
        else:
            if "0,01€" not in dict_change:
                dict_change["0,01€"] = 1
                change_value -= 0.01
            else:
                dict_change["0,01€"] += 1
                change_value -= 0.01
    result = set(dict_change.items())
    return result

def test(money_to_change, expected_set):
    result= coins_for_change(money_to_change).difference(expected_set)
    print(result)
    return result == set()
print(test(1.36, {('0,10€', 1), ('0,01€', 1), ('0,05€', 1), ('0,20€', 1), ('1€', 1)}))
print(test(2.63, {('2€', 1), ('0,50€', 1), ('0,10€', 1), ('0,02€', 1), ("0,01", 1)}))
print(test(3.72, {('0,50€', 1), ('0,02€', 1), ('0,20€', 1), ('1€', 1), ('2€', 1)}))

[ChiaraCati]

def test_coin_change(coins_list, total, given, expected):
    t_result = coin_change(coins_list, total, given)
    if t_result== expected:
        return True
    else:
        return False

def coin_change(coins_list, total, payed):  
    coins_d = dict()
    change = payed - total
    secure = change + 0.001
    tot_amount = 0
    if total >= payed:
        return None

    for coin in coins_list:
        amount = int(secure // coin)
        if amount > 0 and change > 0.001:
            coins_d[coin] = int(amount)
            tot_amount += int(amount)
            change -= (int(amount) * coin)
            secure -= (int(amount) * coin)

    return tot_amount

eu_coins = [2.0, 1.0, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01]

print(test_coin_change(eu_coins, 20, 12.95, None))
print(test_coin_change(eu_coins, 20, 20, None))
print(test_coin_change(eu_coins, 15.36, 20, 6))
print(test_coin_change(eu_coins, 15, 20, 3))
print(test_coin_change(eu_coins, 15.91, 20, 5))
print(test_coin_change(eu_coins, 15.9, 20, 3))
print(test_coin_change(eu_coins, 15.99, 20, 3))
print(test_coin_change(eu_coins, 15.95, 20, 3))
print(test_coin_change(eu_coins, 12.95, 20, 5))

[fcagnola]

I know the instructions were to only return the amount of the change, but I thought it would be useful to see if the function actually worked in real-life situations. I opted for returning a tuple with the list of coins to give back as change and the value of the change in euros.

def test_2_parameter(function, p1, p2, expected):
    result = function(p1, p2)
    return result == expected

def greedy_coin_change(amount, paid):
    coin_types = [2, 1, 0.5, 0.2, 0.1, 0.02, 0.01]  # this list contains all coin types decrementally ordered
    coins = []     # this list will contain the result, with all coins used as change
    if paid == amount:
        return None
    else:
        for coin in coin_types:  # loops through coins
            if amount + coin <= paid:
                while amount + coin <= paid:  # continue adding change until the paid sum is reached
                    amount += coin
                    coins.append(coin)  # add each coin to the result list
    return coins, sum(coins)

print(test_2_parameter(greedy_coin_change, 13, 20, ([2,2,2,1], 7))) # returns True
print(test_2_parameter(greedy_coin_change, 16.73, 20, ([2, 1, 0.2, 0.02, 0.02, 0.02, 0.01], 3.27))) # returns True
print(test_2_parameter(greedy_coin_change, 20, 20, None)) # returns True

[AleRosae]

Since it is supposed to be a greedy algorithm I tried not only to return a collection of coins needed to reach a specific change, but also the "best" set of coins avoiding as much as possible small coins. This code apparently works, but for reasons I cannot understand sometimes it skips an if statement (I have checked that on python tutor), thus returning a different list from the one expected. Can someone explain to me why?

def test_greedy_coins(amount, price, expected):
    if greedy_coins(amount, price) == expected:
        return True
    else:
        return False

def greedy_coins(amount, price):

    change = abs(price - amount) #calculate the change value
    result = list() #create the list of coins to return
    while change != 0: #iterate until there is no charge left
        if (change - 2) >= 0:
            result.append("2€")
            change = change - 2
        else:
            if (change - 1) >= 0:
                    result.append("1€")
                    change = change - 1
            else:
                if (change - 0.50) >= 0:
                        result.append("0,50€")
                        change = change - 0.50
                else:
                    if (change - 0.20) >= 0:
                            result.append("0,20€")
                            change = change - 0.20
                    else:
                        if (change - 0.10) >= 0:
                                result.append("0,10€")
                                change = change - 0.10
                        else:
                            if (change - 0.05) >= 0:
                                    result.append("0,05€")
                                    change = change - 0.05
                            else:
                                if (change - 0.02) >= 0:
                                        result.append("0,02€")
                                        change = change - 0.02
                                else:
                                    if (change - 0.01) >= 0:
                                            result.append("0,01€")
                                            change = change - 0.01
                                    else:
                                        result.append("0,01€")
                                        change = 0

    return result

print(test_greedy_coins(20,16,["2€", "2€"]))
print(test_greedy_coins(20,15.50,["2€", "2€", "0,50€"]))
print(test_greedy_coins(20,13.64,["2€", "2€", "2€", "1€", "0,20€", "0,10€", "0,05€", "0,01€"]))
print(test_greedy_coins(20,13.38,['2€', '2€', '2€', '1€', '0,50€', '0,10€', '0,02€'])) # returns false because the output is ['2€', '2€', '2€', '1€', '0,50€', '0,10€', '0,01€', '0,01€']

[yunglong28]

Not as precise as @essepuntato's solution for sure but I think this reflects at least the greedy algorithm logic:

   def test_money_change(amount_to_change, coins_list, expected):
    if money_change(amount_to_change, coins_list) == expected:
        return True
    else:
        return False

def money_change(amount_to_change, coins_list):
    change = []

    for coin in coins_list:
        still_to_add = amount_to_change
        maximal = max(coins_list)
        change.append(maximal)  #being greedy: always append the max value
        coins_list.remove(maximal)
        still_to_add -= sum(change)
        if still_to_add > 0:
            if still_to_add in coins_list:  #if I have the exact other value I go with that
                idx = coins_list.index(still_to_add)
                change.append(coins_list[idx])
                still_to_add -= coins_list[idx]
                if still_to_add == 0:
                    return change
        elif still_to_add < 0:
            change.clear()
            still_to_add = 0
        elif still_to_add == 0:
            return change
    return []

print(test_money_change(0.5, [2, 2, 0.5, 0.5, 0.2, 0.5, 1], [0.5]))  #True
print(test_money_change(5, [2, 2, 0.5, 0.5, 0.2, 0.5, 1], [2, 2, 1]))  #True
print(test_money_change(3, [2, 2, 0.5, 0.5, 0.2, 0.5, 1], [2, 1])) #True 
`