DropBlox: Coding Challenge auf der PyCon DE & PyData Berlin 2022

Konferenzen sind großartig. Sie treffen neue Leute, Sie lernen neue Dinge. Aber haben Sie sich schon einmal nach einem Tag auf einer Konferenz im Hotel wiedergefunden und überlegt, was Sie jetzt tun sollen? Oder saßen Sie schon einmal in einer Sitzung fest und wünschten sich, Sie wären zu einer anderen gegangen? Diese Momente sind die perfekte Gelegenheit, um Ihren Laptop aufzuschlagen und sich mit Gleichgesinnten in einer Coding Challenge zu messen.

Die Teilnehmer der dreitägigen Konferenz PyCon DE & PyData Berlin 2022 hatten die Möglichkeit, dies mit unserer Coding Challenge DropBlox zu tun.

Die Teilnehmer hatten etwas mehr als einen Tag Zeit, um ihre Lösungen einzureichen. Nach Ablauf der Frist hatten wir über 100 Einsendungen erhalten und belohnten den wohlverdienten Gewinner vor einem großen Publikum mit einem Lego R2D2.

Lesen Sie weiter, um mehr über diese Herausforderung zu erfahren. Wir werden das Folgende besprechen:

• Worin genau bestand die Herausforderung und welche Kompromisse wurden bei der Gestaltung eingegangen?
• Was geschah hinter den Bildschirmen, um diese Herausforderung zu ermöglichen?
• Wie haben wir den Hype auf der Konferenz selbst erzeugt?
• Welche Strategien wurden von den Teilnehmern angewandt, um das Problem zu lösen?

Die Teilnehmer nutzten ein öffentliches Repository, das wir hier zur Verfügung stellen.

Herausforderung

Die Teilnehmer der Herausforderung erhielten folgende Aufgaben:

• Ein 100 x 100 Feld
• 1500 Blöcke in verschiedenen Farben und Formen, jeder mit einer eindeutigen Kennung (siehe Abb. 1)
• Eine Belohnungstabelle, in der die Punkte und Multiplikatoren pro Farbe angegeben sind (siehe Tabelle 1)

Abbildung 1: Eine zufällige Teilmenge von Blöcken aus der Challenge und ihre entsprechenden IDs.

Tabelle 1: Die Belohnungstabelle, die angibt, wie jede Farbe zur Punktzahl einer Lösung der Herausforderung beiträgt. Wir vergeben Punkte für jede Kachel in der endgültigen Lösung, während der Multiplikator nur für Reihen gilt, die mit Kacheln der gleichen Farbe gefüllt sind.

Die Regeln lauten wie folgt:

• Blöcke können von oben an einer bestimmten x-Koordinate in das Feld fallen gelassen werden, ohne ihre Drehung zu verändern (siehe Abb. 2).
• Jeder Block kann höchstens einmal verwendet werden
• Die Punktzahl einer Lösung wird anhand der Belohnungstabelle berechnet. Für jede Zeile addieren wir die Punkte der einzelnen Spielsteine zur Punktzahl. Wenn die Zeile nur aus Steinen einer einzigen Farbe besteht, multiplizieren wir die Punkte dieser Zeile mit dem entsprechenden Multiplikator. Die endgültige Punktzahl ergibt sich aus der Summe der Punktzahlen der einzelnen Reihen. (siehe Abb. 3)

Abbildung 2: Ein Beispiel für ein 6x6-Feld und einen blauen Block, der an der x-Koordinate 1 abgelegt wurde.

Abbildung 3: Ein Beispiel für die Berechnung der Punktzahl einer Lösung. Die Punkte und Multiplikatoren pro Farbe sind in Tabelle 1 angegeben.

Die Lösung ist eine Liste von Block-IDs mit den entsprechenden x-Koordinaten. Diese Liste gibt an, welche Blöcke an welcher Stelle fallen gelassen werden müssen, um zur endgültigen Lösung zu gelangen. Das Ziel der Herausforderung? So viele Punkte wie möglich zu bekommen.

