Question

I'm having trouble with part 2 of problem set 9. I don't know how to use the comparison functions (cmpWork, cmpValue, cmpRatio) to sort the dictionary of classes (or maybe the values in the dictionary?) in order to get the greedy algorithm to work. I saw one solution that used "sorted()" with cmp=comparison function and key = lambda x:x[1], but it wasn't returning the right answer. I tried to paste the code, but my character count is being limited for some reason.

Answer 1

# 6.00 Problem Set 9
#
# Intelligent Course Advisor
#
# Name:
# Collaborators:
# Time:
#

SUBJECT_FILENAME = "subjects.txt"
SHORT_SUBJECT_FILENAME = "shortened_subjects.txt"
VALUE, WORK = 0, 1

#
# Problem 1: Building A Subject Dictionary
#
def loadSubjects(filename):
"""
Returns a dictionary mapping subject name to (value, work), where the name
is a string and the value and work are integers. The subject information is
read from the file named by the string filename. Each line of the file
contains a string of the form "name,value,work".

returns: dictionary mapping subject name to (value, work)
"""

# The following sample code reads lines from the specified file and prints
# each one.
inputFile = open(filename)
subject_dict = {}
for line in inputFile:
## print line
n, v, w = line.split(',')
subject_dict[n] = (int(v), int(w))

## print subject_dict
return subject_dict


# TODO: Instead of printing each line, modify the above to parse the name,
# value, and work of each subject and create a dictionary mapping the name
# to the (value, work).

def printSubjects(subjects):
"""
Prints a string containing name, value, and work of each subject in
the dictionary of subjects and total value and work of all subjects
"""
totalVal, totalWork = 0,0
if len(subjects) == 0:
return 'Empty SubjectList'
res = 'Course\tValue\tWork\n======\t====\t=====\n'
subNames = subjects.keys()
subNames.sort()
for s in subNames:
val = subjects[s][VALUE]
work = subjects[s][WORK]
res = res + s + '\t' + str(val) + '\t' + str(work) + '\n'
totalVal += val
totalWork += work
res = res + '\nTotal Value:\t' + str(totalVal) +'\n'
res = res + 'Total Work:\t' + str(totalWork) + '\n'
print res

#
# Problem 2: Subject Selection By Greedy Optimization
#

def cmpValue(subInfo1, subInfo2):
"""
Returns True if value in (value, work) tuple subInfo1 is GREATER than
value in (value, work) tuple in subInfo2
"""
# TODO...

return subInfo1[0] > subInfo2[0]

def cmpWork(subInfo1, subInfo2):
"""
Returns True if work in (value, work) tuple subInfo1 is LESS than than work
in (value, work) tuple in subInfo2
"""
# TODO...

return subInfo1[1] > subInfo2[1]

def cmpRatio(subInfo1, subInfo2):
"""
Returns True if value/work in (value, work) tuple subInfo1 is
GREATER than value/work in (value, work) tuple in subInfo2
"""
# TODO...

return (float(subInfo1[0])/subInfo1[1]) > (float(subInfo2[0]/subInfo2[1]))


def greedyAdvisor(subjects, maxWork, comparator):
"""
Returns a dictionary mapping subject name to (value, work) which includes
subjects selected by the algorithm, such that the total work of subjects in
the dictionary is not greater than maxWork. The subjects are chosen using
a greedy algorithm. The subjects dictionary should not be mutated.

subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
comparator: function taking two tuples and returning a bool
returns: dictionary mapping subject name to (value, work)
"""
# TODO...





#
# Problem 3: Subject Selection By Brute Force
#
def bruteForceAdvisor(subjects, maxWork):
"""
Returns a dictionary mapping subject name to (value, work), which
represents the globally optimal selection of subjects using a brute force
algorithm.

subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
returns: dictionary mapping subject name to (value, work)
"""
# TODO...

Answer 2

FWIW, cmpWork() is wrong. Your code would be more readable/maintainable if you'd use the constants VALUE and WORK declared at the top of the file. This (from your file) may be useful:

def greedyAdvisor(subjects, maxWork, comparator):
""" Returns a dictionary mapping subject name to (value, work)

Answer 3

Thanks! I didn't see the constants before but incorporated them and fixed cmpWork(). I'm still confused on how to use the "cmp" function in order to sort the dict values for the greedy algorithm since I am guessing those three functions are supposed to be the cmp in a sorted() function and I keep getting errors that the cmp needs to return an integer, while these functions return True or none.

Answer 4

Also, here's some code I found on github that returns a sorted dict using the three "cmp" functions but it's not ordered properly. I'm confused as to why it even works in the first place is the cmp function is supposed to return an integer.

Answer 5

subjects_to_take = {}
for item in sorted(subjects.iteritems(), cmp=comparator, key=lambda x:x[1], reverse=True):
if item[1][1] <= maxWork:
maxWork -= item[1][1]
subjects_to_take[item[0]] = item[1]
return subjects_to_take

Answer 6

I think this is the same problem. My "main" is:

if( __name__ == "__main__" ):
subjects = loadSubjects( SUBJECT_FILENAME )
greedyAdvisor(subjects, 15, cmpWork)
# bruteForceTime()
# dpTime()

It's the only call to cmp* in my code. HTH.

Answer 7

Sorryy, but I don't follow.

Answer 8

TBH, I don't know. I looked through my code from the 2008 versio of the class and found either the same assignment, or a similar one. I filtered the code looking for "cmp" and posted what I found. Weak, I'll admit, but it's the best I have.

Answer 9

No worries. Thanks for all your help so far. I greatly appreciate it.