Space Cows

ps1a.py

import time
from functools import reduce
from random import sample
from operator import itemgetter
from ps1_partition import get_partitions

# ================================
# Part A: Transporting Space Cows
# ================================

# Problem 1
def load_cows(filename="ps1_cow_data.txt"):
    """
    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
    """
    with open(filename) as f:
        return {cow: int(weight) for cow, weight in (line.split(",") for line in f)}


# Problem 2
def greedy_cow_transport(cows, limit=10):
    """
    Uses a greedy heuristic to determine an allocation of cows that attempts to
    minimize the number of spaceship trips needed to transport all the cows. The
    returned allocation of cows may or may not be optimal.
    The greedy heuristic should follow the following method:

    1. As long as the current trip can fit another cow, add the largest cow that will fit
        to the trip
    2. Once the trip is full, begin a new trip to transport the remaining cows

    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
    """
    sorted_cows = sorted(cows.items(), key=itemgetter(1), reverse=True)
    trips = []
    trip_weights = []
    for cow, weight in sorted_cows:
        index = -1
        for i, trip_weight in enumerate(trip_weights):
            if trip_weight + weight <= limit:
                index = i
        if index == -1:
            trips.append([])
            trip_weights.append(0)
        trips[index].append(cow)
        trip_weights[index] += weight
    return trips


def greedy_cow_transport_functional(cows, limit=10):
    sorted_cows = sorted(cows.items(), key=itemgetter(1), reverse=True)

    def process_cow(trips, cow_weight):
        cow, weight = cow_weight
        place = next(
            (
                i
                for i, trip in enumerate(trips)
                if sum(map(cows.get, trip)) + weight <= limit
            ),
            -1,
        )
        return [
            trip + [cow] if i == place else trip for i, trip in enumerate(trips)
        ] + ([[cow]] if place == -1 else [])

    return reduce(process_cow, sorted_cows, [])


def random_best_fit_cow_transport(cows, limit=10, iterations=8):
    def process_cow(trips, cow_weight):
        cow, weight = cow_weight
        new_weights = (sum(map(cows.get, trip)) + weight for trip in trips)
        try:
            place = max(
                (new_weight, i)
                for i, new_weight in enumerate(new_weights)
                if new_weight <= limit
            )[1]
        except ValueError:  # max() arg is an empty sequence
            place = -1
        return [
            trip + [cow] if i == place else trip for i, trip in enumerate(trips)
        ] + ([[cow]] if place == -1 else [])

    # https://repository.tudelft.nl/islandora/object/uuid%3Af4ee26b5-b94e-4cd3-9c7a-c281b0c8d8a8
    # claims 8 reptitions gives optimal solutions 99.97% of the time, if i'm understanding right
    return min(
        (
            reduce(process_cow, sample(cows.items(), len(cows)), [])
            for i in range(iterations)
        ),
        key=len,
    )


# i thought it was kind of like an iterated napsack problem
# and that maximizing cows per transport would minimize transports
# but it's actually the bin packing problem which can't be solved like this
def maxamized_cow_transport(cows, limit=10):
    def scorer(limit):
        def score(cow_names):
            if sum(map(cows.get, cow_names)) <= limit:
                return len(cow_names)
            return 0

        return score

    cache = {}

    def solve(cow_names: set, limit: int):
        if not cow_names:
            return set()
        if (tuple(cow_names), limit) not in cache:
            head, *tail_list = cow_names
            tail = set(tail_list)
            include = {head} | solve(tail, limit - cows[head])
            dont_include = solve(tail, limit)
            cache[(tuple(cow_names), limit)] = max(
                (include, dont_include), key=scorer(limit)
            )
        return cache[(tuple(cow_names), limit)]

    trips = []
    to_transport = set(cows)
    while to_transport:
        trip = solve(to_transport, limit)
        trips.append(list(trip))
        to_transport -= trip
    return trips


# Problem 3
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
    """
    return min(
        (
            trips
            for trips in get_partitions(cows)
            if all(sum(map(cows.get, trip)) <= limit for trip in trips)
        ),
        key=len,
    )


# Problem 4
def compare_cow_transport_algorithms():
    """
    Using the data from ps1_cow_data.txt and the specified weight limit, run your
    greedy_cow_transport and brute_force_cow_transport functions here. Use the
    default weight limits of 10 for both greedy_cow_transport and
    brute_force_cow_transport.
    
    Print out the number of trips returned by each method, and how long each
    method takes to run in seconds.

    Returns:
    Does not return anything.
    """
    cows = load_cows()
    for algo in (
        greedy_cow_transport,
        random_best_fit_cow_transport,
        brute_force_cow_transport,
    ):
        print(algo.__name__, end=" trips: ")
        now = time.time()
        print(len(algo(cows)))
        print(round(time.time() - now, 6))

ps1b.py

###########################
# 6.0002 Problem Set 1b: Space Change
# Name:
# Collaborators:
# Time:
# Author: charz, cdenise

# ================================
# Part B: Golden Eggs
# ================================
DEBUG = True
# Problem 1
def dp_make_weight(
    egg_weights: tuple, target_weight: int, memo: dict = {0: 0, 1: 1}
) -> int:
    """
    Find number of eggs to bring back, using the smallest number of eggs. Assumes there is
    an infinite supply of eggs of each weight, and there is always a egg of value 1.
    
    Parameters:
    egg_weights - tuple of integers, available egg weights sorted from smallest to largest value (1 = d1 < d2 < ... < dk)
    target_weight - int, amount of weight we want to find eggs to fit
    memo - dictionary, OPTIONAL parameter for memoization (you may not need to use this parameter depending on your implementation)
    
    Returns: int, smallest number of eggs needed to make target weight
    """
    if target_weight not in memo:
        memo[target_weight] = min(
            dp_make_weight(egg_weights, target_weight - egg, memo) + 1
            for egg in egg_weights[::-1]
            if egg <= target_weight
        )
        if DEBUG:
            print(f"memoized {target_weight}lbs as {memo[target_weight]}")
    return memo[target_weight]


# EXAMPLE TESTING CODE, feel free to add more if you'd like
if __name__ == "__main__":
    ex_egg_weights = (1, 5, 10, 25)
    n = 99
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 99")
    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(ex_egg_weights, n))
    print()