Intro

On Thursday February 24:th an excited team of Meepo employees sat down together to take part in the qualification round of Googles annual Hash Code programming competition. We thought we’d share some thoughts about the assignment and what went well and what didn’t here.

The Competition

Google Hash Code is an annual programming competition in two parts. First there is an online qualification round which usually has around 10 000 teams taking place. A team is made up of two to four people. The qualification round lasts for around four hours and the top 30 to 50 teams are invited to the final competition which is usually held onsite at a Google office, but this year will be held online.

What stands out with Google Hash Code is that the problems are always optimization problems where the goal is not to find the optimal solutions, the inputs are designed to not be optimally solvable in a reasonable time. Instead, you get a score depending on how good your solution is and you can refine your solution throughout the competition and submit multiple times.

Each year there is a single optimization problem to solve, but the problem has multiple inputs of different sizes. Each input is scored separately.

This years problem

The problem this year was to allocate contributors with certain skills to projects to complete them. Your score was the number of projects you completed with a penalty for completing them late. There was also an added twist that contributors could gain skills from completing projects and contributors could mentor each other so that the contributors did not have to match the exact skill level that the project roles required. For more information, see the problem statement.

Our solution

It took us almost two hours to get an algorithm in place that could parse all in input files and produce a first solution to them. We didn’t look too closely at the input data but used the small example input to structure our data model and then found out that the larger inputs had some cases we hadn’t thought of, like that there could be multiple roles for a project that required the same skill. In the first version we completely ignored the mentor aspect and that contributors could level up to not complicate the first solution too much.

Our first solution was simply to step forward in time and at each interesting time try to start all projects that could be started by looping through all not started projects according to a project score (the number of points per day this project took to complete that it was worth).

For each project that we wanted to check if we could start we simply looped over all the roles and found the contributor with the lowest score in the skill the role required that was still qualified and didn’t work on any other project at the time.

This solution still got us quite a lot of points and for a while we were in the top 10 list in the world :)

This was about halfway through the competition and after that we spent the time refining the solution by implementing mentorship and that contributors could level up. We also tried different ways of sorting the projects to account for days left until the project would be worth less to complete and how many contributors we could level up.

We quite early on implemented that each input could be solved in it’s own thread, but since some inputs took a long time to solve with our algorithm, input e and f took several minutes, it took a while to try different versions of the algorithm and different parameters.

A few of the inputs were really quick, like input b and d, but we very late started running only those with different parameters to get a quicker feedback loop, but it was a bit too late in the competition for it to do us much good.

We had several ideas during the competition for how to model this as a graph problem and backtrack solutions to see if we could do better that way, but we didn't have time to try them out or implement them far enough to produce solutions for the inputs.

Our code for this competition is available at https://gitlab.com/meepoab/public/hash-code-2022.

Conclusion and thoughts for next year

In the end we finished in 79th place and in fourth place amongst Swedish teams.

That was a lot better than we had finished previous years. All in all we are very happy with the final results, but as always there were things we would have liked to try that we never got around to. After the competition, on the way from the office, we thought of a small change that when we tried it the next day meant we got 61 000 more points which would have placed us around place 56 if we had thought of it during the competition.

Some things that we take away from the competition for next year (which we are already gearing up for):

• A good live share functionality for the IDE:s is good, but make sure to really try it out beforehand as we had some problems with the Live Share functionality of Visual Studio as compile errors were only seen by the person starting the Live Share, not the other people, even if they wrote the code that didn’t compile. The code completion was a bit buggy as well.

• Getting a first general version of the algorithm up and running and getting in a first submission is good, but to then refine the general solution is difficult. It is better to try to focus on individual inputs and modify the algorithm for them specifically. For example the larger inputs had many, many more projects than contributors which probably means a specific algorithm for that situation would be better for those.

• It is also good to be able to calculate the final score in the algorithm, so the algorithm can automatically determine if this configuration of parameters was good or not. That way the algorithm can be run multiple times with many different parameter sets and automatically determine the best output and only produce that instead of manually having to go submit all solutions to see if they were better or not.

All in all it was a very fun night and time flew by really quickly. As always we are amazed at how the winning teams got as high scores as they did.

Thank you Google for a fun competition, we will definitely be back next year and our aim is set for top 50.