Coding challenges on brute force and dynamic programming — MIT problem set

Problem 1The Knapsack Search Tree: Every Combination, 2ⁿ Nodes

Space Cows: Brute Force Cow Transport

MIT 6.0002 Introduction to Computational Thinking and Data Science, Fall 2016 · Problem set 1, Problem A.3: Brute Force Cow Transport — brute_force_cow_transport · Prof. Eric Grimson, Prof. John Guttag and Dr. Ana Bell · CC BY-NC-SA 4.0 · MIT publishes no solution for this set; the worked solution is ours

Implement a brute force algorithm to find the minimum number of trips needed to take all the cows across the universe in brute_force_cow_transport. The result should be a list of lists, where each inner list represents a trip and contains the names of cows taken on that trip.

Another way to transport the cows is to look at every possible combination of trips and pick the best one. This is an example of a brute force algorithm. The brute force algorithm should follow this method:

Enumerate all possible ways that the cows can be divided into separate trips. Use the given get_partitions function to help you!
Select the allocation that minimizes the number of trips without making any trip that does not obey the weight limitation.

Notes:

Make sure not to mutate the dictionary of cows!
In order to enumerate all possible combinations of trips, you will want to work with set partitions. MIT provides a helper function called get_partitions that generates all the set partitions for a set of cows (it is in the starter code, above your function).

Assumptions:

Again, you can assume that order doesn't matter. [[1,2],[3,4]] and [[3,4],[1,2]] are considered equivalent lists of trips, and [[1,2],[3,4]] and [[2,1],[3,4]] are considered the same partitions of [1,2,3,4].
You can assume that all the cows are between 0 and 10 tons in weight.
All the cows have unique names.
If multiple cows weigh the same amount, break ties arbitrarily.
The spaceship has a cargo weight limit (in tons), which is passed into the function as a parameter (default 10).

