Our solution: https://github.com/albertherd/Hash-Code-2018-Team-Stark

I recently had the honour to team up with my friends (and co-workers) to have a crack at the Google Hash Code 2018 online qualification round. We went to compete with little to no expectation. In fact, by the first two hours of the competition, we had almost nothing!

Google Hash Code is a team based competition, where teams all over the world gather together to participate and solve a Google engineering problem, using a language of their choice.

The problem was: Given a set of rides and a number of cars in a city grid, assign rides to cars, and serve the rides in a restricted time. There are also bonuses if you manage to start the ride as early as possible. Here is the Problem statement, input data set A,  input data set B,  input data set C  input data set D,  input data set E,

Our solution is not the cleanest solution, I must admit. One has to keep in mind that when undertaking these competitions, the biggest challenge is to come up with a decent solution the problem in a very short amount of time, rather than creating a complex solution which does solves the problem perfectly.

However imperfect, hacks-infested and dirty, it managed to place us first in the Maltese islands, and in the top 20% worldwide (more specifically, 895th).

Our solution does not make use of a Genetic Algorithm; we tried to create a Greedy Algorithm with several optimizations in order to boost the quality of the output. Optimizations include:

• Having the main loop revolve around steps, rather than cars or rides (much like a game engine main loop).
• Sort all the initial rides by start time.
• Discard any rides that have been already undertaken.
• When trying to pick out a ride, we make sure that given current time (or step), we check if the ride can actually be served on time. Using this thought, we’ve managed to produce output with 0 late rides across the board!
• Get the first feasible N rides – sort them out by closest, then by travelling and undertake that ride. Since each ride yielded the same bonus, irrespective of the distance traveled, the shortest rides were always the most profitable.
• Other minor optimizations.

There are multiple optimizations and enhancements that we wished to include, such as removing those impossible rides from the data set as we go along, and distributing each car / ride according to a “zone”. In fact, the code does have a Zone class, which never got used.

Have a look at our solution : https://github.com/albertherd/Hash-Code-2018-Team-Stark

Until the next one!