DropBlox: Coding Challenge at PyCon DE & PyData Berlin 2022 (on Xebia.com ⧉)

Conferences are great. You meet new people, you learn new things. But have you ever found yourself back in the hotel after a day at a conference, thinking what to do now? Or were you ever stuck in one session, wishing you had gone for that other one? These moments are the perfect opportunity to open up your laptop and compete with your peers in a coding challenge.

Attendees of the three-day conference PyCon DE & PyData Berlin 2022 had the possibility to do so, with our coding challenge DropBlox.

Participants had a bit over one day to submit their solutions. After the deadline, we had received over 100 submissions and rewarded the well-deserved winner a Lego R2D2 in front of a great crowd.

Read on to learn more about this challenge. We will discuss the following:

• What was the challenge exactly, and what trade-offs were made in the design?
• What was happening behind the screens to make this challenge possible?
• How did we create hype at the conference itself?
• What strategies were adopted by the participants to crack the problem?

Participants used a public repository that we made available here.

Challenge

Participants of the challenge were given the following:

• A 100 x 100 field
• 1500 blocks of various colors and shapes, each with a unique identifier (see Fig. 1)
• A rewards table, specifying the points and multipliers per color (see Table 1)

The rules are as follows:

• Blocks can be dropped in the field from the top at a specified x-coordinate, without changing their rotation (see Fig. 2)
• Each block can be used at most once
• The score of a solution is computed using the rewards table. For each row, we add the points of each tile to the score. If the row consists of tiles of a single color only, we multiply the points of that row by the corresponding multiplier. The final score is the sum of the scores of the rows. (see Fig. 3)

The solution is a list of block IDs with corresponding x-coordinates. This list specifies which blocks to drop and where, in order to come to the final solution.
The goal of the challenge? Getting the most points possible.

The design

When designing the challenge, we came up with a few simple requirements to follow:

• The challenge should be easy to get started with
• The progress and final solution should be easy to visualize
• It should be difficult to approach the optimum solution

Ideas about N-dimensional versions of this challenge came along, but only the ‘simple’ 2D design ticked all the boxes. It’s easy to visualize, because it’s 2D, and (therefore) easy to get started with. Still, a 100 x 100 field with 1500 blocks allows for enough freedom to play this game in more ways than there are atoms in the universe!

Behind the screens

Participants could, and anyone still can, submit their solutions on the submission page, as well as see the leaderboard with submissions of all other participants. To make this possible, several things happened behind the screens, which are worth noting here.

Most importantly, we worked with a team of excited people with complementing skill sets. Together we created the framework that is visualized in Fig. 4.

We have a separate private repository, in which we keep all the logic that is hidden to the participant. In there, we have the ground-truth scoring function, and all logic necessary to run our web app. When participants submit their solution or check out the leaderboard, an Azure Function spins up to run the logic of our web app. The Azure Function is connected to an SQL database, where we store or retrieve submissions from.  We store images, such as the visualization of the final solution, in the blob storage. To create the leaderboard, we retrieve the top-scoring submissions of each user and combine them with the corresponding images in the blob storage.

Creating hype

What’s the use of a competition if nobody knows about it? Spread the word!

To attract attention to our coding competition, we did two things. First, we set up an appealing booth at the company stands. We put our prize right in front, and a real-time dashboard showing the highscores beside. Surely, anyone walking past will at least question themselves what that Lego toy is doing at a Python conference.

Second, we went out to the conference Lightning Talks and announced our competition there. Really, the audience was great. Gotta love the energy at conferences like these.

With our promotion set up, competitors started trickling in. Let the games begin!

Strategies

Strategies varied from near brute-force approaches to the use of convolutional kernels and clever heuristics. In the following, we discuss some interesting and top-scoring submissions of participants.

#14