Helper function get_partitions: to generate all the possibilities for the brute force method, you will want to work with set partitions (https://en.wikipedia.org/wiki/Partition_of_a_set). For instance, all the possible 2-partitions of the list [1,2,3,4] are [[1,2],[3,4]], [[1,3],[2,4]], [[2,3],[1,4]], [[1],[2,3,4]], [[2],[1,3,4]], [[3],[1,2,4]], [[4],[1,2,3]].

get_partitions(list) takes as input a list and returns a generator that contains all the possible partitions of this list, from 0-partitions to n-partitions, where n is the length of this list. To use generators, you must iterate over the generator to retrieve the elements; you cannot index into a generator! For instance, the recommended way to call get_partitions on a list [1,2,3] is the following:

for partition in get_partitions([1,2,3]):
    print(partition)

Try out this snippet of code to see what is printed!

Example: suppose the spaceship has a cargo weight limit of 10 tons and the set of cows to transport is {"Jesse": 6, "Maybel": 3, "Callie": 2, "Maggie": 5}.

The brute force algorithm will first try to fit them on only one trip, ["Jesse", "Maybel", "Callie", "Maggie"]. Since this trip contains 16 tons of cows, it is over the weight limit and does not work.

Then the algorithm will try fitting them on all combinations of two trips. Suppose it first tries [["Jesse", "Maggie"], ["Maybel", "Callie"]]. This solution will be rejected because Jesse and Maggie together are over the weight limit and cannot be on the same trip. The algorithm will continue trying two trip partitions until it finds one that works, such as [["Jesse", "Callie"], ["Maybel", "Maggie"]].

The final result is then [["Jesse", "Callie"], ["Maybel", "Maggie"]]. Note that depending on which cow it tries first, the algorithm may find a different, optimal solution. Another optimal result could be [['Jesse', 'Maybel'], ['Callie', 'Maggie']]. (So the tests check that every cow travels exactly once, that no trip is over the limit, and that the number of trips is the minimum — not which optimal allocation you return.)

print(len(brute_force_cow_transport({"Jesse": 6, "Maybel": 3, "Callie": 2, "Maggie": 5}, 10)))  # 2
print(len(brute_force_cow_transport(load_cows('ps1_cow_data_2.txt'))))  # 5

Adapted for the browser: MIT's get_partitions from ps1_partition.py and the load_cows you wrote in Problem A.1 are given at the top of the editor instead of imported, and ps1_cow_data_2.txt is written into the working directory before your code runs. The tests use herds of at most 8 cows so that the brute force finishes quickly.

# --- given: MIT's ps1_partition.py (do not edit) ---
# From codereview.stackexchange.com
def partitions(set_):
    if not set_:
        yield []
        return
    for i in range(2**len(set_)//2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1
        for b in partitions(parts[1]):
            yield [parts[0]]+b

def get_partitions(set_):
    for partition in partitions(set_):
        yield [list(elt) for elt in partition]


# --- given: load_cows, from Problem A.1 (do not edit) ---
def load_cows(filename):
    """
    Read the contents of the given file.  Assumes the file contents contain
    data in the form of comma-separated cow name, weight pairs, and return a
    dictionary containing cow names as keys and corresponding weights as values.

    Parameters:
    filename - the name of the data file as a string

    Returns:
    a dictionary of cow name (string), weight (int) pairs
    """
    cows = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()
            if line == '':
                continue
            name, weight = line.split(',')
            cows[name] = int(weight)
    return cows


def brute_force_cow_transport(cows,limit=10):
    """
    Finds the allocation of cows that minimizes the number of spaceship trips
    via brute force.  The brute force algorithm should follow the following method:

    1. Enumerate all possible ways that the cows can be divided into separate trips 
        Use the given get_partitions function in ps1_partition.py to help you!
    2. Select the allocation that minimizes the number of trips without making any trip
        that does not obey the weight limitation
            
    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)
    
    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    pass

# --- given: MIT's ps1_partition.py (do not edit) ---
# From codereview.stackexchange.com
def partitions(set_):
    if not set_:
        yield []
        return
    for i in range(2**len(set_)//2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1
        for b in partitions(parts[1]):
            yield [parts[0]]+b

def get_partitions(set_):
    for partition in partitions(set_):
        yield [list(elt) for elt in partition]


# --- given: load_cows, from Problem A.1 (do not edit) ---
def load_cows(filename):
    """
    Read the contents of the given file.  Assumes the file contents contain
    data in the form of comma-separated cow name, weight pairs, and return a
    dictionary containing cow names as keys and corresponding weights as values.

    Parameters:
    filename - the name of the data file as a string

    Returns:
    a dictionary of cow name (string), weight (int) pairs
    """
    cows = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()
            if line == '':
                continue
            name, weight = line.split(',')
            cows[name] = int(weight)
    return cows


def brute_force_cow_transport(cows,limit=10):
    """
    Finds the allocation of cows that minimizes the number of spaceship trips
    via brute force.  The brute force algorithm should follow the following method:

    1. Enumerate all possible ways that the cows can be divided into separate trips 
        Use the given get_partitions function in ps1_partition.py to help you!
    2. Select the allocation that minimizes the number of trips without making any trip
        that does not obey the weight limitation
            
    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)
    
    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    pass

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 3Examples — click to expand

MIT's example: limit 10, four cows, two trips

The cows of ps1_cow_data_2.txt at the default limit of 10

Brute force beats greedy: greedy needs 3 trips here, the best allocation needs 2

Hidden tests · 6Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Hidden test 4

Hidden test 5

Hidden test 6

Space Cows: Brute Force Cow Transport

Enumerate all possible ways that the cows can be divided into separate trips. Use the given get_partitions function to help you!
Select the allocation that minimizes the number of trips without making any trip that does not obey the weight limitation.

Notes:

Make sure not to mutate the dictionary of cows!
In order to enumerate all possible combinations of trips, you will want to work with set partitions. MIT provides a helper function called get_partitions that generates all the set partitions for a set of cows (it is in the starter code, above your function).

Assumptions:

Again, you can assume that order doesn't matter. [[1,2],[3,4]] and [[3,4],[1,2]] are considered equivalent lists of trips, and [[1,2],[3,4]] and [[2,1],[3,4]] are considered the same partitions of [1,2,3,4].
You can assume that all the cows are between 0 and 10 tons in weight.
All the cows have unique names.
If multiple cows weigh the same amount, break ties arbitrarily.
The spaceship has a cargo weight limit (in tons), which is passed into the function as a parameter (default 10).

for partition in get_partitions([1,2,3]):
    print(partition)

Try out this snippet of code to see what is printed!

Example: suppose the spaceship has a cargo weight limit of 10 tons and the set of cows to transport is {"Jesse": 6, "Maybel": 3, "Callie": 2, "Maggie": 5}.

print(len(brute_force_cow_transport({"Jesse": 6, "Maybel": 3, "Callie": 2, "Maggie": 5}, 10)))  # 2
print(len(brute_force_cow_transport(load_cows('ps1_cow_data_2.txt'))))  # 5

# --- given: MIT's ps1_partition.py (do not edit) ---
# From codereview.stackexchange.com
def partitions(set_):
    if not set_:
        yield []
        return
    for i in range(2**len(set_)//2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1
        for b in partitions(parts[1]):
            yield [parts[0]]+b

def get_partitions(set_):
    for partition in partitions(set_):
        yield [list(elt) for elt in partition]


# --- given: load_cows, from Problem A.1 (do not edit) ---
def load_cows(filename):
    """
    Read the contents of the given file.  Assumes the file contents contain
    data in the form of comma-separated cow name, weight pairs, and return a
    dictionary containing cow names as keys and corresponding weights as values.

    Parameters:
    filename - the name of the data file as a string

    Returns:
    a dictionary of cow name (string), weight (int) pairs
    """
    cows = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()
            if line == '':
                continue
            name, weight = line.split(',')
            cows[name] = int(weight)
    return cows


def brute_force_cow_transport(cows,limit=10):
    """
    Finds the allocation of cows that minimizes the number of spaceship trips
    via brute force.  The brute force algorithm should follow the following method:

    1. Enumerate all possible ways that the cows can be divided into separate trips 
        Use the given get_partitions function in ps1_partition.py to help you!
    2. Select the allocation that minimizes the number of trips without making any trip
        that does not obey the weight limitation
            
    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)
    
    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    pass

# --- given: MIT's ps1_partition.py (do not edit) ---
# From codereview.stackexchange.com
def partitions(set_):
    if not set_:
        yield []
        return
    for i in range(2**len(set_)//2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1
        for b in partitions(parts[1]):
            yield [parts[0]]+b

def get_partitions(set_):
    for partition in partitions(set_):
        yield [list(elt) for elt in partition]


# --- given: load_cows, from Problem A.1 (do not edit) ---
def load_cows(filename):
    """
    Read the contents of the given file.  Assumes the file contents contain
    data in the form of comma-separated cow name, weight pairs, and return a
    dictionary containing cow names as keys and corresponding weights as values.

    Parameters:
    filename - the name of the data file as a string

    Returns:
    a dictionary of cow name (string), weight (int) pairs
    """
    cows = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()
            if line == '':
                continue
            name, weight = line.split(',')
            cows[name] = int(weight)
    return cows


def brute_force_cow_transport(cows,limit=10):
    """
    Finds the allocation of cows that minimizes the number of spaceship trips
    via brute force.  The brute force algorithm should follow the following method:

    1. Enumerate all possible ways that the cows can be divided into separate trips 
        Use the given get_partitions function in ps1_partition.py to help you!
    2. Select the allocation that minimizes the number of trips without making any trip
        that does not obey the weight limitation
            
    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)
    
    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    pass

Scratchpad— run any Python to test ideas

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment

Visible tests · 3Examples — click to expand

MIT's example: limit 10, four cows, two trips

The cows of ps1_cow_data_2.txt at the default limit of 10

Brute force beats greedy: greedy needs 3 trips here, the best allocation needs 2

Hidden tests · 6Bodies hidden — pass/fail only

Hidden test 1

Hidden test 2

Hidden test 3

Hidden test 4

Hidden test 5

Hidden test 6