How to design an optimisation problem for 20,000 coders worldwide
On 12th March 2020, more than 2,800 teams from all over the world competed in the third edition of the Reply Code Challenge.
Thousands of programmers tested their wits over four intense hours. Their aim: to be crowned the best coding team.
But what goes into the making of the Reply Code Challenge? How is the actual challenge developed and how is an event of this calibre organised?
Put simply, there's a whole team of Reply programmers, designers and social networkers collaborating for months, to take care of every last detail of the event.
To explain how we developed the coding problem, we'll follow the 7-step process the Code Masters – the team of Reply coding experts who set the problem – went through.
Obviously, designing a problem is not a linear process. Instead, it involves various proposals, drafts, run-throughs and tests to achieve the final result.
in the Reply Code Challenge 2020
The Problem
Programmers work with problems every day. Not all of them are solvable. Some are easy and some are difficult (in computer science we talk about calculability and complexity theory). Others have interesting practical applications, and others still, never go beyond the theoretical phase.
The two most important requirements of the perfect problem are: one, it has to arouse curiosity and, two, it has to be challenging to solve.
It also has to be the right type of problem. At Reply, we're very interested in 'optimisation problems'. In other words, problems where it's not possible to find the best solution in a set time, but it's possible to get close enough.
This year's topic was about assigning developers to office places – specifically, organising thousands of people with various skills, so they can collaborate effectively and efficiently.
Generally, allocating limited resources in the best way possible is a question that often arises in our work. In fact, you'll see this theme running through previous editions of the Code Challenge in different forms.
The problem statement
A good problem is one that's easy to explain.
The text of a problem should never be longer than a page. Why? Because it's essential to understand what the problem's objective is immediately.
How? By clearly and quickly defining all the variables involved, while explaining the context to the problem – yet leaving out the technical details, such as formulas, formats and examples included in subsequent pages.
The scoring formula
The scoring is the real heart of the whole competition.
In fact, finding the right scoring formula often determines how successful a problem statement becomes.
Too simple a formula risks losing the optimisation part of the problem. Too complex a formula risks making the writing part of the challenge too difficult.
For our challenge, we considered a score based on the different competences of adjacent developers, adding a bonus where there were complementary skills. In other words, a formula with the right balance of simplicity of implementation and difficulty in optimisation.
Constraint
Once the problem and the formula were chosen, we needed to define the limits of the inputs we wanted to solve.
As with the scoring formula, it's necessary to find the right balance between low and high limits.
A limit that's too low in size makes the problem easy to solve, even with inefficient solutions. A limit that's too high takes too long to solve, even for highly optimised solutions.
Another factor to remember is that high limits lead to larger files, which could lead to download issues such or having limited resources for analysis.
without having several solutions
Input and output
Once we've defined all the theoretical aspects of the problem, we can move onto the practical aspects.
It's not possible to generate inputs without having several solutions to the problem ready – and to be able to calculate the points, you need feedback on the scores for possible solutions.
In this case, both good and bad solutions are essential for choosing the perfect inputs, since the competition must be balanced to have a well-distributed score ranking.
An interesting thing about these optimisation problems is that, by choosing inputs with particular formats, you can solve them using different approaches and maximise the score for specific solutions.
If you download this year's input files, you'll see each one has its own particular feature. Some examples may be the input with many small clusters of places (ideally tables), the input where bonuses are all the same, or the input where the seating arrangement is spiral shaped.
The visualizer
The viewer is an important component that allows us to show our solutions graphically.
Having a general overview of the output helps us understand what an output’s strengths and weaknesses are, and therefore see how to improve the solution.
A good viewer must show the essential output information, the scores received, and the statistics that help understand the distribution of assignments.
You can relive the competition and take on this year's problem in the sandbox here. The previous edition’s sandboxes are available here if you want to practice again. If you still want more, you can learn from the best by downloading the official winners' solutions directly here.
For the first time this year, you can see 'Live Coding', where some of our Code Masters write and comment directly on a possible solution to this year’s problem statement here.
We look forward to seeing you for Reply Challenge 2021!