Produces a stable matching of Mozillians to summit locations based on each Mozillian's preferences over the different summit locations. see: http://xor.lonnen.com/2013/05/04/gale-shapley.html

matching.py

# !/usr/bin/env python
# coding=utf-8
"""
Produces a stable matching of Mozillians to summit locations based on each
Mozillian's preferences over the different summit locations.

see: http://xor.lonnen.com/2013/05/04/gale-shapley.html
"""

import csv
import random

from optparse import OptionParser

# random seed for initial ordering
SEED = "Summit 2013"
SUMMIT_SPOTS = {
    "Brussels": 13,
    "Toronto": 14,
    "Santa Clara": 14,
}


def match():
    parser = OptionParser(usage='usage: %prog [options] preferences.csv')
    parser.add_option('-v', '--verbose', help='explain everything',
                      dest='verbose', default=False, action='store_true')

    (options, args) = parser.parse_args()
    verbose = options.verbose or False

    if len(args) != 1:
        parser.error('must provide 1 and only 1 preferences file')

    no_preference = []
    unmatched = []
    matched = []

    summit_spots = SUMMIT_SPOTS

    if verbose:
        print "Locations and Seats:"
        for location, seats in summit_spots.iteritems():
            print "\t%s: %s" % (location, seats)

    if verbose:
        print "\nreading preferences from '%s'" % args[0]

    with open(args[0], 'rb') as f:
        # expected positions of important info for each row:
        # 0 - name, preferences from first to last - 1,2,3, do not want - 4
        for preference in csv.reader(f):

            person = {
                "name": preference[0],
                # order from least to most important
                "prefs": preference[3:0:-1],
                "do_not_want": preference[4]
            }

            if verbose:
                print person['name']
                print "\tprefers: %s, %s, %s" % tuple(person['prefs'][::-1])
                print "\tDoes not want: %s" % person['do_not_want']

            if person['prefs'][2] == "":
                no_preference.append(person['name'])
            else:
                unmatched.append(person)

    # arbitrary seed ot keep things consistent
    random.seed(SEED)
    random.shuffle(unmatched)
    if verbose:
        print "\nRandom seed: %s" % SEED
        print "Shuffle order: "
        for person in reversed(unmatched):
            print "\t%s" % person['name']
        print "\nStarting to match..."

    while unmatched:
        person = unmatched.pop()
        name = person['name']

        try:
            preference = person['prefs'].pop()
        except IndexError:
            # person has run out of preferences
            if verbose:
                print "%s has run out of preferances and is unmatchable" % name

        if preference is "":
            if verbose:
                print "%s has not responded with a preference" % name
            continue

        if verbose:
            print "%s will ask for %s" % (name, preference)

        if summit_spots[preference] > 0:
            summit_spots[preference] -= 1
            matched.append((name, preference))
            if verbose:
                print "%s was matched with %s" % (name, preference)
                if person['do_not_want'] == preference:
                    "WARNING: %s does not want what was assigned" % name
                print "%s has %s spots remaining" % (preference,
                                                     summit_spots[preference])
            continue

        if verbose:
            print "%s heads to the back of the queue" % name
        unmatched.insert(0, person)

    if no_preference:
        if verbose:
            print "\nThe following have no preferences and need to be matched:"
            for person in no_preference:
                print "\t%s" % person
        for place, seats in summit_spots.iteritems():
            for _ in range(seats):
                if not no_preference:
                    continue
                name = no_preference.pop()
                matched.append((name, place))
                summit_spots[place] -= 1
                if verbose:
                    print "%s was matched with %s" % (name, place)

    print "\n-------------"
    print "Final Tallies"
    print "-------------"
    if matched:
        seen = set()
        for (name, place) in sorted(matched, key=lambda x: x[1] + x[0]):
            if place not in seen:
                print "\nGoing to %s:" % place
                seen.add(place)
            print "\t%s" % name
    else:
        print "No matches were made!"

    if unmatched:
        print "\nCould not be matched:"
        for person in unmatched:
            print "\t%s" % name

    if no_preference:
        print "\nHad no preferences and needs to be matched:"
        for person in no_preference:
            print "\t%s" % person

    print "\nRemaining spots at each location:"
    for location, remaining in summit_spots.iteritems():
        print "\t%s: %s" % (location, remaining)


if __name__ == '__main__':
    match()

note: the original posting of this effectively printed out the queue backwards, because the list is iterated over with .pop(). I've updated the script so that it properly reverses the queue before printing.