Yesterday (1st March 2018), a number of HullCSS students got together to compete in Google’s HashCode competition. Everyone managed to submit a solution and gain points, and great fun was had by all.

The Event

HullCSS (The Hull Computer Science Society) ran a HashCode Hub in the Fenner SuperLab, where teams from all over the University came together to compete. It was the first time HashCode was run at the University of Hull, and all students were welcome.

All teams managed to submit a working solution, with the lowest point total being 10 Million, and the highest being 45 Million. All were impressive solutions, with each taking a different approach to solving the problem. Everyone relished the challenge, and it was interesting to see all skill levels working together.

All teams were eagerly watching the scoreboard throughout the event. Everyone wanted to make it above the top 1000 teams (top 25%).

My team consisted of Josh Taylor, Alexander Rossa, and myself, and was named Gravity Gun. We kicked off at 5.45pm with the release of the problem (which you can find here), and got to work planning out our algorithm.

The Solution

We decided to take a Supervisor/Worker approach, with our main program acting as a coordinator of rides, and the cars doing much of the route finding/calculation themselves.

A basic set of properties were given to the car, to allow it to know about itself, such as its position, the rides it has completed, and the current global step it is on. This allows the supervisor to ask the car how long it will take to complete a given ride. The car is capable of calculating at what points it will pick up the customer, and arrive at the destination.

The supervisor knows more generalised information about the problem, such as the size of the grid, the list of cars and rides to complete, and the number of steps in which the rides have to be completed. It prioritised the list of rides, then asks each car how long it will take to complete the ride. In this version the prioritisation is very basic, and is only ordered by the end step in ascending order. It then gathers the results, and immediately removes any result that will complete after the maximum finish step of the ride. If the ride won’t complete the ride in time, we don’t even want to attempt it, as we could be using this time to get more points.

Next, it will check to see if any of the cars can achieve the bonus points. If they can, it will pick one of these cars, otherwise it will pick any car. It will then pick the car that reported the least number of steps to complete the job. This provides a fairly optimal path for completing rides (though clearly not the best!).

Conclusions

This model is fairly good, achieving 45 million points, though not without its faults. The top team managed to achieve over 49 million points. Given more time (there was a fair amount of time finding and fixing silly logic errors), we’d look to improve the prioritisation algorithm, looking at balancing the choice of going on a long journey, vs doing multiple short ones.

The competition was great fun, and I’ll certainly look to do it again next year. I’d encourage any student who wants experience with a real world, complex programming problem to compete! It offers something drastically different from  a University module, and it can be really rewarding to build a working solution. As a student, the challenge was really engaging, but not too difficult as to be unsolvable.

I’ll definitely be encouraging HullCSS to run the event again next year. If you’re in Hull and want to get involved, let me know. If there is enough interest, it may be that the Hub is opened up to the whole city!

Links

Want to know more about HashCode or get involved? You can find some info here:

https://hashcode.withgoogle.com/

 

Want to see my solution? Check it out on GitHub! (We were really tired, and were rushing when we wrote this, apologies in advance!)

https://github.com/HarryGwinnell/HashCode2018

 

Want to have a go yourself? Find the PDF problem here! And the inputs are here.

 

Why not check out my other projects?