Maximizing grad student happiness

Question

A local university's graduate school has a field placement that's a required component for graduation. Each student works in the field (something like a residency for medical students) for one year in addition to completing their course work.

The process of matching students with placement locations is called the match. The various placement agencies work with the university to establish field instructors and placement slots. An individual agency can have slots for one or more students. Students then indicate their first, second and third choices for placements. The university then tries to accommodate the students wishes to the extent possible. In the past this had been a manual process, but I wrote a Python program to automate this matching process and attempt to maximize collective student happiness.

The inputs

There are three input files. The first is the list of weights for the happiness for first, second, third and lower choices. The second is a list and count of placements, and the third is a list of students and their choices. There are guaranteed to always be more placement slots than students.

weights.txt

# this file contains the weights for first, second, third, and
# lower choices.  Weights must be monotonically nondecreasing
# (that is, each number must be greater than or equal to the
# number on the line above)
0
1
3
5

placements.txt

# number, name, slots
1,Agency A,3
2,Agency B,1
3,Agency C,1
4,Agency D,1
5,Agency E,2

students.txt

# comment lines begin with a # in the first column
# name, first, second, third
Annabelle,1,9,9
Margaret,1,9,3
Edward,2,9,1
Catherine,2,4,1
Marie,1,3,5
Katie,4,5,3
Michael,4,5,3
Justin,9,1,9
Jennifer,9,5,4

The program

The program reads in all three of the input files and attempts to match each student to a placement. In the first pass, the program simply assigns each student to his or her first choice placement unless there are no slots left, in which case it assigns the student to a second place slot, etc. so that at the end of the first pass, every student has a placement. Next, the program considers swapping students to maximize collective happiness. For example, one student might choose agencies A, B, C in that order, while another might have specified B, C, A. If the students were assigned to agencies C and A respectively (both third choices), swapping the two placements would increase collective happiness (to first and second choices) so this swap is made. This proceeds until no swap would increase happiness, at which point the algorithm terminates and a report is printed showing the results. Additionally, the program shows all of the possible "happiness-neutral changes" which are swaps that could be made that don't affect the total happiness score, but might be made for other reasons that the computer doesn't know about (e.g. a student who lives much closer to a particular placement, and so would find it more convenient).

Note that the program actually handles the case in which there are more students than placements, even though this should never happen in practice. It also considers anyone who did not get one of their top three choices as "unmatched" which is consistent with the university's existing terminology used for their current manual process.

I should also note that the students.txt file above has a number of choices which are 9 which is not a valid agency. This was to simulate if the student had made a duplicate selection. That is, if they had indicated the agency D for their first, second and third choices, this would be encoded as 4,9,9.

I'm interested in comments about both the program and the algorithm.

match.py

import sys
import string

# reads in a file containing student names and preferences
def read_students(filename):
    students = []
    i = 0
    for line in open(filename):
        if (line[0] != '#'):
            fields = line.strip().split(',')
            student = {
                'name'  : fields[0],
                'first' : int(fields[1]),
                'second': int(fields[2]),
                'third' : int(fields[3]),
                'placement' : 0,
                'index' : i
            }
            i += 1
            students.append(student)
    return students

# reads in a file containing weighting factors for first, second, third, and no choice
def read_weights(filename):
    weights = []
    for line in open(filename):
        if (line[0] != '#'):
            weights.append(int(line))
    sw = [w for w in weights]
    sw.sort()
    if sw != weights:
        raise ValueError
    return weights

# reads in a file containing agency index, name and numbr of slots
def read_placements(filename):
    placements = []
    for line in open(filename):
        if (line[0] != '#'):
            fields = line.strip().split(',')
            placement = {
                'number': int(fields[0]),
                'name'  : fields[1],
                'slots' : int(fields[2]),
                'available' : int(fields[2])
            }
            placements.append(placement)
    return placements

# adds a student to a placement if the placement exists and if there's a slot available
# returns True if the student was added, otherwise False
def add_student(student, placenum, placements):
    try:
        placement = [p for p in placements if p['number'] == placenum][0]
    except:
        return False

    if (placement['available'] > 0):
        placement['available'] -= 1
        student['placement'] = placement['number']
        return True
    else:
        return False

# returns the name of the placement corresponding to the passed number
# if none, then raises a KeyError
def placement_name(placements, number):
    for p in placements:
        if p['number'] == number:
            return p['name']
    raise KeyError

