Reaching top 10 in Google Hash Code by playing games

Aron Granberg February 23, 2023

This is the story of how we ended up in 8ᵗʰ place in Google Hash Code, and why we spent the last 30 minutes of the competition fervently playing games.

Hash Code

You might have heard of Hash Code. It was an annual team programming contest hosted by Google, and it was a little different than most other contests. Yesterday Google announced that Hash Code will be discontinued, which was an incredibly sad piece of news, because Hash Code was such a special competition.

Hash Code eschewed the strict programming competition formula of having a set of algorithmic problems that can be solved perfectly, and substituted it with chaos. There was only a single task, which was impossible to solve perfectly in any reasonable amount of time. Instead, all teams competed to solve the task as well as possible, using whatever tools they thought might be useful.

A lot of people clearly thought this was a fun concept, because last year more than 10 000 teams participated in the qualifications. The top 40 teams qualified for the finals, and our team 1 was among the lucky few!

To commemorate Hash Code, and get a bit sentimental, I have written up our experience from last year’s finals where our team used a weird strategy befitting this weird competition.

The problem

The finals featured a very Christmassy problem: Santa had a ton of gifts to deliver, and we had to help him plan his route so as to deliver as many gifts as possible. The full problem statement is quite long, but I’ll do my best to summarize it here 2:

• Santa has his base at the center of the large grid known as planet Earth.
• Santa has up to 10 000 gifts to deliver, each with a given weight and a child it is intended for.
• Santa can pick up gifts whenever he is close to his base, and deliver them when he is close enough to a child.
• Santa’s sleigh is pulled by magical reindeer, which can accelerate the sleigh in any of the four cardinal directions once per time step.
• The reindeer, despite being magical, have a limit. Their acceleration decreases as the sleigh gets heavier, even going down to zero if the sleigh is too heavy.
• Santa needs to race against the clock to deliver gifts before Christmas is over (up to 10 000 time steps).

Apparently, Santa’s sleigh obeys a set of physical laws that are almost, but not quite, entirely unlike the physical laws of the real world.

Analysis

This is quite a tricky problem. Santa has to load gifts, deliver them to some children, then return to get more gifts, and continue doing that as efficiently as he can.

You might be tempted to draw parallels to the traveling salesman problem, but this problem is a bit different since the sleigh has additional state (its weight and velocity), and it is not even trivial to write code to just move the sleigh from one point to another given all the crazy acceleration shenanigans going on.3

But let’s start with the fundamentals. If you have participated in Hash Code before, you might know that it was a so-called Open Input competition. This means that all scenarios (6 of them, in this case) on which you will be evaluated are available as soon as the competition starts, and during the competition you upload your best answer file for each scenario. You don’t necessarily need to use a program to generate the answer files. You could read tea leaves to find the answers, if you think that might help. In fact, the easiest scenario is often solvable by hand.

So how did we approach this problem? Well, the first step when trying to solve any Hash Code problem should in my opinion always be to visualize the scenarios to be solved. This is because each scenario typically contains data following some specific pattern, which can be exploited to earn more points!

So we started by plotting the coordinates of the children in each scenario:

As you can see, this was far from just a bunch of random points. All of them had their own distinct patterns, and so we started brainstorming:

• In Better Hurry, Santa could go to one of the corners and deliver all the presents there, and then he could go to the opposite corner and pick up presents on the way, without having to stop in the middle.4
• In Carousel, maybe we could make the sleigh follow the spiral, without ever having to go back home to stock up on presents.
• In Festive Flyover we considered a complicated setup where Santa would fly with an empty sleigh in one direction, accelerate to a high velocity in the opposite direction, and pick up a lot of presents on the way. Then it wouldn’t matter if the sleigh got too heavy to steer, because Santa could drop off presents until he could steer again.

We felt that these were promising ideas, but the idea that we really fell in love with was this one:

Instead of trying to implement all these complicated strategies in code, why not make a game out of it?

This actually made a lot of sense. The competition was only four hours long, and we realized that none of the teams would be able to solve the problem even close to optimally within that time frame. But if we could turn the problem into a game, we would have at our disposal four neural networks tuned by evolution over millions of years and with excellent spatial capabilities. Yes, I’m talking about our brains!

How to turn the problem into a game

For the gamification strategy to be feasible, we would have to minimize the number of low-level decisions taken by the player. There were many thousands of presents to be delivered, so if the player had to take explicit actions to pick up and drop off presents, then playing the game would have taken too much time. Therefore we had to make the low-level decisions automatic, leaving only the high-level strategic decisions to the player.

So we needed to figure out how to make the game automatically decide which gifts Santa should pick up at his base. We would have wanted to just pick up the gifts intended for children that Santa would later fly by, but when picking up the gifts we didn’t know where the player would choose to fly, and which gifts we picked up would affect where the player could fly because the sleigh’s acceleration depended on its weight. It looked like we had a catch-22 on our hands.

Except, we could actually solve this using a clever bit of time travel. You see, it didn’t actually matter which specific gifts Santa picked up; it only mattered how much they weighed in total. So we could just make Santa pick up an unspecified bundle of gifts which was just light enough that the reindeer could still accelerate the sleigh. Then, when we came into range of a child, we would retroactively change the past to say that the child’s gift totally was among those he picked up last time he visited his base.

Using that idea, the game would be able to automatically pick up and deliver gifts, and all the player had to do would be to steer the sleigh. Perfect!

The result

I implemented the game in Unity in the quickest way possible, for the most part using debug drawing utilities from a Unity package I built a couple of years ago.

Once the game was ready, we immediately saw that we were onto something. My initial stumbling attempts at Excellent Weather easily got us the best submitted score for that scenario at that time in the competition. As a bonus, we got a much better feel for the problem than we could have ever gotten otherwise (after all, reading tables of numbers only gets you so far).

Sadly, the game only proved appropriate for 3 of the scenarios: Carousel, Excellent Weather and Festive Flyover. The other ones had too weird accelerations, or required too much precision, which made them very hard to play. But the competition was nearing its end, so we sat down, flexed our fingers, and spent the remaining 30 minutes frantically playing the game over and over, trying to beat our own high scores.

In the end, even though we only submitted solutions to 3 out of 6 scenarios, we still got enough points for an 8ᵗʰ place. This was our best result ever in Hash Code, and all thanks to the weirdest strategy we’ve ever used in a programming competition!

You can play the game too! Maybe you can even beat our high scores!

— Aron Granberg

About the authors

We are Aron Granberg and Mårten Wiman, two passionate programmers from Stockholm who are always looking for interesting problems to solve. Reach out to us at contact@optimeringsfabriken.se if you have an interesting project in need of programmers, or if you just want to say hi.