Greedy algorithm in Python

Question

I want c in plunder(aList, c) to equal 0.

List = [('Gold', 10, 500), ('Silver', 5, 200), ('Diamond', 2, 2000), ('Platinum', 20, 1000)]
aList = sorted(List, key =  lambda x : x[2]) # sort the list above

Gives me the sorted list based on the 3rd value of each tuple. So I get:

[('Silver', 5, 200), ('Gold', 10, 500), ('Platinum', 20, 1000), ('Diamond', 2, 2000)]

I am trying to get the plunder(aList, c) to keep subtracting the middle values of each tuple (2, 20, 10, 5) from c until c = 0.

Here is my code:

List = [('Gold', 10, 500), ('Silver', 5, 200), ('Diamond', 2, 2000), ('Platinum', 20, 1000)]
aList = sorted(List, key =  lambda x : x[2]) # sort the list above

def plunder(aList, c):
    aList[-1] = list(aList[-1])
    i = aList[-1]
    r = 0
    if c > 0 and i[1] != 0:
        c -= 1
        i[1] -=1
        r += 1
        return plunder(aList, c-r)
    elif c == 0:
        pass
        print('Done')
    else:
        return plunder(aList[:-1], c-r)

plunder(aList, 10)

But when I run it, it prints done and the new list is:

[('Silver', 5, 200), ('Gold', 10, 500), ('Platinum', 20, 1000), ['Diamond', 0, 2000]]

and also when I type c in the python shell, it tells me that c is not defined. How could I fix these issues?

So if the c value is 10. My expected output would be:

[('Silver', 5, 200), ('Gold', 10, 500), ['Platinum', 12, 1000], ['Diamond', 0, 2000]]

I subtracted as many diamonds as I could from the 10 (10 - 2 = 8) so 0 diamonds were left. Then I subtracted 8 from 20 platinums and the weight of the platinums changed to 12 (since I took 8 platinums. And now my c ('capacity') is 0. 2 diamonds + 8 platinums = 10 (which was my c).

Answer 1

The main problem is that you are relying on Python's pass by reference for lists to modify the list in place. That works fine initially, but when you reach

plunder(aList[:-1], c-r)

Python creates a copy of the list and proceeds to modify that copy. Thus your original list remains unchanged after Diamonds are exhausted (you hit the else part).

Note that you can see this behaviour in your printed aList as only last entry is a list and all other are tuples.

[
 ('Silver', 5, 200), 
 ('Gold', 10, 500), 
 ('Platinum', 20, 1000), 
 ['Diamond', 0, 2000]   #Only list
]

If you add a print alist[-1] statement to the function, you can see it even more clearly.

['Diamond', 2, 2000]
['Diamond', 1, 2000]
['Diamond', 0, 2000]
['Platinum', 20, 1000]
['Platinum', 19, 1000]
['Platinum', 18, 1000]
['Platinum', 17, 1000]
['Platinum', 16, 1000]
['Platinum', 15, 1000]
['Platinum', 14, 1000]
['Platinum', 13, 1000]
['Platinum', 12, 1000]

So your algorithm does work but as you have no way of keeping the result, it does not (fully) affect your original list.

Answer 2

Here is what I think is a more simple approach. Simply iterate through the available treasure and grab as much as you can/need from each one.

def demo():
    units_to_plunder = 10
    treasure = new_treasure_pile()
    plundered_units = plunder_units(treasure, units_to_plunder)
    print treasure
    print plundered_units

    units_to_plunder = 1000
    treasure = new_treasure_pile()
    plundered_units = plunder_units(treasure, units_to_plunder)
    print treasure
    print plundered_units



def plunder_units(treasure, total_plunder_units):
    treasure_sorted = list(sorted(treasure, key=lambda t: t[2], reverse=True))
    plundered = list()
    for treasure_type in treasure_sorted:
        # stop condition when desired units taken
        if total_plunder_units <= 0:
            break
        t_units_to_take = min(total_plunder_units, treasure_type[1])
        # update the 3 moving parts
        treasure_type[1] -= t_units_to_take
        plundered.append([treasure_type[0], t_units_to_take, treasure_type[2]])
        total_plunder_units -= t_units_to_take
    return plundered


def new_treasure_pile():
    return [['Gold', 10, 500],
            ['Silver', 5, 200],
            ['Diamond', 2, 2000],
            ['Platinum', 20, 1000]]


if __name__ == '__main__':
    demo()

Output for c=10 (I think as you expect)

[['Gold', 10, 500], ['Silver', 5, 200], ['Diamond', 0, 2000], ['Platinum', 12, 1000]]
[['Diamond', 2, 2000], ['Platinum', 8, 1000]]

Output for c=1000 (take it all)

[['Gold', 0, 500], ['Silver', 0, 200], ['Diamond', 0, 2000], ['Platinum', 0, 1000]]
[['Diamond', 2, 2000], ['Platinum', 20, 1000], ['Gold', 10, 500], ['Silver', 5, 200]]