2nd e-Travel Code Challenge
May 18, 2017
Code Challenge Stable Marriage Hospitals/Residents Gale–Shapley Algorithm

Our second internal code contest was held during December 2016/January 2017. This time participants could sharpen their algorithmic & problem solving skills, utilizing the programming language of their choice to solve a rather old problem:

You work as a developer at LinkedOut, a platform that connects companies with professionals.

LinkedOut operates a website for both professionals and companies to register and seek for jobs and candidates, respectively.

The basic goal of LinkedOut is to match professionals to companies so that both parts will be happy.

How professionals and companies choose each other?

  1. Each professional creates a “professional wish list” of companies based on his/her preferences. Top in the list is the one which is the most preferred..

  2. Every company creates a similar list of professionals ordered from the most to least preferred to hire. In addition, each company provides the number of its currently opened positions (slots) that wishes to fill in.

Scoring

Submissions will be scored taking into account the following factors:

  1. Penalty points. For each match that both of the below points are true the submission gets one penalty point:

    • Professional P would prefer to work for company C over the company he is currently matched with and, at the same time,

    • Company C would prefer professional P over one of the candidates currently filling one of its empty slots.

  2. Tiebreaker: Total execution time

Some background

Again, Google proved to be every programmer’s best friend and after a few searches everybody came to understand that the above problem was actually the famous “Stable marriage problem”, also known with the following names:

  • assignment problem

  • stable roommates problem

  • hospitals/residents problem

  • college admissions problem

Algorithms for finding solutions to this problem or to its many numerous variations, can be applied to a variety of real-world situations, perhaps the best known of these being the assignment of graduated medical students to their first hospital appointments. There is even a U.S. national program dedicated to this task since 1952.

In 1962, David Gale and Lloyd Shapley presented an algorithm (Gale–Shapley algorithm) that guarantees the optimal solution to the problem. Lloyd S. Shapley was co-awarded in 2012 The Nobel Prize in Economic Sciences for his work in market design and game theory.

A very intuitive visualization of the algorithm can be found here.

There is also an excellent and detailed lecture from the McGill CS School on the subject, that I suggest you should read.

Back to the contest

The interesting thing about this contest was that submitters were allowed to implement their solution in any programming language they would like.

The only restriction was that the final executable should be able to run on a system running on Debian Jessie, but that didn’t discourage our C# fans with .NET Core saving the day.

Since most devs here use C# and Ruby, it was expected that the first “exploratory” submissions were implemented in those languages.

After a few failed attempts everybody was on the right track, having implemented correctly the Gale–Shapley algorithm or at least a variant of it.

Then, the time race started. Ruby gave its place to Scala and C# to C, though the few brave ones trusted C# till the end.

Programming language change, followed by some smart optimizations (custom data-structures, tokenization etc) resulted in a huge performance improvement.

The benchmark

Two Scala scripts were used for the evaluation and score of the candidates’ submissions.

The first script (DataGeneratorRand.scala) produced two random files. The first file contained a list of companies and their professionals wish-list and the second one a list of professionals and an ordered list of companies that she/he wishes to work for.

Files generated from this script contained an average of 2000 companies and 8000 professionals with their respective preference lists and a random number of open slots per company.

The file size of each dataset was approximately 300MB.

Each submission was tested against a set of 8 random generated data-sets for penalty points using the Scorer.scala script and then timed using the time command.

The final solutions of the participants were very close (1% - 8% difference) in terms of total execution time.

As expected, the C implementation had the best time and Iasonas Gavriilidis was the second e-Traveler to be included in the Hall of Fame and win a Raspberry Pi 3 board.

Figure 1

Congratulations, Jason!

You can find the final ranking and the final submission in our GitHub repository.

Needless to say, the contest was a very entertaining and rewarding experience that helped participants to expand their algorithmic arsenal and experiment with new languages and technologies.

Share on