Assignment 1 Space Cows Transportation

Introduction

In this assignment, a colony of Aucks (super-intelligent alien bio-engineers) has landed on Earth and has created new species of farm animals! The Aucks are performing their experiments on Earth, and plan on transporting the mutant animals back to their home planet of Aurock. In this problem set, you will implement algorithms to figure out how the aliens should shuttle their experimental animals back across space.

Getting Started

Download Assignment1.zip from the website.

Please do not rename the provided files, change any of the provided helper functions, change function/method names, or delete provided docstrings. You will need to keep a1_cow_data.txt, and a1_cow_data_1.txt, in the same folder as a1.ipynb.

Problem Set Overview

The aliens have succeeded in breeding cows that jump over the moon! Now they want to take home their mutant cows. The aliens want to take all chosen cows back, but their spaceship has a weight limit and they can only travel a limitted number of trips they have to take across the universe. Somehow, the aliens have evolved and developed breeding technology to make cows with integer weights and IQs.

The data for the cows to be transported is stored in a1_cow_data.txt, and another set of cows for another separate transport are in a1_cow_data_1.txt. (You may use the two files to read data and test your implementation individually). All of your code for the problem solving in this assignment should go into a1.ipynb--you need to expand the given notebook to include your Python code and discussion notes.

For each problem, I provide some skeleton code for you to start your problem solving. Note that most of the code definitions are not complete unless I point out the completion of some certain function such as greedy for Problem 3. For each code cell that contains only incomplete code, you need to extend the code implementation.

You also need to solve the problems in the order presented in this document. That is, you should complete problem 1 first before you approach problems 2 and 3. The solutions of the later problems are dependent on the solutions to earlier problems. For example, in Problem 2, you need to parse a data file to create Cow objects. The class definition of Cow for Problem 1 is needed to create the Cow objects for Problem 2.

Problem 1: Defining Cow Class

First we need to define a Cow class. Each cow object state is described using name as a string and weight as an int. (You may check the Food class definition in the lecture notes as a reference when you are working on defining the Cow class.)

Note that I provided some skeleton code below so that you may expand based on what is provided.

In [ ]:

#Problem 1 class Cow(object): """ Cow is defined as a means to organize cow data including name and weight as well as accessing name and weight from a cow object Cow object data name - cow name as a string weight - cow weight as an int IQ -cow intelligence as an int Methods to define __init__ __str__ getName getWeight getIQ getDensity """ def __init__(self, n, w, i): self.name = n self.weight = w self.i = i self.transported = 0 # TODO: Your code here to define other methods #test code mary= Cow('mary', 3, 120) print(mary) print(mary.getDensity()) 

Note the test code provided above doesn't provide a throughout checking and evaluation of your class definition. It only checks the init, str, and getDensity methods. You should extend the test code to evaluate other methods you define in the class definition. The output of the above test code could be like

Cow mary: Weight 3, IQ 120 40.0

The first output is determined by the definition of str in the class definition.

Problem 2: Loading Cow Data

Second we need to load the cow data from the data file a1_cow_data.txt. The file a1_cow_data_1.txt is given as another file that you can read and test from, but for now, just work with a1_cow_data.txt.

You can expect the data to be formatted in triples of x,y,z on each line, where x is the name of the cow, y is a number indicating how much the cow weighs in tons, and z is a number indicating the cow's IQ value. Here are the few lines of a1_cow_data.txt:

Maggie,3,165 Herman,7,126 Betsy,9,122 Oreo,6,104 Moo Moo,3,151 Milkshake,2,117 Millie,5,84 Lola,2,131 Florence,2,101 Henrietta,9,106

You can assume that all the cows have unique names. Hint: If you dont remember how to read lines from a file, check out the online python documentation, which has a chapter on Input and Output that includes file I/O here: https://docs.python.org/3/tutorial/inputoutput.html

Some functions that may be helpful:

str.split open file.readline file.close

In [9]:

! cat "a1_cow_data.txt" 

Maggie,3,165 Herman,7,126 Betsy,9,122 Oreo,6,104 Moo Moo,3,151 Milkshake,2,117 Millie,5,84 Lola,2,131 Florence,2,101 Henrietta,9,106 

In [10]:

! cat "a1_cow_data_1.txt" 

Miss Moo-dy,3,172 Milkshake,4,102 Lotus,10,149 Miss Bella,2,103 Horns,9,81 Betsy,5,97 Rose,3,155 Dottie,6,91 

In [ ]:

# Problem 2 def load_cows(filename): """ Read the contents of the given file. Assumes the file contents contain data in the form of comma-separated triples composed of cow name, weight, and iq, and return a list containing Cow objects each of which has has a name, a weight, and an iq Parameters: filename - the name of the data file as a string Returns: a list of Cow objects """ #define a list to contain the to-be-created Cow objects data = [] f = open(filename) line = f.readline() while line !='': #parse the row data and create a Cow object #Add the Cow object to the data list return data data = load_cows("a1_cow_data.txt") for i in range(len(data)): print(data[i]) 

By running the above test code, your code should get output like below Cow Maggie: Weight 3, IQ 165 Cow Herman: Weight 7, IQ 126 Cow Betsy: Weight 9, IQ 122 Cow Oreo: Weight 6, IQ 104 Cow Moo Moo: Weight 3, IQ 151 Cow Milkshake: Weight 2, IQ 117 Cow Millie: Weight 5, IQ 84 Cow Lola: Weight 2, IQ 131 Cow Florence: Weight 2, IQ 101 Cow Henrietta: Weight 9, IQ 106

