Hackathon/Stable Marriage Problem

I recently volunteered at a hackathon at my workplace, where university students were invited to team up to solve problems for charities and NGOs, which also doubled as a thinly-veiled recruitment exercise (everybody wins!). I was on hand to answer technical questions that the participants had; it was an enjoyable couple days working with some bright, young, talented people. And of course, they had plenty of snacks to keep them going!

One thing I noticed was that many of the problems were variations on the Stable Marriage problem – the problem of “finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element”, which has many important applications, including matching users to servers in CDNs (where proximity determines preference).

A solution to this problem is to use the Gale-Shaply algorithm, so I had a go at coding it up myself. As ever, source code here!