1
\$\begingroup\$

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)}
\$\endgroup\$
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.