S. Tschöke named his first approach “Breakfast cereal”, as he was inspired by smaller cereal pieces collecting at the bottom and larger ones in the top of a cereal bag. Pieces were dropped from left to right, smaller ones before larger ones, until none could fit anymore. This approach, resulting in around 25k points, was however not successful enough.

After a less successful, but brave approach using a genetic algorithm, he extended the breakfast cereal approach. This time, instead of the size of a block he used the block’s density, or the percentage of filled tiles within the height and width of a block; and he sorted the blocks by color. Taking a similar approach as before, but now including the different color orderings, resulted in 46k points. (See Fig. 6)

#2

We jump up a few places to R. Garnier, who was #1 up until the last moments of the challenge. He went along with a small group of dedicated participants who started exploiting the row multipliers. Unexpectedly, this led to an interesting and exciting development in the competition.

His strategy consisted of two parts. The first is to manually construct some rows of the same color of the same height. This way, he created 3 full orange rows, one red and one purple. Subsequently, he uses a greedy algorithm, following the steps:

1. Assign a score to each block: score = (block values) / (block surface)
2. Sort the blocks by score
3. For each block, drop the block where it falls down the furthest​​

This strategy resulted in 62k points. (See Fig. 7)

#1

With a single last-minute submission, G. Chanturia answered the question to “How far can we go?”. He carefully constructed pairs of blocks that fit together, to manually engineer the bottom half of his solution, taking the row multipliers to the next level.

G. is doing a PhD in Physics and a MSc in Computer Science, and fittingly splits his solution into a “physicist’s solution” and a “programmer’s solution”.

The physicist’s solution refers to the bottom part of the field. The strategy used here, as summarized by G., was (1) taking a look at the blocks, and (2) placing them in a smart way. Whether you are a theoretical or experimental physicist, data serves as a starting point. G. noticed there is an order in the blocks. First of all, a lot of orange blocks had their top and bottom rows filled. Placing these in a clever way already results in six completely filled rows.
Second, there were “W” and “M”-shaped blocks that fit perfectly together. He kept going on like this to manually construct the bottom 1/3 of the field, accounting for 57% of the total score.

The programmer’s solution refers to the rest of the field. The problem with the first approach is that it is not scalable. Even more, if the blocks would change he would have to start all over. This second approach is more robust, and is similar to R. Garnier’s approach. The steps are:

1. Filter blocks based on their height. Blocks above height = 5 are filtered out, because many of these blocks have too weird shapes to work with.
2. Sort the blocks by points (or similarly, by color). Blocks with higher scoring colors are listed first.
3. Pick the first n available blocks in the sorted list. The larger n, the better the solution, but the longer it takes to run. The chosen number was around 50.
4. Find out which block can fall the furthest down in the field
5. Drop that block and remove it from the list
6. Repeat from 3

And most importantly, the #1 place does not go home empty-handed. The #1 contender wins the infamous Lego R2D2! And we can acknowledge that indeed, yes, the R2D2 turned quite some heads at the conference. The award was given to the winner at the last Lightning Talk series of the conference.

Conclusion

Organising the coding challenge has been lots of fun. We created a framework to host a high score leaderboard, process submissions and display the puzzles online. To sum up the process in a few words:

• Hosting a coding challenge at a conference is fun!
• Gather participants by promoting the challenge
• Hand over the prize to the winner

It was interesting to see what strategies our participants came up with, and how the high score constantly improved even though this seemed unlikely at some point. We learned that starting off with a simple heuristic and expanding upon that is a good way to get your algorithm to solve a problem quickly. However, to win in our case, a hybrid solution involving a bit of manual engineering was needed to outperform all strategies relying solely on generalizing algorithms.

Quite likely, we will be re-using the framework we built to host some more code challenges. Will you look out for them?
Until that time, check out the repository of the DropBlox challenge here.

We made the figures in this post using Excalidraw.

At GoDataDriven, we use data & AI to solve complex problems. But we share our knowledge too! If you liked this blogpost and want to learn more about Data Science, maybe the Data Science Learning Journey is something for you.