Der Entwurf

Bei der Gestaltung des Wettbewerbs haben wir uns ein paar einfache Anforderungen ausgedacht, die wir befolgen müssen:

• Die Herausforderung sollte leicht zu bewältigen sein
• Der Fortschritt und die endgültige Lösung sollten einfach zu visualisieren sein
• Es dürfte schwierig sein, sich der optimalen Lösung zu nähern

Es gab Ideen für N-dimensionale Versionen dieser Herausforderung, aber nur das 'einfache' 2D-Design erfüllte alle Anforderungen. Es ist einfach zu visualisieren, weil es 2D ist, und (daher) einfach zu beginnen. Ein Feld von 100 x 100 mit 1500 Blöcken bietet jedoch genug Freiheit, um dieses Spiel auf mehr Arten zu spielen, als es Atome im Universum gibt!

Hinter den Bildschirmen

Die Teilnehmer konnten und können immer noch ihre Lösungen auf der Einreichungsseite einreichen und die Bestenliste mit den Einreichungen aller anderen Teilnehmer einsehen. Um dies zu ermöglichen, sind hinter den Bildschirmen einige Dinge passiert, die hier erwähnt werden sollten.

Am wichtigsten ist, dass wir mit einem Team von begeisterten Menschen mit sich ergänzenden Fähigkeiten zusammengearbeitet haben. Gemeinsam haben wir den Rahmen geschaffen, der in Abb. zu sehen ist. 4.

Wir haben ein separates privates Repository, in dem wir die gesamte Logik aufbewahren, die für den Teilnehmer verborgen ist. Darin befinden sich die grundlegende Bewertungsfunktion und die gesamte Logik, die für die Ausführung unserer Web-App erforderlich ist. Wenn die Teilnehmer ihre Lösung einreichen oder sich die Bestenliste ansehen, wird eine Azure-Funktion gestartet, um die Logik unserer Web-App auszuführen. Die Azure-Funktion ist mit einer SQL-Datenbank verbunden, in der wir die Einsendungen speichern oder abrufen. Bilder, wie z.B. die Visualisierung der endgültigen Lösung, speichern wir im Blob-Speicher. Um die Bestenliste zu erstellen, rufen wir die Beiträge jedes Nutzers mit den höchsten Punktzahlen ab und kombinieren sie mit den entsprechenden Bildern im Blob-Speicher.

Abbildung 4: Die verschiedenen Komponenten der Herausforderung, einschließlich derer, die für die Teilnehmer verborgen sind.

Hype erzeugen

Was nützt ein Wettbewerb, wenn niemand davon weiß? Verbreiten Sie die Nachricht!

Um die Aufmerksamkeit auf unseren Programmierwettbewerb zu lenken, haben wir zwei Dinge getan. Erstens haben wir einen ansprechenden Stand an den Ständen des Unternehmens aufgebaut. Wir haben unseren Preis direkt davor platziert und daneben ein Echtzeit-Dashboard, das die Highscores anzeigt. Sicherlich wird sich jeder, der vorbeigeht, zumindest fragen, was dieses Lego-Spielzeug auf einer Python-Konferenz zu suchen hat.

Abbildung 5: Unser Firmenstand auf der PyCon DE & PyData Berlin 2022

Zweitens sind wir zu den Lightning Talks der Konferenz gegangen und haben dort unseren Wettbewerb angekündigt. Das Publikum war wirklich großartig. Man muss die Energie auf solchen Konferenzen einfach lieben.

Abbildung 6: Werbung für die Herausforderung bei einem Lightning Talk

Nachdem wir unsere Aktion gestartet hatten, trudelten die Teilnehmer ein. Lassen Sie die Spiele beginnen!

Strategien

