Find the best next key in a dictionary which value fits in a constrain

Question

I have a dictionary with names:weights of cows.

cows = {'Herman': 7, 'Moo Moo': 3, 'Betsy': 9, 'Lola': 2, 'Milkshake': 2, 'Florence': 2, 'Henrietta': 9, 'Maggie': 3, 'Millie': 5, 'Oreo': 6}

I have to create a list of lists from this dictionary using a greedy algorithm. Each sub-list has a constrain: the weight limit is 10. That means, I have to select the biggest cow by weight first and find the next cow that fits in the sub-list. For example, the right answer for the problem with this dictionary would be:

[ ['Betsy'],
['Henrietta'],
['Herman', 'Moo Moo'],
['Oreo', 'Maggie'],
['Millie', 'Florence', 'Milkshake'],
['Lola']]

I'm trying to create a function to find the next best fit for the subtrip. For example, if the first element of the sublist is 'Herman' (weight of 7 tons), I need to find the next key that fits best the value that gets closer to 10, in this case is 'Moo Moo' (weight of 3 tons). So, here is the function I wrote to find the next fit:

def findNextFit(adict, val, limit=10):             
       v=list(adict.values())               # list of the dict's values
       k=list(adict.keys())                 # list of the dict's keys
       diff = limit - val                   # value we are looking for

       if diff in v:                        # Perfect fit.
           return k[diff]

       elif diff not in v or diff < 0:      # No fit. 
           return False

       else:               # Difference is positive but not a perfect fit
           vfit = [i for i in v if i < diff]    # list of candidates
           return k[max(vfit)]                  # key with maximum value

When I test this function I get an unexpected result:

>>> findNextFit(cows, 7, 10)
'Lola'

Where I should have get as a result 'Moo Moo'.

Anybody can point me at what I'm doing wrong in this findNextFit function?. I have been working on it the whole day and I'm running out of ideas.

Answer 1

Your issue is here:

 if diff in v:                        # Perfect fit.
       return k[diff]

diff is not necessarily the index at which the corresponding key for the entry with value diff would be.

You can fix this by using the index* method:

if diff in v:
    return k[v.index(diff)]

Similarly in your third conditional you'd have to do: return k[v.index(max(fit))]

Also your second conditional should not be an or but rather an and.

With all fixes:

def findNextFit(adict, val, limit=10):             
     v=list(adict.values())               # list of the dict's values
     k=list(adict.keys())                 # list of the dict's keys
     diff = limit - val                   # value we are looking for

     if diff in v:                        # Perfect fit.
         return k[v.index(diff)]

     elif diff < 0:      # No fit. Don't need to check if diff not in v because earlier if wouldve caught this case
         return False

     else:               # Difference is positive but not a perfect fit
         vfit = [i for i in v if i < diff]      # list of candidates
         if not vfit: return False
         return k[v.index(max(vfit))]                  # key with maximum value