Greedy Algorithm - Tuple Comparator

Question

I've completed the problem set 9 of the OCW 6.00sc course which requires the implementation of a greedy algorithm - see prompt.

When completing problem 2, it is asked to implement comparator functions that will be selected when running the greedy algorithm function. Even though I've implemented them, and everything is running as it should, my greedy algorithm function does not make explicit use of them. I know I should call the comparator functions, but I am not sure how to do this with the comparator being a tuple.

Edit: Subject

import itertools
SUBJECT_FILENAME = "subjects.txt"
VALUE, WORK = 0, 1
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.
 catalog = {}
 inputFile = open(filename)
 for line in inputFile:
 name, value, hours = line.split(',')
 catalog[name] = (int(value),int(hours))
 return catalog
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

Comparator functions

def cmpValue(subInfo1, subInfo2):
 """
 Returns True if value in (value, work) tuple subInfo1 is GREATER than
 value in (value, work) tuple in subInfo2
 """
 if subInfo1[VALUE] >= subInfo2[VALUE]:
 return True
 else:
 return False
def cmpWork(subInfo1, subInfo2):
 """
 Returns True if work in (value, work) tuple subInfo1 is LESS than than work
 in (value, work) tuple in subInfo2
 """
 if subInfo1[WORK] <= subInfo2[WORK]:
 return True
 else:
 return False
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
 """
 if subInfo1[VALUE]/subInfo1[WORK] >= subInfo2[VALUE]/subInfo2[WORK]:
 return True
 else:
 return False

Greedy algorithm

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)
 """
 course_catalog = {}
 work_hours = 0
 subjects_copy = subjects
 if comparator == cmpValue:
 subjects_copy = sorted(subjects.items(),key=lambda x: x[1][0],reverse=True)
 if comparator == cmpWork:
 subjects_copy = sorted(subjects.items(),key=lambda x: x[1][1])
 if comparator == cmpRatio:
 subjects_copy = sorted(subjects.items(),key=lambda x: x[1][0]/x[1][1],reverse=True)
 i = 0
 while work_hours <= maxWork and i < len(subjects_copy):
 course = subjects_copy[i]
 course_name = course[0]
 course_value = course[1][0]
 course_hours = course [1][1]
 if work_hours + course_hours > maxWork:
 i += 1
 continue
 course_catalog[course_name] = (course_value,course_hours)
 work_hours += course_hours
 i += 1
 return course_catalog
def powerset(iterable):
 s = list(iterable)
 return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

Edit: Example:

Input

subjects = loadSubjects('subjects.txt')
print(greedyAdvisor(subjects, 7, cmpWork))

Output

{'6.00': (10, 1), '6.12': (6, 3), '6.04': (1, 2)}

Answer 1

These compareres can be returned directly, because this:

if subInfo1[VALUE] >= subInfo2[VALUE]:
 return True
else:
 return False

return the same as:

return subInfo1[VALUE] >= subInfo2[VALUE]

• Teddy: Thanks for the feedback. How would I use the comparator function within the greedAdvisor? Right now as my code is the comparators are useless as they are not invoked at all. Instead I am using an If statement as a workaround. N.B: Subjects is a dictionary containing value as follow: subject {‘course’:(Value, Work)}
• Ludisposed: @Teddy Maybe if you'd add an example with what input your code would be run. I could give a better answer.
• Teddy: cmpValue Example: input: print greedyAdvisor(subjects, 7, cmpValue) | output: {'6.00': (10, 1), '6.18': (10, 4), '6.04': (1, 2)} cmpWork Example input: print greedyAdvisor(subjects, 7, cmpWork) | output: {'6.00': (10, 1), '6.12': (6, 3), '6.04': (1, 2)}
• Ludisposed: I'm sorry, but this is not enough: What is subjects it be best if you update your question with a full working example
• Teddy: just edited the code to include everything + example. The subjects.txt file is a text file with course name, value, work separated by a space with 1 course per line.