Given a dictionary of cows and their weight:

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

I want to get a list of lists to move all cows, each nested list of cow's a total weight <= 10, hence to first two trips will have just Betsy and Henrietta:


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

Here is my code that took too long in a net grader:

def greedy_cow_transport(cows,limit=10):
    train = []
    cart = [] 

# get tuples from dictionary key ordered by value high to low
    CowTupleList = sorted(cows.items(), key=lambda x: x[1], reverse = True)

# put cow names in list order high to low to loop over
    names = []
    for i in range(len(cows)):
    train = []
    while sum(cows.values()) > 0:
        cart = []
        total = 0

        for cow in names:
            if cows[cow] != 0 and cows[cow] + total <=limit:
                total += cows[cow]
                cows[cow] = 0
    return train

This took too much time for the online grader, so I failed. Can this be done in only a few lines?


3 Answers 3


You sort the cows, but you don't take advantage of the fact that they're sorted. Instead of iterating over the cows multiple times (which leads to \$\mathcal{O}(n^2)\$ time w.r.t. the number of cows), iterate over the sorted list once.

Unfortunately, I can't think of an easy way to do this using Python's built-in data structures. However, if we assume that CowTupleList is some list-like datastructure that has \$\mathcal{O}(\log{n})\$ or better performance for all operations (including del), then we can use binary search to find the largest cow that will fit in a cart's remaining capacity:

def greedy_cow_transport(cows,limit=10):
  # Sort cows from largest to smallest
  CowTupleList = sorted(cows.items(), key=lambda x: x[1], reverse = True)

  while CowTupleList:
    # Add first (largest) cow to a new cart
    name,weight = CowTupleList[0]
    cart = [name]
    remaining_capacity = limit - weight

    # Remove first cow from list
    del CowTupleList[0]

    # Find largest remaining cow that fits in remaining capacity (if any)
    idx = find_largest_fitting(CowTupleList, remaining_capacity)
    while idx is not None:
      # Add the cow at idx to the cart
      name,weight = CowTupleList[idx]
      remaining_capacity -= weight

      # Remove cow at idx from list
      del CowTupleList[idx]

      # Find largest remaining cow that fits (if any)
      idx = find_largest_fitting(CowTupleList, remaining_capacity)

    # No more cows fit => yield the cart
    yield cart

Assuming find_largest_fitting is implemented as a binary search over CowTupleList (and an appropriate data structure is chosen for CowTupleList), this should take \$\mathcal{O}(n\log{n})\$ time. If linear search is used for find_largest_fitting and/or Python's build-in list type is used for CowTupleList (so that del operates in \$\mathcal{O}(n)\$), then this algorithm will operate in \$\mathcal{O}(n^2)\$ time.

  • \$\begingroup\$ BINGO! Thank you nathan, yeild statements, another way... \$\endgroup\$ Nov 16, 2016 at 1:10
  • \$\begingroup\$ BUT WAIT, you MIGHT fit a very light cow further down the list. Dont you have to check the entire list each time? That would be VERY greedy otherwise. Greedy is what we did (without knowing it) when choosing the words from a hand in scrabble, ONLY you didn't have to delete a word once it was chosen.... grrrrrrrr \$\endgroup\$ Nov 16, 2016 at 1:22
  • \$\begingroup\$ Ah yes, you are right, of course. Don't know what I was thinking. \$\endgroup\$ Nov 16, 2016 at 2:38
  • \$\begingroup\$ Although about checking the entire list ... you are only interested in the portion of the list that has cows that are no heaver than the remaining capacity. So I suppose you could use a binary search to find the largest cow that fits? \$\endgroup\$ Nov 16, 2016 at 2:44
  • \$\begingroup\$ Thanks so much Nat, YOURS was the major DUH!! moment with the <name, weight in tuples> ... \$\endgroup\$ Nov 16, 2016 at 10:11

This is the best I got so far:

def greedy_cow_transport(cows,limit=10):
    train = []
    while sum(cows.values()) > 0:
        cart = []
        total = 0
        for cow, value in sorted(cows.items(), key=lambda x: x[1], reverse = True):
            if cows[cow] != 0 and value + total <= limit:
                total += value
                cows[cow] = 0
    return train

For the dictionary:

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

We get:

 ['Herman', 'Maggie'],
 ['Oreo', 'Moo Moo'],
 ['Millie', 'Milkshake', 'Lola'],

Although, I have mutated the original dictionary which we're not supposed to do.

  • \$\begingroup\$ You can always create a copy of the original dictionary and mutate the copy. \$\endgroup\$ Nov 16, 2016 at 3:24

I'll give it a shot too.

I wrote various iterations of the code for this problem and the one I'm the most happy about (and that is easy to read and understand) is the following where I use a while-loop but start the counter at one less than the length and decrease the value each time in order to not go through the list of cows more than once.

def greedy_cow_transport_third_iteration(cows, limit=10):
trips, available = [], limit
# Make a list of cows, sort by weight in ascending fashion (lightest first)
cows = sorted([(weight, name) for name, weight in cows.items()])
while cows:                     # Loop through available cows
    trips.append([cows[-1][1]]) # Allocate heaviest cow on a new trip
    available -= cows[-1][0]    # Adjust available weight accordingly
    cows.remove(cows[-1])       # Remove this cow from future loops
    i = len(cows) - 1           # Reset index
    while i >= 0:               # Loop back through all remaiing cows
        if available > 0 and cows[i][0] <= available:
            trips[-1].append(cows[i][1])  # Allocate this cow!
            available -= cows[i][0]       # adjust available weight
            cows.remove(cows[i])          # Remove it from future loops
        i -= 1                  # Avoid infinite loops
    available = limit           # Reset available weight for next trip
return trips                    # Returns solution

I hope that helps somehow.

  • \$\begingroup\$ Each and every answer on Code Review should contain an insightful comment about the code provided. This is an alternative implementation without reviewing the code provided. Either provide a review or your answer isn't up to par. \$\endgroup\$
    – Mast
    Dec 27, 2017 at 14:55
  • \$\begingroup\$ Afar from that, welcome to Code Review! \$\endgroup\$
    – Mast
    Dec 27, 2017 at 14:56
  • \$\begingroup\$ Ok, sorry about that, and thanks :) I can also delete my reply altogether if that's for the better. \$\endgroup\$ Dec 28, 2017 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.