# Greedy Algorithm - Tuple Comparator

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

"""
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,reverse=True)

if comparator == cmpWork:
subjects_copy = sorted(subjects.items(),key=lambda x: x)

if comparator == cmpRatio:
subjects_copy = sorted(subjects.items(),key=lambda x: x/x,reverse=True)

i = 0
while work_hours <= maxWork and i < len(subjects_copy):
course = subjects_copy[i]
course_name = course
course_value = course
course_hours = course 
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')


Output

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


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]

• 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)} – Teddy Oct 17 '17 at 4:31
• @Teddy Maybe if you'd add an example with what input your code would be run. I could give a better answer. – Ludisposed Oct 17 '17 at 7:20
• 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)} – Teddy Oct 18 '17 at 15:03
• I'm sorry, but this is not enough: What is subjects it be best if you update your question with a full working example – Ludisposed Oct 19 '17 at 12:27
• 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. – Teddy Oct 19 '17 at 15:19