# first pass match
# assigns first choice if available, else second else third.
# then assigns students to remaining slots regardless of pref
def match_students(students, placements):
    for s in students:
        if not add_student(s, s['first'], placements):
            if not add_student(s, s['second'], placements):
                add_student(s, s['third'], placements)
    unfilled = [p for p in placements if p['available']>0]
    for p in unfilled:
        unmatched = [s for s in students if s['placement'] == 0]
        if (len(unmatched) > 0):
            add_student(unmatched[0],p['number'],placements)
        else:
            return [];

    return [s for s in students if s['placement']==0]

# returns unhappiness total for this particular student if testval were the assigned placement    
def unhappiness(s, testval, weights):
    if testval == s['first']:
        return weights[0]
    elif testval == s['second']:
        return weights[1]
    elif testval == s['third']:
        return weights[2]
    else:
        return weights[3]

# total unhappiness of all students
def total_unhappiness(students, weights):
    return sum([unhappiness(s,s['placement'],weights) for s in students])

# print the name of the organization, with a leading asterisk if it matches
# the passed pref
def print_org(choice, pref, placements):
    s = " "
    if choice == pref:
        s = "*"
    try:
        return s+placement_name(placements, choice)
    except:
        return s+" "

# considers the result of swapping two students.  If this decreases total
# unhappiness, the swap is made and True is returned.  If neutral is True,
# and total unhappiness would be unchanged, a message is printed and True is
# returned.  In all other cases, False is returned.
def improve_students(s1, s2, placements, weights, neutral=False):
    h = [ [unhappiness(s1, s1['placement'], weights),
           unhappiness(s2,s2['placement'], weights)],
          [unhappiness(s1, s2['placement'], weights),
           unhappiness(s2,s1['placement'], weights)]
        ]
    if sum(h[0]) > sum(h[1]):
        temp  = s1['placement']
        s1['placement'] = s2['placement']
        s2['placement'] = temp
        # print "swapping {0} and {1}".format(s1['name'], s2['name'])
        return True
    elif neutral and sum(h[0]) == sum(h[1]):
        print "swap {0} and {1}".format(s1['name'], s2['name'])
        return False
    else:
        # print "NOT swapping {0} and {1}".format(s1['name'], s2['name'])
        return False

# prints out all students and their choices
def print_students(students, placements, weights):
    print "{0:4} {1:15} {2:15} {3:15} {4:15}".format("unhp", "name", "first", "second", "third")
    for st in students:
        s = "{0:4} {1:15}".format(unhappiness(st,st['placement'],weights), st['name'])
        s += "{0:15} ".format(print_org(st['first'],st['placement'], placements))
        s += "{0:15} ".format(print_org(st['second'],st['placement'], placements))
        s += "{0:15} ".format(print_org(st['third'],st['placement'], placements))
        print s

# prints out all placements, number of available slots and number of total slots
def print_placements(placements):
    print "{0:15} {1:4} {2:4}".format("name", "avail", "slots")
    for p in placements:
        print "{0:15} {1:4} {2:4}".format(p['name'], p['available'], p['slots'])

# after initial pass, attemps to optimize student placements by minimizing unhappiness
def optimize_students(students, placements, weights):
    improvement = False
    for s in [s for s in students if unhappiness(s, s['placement'],weights) > weights[1]]:
        for s2 in [s2 for s2 in students if s2['placement']==s['first'] or s2['placement']==s['second']]:
            improvement = improvement or improve_students(s, s2, placements, weights)
    return improvement

# similar to optimization, but here we're just looking for swaps we could make which
# leave the unhappiness level unchanged.
def equivocate(students, placements, weights):
    for s in [s for s in students if unhappiness(s, s['placement'],weights) > weights[0]]:
        for s2 in [s2 for s2 in students if s2['name'] != s['name'] and s2['placement'] != s['placement']]:
            if s['index'] < s2['index']:
                improve_students(s, s2, placements, weights, True)

# prints the whole report include weights, students, and placements
def print_report(students, placements, weights):
    print "\nWeights:"
    print "{0:4} First, {1:4} Second, {2:4} Third, {3:4} unmatched".format(weights[0], weights[1], weights[2], weights[3])
    print "\nStudents:"
    print_students(students, placements, weights)
    print "\nPlacements:"
    print_placements(placements)
    print "\nTotal unhappiness = {0}".format(total_unhappiness(students, weights))