Again, I would like to remind you that the str method of the Cow object represented by data[i] is called when print(data[i]) is invoked.

Problem 3: Greedy Cow Transport

One way of transporting cows is to always pick the cow that has the most intelligence density (IQ/weight) onto the spaceship first. This is an example of a greedy algorithm. You may choose a criteria to use, which you think suitable to accomplish the goal ---to transport the maximum intelligence values of cows back home.

Implement a greedy algorithm for transporting the cows back across space in greedy_cow_transport. The constraints include the weight limit for each space trip and the total number of trips the aliens can make. The result should be a pair composed of two values: the first value presents the total sum of the IQs of the cows transported and the second is a list of lists, with each inner list containing cows (cow objects) transported on a particular trip

To facilitate your problem solving, I provide a function definition of greedy, which is complete. (It means that you do NOT need to change anything. I also provide some skeleton code for greedy_cow_transport including the function call of greedy on line 35. The function definition of greedy is based on the greedy algorithm we studied in the lecture.

In [12]:

#Implementation of Flexible Greedy def greedy(cows, maxCost, keyFunction): """ Uses a greedy approach based on a criterion to determine a list of Cow objects to take on a single trip by a spaceship that can carry a certain amount of weight. Parameters: cows - a list of Cow objects maxCost - should be a positive int to indicate the maximum weight (tons) the trip can do keyFunction - should be a function that is used to sort the cows and it maps an item to a number Returns: result - a list of Cows chosen to be transported by a trip totalValue - an int value to keep track of the sum of IQ values of the transported Cow objects totalCost - an int value to keep track of the sum of weights of the transfored Cow objects """ #Attention check sorted function documentation itemsCopy = sorted(cows, key = keyFunction, reverse = True) result = [] totalValue, totalCost = 0, 0 for i in range(len(itemsCopy)): #Attention if (totalCost+itemsCopy[i].getWeight()) <= maxCost: #Attention result.append(itemsCopy[i]) totalCost += itemsCopy[i].getWeight() totalValue += itemsCopy[i].getIQ() return (result, totalValue, totalCost) 

In [ ]:

# Problem 3 def greedy_cow_transport(cows,oneTripWeightLimit=10, numberOfTrips=3): """ Uses a greedy heuristic to determine an allocation of cows that attempts to maxminize the intelligence (sum of IQs) of the cows that can be transported back to Aurock. 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 based on your critera, add the cow that will fit to the trip 2. Once the trip is full, begin a new trip to transport the remaining cows 3. Stop the trasportation after the number of limitted trips Parameters: cows - a list of cow objects oneTripWeightLimit - weight limit of the spaceship (an int) for one trip numberOfTrips -- limit of number of trips for the whole transportation Returns: A tuple composed of two int values and a list. The first value presents the total sum of the IQs of the cows transported The second value presents the total sum of weights (tons) of the cows transported The third is a list of lists, with each inner list containing cows (cow objects) transported on a particular trip and the overall list containing all the trips """ trips = [] totalValue = 0 totalCost = 0 while numberOfTrips >0: #call greedy to return one trip result and value result, oneTripValue, oneTripCost = greedy(cows, oneTripWeightLimit, Cow.getDensity) #based on returned data from the greedy call, #update the trips #update totalValue by adding the sum of IQs of the cows transported by the single trip #update the totalCost by adding the sum of weights of the cows transported by the trip #and update the cows so that cows is used to keep track of the cows that haven't been transported #update another information you think necessary return totalValue, totalCost, trips cows = load_cows("a1_cow_data.txt") totalValue, totalCost, trips = greedy_cow_transport(cows) for i in range(len(trips)): print("Trip " + str(i) + ":") for j in range(len(trips[i])): print(trips[i][j]) print(" ") print("Total IQs transported = " + str(totalValue)) print("Total weights (tons) transported = " + str(totalCost)) 

The output of the above test code should be like below

Trip 0: Cow Lola: Weight 2, IQ 131 Cow Milkshake: Weight 2, IQ 117 Cow Maggie: Weight 3, IQ 165 Cow Florence: Weight 2, IQ 101

Trip 1: Cow Moo Moo: Weight 3, IQ 151 Cow Herman: Weight 7, IQ 126

Trip 2: Cow Oreo: Weight 6, IQ 104

Total IQs transported = 895 Total weights (tons) transported = 25

Problem 4: Writeup

Answer the following questions:

• Does the greedy algorithm return the optimal solution? Think: How do you evaluate greedy algorithms in general? How about this case?
• If yes, why?
• If not, what could be a solution that can find the optimal solution?

Note that you can write your answers to the questions in this notebook document with your code implementations.

a1_cow_data_1.txt

Miss Moo-dy,3,172 Milkshake,4,102 Lotus,10,149 Miss Bella,2,103 Horns,9,81 Betsy,5,97 Rose,3,155 Dottie,6,91

a1_cow_data.txt

Maggie,3,165 Herman,7,126 Betsy,9,122 Oreo,6,104 Moo Moo,3,151 Milkshake,2,117 Millie,5,84 Lola,2,131 Florence,2,101 Henrietta,9,106