Written by Florian Jüngermann, Co-Founder XOrigin
In February 2020, more than 10,000 teams from all over the world came together to compete in the Google Hashcode competition. What sets this contest apart from all the other programming competitions, is the type of problems posed. Here, you solve optimization problems close to the real world, often inspired by Google's challenges. The past problems reached from providing Internet access via high altitude balloons (like in Google Loon) to optimizing video streaming servers needed for Youtube.
Together with my team, we have successfully participated in many past Hashcode rounds, so we knew what to expect in this year's final. Or so we thought...
Learning from the past
A Hashcode problem set consists of only one task statement, but your score is the result of your solutions for roughly six different test cases. Every test case describes a different situation with potentially different bottlenecks. In the video streaming example, there may be one test case with only a few servers, while another test comprises many servers but only a few exceptionally long videos. When we started taking part in the Hashcode competitions, we were able to score remarkably high using a simple approach. We developed a greedy strategy that we could tune with as many variables as possible. This means we chose a grading function which tells us, for example, how valuable a video is. This score depends on many variables like the number of people requesting it, the amount of space it requires, etc. Then, we tried to adapt to how we weight the different factors for each scenario. Back in the days, this approach was extremely effective. I firmly remember how we placed 7th in the qualification round 2018 by only spending half of our time programming and the other half on fine-tuning our parameters.
But with time, the problems changed. In the Final 2019, the scenarios were so different that we needed to develop multiple, completely independent solutions. We adapted to this change by dedicating one team member to inspect the test cases. This way, we were able to solve all the scenarios well and secured place 13 in last year's final. In this year's final, however, the problem was fundamentally different.
The Hashcode Final 2019 in the Google office in Dublin. Unfortunately, the on-site event this year was canceled.
Due to the Coronavirus, the Google Hashcode Finals 2020 did not take place in Dublin, Irland, but happened online. The location was not the only thing that changed though. This year's task revolved around manufacturing planning. To summarize the statement:
You have a list of manufacturing tasks and extendible robot arms.
Every task consists of a sequence of locations where the robot arm must pick up or deliver the product. This means, to complete a task, one robot arm needs to pick the product up at the first location and then, without stopping, must visit a list of locations where the product is assembled. Important to note is that tasks considerably differ in the number of spots, the distance between locations, and the score returned for completion.
A robot arm can only be placed at certain, so-called mounting points. Once installed, the arms can extend like in the arcade game Snake. Similar to the game, a robot arm must not collide with his tailor another robot's tail. For that, a robot arm can retreat to shorten its tail. A robot can move its head one unit in one second.
Now, given a limited amount of time and a fixed number of robots, it is your job to select tasks and plan the robot's movements to maximize the score, which is the sum of the scores from all completed tasks.
As it turns out, the fact that every robot leaves a trail makes the problem quite difficult. Coming up with a strategy that distributes the tasks somehow and moves the robots without collisions proved to be enough of a challenge for the four hours. After this realization, we made a rough plan of how our approach would work. First, we start with one robot and try to find a well-suited mounting point. Then, we try to finish the best tasks from that mounting point. Only then, having calculated the robot's movement for the total time, we move to the next robot. This way, we already know the other robot's current and future positions so that we can avoid them.
Selecting the Mount Point
We started coding the mounting point selection. Here, we used a standard greedy approach. For every mounting point, we estimated which remaining tasks we would be able to complete within the available time. Of course, we could only use rough approximation by looking at how many locations we needed to visit per task and how far the locations were apart. We could, therefore, not account for possible delays caused by other robot's tails blocking the shortest path.
Moving the Robots
While one teammate was coding the mounting point selection, another teammate and I started working on the motion planner for the robots. Our question was, how does a robot move from one assembly location to the next one? One option would be to take the shortest pathway. Unfortunately, as every movement, except for a retreat, causes the tail to grow, after a few paths, the robot's tail will make it impossible to move. One the other hand, retreating completely after every visited location keeps the tail short, but often takes longer than necessary. So, in the contest, we chose a compromise: We let the robot retreat, but only until the path using the rest of the tail is as short as the minimal distance from the mounting point (see figure).
Now, almost half of our time was already up. Still, our program was far from completed as we realized a severe problem.
The real challenge, we realized, is collision avoidance. Until now, we stored for every point in our construction hall and every time step, if the spot was used by any robot. As we process the robots one after the other, this would work perfectly, we thought. The problem arises from the robot's tail. When we see a field that is free at the current time step, we think it is safe for our robot to visit it. However, the field may be assigned to another assembly arm in the future. But when we visit the field, we leave our tail there, which then blocks the other robot. This would destroy our approach of planning one robot after the other.
Running short on time, we needed a fix quickly. Fortunately, my teammate proposed a brilliant solution. When we visit a currently-free field, we keep track of how long it will be free. Then we ensure to retreat no later than this time step to free the space for a different assembly arm.
At this moment, we were almost three hours into the competition. The scoreboard was going to freeze in a few minutes and we had yet to submit anything.
The Final Hour
Having programmed for many hours, here comes the crucial moment: Will the code work correctly? No. Of course not. We encounter multiple issues: our program crashes, the output format is not correct all the time, and we produce collisions between robots. Determined to get our solution running, we work together to fix one bug after the other. Then, finally, only seconds before the scoreboard freeze, we manage to submit our first working solution to one of the test cases.
Google provided a helpful animation tool that helped understanding how our program controlled the robots.
Why did we only submit one test case? Because we have a new problem: our solution is too slow, far too slow. Calculating how to move the robot to avoid any collisions takes so long that we barely finish placing one assembly robot while running our program for five minutes.
In the last hour, we did everything to speed up our algorithm, instead of searching for a path in all directions, we searched target-oriented, instead of looking at all tasks, we limited us to the nearest tasks. In the end, our effort paid off and we were able to generate decent solutions for all scenarios. Still, in one test case, we only utilized 17 out of the 50 available robots because our program did not finish the calculation in time. Nevertheless, with 4,327,978 points in total, we are proud to take 10th place as the team Prove By Submission in the 2020 edition of the Google Hashcode competition.
This year's Google Hashcode was not like any round before. Instead of programming a straight-forward greedy approach and then optimizing parameters or looking deeply into the different scenarios, this time, we were mostly just focused on getting our program running. Without any fancy optimizations, we ranked high as the other teams seemingly also struggled. Personally, I like this change as it challenges the teams and reduces the amount of "luck" needed to find the perfect set of parameters.
Of course, our solution is far from perfect. So if you want to check out the problem yourself, you can find the statement here. If you are interested in other team's solutions, check out the blog post on Codeforces.