# matches students with placements which minimizing total unhappiness
def match(weightsfile, placementsfile, studentsfile):
    try:
        weights = read_weights(weightsfile)
    except ValueError:
        print "ERROR: Weights must be in order from smaller to larger values."
        print "Program terminated."
        return
    placements = read_placements(placementsfile)
    students = read_students(studentsfile)
    unmatched = match_students(students, placements)
    print "There are {0} unmatched students {1}".format(len(unmatched), [s2['name'] for s2 in unmatched])

    unoptimized = True
    while (unoptimized):
        unoptimized = optimize_students(students, placements, weights)

    print_report(students, placements, weights)

    print "\nPossible happiness-neutral changes:"    
    equivocate(students, placements, weights)

match("weights.txt", "placements.txt", "students.txt")

Sample output

With the inputs shown above (which is a little unusual in that there are more students than placements), the output looks like this. The * next to an agency name means that this student is placed at this agency:

There are 1 unmatched students ['Jennifer']

Weights:
   0 First,    1 Second,    3 Third,    5 unmatched

Students:
unhp name            first           second          third          
   0 Annabelle      *Agency A                                       
   0 Margaret       *Agency A                        Agency C       
   0 Edward         *Agency B                        Agency A       
   1 Catherine       Agency B       *Agency D        Agency A       
   1 Marie           Agency A       *Agency C        Agency E       
   1 Katie           Agency D       *Agency E        Agency C       
   1 Michael         Agency D       *Agency E        Agency C       
   1 Justin                         *Agency A                       
   5 Jennifer                        Agency E        Agency D       

Placements:
name            avail slots
Agency A           0    3
Agency B           0    1
Agency C           0    1
Agency D           0    1
Agency E           0    2

Total unhappiness = 10

Possible happiness-neutral changes:
swap Katie and Jennifer
swap Michael and Jennifer

Answer 1

Docstrings

The docstrings don't go above the functions, and they don't use the pound sign. They use triple quotes """ Something """ So:

# reads in a file containing student names and preferences
def read_students(filename):

Becomes:

def read_students(filename):
"""Reads in a file containing student names and preferences"""

(Note you can access __doc__ with the latter, but not the former.)

Unnecessary parenthesis

The parenthesis here, for instance:

if (line[0] != '#'):

Are unneeded. Just replace it with:

if line[0] != '#':

This is favorable when programming in Python. (There are other instances where this occurs).

add_student

I wouldn't return False. What if the data is corrupt and student is good? Your code doesn't handle this now anyway, but if you get an invalid student you would like to know the difference between an invalid student, and not being able to add because of space. I would make different exceptions for these.

main is also a sort of a thing in Python too

This:

match("weights.txt", "placements.txt", "students.txt")

Should be wrapped in

if __name__ == "__main__":
    match("weights.txt", "placements.txt", "students.txt")

See this for more information.

print_org

There are no print calls in print_org, maybe change the name to get_org or format_org?

More PEP 8.

pylint complains when there aren't two newlines between functions (unless they are all class methods.) Maybe this is a pylint only thing but I would put two newlines between your methods.

Answer 2

Improving this is hard, and I can't actually get it to a point I'm happy to say is good. But I still have a couple of improvements. Starting from the top:

• You coding style is inconsistent.

• The way you order functions made an already hard to read program even harder to read.

  I expected functions that work together to be grouped, where if a function is needed in another's call, to be placed before the caller. This can make a sort of 'tree' that can make looking up a needed function easier.

  However if you use an IDE that is not; IDLE, notepad++, atom, etc, this probably isn't a big deal.

• A few of your functions take placements, but don't use it, you may want to remove these.

• You don't use sys or string, so you don't need to import them.
• You should use with when you open a file.

• You may want to make a function to open a file and return all lines that are not commented.

  This could be as simple as the following, but simplify three of your functions.

  def commentless(filename):
      with open(filename) as f:
          for line in f:
              if line[0] != '#':
                  yield line
  

• If you remove the comments before looping through the file in read_students, you could use enumerate instead of manually incrementing i.

• You may want to put the three student options into a list, to be able to use some of Pythons sugar.
• In read_weights it doesn't make sense to force them to be sorted. And so I'd off-load this logic to match.
• Your placements should probably be a dictionary, rather than a list. As you look up by it's ID, number.

• When changing add_student to work with the new placements, you may want to use dict.get, and pass a new object as the default. This new object could just contain the key 'available', to possibly improve readability. Mostly as it cuts the amount of lines needed.

  This can allow you to use something like:

  if placements.get(placenum, {'available': 0})['available'] > 0:
      placement['available'] -= 1
      student['placement'] = placement['number']
      return True
  return False
  

• placement_name can be removed after changing placements to be a dictionary.

• If you opt to change student options to be a list rather than three specific items, you can change match_students from being an arrow antipattern unrolled loop, to a loop.