Die Strategien reichten von nahezu brachialen Ansätzen bis hin zur Verwendung von Faltungskernen und cleveren Heuristiken. Im Folgenden besprechen wir einige interessante und hochkarätige Einreichungen der Teilnehmer.

#14

S. Tschöke nannte seinen ersten Ansatz "Frühstückscerealien", da er sich von den kleineren Cerealienstücken inspirieren ließ, die sich am Boden und die größeren oben in einer Cerealientüte sammeln. Die Stücke wurden von links nach rechts fallen gelassen, die kleineren vor den größeren, bis kein Stück mehr hineinpasste. Dieser Ansatz, der zu etwa 25k Punkten führte, war jedoch nicht erfolgreich genug.

Nach einem weniger erfolgreichen, aber mutigen Ansatz mit einem genetischen Algorithmus, erweiterte er den Ansatz mit den Frühstücksflocken. Diesmal verwendete er statt der Größe eines Blocks die Dichte des Blocks, d.h. den Prozentsatz der gefüllten Kacheln innerhalb der Höhe und Breite eines Blocks, und er sortierte die Blöcke nach Farben. Ein ähnlicher Ansatz wie zuvor, aber nun unter Einbeziehung der verschiedenen Farbreihenfolgen, ergab 46k Punkte. (Siehe Abb. 6)

Abbildung 6: Endgültige Lösung der #14 im Wettbewerb, S. Tschöke, mit 45844 Punkten.

#2

Wir springen ein paar Plätze nach oben zu R. Garnier, der bis zu den letzten Momenten der Herausforderung auf Platz 1 lag. Er schloss sich einer kleinen Gruppe engagierter Teilnehmer an, die begannen, die Reihenmultiplikatoren auszunutzen. Unerwartet führte dies zu einer interessanten und spannenden Entwicklung des Wettbewerbs.

Seine Strategie bestand aus zwei Teilen. Der erste besteht darin, manuell einige gleichfarbige Reihen in gleicher Höhe zu erstellen. Auf diese Weise erstellte er 3 volle orangefarbene Reihen, eine rote und eine violette. Anschließend verwendet er einen gierigen Algorithmus, der die folgenden Schritte durchführt:

1. Weisen Sie jedem Block eine Punktzahl zu: Punktzahl = (Blockwerte) / (Blockfläche)
2. Sortieren Sie die Blöcke nach Punkten
3. Lassen Sie für jeden Block den Block dort fallen, wo er am weitesten nach unten fällt.

Diese Strategie führte zu 62k Punkten. (Siehe Abb. 7)

Abbildung 7: Endgültige Lösung der Nummer 2 im Wettbewerb, R. Garnier, mit 62032 Punkten.

#1

Mit einer einzigen Einsendung in letzter Minute beantwortete G. Chanturia die Frage "Wie weit können wir gehen?". Er konstruierte sorgfältig Paare von Blöcken, die zusammenpassen, um die untere Hälfte seiner Lösung manuell zu konstruieren und die Reihenmultiplikatoren auf die nächste Stufe zu bringen.

G. hat einen Doktortitel in Physik und einen MSc in Informatik und teilt seine Lösung passenderweise in eine "Physikerlösung" und eine "Programmiererlösung" auf.

Die Lösung des Physikers bezieht sich auf den unteren Teil des Feldes. Die Strategie, die hier angewandt wurde, war, wie von G. zusammengefasst, (1) einen Blick auf die Blöcke zu werfen und (2) sie auf intelligente Weise zu platzieren. Ob Sie nun ein theoretischer oder experimenteller Physiker sind, die Daten dienen als Ausgangspunkt. G. bemerkte, dass es eine Ordnung in den Blöcken gibt. Zunächst einmal waren bei vielen orangefarbenen Blöcken die oberen und unteren Reihen gefüllt. Wenn man diese auf geschickte Weise platziert, ergeben sich bereits sechs vollständig gefüllte Reihen. Zweitens gab es "W"- und "M"-förmige Blöcke, die perfekt zusammenpassen. Er machte so weiter und baute das untere 1/3 des Feldes manuell auf, was 57% der Gesamtpunktzahl ausmachte.

