Google Hash Code 2018 solution and source code – 1st in Malta and top 20% worldwide

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).

Capture

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!

Putting a face to the name

If you’re a developer on an island like me, chances are your end clients are foreigners, not local. This means that most of the communication is done either by e-mails or by some kind of voice calls. This is exactly my case; but after working with the clients for around three years, I finally got a chance to meet them in person, in London.

Although I’ve spent quite a lot of time talking to these people by both e-mails and weekly phone conversations, the experience of communicating with a person face to face is so much better than behind a screen. Face to face communications shows far more emotion and connection between people; it’s amazing.

I’ve only had two days with my clients; so time was definitely not on our side. Would more time meant better understanding of what they want from our side? Of course! But it does not matter that much; plus such conversations can now be continued by phone in the coming days. Of course, we went through lengthy discussions with regards to our vision for the foreseeable future. The sad part is that half of what we said will probably never be realised due to the usual problem: budgets.

What did this trip yield? Frankly; less than expected. Conversations got dragged and go on tangents, schedules were ignored and sometimes the clients just started having conversations with each other, leaving us just listening and waiting for them to conclude. But the fact that both my clients and I can now put a face to the name is worth the trip on its own.

In the end of the day, was the trip worth? Yes, hands down! Such meetings aid in boosting the confidence of both parties; which will (hopefully) result in better understanding between the two parties.

Plus, I got to spend some time touring through London, so that’s great as well!