• It doesn't make sense to loop through the entire students list to get one unmatched student. Instead you could create a generator and take the first student by using next.

  Note: I changed this to be a method on a class, you may like it, or you may prefer it to be a standard function.

• Returning when mutating is un-Pythonic, and so you may want to create the unmatched list out of match_students.

• The function unhappiness can be rolled into a loop if you change the student options to a list.
• It doesn't make sense to build a list of numbers to reduce them in total_unhappiness. Instead remove the square brackets, and let it be a generator comprehension.
• I changed print_org to use a turnery, you may or may not prefer it that way. I also merged placement_name into it.
• I don't like how you make h look like a one dimensional list, from a glance, and how it's hard to tell where the second item starts, again from a glance.

• You don't need a temporary variable in Python, to swap them in Python you can use tuple unpacking and packing.

  >>> a, b = 0, 1
  >>> a, b = b, a
  >>> a, b
  (1, 0)
  

• It doesn't make sense to build two whole lists in optimize_students, instead you could write an easy to read generator comprehension to get s and s2 for you.

• You can stop looping after you improve the first student in optimize_students. This is as it doesn't make sense to go through all of them, if you're not going to improve another. As you are using improvement or ....

• You may want to use if __name__ == '__main__': so that if you accidentally import the file, you don't run it.