Die Lösung des Programmierers bezieht sich auf den Rest des Feldes. Das Problem mit dem ersten Ansatz ist, dass er nicht skalierbar ist. Mehr noch, wenn sich die Blöcke ändern würden, müsste er ganz von vorne anfangen. Dieser zweite Ansatz ist robuster und ähnelt dem Ansatz von R. Garnier. Die Schritte sind:

1. Filtern Sie Blöcke nach ihrer Höhe. Blöcke über Höhe = 5 werden herausgefiltert, da viele dieser Blöcke zu seltsame Formen haben, um damit zu arbeiten.
2. Sortieren Sie die Blöcke nach Punkten (oder, ähnlich, nach Farben). Die Blöcke mit den höher bewerteten Farben werden zuerst aufgeführt.
3. Wählen Sie die ersten n verfügbaren Blöcke in der sortierten Liste. Je größer n, desto besser die Lösung, aber desto länger dauert die Ausführung. Die gewählte Zahl liegt bei etwa 50.
4. Finden Sie heraus, welcher Block im Feld am weitesten nach unten fallen kann
5. Lassen Sie diesen Block fallen und entfernen Sie ihn aus der Liste
6. Wiederholen Sie von 3

Abbildung 8: Endgültige Lösung der #1 in der Challenge, G. Chanturia, mit 68779 Punkten.

Und am wichtigsten ist, dass die Nummer 1 nicht mit leeren Händen nach Hause geht. Der #1-Anwärter gewinnt den berüchtigten Lego R2D2! Und wir können bestätigen, dass der R2D2 in der Tat einige Köpfe auf der Konferenz verdreht hat. Der Preis wurde dem Gewinner bei der letzten Lightning Talk-Reihe der Konferenz verliehen.

Abbildung 9: Unser Gewinner erhält seinen begehrten Preis!

Fazit

Die Organisation der Coding Challenge hat viel Spaß gemacht. Wir haben ein Framework entwickelt, um eine Bestenliste zu erstellen, die Einsendungen zu bearbeiten und die Rätsel online anzuzeigen. Um den Prozess in ein paar Worten zusammenzufassen:

• Eine Coding Challenge auf einer Konferenz zu veranstalten, macht Spaß!
• Sammeln Sie Teilnehmer durch Werbung für die Herausforderung
• Übergabe des Preises an den Gewinner

Es war interessant zu sehen, welche Strategien sich unsere Teilnehmer einfallen ließen und wie sich der Highscore ständig verbesserte, obwohl dies irgendwann unwahrscheinlich schien. Wir haben gelernt, dass es ein guter Weg ist, mit einer einfachen Heuristik zu beginnen und diese zu erweitern, damit Ihr Algorithmus ein Problem schnell lösen kann. Um in unserem Fall zu gewinnen, war jedoch eine hybride Lösung mit ein wenig manuellem Engineering erforderlich, um alle Strategien zu übertreffen, die sich ausschließlich auf verallgemeinernde Algorithmen verlassen.

Höchstwahrscheinlich werden wir das von uns erstellte Framework wiederverwenden, um weitere Code-Challenges zu veranstalten. Werden Sie danach Ausschau halten? Bis dahin können Sie sich das Repository der DropBlox-Herausforderung hier ansehen.

Wir haben die Figuren in diesem Beitrag mit Excalidraw erstellt.

Bei GoDataDriven nutzen wir Daten und KI, um komplexe Probleme zu lösen. Aber wir teilen unser Wissen auch! Wenn Ihnen dieser Blogpost gefallen hat und Sie mehr über Data Science erfahren möchten, ist vielleicht die Data Science Learning Journey etwas für Sie.