Bundeswettbewerb Informatik 16/17

September 2016, das klingt für einige wahrscheinlich nach Schnee von vorgestern, aber damals fing es an. Wir saßen in der Schule und bekamen wie so üblich einige Aufgaben unseres Lehrers zur Bearbeitung. Es war aber keine gewöhnliche Aufgabe von ihm, sondern Aufgaben für den Bundeswettbewerb Informatik. Wem das noch nichts sagt, das ist etwa vergleichbar mit der Matheolympiade aus der Schule, nur eben für Informatiker.

Die Aufgabe bestand darin, eines der gestellten Rätsel zu lösen und zu dokumentieren. Es ging dabei zwar nicht um Rätsel, wie sie die drei Fragezeichen lösen, es war aber dennoch eine interessante Abwechslung zum normalen Schulunterricht. Jeder suchte sich also eine Aufgabe aus und es fanden sich Gruppen zusammen, die sich bei der Lösung der Rätsel gegenseitig unterstützten. Um euch mal einen kleinen Überblick darüber zu geben, wie das alles ablief und euch einen kleinen Einblick in die Welt der Informatik zu bieten, nehme ich mein Rätsel als Beispiel.

Es ging dabei um ein Puzzle, welches aus einem Rahmen besteht und innerhalb des Rahmens kleinere Stäbe hat, die bei einer Drehung des Puzzles nach unten fallen. Das Ziel dabei ist es, dass ein Stab durch Drehung des Puzzles unten aus einer kleinen Lücke herausfällt.

Wie man an diesem Bild sehen kann, ist der Rahmen (grau) einen Block dick und hat eine Lücke, durch welche die Stäbe rausfallen können. Die Stäbe sind einen Block breit und unterschiedlich lang (z.B. rot = 2 Blöcke lang, hellgrün = 4 Blöcke lang), außerdem liegen nicht alle in die gleiche Richtung. Da das aber nur ein Beispiel ist und die Lösung schon vorliegt, muss man diesen Lösungsvorgang für alle möglichen Puzzle verallgemeinern. Man kommt folglich nicht umher, ein Programm zu entwickeln, welches ein Puzzle automatisch einliest, löst und anschließend die Folge der Drehungen ausgibt.

Schritt 1 ist das Einlesen eines Puzzles.

Das ist auch noch relativ einfach, man bekommt kein Bild, sondern eine Text-Datei, bei der die Blöcke durch eigene Zeichen repräsentiert werden. Der Rand ist das Zeichen ‚#‘, ein „Luftblock“ ist das Leerzeichen ‚ ‚ und die Stäbe werden durch Zahlen dargestellt, jeder Stab hat eine Zahl, aber die Stäbe untereinander haben verschiedene Nummern. Das Puzzle wird im Programm als Feld bzw. Array gespeichert, man kann sich das als Tabelle vorstellen, wobei es für jedes Zeichen eine eigene Zelle gibt. Das Beispiel oben hat demzufolge acht Zeilen und Spalten, wobei die äußeren Zellen, bis auf die Lücke, mit ‚#‘ gefüllt sind.

Schritt 2 ist das Lösen, das ist auch der Hauptteil des Programms.

Da die meisten Puzzle recht komplex sind, muss das Programm jede einzelne Möglichkeit das Puzzle zu drehen ausführen, in der Informatik spricht man von Brute-Force. Diese Methode kann sehr schnell sehr unübersichtlich werden. Nach nur 2 Drehungen sind insgesamt schon 4 verschiedene Möglichkeiten der Drehung vorhanden: 2-mal nach rechts gedreht, erst rechts, dann links, erst links, dann rechts und 2-mal links.

Wenn man nun das Puzzle dreht und es zu einer Lösung kommt, also ein Stab unten rausfällt, muss man diese Reihenfolge der Drehungen nur noch ausgeben. Dafür merkt man sich die Reihenfolge der Drehungen, sobald man das Puzzle dreht. Es ergibt sich damit etwa folgendes Muster: am Anfang ist keine Drehung, dreht man das Puzzle nach rechts, merkt sich das Programm ‚R‘, dreht man das Puzzle danach nach links, merkt sich das Programm ‚L‘ und hängt es an die bereits bestehende Reihenfolge an, die gesamte Reihenfolge ist damit dann „RL“.

Schritt 3 ist die Ausgabe der Drehungen und damit auch der einfachste.

Die vom Programm gemerkte Reihenfolge muss nur noch ausgegeben werden, es schreibt somit die Reihenfolge „RRRRLR“ auf den Bildschirm, damit ist das Programm mit dem Puzzle fertig.

Etwa zwei Monate hatten wir bis zur Abgabe Zeit. Wenn man betrachtet, dass wir nur einmal pro Woche Schule haben, ein doch recht überschaubarer Zeitraum. Unser Lehrer bewertete das Programm und die Dokumentation unabhängig vom Wettbewerb, weshalb zumindest ich vergessen hatte, dass der Wettbewerb die Abgabe ebenfalls bewertet. Umso überraschender kam dann im Februar die Bewertung vom Bundeswettbewerb Informatik an sich.

Ergebnis: Ein 2. Preis für uns als Gruppe und eine Urkunde für die Schule.