I've not improved your algorithm, as I found your code hard to read and still don't get one hundred percent what your code is doing. And I didn't change your prints. However, here is an example of how I'd implement all the above. (It's untested, and intended just as a rough guide)

class Students(list):
    def unmatched(self):
        for s in self:
            if s['placement'] == 0:
                yield s

def commentless(filename):
    with open(filename) as f:
        for line in f:
            if line[0] != '#':
                yield line

def read_students(filename):
    students = []
    for index, line in enumerate(commentless(filename)):
        fields = line.strip().split(',')
        student = {
            'name'  : fields[0],
            'choices': [int(f) for f in fields[1:4]]
            'placement' : 0,
            'index' : index
        }
        students.append(student)
    return Students(students)

def read_weights(filename):
    return [int(line) for line in commentless(filename)]

def read_placements(filename):
    placements = {}
    for line in commentless(filename):
        fields = line.strip().split(',')
        placements[int(fields[0])] = {
            'name'  : fields[1],
            'slots' : int(fields[2]),
            'available' : int(fields[2])
        }
    return placements

def add_student(student, placenum, placements):
    if placements.get(placenum, {'available': 0})['available'] > 0:
        placement['available'] -= 1
        student['placement'] = placement['number']
        return True
    return False

def match_students(students, placements):
    for s in students:
        for choice in s['choices']:
            if add_student(s, choice, placements):
                break
    unfilled = [p for p in placements.values() if p['available']>0]
    for p in unfilled:
        try:
            unmatched = next(students.unmatched())
        except StopIteration:
            return None
        add_student(unmatched, p['number'], placements)
    return None

def unhappiness(student, testval, weights):
    for v, w in zip(student['choices'], weights):
        if v == testval:
            return w
    return weights[-1]

def improve_students(s1, s2, weights, neutral=False):
    h = [
        [
            unhappiness(s1, s1['placement'], weights),
            unhappiness(s2, s2['placement'], weights)
        ],
        [
            unhappiness(s1, s2['placement'], weights),
            unhappiness(s2, s1['placement'], weights)
        ]
    ]
    if sum(h[0]) > sum(h[1]):
        s1['placement'], s2['placement'] = s2['placement'], s1['placement']
        # print "swapping {0} and {1}".format(s1['name'], s2['name'])
        return True
    elif neutral and sum(h[0]) == sum(h[1]):
        print "swap {0} and {1}".format(s1['name'], s2['name'])
        return False
    else:
        # print "NOT swapping {0} and {1}".format(s1['name'], s2['name'])
        return False

def optimize_students(students, weights):
    possible_improvements = (
        (s, s2)
        for s in students
        if s['placement'] not in s['choices'][0:2]
        for s2 in students
        if s2['placement'] in s['choices'][0:2]
    )
    for s, s2 in possible_improvements:
        if improve_students(s, s2, weights):
            return True
    return False

def print_org(choice, pref, placements):
    return ('*' if choice == pref else ' ') \
        + placements.get(number, {'name': ' '})['name']

def print_students(students, placements, weights):
    print "{0:4} {1:15} {2:15} {3:15} {4:15}".format("unhp", "name", "first", "second", "third")
    for st in students:
        s = "{0:4} {1:15}".format(unhappiness(st, st['placement'], weights), st['name'])
        s += "{0:15} ".format(print_org(st['first'], st['placement'], placements))
        s += "{0:15} ".format(print_org(st['second'], st['placement'], placements))
        s += "{0:15} ".format(print_org(st['third'], st['placement'], placements))
        print s

def print_placements(placements):
    print "{0:15} {1:4} {2:4}".format("name", "avail", "slots")
    for p in placements.values():
        print "{0:15} {1:4} {2:4}".format(p['name'], p['available'], p['slots'])

def total_unhappiness(students, weights):
    return sum(unhappiness(s, s['placement'], weights) for s in students)

def print_report(students, placements, weights):
    print "\nWeights:"
    print "{0:4} First, {1:4} Second, {2:4} Third, {3:4} unmatched".format(weights[0], weights[1], weights[2], weights[3])
    print "\nStudents:"
    print_students(students, placements, weights)
    print "\nPlacements:"
    print_placements(placements)
    print "\nTotal unhappiness = {0}".format(total_unhappiness(students, weights))

def equivocate(students, weights):
    for s in [s for s in students if unhappiness(s, s['placement'],weights) > weights[0]]:
        for s2 in [s2 for s2 in students if s2['name'] != s['name'] and s2['placement'] != s['placement']]:
            if s['index'] < s2['index']:
                improve_students(s, s2, weights, True)

def match(weightsfile, placementsfile, studentsfile):
    weights = read_weights(weightsfile)
    if weights != list(sorted(weights)):
        print "ERROR: Weights must be in order from smaller to larger values."
        print "Program terminated."
        return
    placements = read_placements(placementsfile)
    students = read_students(studentsfile)
    match_students(students, placements)
    unmatched = list(students.unmatched())
    print "There are {0} unmatched students {1}".format(len(unmatched), [s2['name'] for s2 in unmatched])

    while optimize_students(students, weights):
        pass

    print_report(students, placements, weights)

    print "\nPossible happiness-neutral changes:"    
    equivocate(students, weights)

if __name__ == '__main__':
    match("weights.txt", "placements.txt", "students.txt")

Answer 3

Eliminate long nested loops

Both optimize_students and equivocate contain nested loops, each of which runs through the whole student list.

for s in [s for s in students if ...]:
    for s2 in [s2 for s2 in students if ...]:

This is unnecessary and scales poorly (you probably won't have 10,000 students in your program but still).

Further, after your conditionals are applied, optimize_students then considers every pairwise combination of students from the two lists unhappiness > weights[1] and placement = first or second. So, depending on the number of "unhappy" students after the first pass, the number of comparisons needed for optimize_students is on the order of , where n is the number of students.

The long nested loops can be avoided by having the inner loop look only in the preference lists of the students returned by the outer loop. Indeed, the only way to get a better match is to move a student from within one of their preference slots to another. And as the length of the preference list is fixed, runtime for this version would scale with .

Eg. instead of this (in optimize_students):

    for s in [s for s in students if unhappiness(s, s['placement'],weights) > weights[1]]:
        for s2 in [s2 for s2 in students if s2['placement']==s['first'] or s2['placement']==s['second']]:

Do this:

    for s in [s for s in students if unhappiness(s, s['placement'],weights) > weights[1]]:
        for s2 in [agency_list[agency]['students'] for agency in s['first'], s['second']]:

Having an 'agency_list' allows placement slots to be accessed given only an agency number, rather than looking through the students list. Eg. a list of agencies would be kept and updated with student placements. For example, the following would be in your add_student function:

        student['placement'] = placement['number']
        agency_list[placement['number']]['students'].append(student)   # this line
        return True

Pay attention to the order of students

The while loop

while (unoptimized):

terminates when no more beneficial swaps can be made. This is fine, but the final "happiness" score is then heavily dependent on the initial first placement pass, rather than searching further for the optimal solution.

As it stands, students coming first in the student list get their first preferences, students coming later get their second, and the last students get either their third preference or none at all. There are two possibilities:

• This is a desired feature (ie. first-in-best-dressed). If so, the method you have chosen is appropriate. You first order the students by grades, timely application, or whatever you are judging them on. Then run your code.

• This is not a desired feature, and preferences should be distributed fairly. In this case, you should randomize the order of students.

For example:

from random import shuffle

random_students = shuffle(students)

Then, if changing the order of students is allowed, you may be able to get better scores by running match_students repeatedly, shuffling students each time. If the number of students is < 100 this won't cause delays noticeable to the user.