Hashcode 2018 - How to secure a global rank of 13 with just 100 simple lines of code and reach World Finals!
We (Nikhil Chandak and Shashwat Goel) decided to attempt Hashcode 2018 in a timed (4-hours) virtual environment, as just a team of 2 as our other teammates weren’t available. As the official checker wasn’t available as is in-contest, we decided to use the one by PicoJr on Github. We went in hoping to apply some of the discrete optimization techniques we’d recently picked up, specifically Mixed Integer Programming and Local Search. However, with just an easy to code, generalized and extremely intuitive greedy algorithm, we were able to rack up a score that would have us in the top-15 well within the time limit. This was surprising considering the simplicity of our approach, with no complication whatsoever. It all depended on one clever one-line selection function. Read on to find out more ;)
This blog focuses on the process of attempting hashcode, rather than just providing an editorial of sorts. This is why it’s a relatively long post, but we believe it’s the process that is more useful when starting off, because the solution to every Hashcode will differ. But some insights remain common to all, which we’ll summarize in the conclusion section. Thus, we’ve proceeded to structure the blog on a temporal basis, adding insights roughly corresponding to when we got them, instead of logically clubbing things together. This leads to a more complicated blog, but a more realistic one. However, for serious future aspirants, hopefully this will be more useful.
For those wishing to quickly check our solution, read sections Intro to Greedy A, Implementing Greedy A, The ride picking function, 200-240 minutes breakthrough. Our data analysis is in the section “The Data” and conclusions are at the end of the blog.
Luckily, unlike most Hashcodes, the problem statement was short and easy to understand. The scenario is of operating a fleet of self-driving cars on a
- Starting coordinates
- Destination coordinates
- Earliest possible start time
- Latest possible finish time
A car can service one ride at a time, but the fleet can operate simultaneously. Each car has to drive to the starting location of the ride to collect it and wait till the earliest possible start time. There is a bonus B for every ride that starts exactly at the earliest possible start time. There is no payment for a ride that ends after the latest possible finish time. Otherwise the payment is proportional to the hamming distance traveled during the ride
Pretty intuitive right? It almost sounds like Uber, except that here we have the luxury of pre-booked rides and don’t have to service them online. Other simplifying assumptions in this comparison include uniform time taken per distance traveled and also uniform payments. The bonus on earliest start time and absolute penalty on crossing the finish time are different from a realistic model.
The output which we have to produce is straightforward. For each vehicle, we have to output the number of rides it has performed (
The checker just simulates all the assigned rides to a vehicle. After finishing a ride, the vehicle is instantly transported to the starting location of the next ride. After arriving, if the earliest start time for beginning the ride is more the current time, it simply waits; otherwise, no need to wait. The checker rewards B bonus points if the ride began exactly at the starting time. Also the (manhattan) distance for traveling is awarded only if the ride finished within the latest time; otherwise,
In case anything is unclear, here is the sample explanation for test file A:
We first read and ensured we understood the problem statement. Following this, we started analyzing the data on what properties it could be exploited. This was a time-taking process, but we had realized with experience that it’s essential. The data file names hinted at the properties, and these were the ones we managed to decipher, mostly within the first half-an-hour:
This was just an example. This was just for sanity-checking and contributed negligibly to the score.
This was basically named ‘easy’. It was a small
This was named ‘no hurry’, and as the name suggests, the ‘time’ factors for each rides
This was named ‘metropolis’. Initially, we couldn’t really spot a property except the small bonus of
This was named ‘High bonus’, and you guessed it, the earliest start time bonus in the file was high
We began by reading and ensuring we understood the problem statement. This was followed by exploring all the data files and noting our observations about the data, which came iteratively. We did consider doing more detailed analysis of each data file, including the average distances cars have to travel, to get an idea of whether rides took the car from one end of the city to the other or what. However, there’s always an inherent laziness to this, no matter how much you wish you could write up a clean insightful visualization of the whole data, which even given infinite time, might be infeasible for such datasets.
Within the first hour, we started discussing whatever greedy approaches came to our mind. It’s impossible to document every single approach that came to mind for most were just passing ideas at the back of our minds. However, most were greedy, until our thought process evolved a bit further which we’ll detail.
Initially, Nikhil suggested just using the low duration in test-file B to naively simulate the process, picking a new ride using a to-be-decided heuristic for each vehicle when its previous one got over. The complexity of this process is roughly spoiler: ha!) and wanted to think more, and so we did. For now we’ll refer to this approach as Greedy A.
Shashwat initially floated the comparison between scheduling algorithms in Operating Systems and the problem at hand, but Nikhil was smart to stop that chain of thought in its tracks, before time was wasted on further exploration. The key difference was the transition time between 2 rides, that is shifting a vehicle from one ride to another, and then making it wait till the earliest start time of the latter ride when required. This transition time turns out to be the key factor in this problem, because score = T*F - sum(transition time) + bonuses. This is because
- we have multiple cars
- transition time from ride A to B changes based on when ride A was completed in the first place, because that decides how much time the car wastes on waiting for the earliest start time of B.
A tighter-bound is calculating the sum of distances for all rides for every test-file, and assuming we manage we achieve bonus for each ride. This bound was helpful in setting a benchmark towards what the scope for optimization on each file is.
Pro Tip: If you’re within
$0.1%$ of the optimal value in a test file, it is better to focus on other files where there is larger scope for improvement. Well, if you’re within$0.1%$ of the optimal value in all the test files, then I guess you have already secured a seat in Hashcode Finals? ;)
Meanwhile Shashwat realized that test E could be approached by just trying to maximize the number of rides scheduled with a bonus, ignoring distances for the time being. Nikhil brought in the comparison with the classic CP problem of choosing maximal non-intersecting intervals over a given time axis. Basically, just sort the rides by end time (why not start time?), and try to assign a vehicle to each so that we maximize the ones that get a bonus. We’ll refer to this as Greedy B. Around the 1 hour mark itself, Nikhil decided to take up the implementation for this.
He ensured that whichever ride a vehicle takes, it should always get a bonus on that. After sorting the rides by the earliest finish time, one just had to repeat this simple procedure:
- maintain a global list of remaining rides and iterate over each vehicle
- pick the maximal number of non-intersecting rides
- assign it to the current vehicle and calculate the score
- remove the assigned rides from the global list of remaining ones and move to the next vehicle
Nikhil was able to code this in roughly 20-25 minutes and it got a whooping
Initial bench-mark of our score
It was definitely a good score to begin with but as with every optimization contest, you want more :) Nikhil inspected the output and noticed that
So a natural yet extremely simple fix was to go over each un-riden ride and assign a not used vehicle to it, with the hope that the vehicle will be able to complete the ride within the latest finish time. We definitely didn’t have scope to get more bonus but we could improve our score by rides’ distances/length. This approach improved the score by over
We were happy that we got a pretty good score halfway through the contest on E. Nikhil analyzed further on how many rides remained unscheduled and there were
Shashwat meanwhile tried to attack the more general structure of the problem. The observation was that the problem at hand was a mixture of assignment and ordering (routing, similar to traveling salesman). Any solution can be viewed as assigning cars to rides and then ordering the rides of that car for each car independently. At this point, ideas like doing random assignments of cars to rides (as cars were symmetric resources) and then tackling the ordering problem separately, perhaps using Local Search, were considered. However, these seemed time-taking to implement, so more thought and confidence was needed before starting.
Around 15 minutes (around 75 mins since the start) after Nikhil had started coding the test E greedy, Shashwat decided to implement greedy A. A quick recap, this is just simulating the whole situation by assigning rides to available cars greedily on-the-go.
Before implementing, I realized the simulation could be made efficient using a C++ STL priority queue that keeps cars sorted by when they will become (or last became) free. This way we could just check if the top element in the priority queue is already free, and until that condition remains for the queue, pop the top car out, schedule it a new ride, inserting it back.
Shashwat finished implementing before the 2.5 hour mark, and the code came out surprisingly clean and modular. The final code is attached here, and the only significant change from the initial implementation (as at ~135 minutes) is some minor debugging, and changes to the priority score computation for ride picking. Rest are comments for easy understanding :)
https://gist.github.com/c1695ca919c5f9eaf54de268ac5206e8
The only detail left to be decided in this paradigm is how to pick among the various possible next rides for a particular car. I thought the general approach is to pick using a function of the following parameters:
- Bonus attained on picking next
- Length of the ride
- Wasted time on transitioning to this ride
Then each not-previously-done ride could be evaluated using this function whenever we’re picking a ride. That leads to
Here, it seemed viable to keep the function linear with coefficient multipliers for a) b) and c). This is because intuitively their effect on final score combines linearly. More complicated functions can be tried, but we didn’t do this.
- More bonus attained leads to a proportional (constant 1) growth in score.
- Longer rides mean less time wasted in transition overall, but also less rides get scheduled leading to less bonus. This one can both have a negative and positive coefficient as its net effect is unclear. So this had to be empirically tuned.
- An increase in wasted time leads to a proportional drop in score (constant -1). This was still experimented with but the -1 coefficient turned out to be sufficient.
After implementing, the first run itself gave us a seemingly good score. We got bonus + 0.0*rides[i].length - wasted_time at this point. [Yes, ride length had coefficient 0 initially].
Meanwhile, Nikhil had finished implementing his approach of taking unassigned rides while waiting. Alas, there was no improvement at all in E!
Anyway, we had racked up a pretty good rank on the scoreboard! Shashwat’s approach was particularly great because Greedy A had managed to match the score of Greedy B on Test E, something greedy B had been specialized for. This gave us further hints that improving on Test E further might just be very hard, perhaps this was the optimum? We were anyway close to the theoretical upper-bound. Keeping all this in mind, we decided not to work further on Greedy B as Greedy A was promising across the test-sets. Comparing with our bounds, it was clear the scope for major improvement in score lay in test C and D. Especially test D (metropolis) where we were off by almost
So overall, we were pretty hyped up and with more than 1.5 hour left, perhaps some smart tuning could take us to the top?...
Before moving on, it’s important to mention the mistakes we’d made.
For E, remember the scope for improvement? Yes,
As for Shashwat, he decided to write code from scratch as the I/O seemed uncomplicated. But in hindsight, always take helper functions for input, output the structures used in the program and other common processing functions like calculating hamming distance between 2 intersections from your teammate if they started coding earlier (as Nikhil had, in our case). It took Shashwat 20-30 minutes to finish writing and testing these generic bits, time which could’ve comfortably been saved. Moreover, the structures became very different from Nikhil which could’ve come back to haunt us if we had to combine approaches at some point (luckily, we didn’t!).
So both of us set out to tune the score function. For test file C, after some manual ternary searching on the coefficient for ride length and arriving at
The sad part was that any coefficient tuning on bonus + 0*rides[i].length - wasted_time was only worsening the solution on test file D. We noticed that
Nikhil even tried some exponential scoring functions but they all ended up much worse. We’d spent 30 minutes making minor changes to the scoring function, and were starting to lose hope. Perhaps progress on test file D, the busy metropolis, required more sophisticated approaches like Local Search?
We came up with a local search model actually. If we consider a 2D table with each row representing a car, and each row (car) having a subset of rides allocated in order, perhaps the local moves of swapping 2 rides within a particular row (fixed car) or swapping 2 rides across cars would help. Given we had a good greedy initialization, the chances seemed high infact. The only issue was implementing a swapping move. A glance at the code would tell you that evaluating swaps in the ordering within a constant factor overhead was non-trivial. There were details like start time and end time that needed to be evaluated. The prospect of accurately coding this within 1 hour seemed daunting, though doable.
Our laziness found itself prevailing, and every minute we procrastinated, hoping for some breakthrough using tuning, the likelihood of implementing local search on time got lesser and lesser.
Then came a eureka moment. See if you can spot what information our
We weren’t incentivizing rides that had an earlier latest finish time! This meant that we gave no priority to rides that won’t be available soon overrides which might be available even much later. Bummer! We didn’t exactly think this would give a huge boost, but we changed the scoring function to:
bonus + 0.0*rides[i].length - wasted_time - *coefficient**(rides[i].lastest_end - t ) // t is the current timestep
Some tuning on the coefficient, and at
This meant a total score of:
Small improvement on large gap will be more rewarding then large improvement on small gap, as Hashcode final score is sum of individual file scores
As a consequence, always focus on files that give larger magnitude of output [Eg, ignoring file B in this problem]. For the same reason, having some upper-bounds pre-computed when easy is a nice way to navigate the contest, considering individual file scores are not shown on the leaderboard.
One teammate should write boilerplate code as soon as possible, and make sure everyone sticks to that. This not only saves time for everyone but also makes collaboration and code integration smoother later.
Keep it simple, stupid i.e. KISS principle
Writing a generic greedy with a selection function that can incorporate multiple parameters will most likely be more useful than complicated techniques like discrete optimization. Something like local search requires a good initialization to be effective mostly, so writing greedy first can virtually hit 2 birds with one arrow.
Improvements like coefficient tuning often bring small improvements. They’re best done closer to the end, as that’s also when we work at our fastest. Moreover, tuning is boring and exhausting simultaneously. In the earlier parts, focus on finding new insights, which might lead to large jumps in score even if simple to code.
After doing some other editions as well (and not coming up with as effective solutions, hence no blog for these :P) it seems these tips apply across years in Google Hashcode. Hopefully this chronicle of our experience will help you prepare for future HashCode contests. Let us know what you think in the comments! :D
